On the Impossibility of Uniform Sparse Reconstruction using Greedy Methods

Rauhut, Holger (2008): On the Impossibility of Uniform Sparse Reconstruction using Greedy Methods. In: Sampling Theory in Signal and Image Processing, Vol. 7, No. 2: pp. 197-215

Abstract

It has previously been shown that a trigonometric polynomial having at most M non-vanishing coefficients can be recovered from N = O(M log(D)) random samples by the greedy methods thresholding and orthogonal matching pursuit with high probability. In this note we show that these results cannot be made uniform in the sense that a single (random) sampling set cannot guarantee recovery of all such M-sparse trigonometric polynomials simultaneously with high probability using the two greedy methods.

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