Gradient-Based Methods for Sparse Recovery

被引：38

作者：

Hager, William W. ^{[1
]}

Phan, Dzung T. ^{[2
]}

Zhang, Hongchao ^{[3
]}

机构：

[1] Univ Florida, Dept Math, Gainesville, FL 32611 USA

[2] IBM Corp, Thomas J Watson Res Ctr, Dept Business Analyt & Math Sci, Yorktown Hts, NY 10598 USA

[3] Louisiana State Univ, Dept Math, Ctr Computat & Technol, Baton Rouge, LA 70803 USA

来源：

SIAM JOURNAL ON IMAGING SCIENCES | 2011年 / 4卷 / 01期

基金：

美国国家科学基金会;

关键词：

sparse reconstruction by separable approximation; iterative shrinkage thresholding algorithm; sparse recovery; sublinear convergence; linear convergence; image reconstruction; denoising; compressed sensing; nonsmooth optimization; nonmonotone convergence; BB method; THRESHOLDING ALGORITHM;

D O I：

10.1137/090775063

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The convergence rate is analyzed for the sparse reconstruction by separable approximation (SpaRSA) algorithm for minimizing a sum f(x) + psi(x), where f is smooth and psi is convex, but possibly nonsmooth. It is shown that if f is convex, then the error in the objective function at iteration k is bounded by a/k for some a independent of k. Moreover, if the objective function is strongly convex, then the convergence is R-linear. An improved version of the algorithm based on a cyclic version of the BB iteration and an adaptive line search is given. The performance of the algorithm is investigated using applications in the areas of signal processing and image reconstruction.

引用

页码：146 / 165

页数：20

共 28 条

[1] Fast Image Recovery Using Variable Splitting and Constrained Optimization [J].

Afonso, Manya V. ;

Bioucas-Dias, Jose M. ;

Figueiredo, Mario A. T. .

IEEE TRANSACTIONS ON IMAGE PROCESSING, 2010, 19 (09) :2345-2356

[2] 2-POINT STEP SIZE GRADIENT METHODS [J].

BARZILAI, J ;

BORWEIN, JM .

IMA JOURNAL OF NUMERICAL ANALYSIS, 1988, 8 (01) :141-148

[3] A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems [J].

Beck, Amir ;

Teboulle, Marc .

SIAM JOURNAL ON IMAGING SCIENCES, 2009, 2 (01) :183-202

[4] NESTA: A Fast and Accurate First-Order Method for Sparse Recovery [J].

Becker, Stephen ;

Bobin, Jerome ;

Candes, Emmanuel J. .

SIAM JOURNAL ON IMAGING SCIENCES, 2011, 4 (01) :1-39

[5]

BIOUCAS-DIAS J., 2006, PROC IEEE INT CONF A, V2, P861

[6]

Bioucas-Dias J., 2014, Twist: Two-step iterative shrinkage/thresholding algorithm for linear inverse problems

[7]

BROUGHTON R, 2009, BARZILAI BORWEIN 1 R

[8]

CANDES EJ, 2005, P SPIE WAV APPL SIGN, V5914

[9] Nonlinear wavelet image processing: Variational problems, compression, and noise removal through wavelet shrinkage [J].

Chambolle, A ;

DeVore, RA ;

Lee, NY ;

Lucier, BJ .

IEEE TRANSACTIONS ON IMAGE PROCESSING, 1998, 7 (03) :319-335

[10] Atomic decomposition by basis pursuit [J].

Chen, SSB ;

Donoho, DL ;

Saunders, MA .

SIAM JOURNAL ON SCIENTIFIC COMPUTING, 1998, 20 (01) :33-61

← 1 2 3 →