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

<p>Let me sketch the argument for non-adaptive measurements. If $K$ is a subset of $\ell_p^n$, then the <em>Gelfand $m$-width of $K$</em> 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 <em>compressive $m$-width</em> 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. </p>

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

<p><strong>Proof:</strong> 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$</p>

<p>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&lt; 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}}$$</p>

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

<p><strong>Theorem 2:</strong> 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}$$</p>

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

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

<p>I learnt of this argument from Chapter 10 of Foucart and Rauhut's recent book, <a href="http://www.springer.com/birkhauser/mathematics/book/978-0-8176-4947-0" rel="nofollow">"A Mathematical Introduction to Compressive Sensing"</a>. 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&lt;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 <em>exact</em>-recovery of $k$-sparse vectors.</p>

CC BY-SA 3.0
2014-10-23T21:12:31.987Z
2015-01-13T15:33:23.547Z
2015-01-13T15:33:23.547Z
arnab
<p>You can get references in the <a href="http://statweb.stanford.edu/~markad/publications/ddek-chapter1-2011.pdf" rel="nofollow">book chapter</a> 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))$. </p>

CC BY-SA 4.0
2019-07-10T05:26:25.360Z
It seems that the link above is broken. You probably referred to this (http://www.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..).
gradstudent
CC BY-SA 4.0
2019-07-10T05:31:49.890Z
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, https://arxiv.org/abs/1009.0744
gradstudent
CC BY-SA 3.0
2014-10-23T15:47:49.153Z
2014-10-23T15:47:49.153Z
Sasho Nikolov
<p>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.</p>

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

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

<lower-bounds><it.information-theory><compressed-sensing>
Lower bound proof for compressive sensing (Gel'fand widths)?
user28687
# Lower bound proof for compressive sensing (Gel'fand widths)?

(Asked by: username_0 on 2014-10-23)

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.

**Tags:** lower-bounds, it.information-theory, compressed-sensing

---

## 2 answers

### Answer by username_1 on 2014-10-23. Score: 5 | Accepted answer

$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"](http://www.springer.com/birkhauser/mathematics/book/978-0-8176-4947-0). 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 $0exact-recovery of $k$-sparse vectors.


---

### Answer by username_2 on 2014-10-23. Score: 3

You can get references in the [book chapter](http://statweb.stanford.edu/~markad/publications/ddek-chapter1-2011.pdf) 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))$.

> **Comments:**
> **username_3**: It seems that the link above is broken. You probably referred to this (http://www.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..).  
> **username_3**: 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, https://arxiv.org/abs/1009.0744  

---

