uniqueness of a sparse solution
Let be a field, and let We denote by the Hamming weight of a column vector i.e., Consider a non-negative integer and an matrix whose entries belong to
Theorem 1 (Donoho and Elad)
The following conditions are equivalent:
(1) for each column vector there exists at most one such that and (2)
Proof. First, suppose that condition (1) is not satisfied. Then there exist column vectors such that and Consequently, and Moreover, by the definition of the Hamming weight, Thus, which means that condition (2) is not satisfied.
Next, suppose that (2) is not satisfied. Then there exists a column vector such that and It is easy to see that for some with (If and define by
If define Since and condition (1) is not satisfied.