0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $w$ is precisely defined as a linear combination of the columns of $A_k$ and as such $\operatorname{Rank}([A_k,w]) = k$. $\endgroup$ – Jean-Luc Bouchot Nov 21 at 18:14
  • $\begingroup$ @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$. $\endgroup$ – GavinZZZ Nov 22 at 2:57
  • $\begingroup$ 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 ;) $\endgroup$ – Jean-Luc Bouchot Nov 25 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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