Accelerated Projected Gradient Method for Linear Inverse Problems with Sparsity Constraints

By Ingrid Daubechies, Massimo Fornasier, Ignace Loris. 2007

297 citations recorded by the source corpus.

Regularization of ill-posed linear inverse problems via ℓ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 ℓ1 penalized functional is via an iterative soft-thresholding algorithm. We propose an alternative implementation to ℓ1-constraints, using a gradient method, with projection on ℓ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.

Subfields: Artificial Intelligence, Computational Mechanics, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/819e00b3cd6eaa1fcb16157ac0e2cf6ce81f28e3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Mathematical Physics

Citations in the corpus

Understanding Traffic Density from Large-Scale Web Camera Data (2017, unknown): “It is worth noting that this optimization problem is not convex and the APSD algorithm may lead to local optimal.”
Probing the Pareto Frontier for Basis Pursuit Solutions (2008, methodology): “The method proposed by Daubechies, Fornasier, and Loris [20] is related to Algorithm 1.”
Solving the split feasibility problem without prior knowledge of matrix norms (2012, background): “For more details about this kind of approach, see [8, 10, 22].”
Adaptive Subgradient Methods for Online Learning and Stochastic Optimization (2011, background): “3 l1-ball Projections We next consider the setting in which φ ≡ 0 and X = {x : ‖x‖1 ≤ c}, which has been the topic of recent research (Duchi et al., 2008; Daubechies et al., 2008).”
Iterative deblending of simultaneous-source seismic data using seislet-domain shaping regularization (2014, unknown): “Furthermore we notice that FT ¼ I T T−1 I T ¼ I T−T TT I ¼ I T T−1 I ¼ F and FTF ¼ I T T−1 I I T T−1 I ¼ 2 I T T−1 I ¼ 2F. (13) The least-squares solution of equation 3 is therefore m̂ ¼ ðFTFÞ−1FT ~d ¼ 1 2 F−1FT ~d ¼ 1 2 ~d: (14) According to equation 14, an appropriate choice for B is B ¼ 1 2 ½I 0;”
Linear Convergence of Iterative Soft-Thresholding (2007, unknown): “Consequently, classical convergence results hold for a variety of step-size rules [11], including the ‘Condition (B)’ introduced in [8], see also Remark 7.”
NESTA: A Fast and Accurate First-Order Method for Sparse Recovery (2009, background): “4) for values of τ ranging in an interval [0, τmax], [36] and [25] independently introduced a fixed point continuation technique which solves 1penalized least-squares problems (1.”
Data Poisoning Attacks on Federated Machine Learning (2020, background): “, X can be considered as an `2-norm ball by following [7].”
Fixed-Point Continuation for l1-Minimization: Methodology and Convergence (2008, methodology): “, a gradient projection and Barzilai–Borwein method applied to an equivalent box-constrained QP [28] by Figueiredo, Nowak, and Wright, a direct and accelerated projected gradient method [14] by Daubechies, Fornasier, and Loris, an accelerated multistep gradient method [47] with an error convergence ”
Sparse additive models (2007, methodology): “In particular, if we solve the lasso by iteratively minimizing with respect to a single coordinate, each iteration is given by soft thresholding; see Figure 2. Convergence properties of variants of this simple algorithm have been recently treated by Daubechies et al. (2004, 2007) .”