Accelerated Projected Gradient Method for Linear Inverse Problems with Sparsity Constraints

Abstract

Regularization of ill-posed linear inverse problems via ${\ell }_1$ penalization has been proposed for cases where the solution is known to be (almost) sparse. One way to obtain the minimizer of such an ${\ell }_1$ penalized functional is via an iterative soft-thresholding algorithm. We propose an alternative implementation to ${\ell }_1$-constraints, using a gradient method, with projection on ${\ell }_1$-balls. The corresponding algorithm uses again iterative soft-thresholding, now with a variable thresholding parameter. We also propose accelerated versions of this iterative method, using ingredients of the (linear) steepest descent method. We prove convergence in norm for one of these projected gradient methods, without and with acceleration.

24 pages, 5 figures. v2: added reference, some amendments, 27 pages

References in corpus (1)

• Tomographic inversion using ${\ell }_1$-norm regularization of wavelet coefficients

Cited by in corpus (13)

• NESTA: A Fast and Accurate First-order Method for Sparse Recovery
• Linear convergence of iterative soft-thresholding
• Hessian Schatten-Norm Regularization for Linear Inverse Problems
• Online Sparse System Identification and Signal Reconstruction using Projections onto Weighted ${\ell }_1$ Balls
• Meaning of Interior Tomography
• Accelerating gradient projection methods for ${\ell }_1$-constrained signal recovery by steplength selection rules
• On the performance of algorithms for the minimization of ${\ell }_1$-penalized functionals
• Polyquant CT: direct electron and mass density reconstruction from a single polyenergetic source
• A projected gradient method for $\alpha {\ell }_1-\beta {\ell }_2$ sparsity regularization
• An Accelerated Nonlinear Contrast Source Inversion Scheme For Sparse Electromagnetic Imaging
• The Stochastic Properties of ${\ell }^1$-Regularized Spherical Gaussian Fields
• Greedy Algorithms for Hybrid Compressed Sensing
• Continuous Time Locally Stationary Wavelet Processes