Fast Solution of $\ell _{1}$ -Norm Minimization Problems When the Solution May Be Sparse

By David L. Donoho, Yaakov Tsaig. IEEE Transactions on Information Theory, 2008

868 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/6b8392a93baaca38810415b1e826fa29d7d5f7af

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 Numerical Analysis

Citations in the corpus

Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers (2011, neutral): “[173] compares and benchmarks a number of representative algorithms, including gradient projection [73, 102], homotopy methods [52], iterative shrinkage-thresholding [45], proximal gradient [132, 133, 11, 12], augmented Lagrangian methods [175], and interior-point methods [103].”
NESTA: A Fast and Accurate First-Order Method for Sparse Recovery (2009, background): “The point of this is that it has been noticed (see [34, 45, 27 ]) that solving (1.3) (resp.”
Half-Quadratic-Based Iterative Minimization for Robust Sparse Representation (2014, methodology): “Since S1-FSS, S1-HOMO and S1-PFP all use the active set method, they estimate only one entry as the error in each iteration.”
The Application of Compressed Sensing for Photo-Acoustic Tomography (2009, background): “[27] and applied to underdetermined problems by Donoho and Tsaig [24] constructs the solution by finding one basis coefficient at a time.”
A crowdsourcing triage algorithm for geopolitical event forecasting (2018, methodology): “When L is fixed, the optimization for α j reduces to a LASSO problem [5, 15] for each α j :”
L1-L2 Optimization in Signal and Image Processing (2010, methodology): “…was traditionally treated using: 1) various classical iterative optimization algorithms, ranging from steepest descent, CG, and iterative reweighed least-squares, and all the way to the more involved interior-point algorithms [3]; 2) homotopy solvers [18], [19]; and 3) greedy techniques [20].”
Forward stagewise regression and the monotone lasso (2007, background): “Algorithm 2a is an efficient way of computing the solution to any lasso problem, especially when N ≪ p (Donoho & Tsaig 2006).”
Fixed point and Bregman iterative methods for matrix rank minimization (2009, methodology): “6) have been widely investigat ed nd many algorithms have been suggested including convex optimization methods ([2; 10; 20; 24; 27]) and heuris tic methods ([13; 15; 16; 39; 40]).”
Probing the Pareto Frontier for Basis Pursuit Solutions (2008, methodology): “(See Donoho and Tsaig [ 25 ] and Friedlander and Saunders [28] for discussions of the performance of these methods.) The computational bottleneck for these methods is the accurate solution at each iteration of a least-squares subproblem that involves a subset of the columns of A. In some application”
Compressive Sensing with structured random matrices (2012, methodology): “We refer the interested reader to [32, 33, 34, 43, 47, 76] for further efficient algorithms for `1-minimization.”
Spatiotemporal Reflectance Fusion via Sparse Representation (2012, methodology): “Several fast l1-minimization algorithms have been developed with both relatively high reconstruction precision and quick convergence speed [18].”
An Interior-Point Method for Large-Scale $\ell_1$-Regularized Least Squares (2007, methodology): “Recently, several researchers have proposed homotopy methods and variants for solving l1-regularized LSPs [14, 23, 15, 44, 39].”