The paper extends some results on sparse representations of signals in redundant bases developed for arbitrary bases to two frequently encountered bases. The general problem is the following: given an n/spl times/m matrix, A, with m>n, and a vector, b=Ax/sub 0/, with x/sub 0/ having q<n nonzero components, find sufficient conditions for x/sub 0/ to be the unique sparsest solution to Ax=Ax/sub 0/. The answer gives an upper-bound on q depending upon A. We consider the cases where A is a Vandermonde matrix or a real Fourier matrix and the components of x/sub 0/ are known to be greater than or equal to zero. The sufficient conditions we get are much weaker than those valid for arbitrary matrices and guarantee further that x/sub 0/ can be recovered by solving a linear program.
['Jean-Jacques Fuchs']
Sparsity and uniqueness for some specific under-determined linear systems