A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems

By Amir Beck, Amir Beck, Marc Teboulle. 2009

6,446 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Mathematical Physics, Mathematical Optimization, Numerical Methods & Scientific Computing

How researchers see this paper

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

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Mathematical Physics

In Mathematical Optimization

In Numerical Methods & Scientific Computing

Citations in the corpus

Pedestrian Detection with Unsupervised Multi-stage Feature Learning (2012, positive): “Many efﬁcient algorithms for solving the above convex system has been proposed in recent years [1, 6, 2, 26].”
Optimization Methods for Large-Scale Machine Learning (2016, neutral): “erms of their magnitudes. When only a stochastic estimate g(w k;˘ k) of the gradient is available, it can be used instead of rF(w k). A variant of ISTA with acceleration (recall x7.2), known as FISTA [8], is popular in practice. We also mention that eective techniques have been developed for computi”
Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition (2016, neutral): “Gong and Ye [2014] show that SVRG has a linear convergence rate without SC under the weaker assumption of QG plus convexity (where QG is equivalent to PL).”
Interpretable Recurrent Neural Networks Using Sequential Sparse Recovery (2016, neutral): “…efﬁcient variants of ISTA have been proposed that use an adaptive step size α ( k ) and iteration-dependent λ ( k ) , such as fast ISTA (FISTA) [20], which combines Nesterov’s adaptive step size method [21] with a gradual decrease in λ ( k ) , and sparse reconstruction by separable…”
Generalized Sparse Additive Models (2019, neutral): “In many cases, this algorithm has a per-iteration complexity of O ( np ) — precisely that of state-of-the-art algorithms for the lasso [Friedman et al., 2010, Beck and Teboulle, 2009b].”
Fused Lasso Additive Model (2014, neutral): “Generalized gradient descent (GGD) can be used to solve (15) [Beck and Teboulle, 2009].”
Sparse Partially Linear Additive Models (2014, positive): “It is known that setting the step size to the reciprocal of the Lipschitz constant of ∇L guarantees convergence (Beck and Teboulle 2009).”
Conditional mean embeddings as regressors (2012, positive): “A direct computation yields that the above optimization problem is equivalent to (17) In the experiments in Section 5.1, we solve problem (17) with FISTA (Beck & Teboulle, 2009), an optimal ﬁrst order method which requires O (1 / √ ) iterations to reach a accuracy of the minimum value in (17), with ”
Distributed optimization with arbitrary local solvers (2015, neutral): “CD Coordinate Descent [51] APPROX Accelerated, Parallel and Proximal Coordinate Descent [20, 21] GD Gradient Descent with Backtracking Line Search [44] CG Conjugate Gradient Method [25] L-BFGS Quasi-Newton with Limited-Memory BFGS Updating [10] BB Barzilai-Borwein Gradient Method [4] FISTA Fast Iter”
An asynchronous parallel stochastic coordinate descent algorithm (2013, neutral): “These methods are inherently serial, in that each iteration depends on the result of the previous iteration.”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, neutral): “FISTA the accelerated gradient method proposed by Beck and Teboulle [3] with a line-search for automatically adjusting the Lipschitz constant.”
Fast Distributed Gradient Methods (2011, positive): “0, for all i;k. Proof of Theorem 11 is omitted for brevity; it uses similar arguments as the proof of Theorem 10, but instead of Theorem 2.2.3 in [7], it uses convergence results for the FISTA method [30]. VII. SIMULATION EXAMPLE This section shows the performance of the proposed distributed Nestero”
Optimization with Sparsity-Inducing Penalties (2011, positive): “The basic proximal algorithm uses the solution of problem (3.2) as the next update wt+1; however fast variants such as the accelerated algorithm presented in [103] or FISTA [17] maintain two variables and use them to combine at marginal extra computational cost the solution of (3.2) with information”
Stochastic Variance Reduction Methods for Saddle-Point Problems (2016, positive): “Following the usual set-up of composite optimization [10], no smoothness assumption is made on M and hence onf or g.”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, positive): “In this section we compare Prox-SDCA, its accelerated version Accelerated-Prox-SDCA, and the FISTA algorithm of [2], on L 1 − L 2 regularized loss minimization problems.”
Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming (2010, neutral): “…us to implement the estimator using eﬃcient algorithmic methods, such as interior-point methods, which provide polynomial-time bounds on computational time [16, 17], and modern ﬁrst-order methods that have been recently extended to handle very large conic programming problems [14, 15, 11, 1].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, neutral): “Figure 4.6 compares the mS2GD algorithm with SGD+, S2GD and FISTA.”