Compressed Sensing and Redundant Dictionaries

Rauhut, Holger ; Schnass, Karin und Vandergheynst, Pierre (2008): Compressed Sensing and Redundant Dictionaries. In: IEEE Transactions on Information Theory, Vol. 54, No. 5: pp. 2210-2219

Abstract

This paper extends the concept of compressed sensing to signals that are not sparse in an orthonormal basis but rather in a redundant dictionary. It is shown that a matrix, which is a composition of a random matrix of certain type and a deterministic dictionary, has small restricted isometry constants. Thus, signals that are sparse with respect to the dictionary can be recovered via basis pursuit (BP) from a small number of random measurements. Further, thresholding is investigated as recovery algorithm for compressed sensing, and conditions are provided that guarantee reconstruction with high probability. The different schemes are compared by numerical experiments.

• Item Type: Journal article
• Faculties: Mathematics, Computer Science and Statistics > Mathematics > Chair of Mathematics of Information Processing
• Subjects: 500 Science > 510 Mathematics
• ISSN: 0018-9448
• Language: English