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

**Emmanuel J. Candes****Terence Tao**

CiteWeb id: 20060000061

CiteWeb score: 4796

DOI: 10.1109/TIT.2006.885507

Suppose we are given a vector f in a class FsubeRopf 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 epsi in the Euclidean (lscr 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 nth largest entry of the vector |f| (or of its coefficients in a fixed basis) obeys |f| (n) lesRmiddotn -1 p/, where R>**0** and p>**0**. Suppose that we take measurements y k =langf #HASH# ,X k rang,k=1,...,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** t , defined as the solution to the constraints y k =langf #HASH# ,X k rang with minimal lscr 1 norm, obeys parf-f #HASH# par lscr2 lesC p middotRmiddot(K/logN) -r , 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

- www.iris.ee.iisc.ernet.in/CS/CS/OptimalRecovery%20and%20Random%20Projections.pdf
- authors.library.caltech.edu/6806/1/CANieeetit06b.pdf
- statweb.stanford.edu/~candes/papers/OptimalRecovery.pdf
- www.signallake.com/innovation/OptimalRecovery06.pdf
- arxiv.org/pdf/math/0410542
- www.maths.tcd.ie/~mnl/store/CandesTao2004a.pdf
- users.ece.gatech.edu/justin/l1magic/downloads/papers/OptimalRecovery.pdf
- home.ustc.edu.cn/~zhanghan/cs/Candes_Tao06.pdf
- www.cs.jhu.edu/~misha/ReadingSeminar/Papers/Candes04.pdf
- www.inatel.br/docentes/dayan/easyfolder/TP542/Artigos/Near%20Optimal%20Signal%20Recovery%20From%20Random%20Projections.pdf
- dblp.uni-trier.de/db/journals/tit/tit52.html#HASH#CandesT06
- https://arxiv.org/abs/math/0410542
- www-stat.stanford.edu/~candes/papers/OptimalRecovery.pdf
- resolver.caltech.edu/CaltechAUTHORS:CANieeetit06b
- authors.library.caltech.edu/6806/
- dl.acm.org/citation.cfm?id=2272610
- yadda.icm.edu.pl/yadda/element/bwmeta1.element.ieee-000004016283
- adsabs.harvard.edu/abs/2004math.....10542C
- acm.caltech.edu/l1magic/downloads/papers/optimalrecovery.pdf
- ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4016283

Emmanuel J. Candes, Terence Tao,

Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?(2006)## HTML code:

## Wiki code: