# Lower bound proof for compressive sensing (Gel'fand widths)?

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.

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

• 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..). Jul 10, 2019 at 5:26
• 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 Jul 10, 2019 at 5:31