Stable signal recovery from incomplete and inaccurate measurements
Emmanuel J. Candès, Justin Romberg, Terence Tao
Communications on Pure and Applied Mathematics · 2006 · 7,039 citationsOpen access
No retraction on record in OpenAlex.Check Crossref now
Cite this paper
Candès, E. J., Romberg, J., & Tao, T. (2006). Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics, 59(8), 1207–1223. https://doi.org/10.1002/cpa.20124
In text: (Candès et al., 2006)
Ask a question about this research
One question, free, no account. Anchorcite finds the papers, checks each against Crossref and links every sentence of the answer to the passage it comes from.
Abstract
Abstract Suppose we wish to recover a vector x 0 ∈ ℝ 𝓂 (e.g., a digital signal or image) from incomplete and contaminated observations y = A x 0 + e ; A is an 𝓃 × 𝓂 matrix with far fewer rows than columns (𝓃 ≪ 𝓂) and e is an error term. Is it possible to recover x 0 accurately based on the data y ? To recover x 0 , we consider the solution x # to the 𝓁 1 ‐regularization problem where ϵ is the size of the error term e . We show that if A obeys a uniform uncertainty principle (with unit‐normed columns) and if the vector x 0 is sufficiently sparse, then the solution is within the noise level As a first example, suppose that A is a Gaussian random matrix; then stable recovery occurs for almost all such A 's provided that the number of nonzeros of x 0 is of about the same order as the number of observations. As a second instance, suppose one observes few Fourier samples of x 0 ; then stable recovery occurs for almost any set of 𝓃 coefficients provided that the number of nonzeros is of the order of 𝓃/(log 𝓂) 6 . In the case where the error term vanishes, the recovery is of course exact, and this work actually provides novel insights into the exact recovery phenomenon discussed in earlier papers. The methodology also explains why one can also very nearly recover approximately sparse signals. © 2006 Wiley Periodicals, Inc.
Related papers
- Compressed sensing2006
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers2011
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information2006
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems2009
- An Introduction To Compressive Sampling2008
Metadata from OpenAlex (CC0). Citations are generated from the published record.