Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
By E.J. Candes, Terence Tao. 2004
7,131 citations recorded by the source corpus.
Suppose we are given a vector f in a class FsubeRopf<sup>N </sup>, e.g., a class of digital signals or digital images. How many linear measurements do we need to make about f to be able to recover f to within precision epsi in the Euclidean (lscr<sub>2</sub>) metric? This paper shows that if the objects of interest are sparse in a fixed basis or compressible, then it is possible to reconstruct f to within very high accuracy from a small number of random measurements by solving a simple linear program. More precisely, suppose that the nth largest entry of the vector |f| (or of its coefficients in a fixed basis) obeys |f|<sub>(n)</sub>lesRmiddotn<sup>-1</sup>p/, where R>0 and p>0. Suppose that we take measurements y<sub>k</sub>=langf<sup># </sup>,X<sub>k</sub>rang,k=1,...,K, where the X<sub>k</sub> are N-dimensional Gaussian vectors with independent standard normal entries. Then for each f obeying the decay estimate above for some 0<p<1 and with overwhelming probability, our reconstruction f<sup>t</sup>, defined as the solution to the constraints y<sub>k</sub>=langf<sup># </sup>,X<sub>k</sub>rang with minimal lscr<sub>1</sub> norm, obeys parf-f<sup>#</sup>par<sub>lscr2</sub>lesC<sub>p </sub>middotRmiddot(K/logN)<sup>-r</sup>, r=1/p-1/2. There is a sense in which this result is optimal; it is generally impossible to obtain a higher accuracy from any set of K measurements whatsoever. The methodology extends to various other random measurement ensembles; for example, we show that similar results hold if one observes a few randomly sampled Fourier coefficients of f. In fact, the results are quite general and require only two hypotheses on the measurement ensemble which are detailed
Subfields: Applied Mathematics, Computational Mechanics, Computer Vision and Pattern Recognition
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Applied Mathematics
- Roman Vershynin
- Richard Baraniuk
- E.J. Candes
- Justin K. Romberg
- Yonina C. Eldar
- Marco F. Duarte
- Martin J. Wainwright
- Joel A. Tropp
In Computational Mechanics
- E.J. Candes
- Richard Baraniuk
- Wotao Yin
- Marco F. Duarte
- Yonina C. Eldar
- Justin K. Romberg
- Lei Zhang
- Francis R. Bach
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Lei Zhang
- Ming-Hsuan Yang
- Dacheng Tao
- Xiaogang Wang
- Trevor Darrell
- Yi Yang
- Andrew Zisserman
Citations in the corpus
- Provable defenses against adversarial examples via the convex outer adversarial polytope (2017, methodology): “are highly structured (such as convolutions), there will be a large amount of sparsity that can be exploited, at least for networks that are not too deep; we could also use random projection methods [Candes and Tao, 2006] to derive high-probability bounds on the norms in question; or we can even use”
- Exact Matrix Completion via Convex Optimization (2008, background): “Our work is inspired by results in the emerging field of compressive sampling or compressed sensing, a new paradigm for acquiring information about objects of interest from what appears to be a highly incomplete set of measurements [10, 12, 16].”
- Introduction to the non-asymptotic analysis of random matrices (2010, neutral): “Earlier, Candes and Tao [18] proved a similar result for random Fourier matrices, although with a slightly higher exponent in the logarithm for the number of measurements in (5.”
- A Singular Value Thresholding Algorithm for Matrix Completion (2008, background): “…and especially by the work on linearized Bregman iterations for compressed sensing, see [9–11, 23, 44, 51] for linearized Bregman iterations and [ 14– 17, When applied to ℓ 1 -minimization problems, linearized Bregman iterations are sequences of soft-thresholding rules operating on vectors.”
- GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “Such a notation has been used in compressed sensing [3], matrix completion [2], and randomized linear algebra [6, 40, 39].”
- Uncertainty Principles and Vector Quantization (2006, background): “Then, with probability at least 1 − p , the matrix U satisfies the uncertainty principle with parameters Theorem 4.3 is a direct of a slightly stronger result established in [7] and improved in [35], [36].”
- Straggler Mitigation in Distributed Optimization Through Data Encoding (2017, background): “This is equivalent to a randomized Fourier or Hadamard ensemble, which is known to satisfy the RIP with high probability [5].”
- Compressed sensing (2006, result): “In fact, Candès has informed us of some recent results he obtained with Tao [47] indicating that, modulo polylog factors, A2 holds for the uniformly sampled partial Fourier ensemble.”
- Online Adaptive Estimation of Sparse Signals: Where RLS Meets the $\ell_1$ -Norm (2010, methodology): “To bypass the nonconvexity of the -norm, VS and CS approaches replace it with convex penalty terms (e.g., the -norm) that capture sparsity but also lead to computationally efficient solvers.”
- Received-Signal-Strength-Based Indoor Positioning Using Compressive Sensing (2012, background): “It is shown in [29] that Q obeys the Restricted Isomatry Property (RIP) that is needed by the CS [30].”
- Random Sampling of Sparse Trigonometric Polynomials (2005, background): “(2.8) Later in Section 4 we will provide some more information on these combinatorial quantities.”
- Stochastic Collocation Algorithms Using l1-Minimization for Bayesian Solution of Inverse Problems (2015, background): “Our first notion is the so-called restricted isometry property (RIP), which was introduced by Candès and Tao in [8].”
- Half-Quadratic-Based Iterative Minimization for Robust Sparse Representation (2014, methodology): “Based on the ‘0-‘1 equivalence theory [4], [5], the solution of an ‘0 minimization problem is equal to that of an ‘1 minimization problem under certain conditions.”
- An efficient algorithm for total variation regularization with applications to the single pixel camera and compressive sensing (2010, methodology): “Grounded on those early efforts, a new CS theory was proposed by Candes, Tomberg, Tao [2, 3], and Donoho [4] in 2006, which theoretically guarantees l\ minimization is equivalent to £Q minimization under some conditions on signal reconstruction.”
- Compressed Sensing for Real-Time Energy-Efficient ECG Compression on Wireless Body Sensor Nodes (2011, methodology): “The output of this module, z, is subsequently uniformly quantized yielding the N -dimensional vector ẑ.”