Sparseness Theorems and Sparse Representation of Signals

We present general sparseness theorems showing that the solutions of various types least square and absolute value optimization problems (linear with respect to $l_{2} $ and $l_{1}$ norm, non-linear ones) possess sparse solutions. These theorems have direct application to the problem of identification (up to scaling and permutation) of the source signals $\mathrm{S}\in \mathrm{R}^{n\mathrm{x}N} $ a $\mathrm{d} $ the mixing matrix A $\in 1\mathrm{R}^{m\cross n} $ , $m\leq $ n, knowing only their mixture $\mathrm{X}= $ AS – this is so called underdetermined sparse component analysis (SCA). We present two new algorithms: for matrix identification (when the sources are very sparse), and for source recovery, improving in such a way the standard basis pursuit method of S. Chen, D. Donoho and M. Sounders (applied when the mixing matrix is known or correctly estimated). We illustrate our algorithms with examples.