Why is spark condition for uniqueness of $l_0$ optimization too strong? In $l_0$ minimization problem, finding sparsest solution to $Ax=b$ for an $m$ by $n$ matrix, uniqueness of the solution can be guaranteed via spark in the following way. Spark is defined as the smallest number of columns from $A$ that are linearly dependent.
[Taken from Elad, Sparse and Redundant Representations]
If a system of linear equations $Ax=b$ has a solution $x$ obeying $||x||_{0}
< \frac{\textrm{spark }A}{2}$, this solution is necessarily the sparsest possible.
I understand the proof of the theorem but I am struggling with the following.
Let $x^{*}$ be a k-sparse vector, at most $k$ non-zero components, consider
$b = Ax^{*}$. Let $A$ has spark $m+1$, for example a Gaussian matrix. Now if we solve the $l_0$ minimization problem, shouldn't it suffice to have $k\le m$. I don't see why the spark needs a stronger condition.
Thank you for any hints or suggestions
 A: Suppose that the solution is not unique or there is another sparser vector $y^*$ which is the solution to:
$$
\min \|x\|_0\\
s.t. Ax=b.
$$
Therefore we have $Ax^*=Ay^*$, which means that $A(x^*-y^*)=0$. Note that this implies that there are $\|x^*-y^*\|_0$ number of columns that are linearly dependent. This means that $\text{spark}(A)\leq \|x^*-y^*\|_0$. However:
$$
\|x^*-y^*\|_0\leq 2\|x^*\|_0.
$$
Therefore $\text{spark}(A)\leq 2\|x^*\|_0$, which goes against the assumption that $\text{spark}(A)>2\|x^*\|_0$. So this condition is sufficient condition for a solution to be the sparsest. 

From the proof, one can construct a counterexample for the case $\text{spark}(A)\leq 2\|x^*\|_0$, which includes your case $\text{spark}(A)=m+1$ and $\|x^*\|_0=k$ and $k< m+1\leq 2k$. Consider $m+1$ linearly dependent column vector of $A$, which means that there is a vector $z$ for which $Az=0$ and $\|z\|_0=m+1$. You can write $z$ as $z_1+z_2$ such that $\|z_1\|_0=k$ and $0<\|z_2\|_0=m+1-k\leq k$. Suppose that $b_1=Az_1$ and consider the following OP:
$$
\min \|x\|_0\\
s.t. Ax=b_1.
$$
Then $z_1$ is a $k-$solution to this problem but it is neither unique nor necessarily the sparsest. Because $Az_1=A(-z_2)$ and $\|z_2\|_0\leq k=\|z_1\|_0$. This means that $z_2$ is either sparser or has $k$ non-zero elements like $z_1$.
