5
votes
Accepted
Lower bound proof for compressive sensing (Gel'fand widths)?
$m = \Omega(k \log(n/k))$ is a lower bound for any compressive sensing scheme, not just $\ell_1$-minimization using RIP guarantees on the measurement matrix. In fact, the recovery algorithm need not ...
- 6,940
3
votes
Lower bound proof for compressive sensing (Gel'fand widths)?
You can get references in the book chapter by Davenport, Duarte, Eldar and Kutinyok: look at the section Measurement Bounds on p.23. The result is that if an $m\times n$ matrix has the RIP property of ...
- 18k
1
vote
The connection between compressed sensing and sparse representation
Consider a real world 'signal' - a discrete set of numbers representing something real (e.g. an image, an audio recording, etc.). These numbers form a vector in some vector space. Any such vector can ...
- 111
Only top scored, non community-wiki answers of a minimum length are eligible