Let $x \in \mathbb{R}^n$ have $k$ non-zero entries. The main insight of compressive sensing is that there exist $m\times n$ matrices $A$ with $m = O(k \log n/k)$ such that any $x$ can be recovered from $Ax$ in polynomial time.

A little thought shows that $Ax$ must have at least $\log \binom{n}{k} = \Theta(k \log n/k)$ bits. I believe a stronger statement is true as well, namely, that we must have $m =\Omega(k \log n/k)$ measurements as well.

I know the lower bound on $m$ has something to do with Gel'fand widths, but am having a hard time finding a resource that lays out the argument explicitly. Either pointers to write-ups or a rough summary of the argument would be helpful.


2 Answers 2


$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 vector with rows $1$ through $i-1$).

Let me sketch the argument for non-adaptive measurements. If $K$ is a subset of $\ell_p^n$, then the Gelfand $m$-width of $K$ is defined to be: $$d^m(K) = \inf_{A: \mathbb{R}^{m \times n}} \sup_{x \in K \cap \ker(A)} \|x\|_p$$ Define the compressive $m$-width as: $$E^m(K) = \inf_{A: \mathbb{R}^{m \times n}, \Delta: \mathbb{R}^m \to \mathbb{R}^n} \sup_{x \in K}\|x - \Delta(A x)\|_p $$ Note that $\Delta$, the reconstruction procedure, can be arbitrary.

Lemma 1: If $K$ is symmetric ($K = -K$), then $E^m(K) \geq d^m(K)$.

Proof: Take some arbitrary matrix $A \in \mathbb{R}^{m \times n}$ and function $\Delta: \mathbb{R}^m \to \mathbb{R}^n$. By definition, $d^m(K) \leq \sup_{x \in K \cap \ker(A)} \|x\|$. On the other hand, for any $x \in K \cap \ker(A)$: $$\|x\| \leq \frac12 \|x-\Delta(0)\| + \frac12 \|-x-\Delta(0)\| \leq \sup_{x \in K} \|x-\Delta(Ax)\|$$ So, we have $d^m(K) \leq \sup_{x \in K \cap \ker(A)} \|x\| \leq E^m(K)$. $\blacksquare$

Now, for the connection with compressive sensing, suppose we have an integer $k \geq 1$, matrix $A \in \mathbb{R}^{m \times n}$ and a function $\Delta: \mathbb{R}^m \to \mathbb{R}^n$ such that for all $x \in \mathbb{R}^n$: $$\|x - \Delta(Ax)\|_p \leq \frac{C}{k^{1-1/p}} \min_{k\text{-sparse } z} \|x - z\|_1$$ where $C$ is a constant. Let $B_1$ be the unit $\ell_1$-ball, viewed as a subset of $\ell_p^n$, for $1< p\leq 2$. We clearly have that: $$E^m(B_1) \leq \frac{C}{k^{1-1/p}} \sup_{x: \|x\|_1 \leq 1} \min_{k\text{-sparse } z} \|x - z\|_1 \leq \frac{C}{k^{1-1/p}}$$

But we also have a lower bound for the Gelfand width of $\ell_1$-balls.

Theorem 2: There exists a constant $c_1$ such that: $$d^m(B_1) \geq c_1 \min\left(1, \frac{\log(n/m)}{m}\right)^{1-1/p}$$

Combining with the above, we have that: $$c' \min\left(1, \frac{\log(n/m)}{m}\right) \leq \frac1k$$ Thus, if $k$ is large enough, this gives the lower bound, $m = \Omega(k \log(n/k))$.

The proof can be extended without much difficulty to the adaptive setting. The assumption that $k$ is sufficiently large can also be removed.

I learnt of this argument from Chapter 10 of Foucart and Rauhut's recent book, "A Mathematical Introduction to Compressive Sensing". It's due to Cohen, Dahmen and Davenport ("Compressed sensing and best k-term approximation", 2009). Theorem 2 is due to Garnaev and Gluskin ("On widths of the Euclidean ball", 1984). Foucart, Pajor, Rauhut and Ullrich ("The Gelfand widths of $\ell_p$-balls for $0<p\leq 1$", 2010) give a relatively simple proof of it. In fact, this latter proof is based on a lower bound for the number of measurements needed for exact-recovery of $k$-sparse vectors.


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

  • $\begingroup$ It seems that the link above is broken. You probably referred to this (ecs.umass.edu/~mduarte/images/IntroCS.pdf) Its a bit curious that the Gelfand width argument above and the this one which is about the sensing matrix being RIP both give the same ball-park estimate and both have the same weakness that neither of them see the sensitivity to the RIP constant of $A$. (..and as Theorem 1.3 in this reference points out $A$ being RIP is somewhat necessary for any recovery to work..). $\endgroup$ Commented Jul 10, 2019 at 5:26
  • $\begingroup$ So in this light maybe the "right" result one is looking for is neither of these two but the one stated at the top of page 24 of your reference which lowerbounds $m$ in ternms of $k$ and the RIP constant $\delta$. And this result has been referred to here, arxiv.org/abs/1009.0744 $\endgroup$ Commented Jul 10, 2019 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.