On Recovery of Sparse Signals Via $\ell _{1}$ Minimization
IEEE Transactions on Information TheoryPublished 16 June 2009
Tommaso Cai, Guangwu Xu, Jun Zhang
Citations202
SJR quartileQ1
SJR score1.46
SNIP1.76
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The results of this paper improve the existing results in the literature by weakening the conditions and tightening the error bounds and shows that signals with larger support can be recovered accurately.
Abstract
This paper considers constrained lscr 1 minimization methods in a unified framework for the recovery of high-dimensional sparse signals in three settings: noiseless, bounded error, and Gaussian noise. Both lscr 1 minimization with an lscr infin constraint (Dantzig selector) and lscr 1 minimization under an l lscr 2 constraint are considered. The results of this paper improve the existing results in the literature by weakening the conditions and tightening the error bounds. The improvement on the conditions shows that signals with larger support can be recovered accurately. In particular, our results illustrate the relationship between lscr 1 minimization with an l lscr 2 constraint and lscr 1 minimization with an lscr infin constraint. This paper also establishes connections between restricted isometry property and the mutual incoherence property. Some results of Candes, Romberg, and Tao (2006), Candes and Tao (2007), and Donoho, Elad, and Temlyakov (2006) are extended.
Keywords
Computer ScienceEngineering
Journal of the Royal Statistical Society Series B (Statistical Methodology)Regression Shrinkage and Selection Via the Lasso
51,790 Citations1996Robert Tibshirani
A new method for estimation in linear models called the lasso, which minimizes the residual sum of squares subject to the sum of the absolute value of the coefficients being less than a constant, is proposed.
The Annals of StatisticsLeast angle regression
9,493 Citations2004Bradley Efron, Trevor Hastie +2 more
IEEE Transactions on Information TheoryDecoding by Linear Programming
7,181 Citations2005Emmanuel J. Candès, Terence Tao
F can be recovered exactly by solving a simple convex optimization problem (which one can recast as a linear program) and numerical experiments suggest that this recovery procedure works unreasonably well; f is recovered exactly even in situations where a significant fraction of the output is corrupted.
Communications on Pure and Applied MathematicsStable signal recovery from incomplete and inaccurate measurements
7,170 Citations2006Emmanuel J. Candès, Justin Romberg +1 more
It is shown that it is possible to recover x0 accurately based on the data y from incomplete and contaminated observations.
Comptes Rendus MathématiqueThe restricted isometry property and its implications for compressed sensing
3,779 Citations2008Emmanuel J. Candès
IEEE Transactions on Information TheoryGreed is Good: Algorithmic Results for Sparse Approximation
3,648 Citations2004Joel A. Tropp
This article presents new results on using a greedy algorithm, orthogonal matching pursuit (OMP), to solve the sparse approximation problem over redundant dictionaries and develops a sufficient condition under which OMP can identify atoms from an optimal approximation of a nonsparse signal.
Communications on Pure and Applied MathematicsFor most large underdetermined systems of linear equations the minimal 𝓁<sub>1</sub>‐norm solution is also the sparsest solution
2,541 Citations2006David L. Donoho
The techniques include the use of random proportional embeddings and almost‐spherical sections in Banach space theory, and deviation bounds for the eigenvalues of random Wishart matrices.
IEEE Transactions on Information TheoryStable recovery of sparse overcomplete representations in the presence of noise
2,209 Citations2005David L. Donoho, Michael Elad +1 more
This paper establishes the possibility of stable recovery under a combination of sufficient sparsity and favorable structure of the overcomplete system and shows that similar stability is also available using the basis and the matching pursuit algorithms.
IEEE Transactions on Information TheoryUncertainty principles and ideal atomic decomposition
1,967 Citations2001David L. Donoho, Xiaoming Huo
It is proved that if S is representable as a highly sparse superposition of atoms from this time-frequency dictionary, then there is only one such highly sparse representation of S, and it can be obtained by solving the convex optimization problem of minimizing the l/sup 1/ norm of the coefficients among all decompositions.
arXiv (Cornell University)The Dantzig selector: Statistical estimation when $p$ is much larger than $n$
1,725 Citations2005Candes, Emmanuel, Tao, Terence
Is it possible to estimate β reliably based on the noisy data y?
IEEE Transactions on Information TheoryJust relax: convex programming methods for identifying sparse signals in noise
1,427 Citations2006Joel A. Tropp
A method called convex relaxation, which attempts to recover the ideal sparse signal by solving a convex program, which can be completed in polynomial time with standard scientific software.
Journal of the American Mathematical SocietyCompressed sensing and best 𝑘-term approximation
1,034 Citations2008Albert Cohen, Wolfgang Dahmen +1 more
The typical paradigm for obtaining a compressed version of a discrete signal represented by a vector x ∈ R is to choose an appropriate basis, compute the coefficients of x in this basis, and then retain only the k largest of these with k < N .
Communications on Pure and Applied MathematicsFor most large underdetermined systems of equations, the minimal 𝓁<sub>1</sub>‐norm near‐solution approximates the sparsest near‐solution
645 Citations2006David L. Donoho
It is shown that for most Φ, if the optimally sparse approximation x0,ϵ is sufficiently sparse, then the solution x1, ϵ of the 𝓁1‐minimization problem is a good approximation to x0 ,ϵ.
IEEE Transactions on Information TheoryOn Sparse Representations in Arbitrary Redundant Bases
569 Citations2004J.-J. Fuchs
The purpose of this contribution is to generalize some recent results on sparse representations of signals in redundant bases and give a sufficient condition for the unique sparsest solution to be the unique solution to both a linear program or a parametrized quadratic program.
IEEE Transactions on Information TheoryRecovery of Exact Sparse Representations in the Presence of Bounded Noise
314 Citations2005J.-J. Fuchs
The purpose of this contribution is to extend some recent results on sparse representations of signals in redundant bases developed in the noise-free case to the case of noisy observations, finding a bound on the number of nonzero entries in xo.
2007 IEEE/SP 14th Workshop on Statistical Signal ProcessingToeplitz-Structured Compressed Sensing Matrices
301 Citations2007Waheed U. Bajwa, Jarvis Haupt +3 more
It is shown that Toeplitz-structured matrices with entries drawn independently from the same distributions are also sufficient to recover x from y with high probability, and the performance of such matrices is compared with that of fully independent and identically distributed ones.
Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements
230 Citations2006Mark Rudelson, Roman Vershynin
The first guarantees for universal measurements (i.e. which work for all sparse functions) with reasonable constants are proved, based on the technique of geometric functional analysis and probability in Banach spaces.
ON BLOCK THRESHOLDING IN WAVELET REGRESSION: ADAPTIVITY, BLOCK SIZE, AND THRESHOLD LEVEL
107 Citations2002Tommaso Cai