5
$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 be polynomial time, and the measurement matrix may be adaptive (in the sense that the $i$'th row of the matrix can depend on the inner product of the input ...
3
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 order $k$, i.e. every submatrix of $k$ columns is almost an isometry as a linear operator, then $m = \Omega(k\log(n/k))$.
2
Assume there is a program that maps every sequence of $n$ bits to a sequence of $n-1$ bits. There are $2^n$ sequences with $n$ bits, but only $2^{n-1}$ sequences with $n-1$ bits. Hence there are two sequences $S,S'$ that get mapped to the same sequence $C$. Therefore there can be no algorithm that reverses the transformation.
1
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 be transformed into many different bases. The vector will be more 'sparse' in some of those bases than others. In fact, there's even a set of bases where the ...
Only top voted, non community-wiki answers of a minimum length are eligible
