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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible