Atomic Decomposition by Basis Pursuit

By Scott Shaobing Chen, David L. Donoho, Michael A. Saunders. 1998

Subfields: Optimization & Training, Statistical Learning Theory

How researchers see this paper

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

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Interpretable Recurrent Neural Networks Using Sequential Sparse Recovery (2016, methodology): “Problem (16) is known as basis pursuit denoising (BPDN) [15], which is also equivalent to minimizing the Lagrangian of the least absolute shrinkage and selection operator (LASSO) method for sparse recovery [16].”
Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso (2017, neutral): “…are classical methods in statistics, dating back to at least Beale et al. (1967); Hocking and Leslie (1967) for best subset selection and Efroymson (1966); Draper and Smith (1966) for forward selection; the lasso is (relatively speaking) more recent, due to Tibshirani (1996); Chen et al. (1998).”
Approximate residual balancing: debiased inference of average treatment effects in high dimensions (2016, methodology): “In our analysis, we focus on the lasso (Chen et al., 1998; Tibshirani, 1996); however, in experiments, we use the elastic net for additional stability (Zou and Hastie, 2005).”
Regularization Paths for Generalized Linear Models via Coordinate Descent (2010, background): “In the signal processing literature, the lasso is also known as basis pursuit (Chen et al. 1998).”
Kernel methods in machine learning (2007, neutral): “[29]), whereas the l2 norm can be extended to Hilbert spaces and kernels.”
Optimization with Sparsity-Inducing Penalties (2011, methodology): “These general optimality conditions can be specialized to the Lasso problem [133], also known as basis pursuit [37]:”
Stability selection (2008, background): “Substantial progress has been made over recent years in developing computationally tractable methods which have provable statistical (asymptotic) properties, even for the high dimensional setting with many more variables than samples.”
High-dimensional graphs and variable selection with the Lasso (2006, neutral): “It is well known that the Lasso, introduced by Tibshirani [16], and known as Basis Pursuit in the context of wavelet regression [2], has a parsimonious property [11].”
Node harvest: simple and interpretable regression and classication (2009, background): “The linear combination β of nodes is then sought in a Lasso-style way by putting a constraint on the ℓ 1 -norm of the coeﬃcient vector [Tibshirani (1996); Chen, Donoho and Saunders (2001 The original variables can be added to the matrix I of binary indicator variables.”
Online Learning for Matrix Factorization and Sparse Coding (2009, neutral): “This problem is also known as basis pursuit (Chen et al., 1999), or the Lasso (Tibshirani, 1996).”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “• Norm Ω to promote sparsity – square loss + l1-norm ⇒ basis pursuit in signal processing (Chen et al., 2001), Lasso in statistics/machine learning (Tibshirani, 1996) – Proxy for interpretability – Allow high-dimensional inference: log p = O(n)”
Stable recovery of sparse overcomplete representations in the presence of noise (2006, background): “…have included multiscale Gabor functions [27], [30], systems defined by algebraic codes [33], amalgams of wavelets and sinusoids [3], [4], [14], libraries of windowed cosines with a range of different widths and locations [5], [42], multiscale windowed ridgelets [32], systems…”
Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals (2007, background): “, convex relaxations from the basis pursuit family [13], [30], [31] or matching pursuit [14], [29], [32] with a termination criterion based on the residual.”
Alternating Direction Algorithms for 1-Problems in Compressive Sensing (2009, background): “A fundamental decoding model in CS is the so-called basis pursuit (BP) problem [12]: Minimizing the ℓ 1 -norm in (1.3) plays a central role in promoting solution sparsity.”
Generalized Low Rank Models (2014, methodology): “, [28, 145]), or exact solutions (for small s) using the branch and bound method [84, 15].”
Compressive Sensing for Background Subtraction (2008, methodology): “We employ Basis Pursuit Denoising methods [14] as well as total variation minimization [5] as convex objectives to process field data.”