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, Bd. 7, Nr. 2: S. 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.

• Dokumententyp: Zeitschriftenartikel
• Fakultät: Mathematik, Informatik und Statistik > Mathematik > Lehrstuhl für Mathematik der Informationsverarbeitung
• Themengebiete: 500 Naturwissenschaften und Mathematik > 510 Mathematik
• ISSN: 1530-6429
• Sprache: Englisch