uniqueness of a sparse solution

Let 𝔽 be a field, and let m,n∈ℕ∖{0}. We denote by ∥x∥0 the Hamming weight of a column vectorMathworldPlanetmath x=[x1,…,xn]T∈𝔽n, i.e., ∥x∥0=#⁢{j∈{1,…,n}:xj≠0}. 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 y∈Fm there exists at most one x∈Fn such that A⁢x=y and ∥x∥0≤k, (2) k<12⁢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 v,w∈𝔽n such that v≠w,A⁢v=A⁢w, and max⁡{∥v∥0,∥w∥0}≤k. Consequently, v-w∈𝔽n∖{𝟎} and A⁢(v-w)=𝟎. Moreover, by the definition of the Hamming weight, ∥v-w∥0≤2⁢k. Thus, spark⁢(A)=inf⁡{∥x∥0:x∈𝔽n∖{𝟎},A⁢x=𝟎}≤2⁢k, 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 A⁢u=𝟎 and ∥u∥0≤2⁢k. It is easy to see that u=p-q for some p,q∈𝔽n with max⁡{∥p∥0,∥q∥0}≤k. (If h:=∥u∥0>k,u=[u1,…,un]T, and {j∈{1,…,n}:uj≠0}={j1,…,jh}, define p=[p1,…,pn]T by

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

If ∥u∥0≤k, define p=u.) Since p≠q and A⁢p=A⁢q, condition (1) is not satisfied. □


  • 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