Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published March 2010 | Accepted Version + Published
Book Section - Chapter Open

The sparsity gap: Uncertainty principles proportional to dimension

Tropp, Joel A.


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.

Additional Information

© 2010 IEEE.

Attached Files

Published - 05464824.pdf

Accepted Version - 1003.0415.pdf


Files (476.2 kB)
Name Size Download all
339.6 kB Preview Download
136.6 kB Preview Download

Additional details

August 19, 2023
August 19, 2023