ℓ1-Analysis minimization and generalized (co-)sparsity: When does recovery succeed?

Genzel, Martin; Kutyniok, Gitta und März, Maximilian (2021): ℓ1-Analysis minimization and generalized (co-)sparsity: When does recovery succeed? In: Applied and Computational Harmonic Analysis, Bd. 52: S. 82-140

Abstract

This paper investigates the problem of stable signal estimation from undersampled, noisy sub-Gaussian measurements under the assumption of a cosparse model. Based on generalized notions of sparsity, a novel recovery guarantee for the -analysis basis pursuit is derived, enabling accurate predictions of its sample complexity. The bounds on the number of required measurements explicitly depend on the Gram matrix of the analysis operator and therefore account for its mutual coherence structure. The presented results defy conventional wisdom which promotes the sparsity of analysis coefficients as the crucial quantity to be studied. In fact, this paradigm breaks down in many situations of interest, for instance, when applying a redundant (multilevel) frame as analysis prior. In contrast, the proposed sampling-rate bounds reliably capture the recovery capability of various practical examples. The proofs are based on establishing a sophisticated upper bound on the conic Gaussian mean width associated with the underlying -analysis polytope.

• Dokumententyp: Zeitschriftenartikel
• Fakultät: Mathematik, Informatik und Statistik > Mathematik > Professur für Mathematische Grundlagen des Verständnisses der künstlichen Intelligenz
• Themengebiete: 500 Naturwissenschaften und Mathematik > 510 Mathematik
• ISSN: 1063-5203
• Sprache: Englisch