# Number of measurements required for sparse recovery with $\ell_0$ minimization

Suppose we have a $$k$$-sparse vector $$x_0 \in \mathbb{R}^N$$, and a Gaussian measurement matrix $$A \in \mathbb{R}^{m\times n}$$. Set $$y=Ax_0$$ and solve the problem $$\min \|x\|_0$$ subject to $$Ax=y$$. How many measurements do we need for $$\ell_0$$ minimization to recovery the exact solution with probability 1?

It is easy to see that $$2k+1$$ measurements suffice, as done in Lemma 2.1 of http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.9526&rep=rep1&type=pdf. But I think the result can be improved to $$k+1$$.

Suppose $$m=k+1$$. All vectors $$x'$$ such that $$\|x'\|_0 \leq \|x_0\|_0$$ lie on a union of $$\binom{n}{k}$$ $$k$$-dimensional subspaces spanned by $$k$$ coordinate vectors. The null space of $$A$$ is $$n-k-1$$ dimensional, so the affine set $$S$$ of all solutions of $$Ax=y$$ is $$n-k-1$$ dimensional. If $$S$$ intersects any of the $$\binom{n}{k}$$ subspaces at a point not equal to $$x_0$$, then we don't have a unique solution and the algorithm fails. But I think the probability of this event should be $$0$$, hence we obtain recovery with probability 1. Is this true? If so, how can I show this formally?

Edit: I guess the question can be formed in a simpler form. I have a point $$x_0$$ that lies on a $$k$$-dimensional subspace spanned by $$k$$ coordinate vectors, and a random affine set of dimension $$n-k-1$$ that passes through $$x_0$$. What is the probability that this random affine set intersects any other $$k$$-dimensional subspace spanned by coordinate vectors? For the case $$n=2$$ and $$k=1$$, the probability is clearly $$0$$ since the affine set contains one point $$x_0$$. I wonder if this generalizes to higher dimensions.

After giving the question some more thought, I think that $$m = k+1$$ measurements would indeed suffice to guarantee exact recovery. Let me give a simple proof.
Proof. Suppose $$A\in \mathbb{R}^{(k+1)\times n}$$ has $$i.i.d.$$ Gaussian entries. We want to show that the probability that there exists some $$k$$-sparse vector $$x$$ such that $$Ax=y$$ is $$0$$. If $$Ax=y$$, then there exists $$k$$ columns of $$A$$, $$a_1,\dots, a_k$$, and coefficients $$c_1,\dots,c_k$$ such that $$\sum_{i=1}^k c_ia_i = y = \sum_{i=1}^n b_i a_i,$$ where $$b_i$$ are the entries of $$x_0$$. Thus $$\sum_{i=1}^k(c_i-b_i)a_i = \sum_{i=k+1}^n b_i a_i.$$ Let $$A_k\in\mathbb{R}^{(k+1)\times k}$$ denote the submatrix containing the columns $$a_1,\dots,a_k$$, and define a vector $$d$$ where $$d_i=c_i-a_i$$. Let $$w$$ denote the right hand side. The equation above becomes $$A_kd = w.$$ This linear system has a solution if and only if $$\mathrm{rank}(A_k) = \mathrm{rank}([A_k, w]).$$ Since the columns of $$A$$ are independent, the columns of $$A_k$$ and $$w$$ are also independent. The matrix $$A_k$$ has rank $$k$$ with probability 1, but the matrix $$[A_k, w]$$ has rank $$k+1$$ with probability 1. Hence, the probability that $$A_kd=w$$ has a solution is $$0$$. This shows that there are no other $$k$$-sparse solutions to the original equation $$Ax=y$$, and $$\ell_0$$ minimization must recover the $$x_0$$.
• $w$ is precisely defined as a linear combination of the columns of $A_k$ and as such $\operatorname{Rank}([A_k,w]) = k$. – Jean-Luc Bouchot Nov 21 at 18:14
• @Jean-LucBouchot Here $w$ is the linear combination of columns $k+1$ to $n$, and $A_k$ contains only the first $k$ columns of $A$. – GavinZZZ Nov 22 at 2:57
• You wrote $A_k d = w$ which means that there $w$ may be written as a linear combination of the columns of $A_k$: $w = d_1 a_1 + d_2 a_2 = ... = d_k a_k$. This being said, the idea you developed is very close to proving the uniqueness of the $\ell_1$ minimization ;) – Jean-Luc Bouchot Nov 25 at 23:00