2017/10/31 by Martin Genzel, Gitta Kutyniok, Maximilian März · 71 citations
Computer Science · Engineering · Mathematics · #Algorithm #Applied mathematics #Artificial intelligence #Compressed sensing #Computer science #Gaussian #Image and Signal Denoising Methods #Mathematical optimization #Mathematical proof #Mathematics #Operator (biology) #Photoacoustic and Ultrasonic Imaging #Restricted isometry property #Sparse and Compressive Sensing Techniques #Wavelet #cs.IT #math.IT #msc:42C15 #msc:42C40 #msc:65J22 #msc:94A08 #msc:94A20
paper · pdf · doi:10.1016/j.acha.2020.01.002
published in Applied and Computational Harmonic Analysis 52, 82-140 (Elsevier BV)
openalex created_date 2017/11/10 · openalex publication_date 2020/01/27 · arxiv created 2021/02/22 · arxiv updated 2021/02/23 · openalex updated_date 2026/08/05
This paper investigates the problem of signal estimation from undersampled noisy sub-Gaussian measurements under the assumption of a cosparse model. Based on generalized notions of sparsity, we derive novel recovery guarantees for the ℓ1-analysis basis pursuit, enabling accurate predictions of its sample complexity. The corresponding bounds on the number of required measurements do explicitly depend on the Gram matrix of the analysis operator and therefore particularly account for its mutual coherence structure. Our findings defy conventional wisdom which promotes the sparsity of analysis coefficients as the crucial quantity to study. In fact, this common paradigm breaks down completely in many situations of practical interest, for instance, when applying a redundant (multilevel) frame as analysis prior. By extensive numerical experiments, we demonstrate that, in contrast, our theoretical sampling-rate bounds reliably capture the recovery capability of various examples, such as redundant wavelets systems, total variation, or random frames. The proofs of our main results build upon recent achievements in the convex geometry of data mining problems. More precisely, we establish a sophisticated upper bound on the conic Gaussian mean width that is associated with the underlying ℓ1-analysis polytope. Due to a novel localization argument, it turns out that the presented framework naturally extends to stable recovery, allowing us to incorporate compressible coefficient sequences as well.