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 ...
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 ...
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
compressed-sensing × 14linear-algebra × 4
it.information-theory × 3
sparse-matrix × 3
cc.complexity-theory × 1
ds.algorithms × 1
reference-request × 1
np-hardness × 1
approximation-algorithms × 1
optimization × 1
ds.data-structures × 1
machine-learning × 1
cg.comp-geom × 1
lower-bounds × 1
lg.learning × 1
matrices × 1
approximation × 1
query-complexity × 1
na.numerical-analysis × 1
streaming-algorithms × 1
linear-equations × 1
norms × 1
stable × 1