Skip to content

Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

Emmanuel J. Candès, Terence Tao

IEEE Transactions on Information Theory · 2006 · 6,816 citationsOpen access

No retraction on record in OpenAlex.Check Crossref now

Cite this paper

Candès, E. J., & Tao, T. (2006). Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Transactions on Information Theory, 52(12), 5406–5425. https://doi.org/10.1109/tit.2006.885507

In text: (Candès & Tao, 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

Suppose we are given a vector $f$ in a class ${\cal F} \subset{\BBR}^N$ , 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 $\epsilon$ in the Euclidean $(\ell_2)$ 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 $n$ th largest entry of the vector $\vert f\vert$ (or of its coefficients in a fixed basis) obeys $\vert f\vert _{(n)} \le R \cdot n^{-1/p}$ , where $R > 0$ and $p > 0$ . Suppose that we take measurements $y_k = \langle f, X_k\rangle, k = 1, \ldots, K$ , where the $X_k$ 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^\sharp$ , defined as the solution to the constraints $y_k = \langle f^\sharp, X_k \rangle$ with minimal $\ell_1$ norm, obeys $$ \Vert f - f^\sharp\Vert _{\ell_2} \le C_p \cdot R \cdot (K/\log N)^{-r}, \quad 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.

  1. Compressed sensing2006
  2. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers2011
  3. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information2006
  4. A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems2009
  5. An Introduction To Compressive Sampling2008

Metadata from OpenAlex (CC0). Citations are generated from the published record.