-Analysis Minimization and Generalized (Co-)Sparsity: When Does Recovery Succeed?
arXiv:1710.04952 · doi:10.1016/j.acha.2020.01.002
Abstract
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 -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 -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.
References in corpus (16)
- The Convex Geometry of Linear Inverse Problems
- Compressed Sensing and Redundant Dictionaries
- The Cosparse Analysis Model and Algorithms
- Computational and Statistical Tradeoffs via Convex Relaxation
- ShearLab 3D: Faithful Digital Shearlet Transforms based on Compactly Supported Shearlets
- Analysis Operator Learning and Its Application to Image Reconstruction
- Insights into analysis operator learning: From patch-based sparse models to higher-order MRFs
- Greedy-Like Algorithms for the Cosparse Analysis Model
- Smoothing and Decomposition for Analysis Sparse Recovery
- Constrained Overcomplete Analysis Operator Learning for Cosparse Signal Modelling
- Compressed Sensing with General Frames via Optimal-dual-based -analysis
- High-Dimensional Estimation of Structured Signals from Non-Linear Observations with General Convex Loss Functions
- Robust analysis -recovery from Gaussian measurements and total variation minimization
- Learning Co-Sparse Analysis Operators with Separable Structures
- Sparse Recovery with Coherent Tight Frames via Analysis Dantzig Selector and Analysis LASSO
- Projection onto the Cosparse Set is NP-Hard
Cited by in corpus (10)
- Compressed Sensing with 1D Total Variation: Breaking Sample Complexity Barriers via Non-Uniform Recovery
- New Risk Bounds for 2D Total Variation Denoising
- NESTANets: Stable, accurate and efficient neural networks for analysis-sparse inverse problems
- A Unified Approach to Uniform Signal Recovery From Non-Linear Observations
- DECONET: an Unfolding Network for Analysis-based Compressed Sensing with Generalization Error Bounds
- Spark Deficient Gabor Frame Provides a Novel Analysis Operator for Compressed Sensing
- Robust 1-Bit Compressed Sensing via Hinge Loss Minimization
- Generalization analysis of an unfolding network for analysis-based Compressed Sensing
- Star DGT: a Robust Gabor Transform for Speech Denoising
- Spark Deficient Gabor Frames for Inverse Problems