# Tag Info

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
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 ...