uniqueness of a sparse solution

Let $\mathbb{F}$ be a field, and let $m,n\in\mathbb{N}\setminus\{0\}.$ We denote by $\displaystyle\left\|x\right\|_{0}$ the Hamming weight of a column vector $\displaystyle x=[x_{1},\ldots,x_{n}]^{\rm T}\in\mathbb{F}^{n},$ i.e., $\displaystyle\left\|x\right\|_{0}=\#\{j\in\{1,\ldots,n\}:\,x_{j}\neq 0\}.$ Consider a non-negative integer $k,$ and an $m\times n$ matrix $A$ whose entries belong to $\mathbb{F}.$

Theorem 1 (Donoho and Elad)

The following conditions are equivalent:
(1) for each column vector $\displaystyle y\in\mathbb{F}^{m}$ there exists at most one $\displaystyle x\in\mathbb{F}^{n}$ such that $Ax=y$ and $\displaystyle\left\|x\right\|_{0}\leq k,$ (2) $k<\frac{1}{2}{\rm spark}(A).$

The standard proof of the theorem (see, for instance, [2]) goes as follows.

Proof. First, suppose that condition (1) is not satisfied. Then there exist column vectors $\displaystyle v,w\in\mathbb{F}^{n}$ such that $v\neq w,\,Av=Aw,$ and $\displaystyle\max\left\{\left\|v\right\|_{0},\left\|w\right\|_{0}\right\}\leq k.$ Consequently, $\displaystyle v-w\in\mathbb{F}^{n}\setminus\{{\bf 0}\}$ and $A(v-w)={\bf 0}.$ Moreover, by the definition of the Hamming weight, $\displaystyle\left\|v-w\right\|_{0}\leq 2k.$ Thus, $\displaystyle{\rm spark}(A)=\inf\left\{\left\|x\right\|_{0}:\,x\in\mathbb{F}^{% n}\setminus\{{\bf 0}\},\,Ax={\bf 0}\right\}\leq 2k,$ which means that condition (2) is not satisfied.
Next, suppose that (2) is not satisfied. Then there exists a column vector $\displaystyle u\in\mathbb{F}^{n}\setminus\{{\bf 0}\}$ such that $Au={\bf 0}$ and $\displaystyle\left\|u\right\|_{0}\leq 2k.$ It is easy to see that $u=p-q$ for some $\displaystyle p,q\in\mathbb{F}^{n}$ with $\displaystyle\max\left\{\left\|p\right\|_{0},\left\|q\right\|_{0}\right\}\leq k.$ (If $\displaystyle h:=\left\|u\right\|_{0}>k,\,u=[u_{1},\ldots,u_{n}]^{\rm T},$ and $\displaystyle\{j\in\{1,\ldots,n\}:\,u_{j}\neq 0\}=\{j_{1},\ldots,j_{h}\},$ define $\displaystyle p=[p_{1},\ldots,p_{n}]^{\rm T}$ by

$p_{j}=\left\{\begin{array}[]{ll}u_{j},&\mbox{if $j\in\{j_{1},\ldots,j_{k}\},$}% \\ 0,&\mbox{otherwise.}\end{array}\right.$

If $\displaystyle\left\|u\right\|_{0}\leq k,$ define $p=u.)$ Since $p\neq q$ and $Ap=Aq,$ condition (1) is not satisfied. $\Box$

References

1 D. L. Donoho and M. Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via $\ell^{1}$ minimization, Proc. Natl. Acad. Sci. USA 100, No. 5: 2197–2202 (2003).
2 Compressed Sensing: Theory and Applications, edited by Y. C. Eldar and G. Kutyniok, Cambridge University Press, 2012.

Title	uniqueness of a sparse solution
Canonical name	UniquenessOfASparseSolution
Date of creation	2013-03-22 19:36:26
Last modified on	2013-03-22 19:36:26
Owner	kammerer (26336)
Last modified by	kammerer (26336)
Numerical id	54
Author	kammerer (26336)
Entry type	Theorem
Classification	msc 15A06