Compressed Sensing with Coherent and Redundant Dictionaries

Authors

Emmanuel J. Candès, Stanford University
Yonina C. Eldar, Israel Institute of Technology
Deanna Needell, Claremont McKenna CollegeFollow
Paige Randall, Center for Communications Research

Document Type

Article - postprint

Department

Mathematics (CMC)

Publication Date

10-16-2010

Abstract

This article presents novel results concerning the recovery of signals from undersampled data in the common situation where such signals are not sparse in an orthonormal basis or incoherent dictionary, but in a truly redundant dictionary. This work thus bridges a gap in the literature and shows not only that compressed sensing is viable in this context, but also that accurate recovery is possible via an ℓ₁-analysis optimization problem. We introduce a condition on the measurement/sensing matrix, which is a natural generalization of the now well-known restricted isometry property, and which guarantees accurate recovery of signals that are nearly sparse in (possibly) highly overcomplete and coherent dictionaries. This condition imposes no incoherence restriction on the dictionary and our results may be the first of this kind. We discuss practical examples and the implications of our results on those applications, and complement our study by demonstrating the potential of ℓ₁-analysis for such problems.

Comments

2011 Top 5 Hottest ACHA Article
2012 Top 2 Hottest ACHA Article
2013 Top 4 Hottest ACHA Article

The publisher's pdf can be found at: http://www.sciencedirect.com/science/article/pii/S1063520310001156

Rights Information

Copyright © 2010 Elsevier Inc. All rights reserved.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1016/j.acha.2010.10.002

Recommended Citation

Candès, E. J., Eldar, Y. C., Needell, D., Randall, P., "Compressed sensing with coherent and redundant dictionaries", Applied and Computational Harmonic Analysis, vol. 31, num. 1, pp. 59-73, 2010. doi: 10.1016/j.acha.2010.10.002