The Sparsity Gap: Uncertainty Principles Proportional to Dimension
arXiv:1003.0415 · doi:10.1109/CISS.2010.5464824
Abstract
In an incoherent dictionary, most signals that admit a sparse representation admit a unique sparse representation. In other words, there is no way to express the signal without using strictly more atoms. This work demonstrates that sparse signals typically enjoy a higher privilege: each nonoptimal representation of the signal requires far more atoms than the sparsest representation-unless it contains many of the same atoms as the sparsest representation. One impact of this finding is to confer a certain degree of legitimacy on the particular atoms that appear in a sparse representation. This result can also be viewed as an uncertainty principle for random sparse signals over an incoherent dictionary.
6 pages. To appear in the Proceedings of the 44th Ann. IEEE Conf. on Information Sciences and Systems