December 1, 2006IEEE Transactions on Information Theory
Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
Authors
Discussion
Loading...
Member takes
Implication
Theoretical analysis demonstrates near-optimal recovery of sparse high-dimensional signals from minimal random projections via l1-minimization, indicating universal efficient encoding strategies.
Key Points
- To determine the minimal number of random linear measurements necessary to accurately reconstruct sparse or compressible high-dimensional signals.
- Modeled compressible signals with power-law decaying coefficient magnitudes obeying |f|_(n) ≤ R * n^(-1/p) in an N-dimensional space.
- Analyzed signal reconstruction accuracy using an l1-norm minimization linear program applied to K random Gaussian projection vectors and sampled Fourier coefficients.
- Proved that l1-reconstruction achieves an l2-error bound of ||f - f^#||_l2 ≤ C_p * R * (K / log N)^(-r), where r = 1/p - 1/2, with overwhelming probability.
- Demonstrated that this recovery rate is near-optimal, establishing that higher accuracy is generally impossible from any K linear measurements across ensembles satisfying two basic hypotheses.
Cite This Study
Candès et al. (2006) studied this question.