uniqueness of a sparse solution


Let 𝔽 be a field, and let m,n{0}. We denote by x0 the Hamming weight of a column vectorMathworldPlanetmath x=[x1,,xn]T𝔽n, i.e., x0=#{j{1,,n}:xj0}. Consider a non-negative integer k, and an m×n matrix A whose entries belong to 𝔽.

Theorem 1 (Donoho and Elad)

The following conditions are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath:
(1) for each column vector yFm there exists at most one xFn such that Ax=y and x0k, (2) k<12spark(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 v,w𝔽n such that vw,Av=Aw, and max{v0,w0}k. Consequently, v-w𝔽n{𝟎} and A(v-w)=𝟎. Moreover, by the definition of the Hamming weight, v-w02k. Thus, spark(A)=inf{x0:x𝔽n{𝟎},Ax=𝟎}2k, which means that condition (2) is not satisfied.
Next, suppose that (2) is not satisfied. Then there exists a column vector u𝔽n{𝟎} such that Au=𝟎 and u02k. It is easy to see that u=p-q for some p,q𝔽n with max{p0,q0}k. (If h:=u0>k,u=[u1,,un]T, and {j{1,,n}:uj0}={j1,,jh}, define p=[p1,,pn]T by

pj={uj,if j{j1,,jk},0,otherwise.

If u0k, define p=u.) Since pq and Ap=Aq, condition (1) is not satisfied.

References

  • 1 D. L. Donoho and M. Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via 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