Accelerated Projected Gradient Method for Linear Inverse Problems with Sparsity Constraints
For researchers in inverse problems and sparse recovery, this provides a theoretically grounded accelerated algorithm for ℓ1-constrained optimization, though it is an incremental improvement over existing iterative soft-thresholding methods.
The paper tackles linear inverse problems with sparsity constraints, proposing an accelerated projected gradient method using iterative soft-thresholding with variable thresholding. Convergence in norm is proven for the method, with and without acceleration.
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.