^1-analysis minimization and generalized (co-)sparsity: when does recovery succeed?
From MaRDI portal
Publication:2659754
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.
Recommendations
- On the Performance of Sparse Recovery Via \ell_p-Minimization (0 \leq p \leq 1)
- On Recovery of Sparse Signals Via $\ell _{1}$ Minimization
- Sparse Recovery Conditions and Performance Bounds for $\ell _p$-Minimization
- A note on guaranteed sparse recovery via \(\ell_1\)-minimization
- Recovery of high-dimensional sparse signals via \(\ell_1\)-minimization
- A necessary and sufficient condition for exact sparse recovery by \(\ell_1\) minimization
- Selective <inline-formula> <tex-math notation="TeX">$\ell_{1}$</tex-math></inline-formula> Minimization for Sparse Recovery
- A necessary and sufficient condition for sparse vector recovery via \(\ell_1-\ell_2\) minimization
- Analyzing Weighted $\ell_1$ Minimization for Sparse Recovery With Nonuniform Sparse Models
- On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
Cites work
- A mathematical introduction to compressive sensing
- A simple tool for bounding the deviation of random matrices on geometric sets
- A useful theorem for nonlinear devices having Gaussian inputs
- A wavelet tour of signal processing. The sparse way.
- An algorithm for total variation minimization and applications
- An extension of Price's theorem (Corresp.)
- Analysis _1-recovery with frames and Gaussian measurements
- Analysis K-SVD: A Dictionary-Learning Algorithm for the Analysis Sparse Model
- Analysis Operator Learning and its Application to Image Reconstruction
- Analysis versus synthesis in signal priors
- Atomic Decomposition by Basis Pursuit
- Compressed sensing
- Compressed Sensing and Redundant Dictionaries
- Compressed sensing with coherent and redundant dictionaries
- Compressed Sensing With General Frames via Optimal-Dual-Based $\ell _{1}$-Analysis
- Compressive sensing with redundant dictionaries and structured measurements
- Computational and statistical tradeoffs via convex relaxation
- Convex Recovery of a Structured Signal from Independent Random Linear Measurements
- Curvelet-wavelet regularized split Bregman iteration for compressed sensing
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Finite frames. Theory and applications.
- Foundations of machine learning
- Graph implementations for nonsmooth convex programs
- Greedy-like algorithms for the cosparse analysis model
- Guarantees of total variation minimization for signal recovery
- High-Dimensional Estimation of Structured Signals From Non-Linear Observations With General Convex Loss Functions
- High-dimensional probability. An introduction with applications in data science
- scientific article; zbMATH DE number 4061904 (Why is no real title available?)
- scientific article; zbMATH DE number 1324223 (Why is no real title available?)
- scientific article; zbMATH DE number 802858 (Why is no real title available?)
- scientific article; zbMATH DE number 1391397 (Why is no real title available?)
- scientific article; zbMATH DE number 3365044 (Why is no real title available?)
- Ideal spatial adaptation by wavelet shrinkage
- Insights Into Analysis Operator Learning: From Patch-Based Sparse Models to Higher Order MRFs
- Intrinsic localization of frames
- Learning Sparsifying Transforms
- Least squares problems with inequality constraints as quadratic constraints
- Living on the edge: phase transitions in convex programs with random data
- Localization of frames, Banach frames, and the invertibility of the frame operator
- Multi-layer sparse coding: the holistic way
- Nonlinear total variation based noise removal algorithms
- On sparse reconstruction from Fourier and Gaussian measurements
- On the Effective Measure of Dimension in the Analysis Cosparse Model
- Physics-Driven Inverse Problems Made Tractable With Cosparse Regularization
- Reconstruction and subgaussian operators in asymptotic geometric analysis
- Recovering Compressively Sampled Signals Using Partial Support Information
- Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach
- Robust analysis ℓ1-recovery from Gaussian measurements and total variation minimization
- Robust Sparse Analysis Regularization
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Sampling Theorems for Signals From the Union of Finite-Dimensional Linear Subspaces
- Sharp MSE bounds for proximal denoising
- Sharp Time–Data Tradeoffs for Linear Inverse Problems
- ShearLab 3D: faithful digital shearlet transforms based on compactly supported shearlets
- Smoothing and Decomposition for Analysis Sparse Recovery
- Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO
- Sparsity and nullity: paradigms for analysis dictionary learning
- Split Bregman methods and frame based image restoration
- Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries
- Stable image reconstruction using total variation minimization
- Stable recovery of analysis based approaches
- Stable signal recovery from incomplete and inaccurate measurements
- Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames
- The convex geometry of linear inverse problems
- The cosparse analysis model and algorithms
- Tradeoffs Between Convergence Speed and Reconstruction Accuracy in Inverse Problems
- Understanding machine learning. From theory to algorithms
- Unified Theory for Recovery of Sparse Signals in a General Transform Domain
- Wavelet footprints: theory, algorithms, and applications
Cited in
(23)- A general version of Price's theorem. A tool for bounding the expectation of nonlinear functions of Gaussian random vectors
- One condition for solution uniqueness and robustness of both _1-synthesis and _1-analysis minimizations
- Greedy-like algorithms for the cosparse analysis model
- NESTANets: stable, accurate and efficient neural networks for analysis-sparse inverse problems
- What is the Largest Sparsity Pattern That Can Be Recovered by 1-Norm Minimization?
- On oracle-type local recovery guarantees in compressed sensing
- Performance analysis for unconstrained analysis based approaches
- A modified greedy analysis pursuit algorithm for the cosparse analysis model
- Image reconstruction using analysis model prior
- Performance bounds for co-/sparse box constrained signal recovery
- On the convergence rate of projected gradient descent for a back-projection based objective
- Compressed data separation via unconstrained l1-split analysis
- Star DGT: a robust Gabor transform for speech denoising
- A unified approach to uniform signal recovery from nonlinear observations
- Tight-frame-like analysis-sparse recovery using nontight sensing matrices
- Sparse recovery with coherent frames via \(\ell_{1-2}\)-analysis
- Compressed data separation via \(\ell_q\)-split analysis with \(\ell_\infty\)-constraint
- Compressed sensing with frames and sparsity in levels class
- Theory and fast learned solver for ^1-TV regularization
- Convergence on thresholding-based algorithms for dictionary-sparse recovery
- Near-optimal tensor recovery guarantees for transformed total variation minimization
- Generalization analysis of an unfolding network for analysis-based compressed sensing
- Analysis _1-recovery with frames and Gaussian measurements
Describes a project that uses
Uses Software
This page was built for publication: \(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2659754)
