Sparse representations are most likely to be the sparsest possible (Q871467)

Summary: Given a signal \(\underline{S} \in \mathbb R^N\) and a full-rank matrix \(\mathbf D \in \mathbb R^{N\times L}\) with \(N <L\), we define the signal's overcomplete representations as all \(\underline{\alpha} \in \mathbb R^L\) satisfying \(\underline{S} = \mathbf {D}\underline{\alpha}\). Among all the possible solutions, we have special interest in the sparsest one -- the one minimizing \(||\underline{\alpha}||_0\). Previous work has established that a representation is unique if it is sparse enough, requiring \(||\underline{\alpha}||_0< \text{Spark}(\mathbf {D})/2\). The measure \(\text{Spark}(\mathbf {D})\) stands for the minimal number of columns from \(\mathbf {D}\) that are linearly dependent. This bound is tight -- examples can be constructed to show that with \(\text{Spark}(\mathbf {D})/2\) or more nonzero entries, uniqueness isviolated. In this paper we study the behavior of overcomplete representations beyond the above bound. While tight from a worst-case standpoint, a probabilistic point of view leads to uniqueness of representations satisfying \(||\underline{\alpha}||_0< \text{Spark}(\mathbf {D})\). Furthermore, we show that even beyond this point, uniqueness can still be claimed with high confidence. This new result is important for the study of the average performance of pursuit algorithms -- when trying to show an equivalence between the pursuit result and the ideal solution, one must also guarantee that the ideal result is indeed the sparsest.