ℓ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, Vol. 52: pp. 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.

• Item Type: Journal article
• Faculties: Mathematics, Computer Science and Statistics > Mathematics > Bavarian Chair for Mathematical Foundations of Artificial Intelligence
• Subjects: 500 Science > 510 Mathematics
• ISSN: 1063-5203
• Language: English