One condition for solution uniqueness and robustness of both _1-synthesis and _1-analysis minimizations

DOI10.1007/S10444-016-9467-YzbMATH Open1362.65064arXiv1304.5038OpenAlexW1848983290MaRDI QIDQ2374380FDOQ2374380

Authors: Hui Zhang, Ming Yan, Wotao Yin 

Publication date: 15 December 2016

Published in: Advances in Computational Mathematics (Search for Journal in Brave)

Abstract: The $el{l}_1$-synthesis model and the $el{l}_1$-analysis model recover structured signals from their undersampled measurements. The solution of former is a sparse sum of dictionary atoms, and that of the latter makes sparse correlations with dictionary atoms. This paper addresses the question: when can we trust these models to recover specific signals? We answer the question with a condition that is both necessary and sufficient to guarantee the recovery to be unique and exact and, in presence of measurement noise, to be robust. The condition is one--for--all in the sense that it applies to both of the $el{l}_1$-synthesis and $el{l}_1$-analysis models, to both of their constrained and unconstrained formulations, and to both the exact recovery and robust recovery cases. Furthermore, a convex infinity--norm program is introduced for numerically verifying the condition. A comprehensive comparison with related existing conditions are included.

Full work available at URL: https://arxiv.org/abs/1304.5038

Recommendations

• Necessary and sufficient conditions of solution uniqueness in 1-norm minimization
• \(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed?
• A necessary and sufficient condition for exact sparse recovery by \(\ell_1\) minimization
• Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained \(\ell_1\) minimization
• Sparse phase retrieval via ℓp (0 < p ≤ 1) minimization

zbMATH Keywords

compressive sensingsparse optimizationsparse signal recoveryexact recovery\(\ell_1\)-analysis\(\ell_1\)-synthesisrobust recoveryconvex infinity-norm optimizationdual certificate condition

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cites Work

• Nonlinear total variation based noise removal algorithms
• Local behavior of sparse analysis regularization: applications to risk estimation
• The Lasso problem and uniqueness
• Stable image reconstruction using total variation minimization
• Linear convergence rates for Tikhonov regularization with positively homogeneous functionals
• Necessary and sufficient conditions for linear convergence of \(\ell^1\)-regularization
• Compressed sensing and best \(k\)-term approximation
• A mathematical introduction to compressive sensing
• On Sparse Representations in Arbitrary Redundant Bases
• Recovery of Exact Sparse Representations in the Presence of Bounded Noise
• Greed is Good: Algorithmic Results for Sparse Approximation
• Convergence rates of convex variational regularization
• A Probabilistic and RIPless Theory of Compressed Sensing
• Sparse nonnegative solution of underdetermined linear equations by linear programming
• Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries
• Stable and Robust Sampling Strategies for Compressive Imaging
• The restricted isometry property and its implications for compressed sensing
• The cosparse analysis model and algorithms
• The convex geometry of linear inverse problems
• Analysis versus synthesis in signal priors
• Compressed sensing with coherent and redundant dictionaries
• Analysis \(\ell_1\)-recovery with frames and Gaussian measurements
• Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions
• Remote sensing via \(\ell_1\)-minimization
• Compressed Sensing With General Frames via Optimal-Dual-Based $\ell _{1}$-Analysis
• Necessary and sufficient conditions of solution uniqueness in 1-norm minimization
• Stable Signal Reconstruction via $\ell^1$-Minimization in Redundant, Non-Tight Frames
• On uniqueness guarantees of solution in convex regularized linear inverse problems
• Near-Optimal Compressed Sensing Guarantees for Total Variation Minimization
• Robust analysis ℓ₁-recovery from Gaussian measurements and total variation minimization
• Model selection with low complexity priors

Cited In (18)

• Learning Regularization Parameter-Maps for Variational Image Reconstruction Using Deep Neural Networks and Algorithm Unrolling
• Necessary and sufficient conditions of solution uniqueness in 1-norm minimization
• Cardinality minimization, constraints, and regularization: a survey
• Signal recovery under cumulative coherence
• A null space analysis of the \(\ell_1\)-synthesis method in dictionary-based compressed sensing
• Robust recovery of signals with partially known support information using weighted BPDN
• Performance analysis for unconstrained analysis based approaches
• Analysis vs synthesis with structure -- an investigation of union of subspace models on graphs
• Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained \(\ell_1\) minimization
• The homotopy method revisited: computing solution paths of \(\ell_1\)-regularized problems
• Quadratic growth conditions and uniqueness of optimal solution to Lasso
• Signal recovery under mutual incoherence property and oracle inequalities
• On uniqueness guarantees of solution in convex regularized linear inverse problems
• RIP-based performance guarantee for low-tubal-rank tensor recovery
• On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery
• The Geometry of Sparse Analysis Regularization
• Exact matrix completion based on low rank Hankel structure in the Fourier domain
• Weak stability of \(\ell_1\)-minimization methods in sparse data reconstruction

This page was built for publication: One condition for solution uniqueness and robustness of both \(\ell_1\)-synthesis and \(\ell_1\)-analysis minimizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2374380)