Sparsity and uniqueness for some specific under-determined linear systems

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×m matrix, A, with m>n, and a vector, b=Ax₀, with x₀ having q0 to be the unique sparsest solution to Ax=Ax₀. 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₀ 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₀ can be recovered by solving a linear program.