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

Abstract

The ${\ell }_1$-synthesis model and the ${\ell }_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 ${\ell }_1$-synthesis and ${\ell }_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.

15 pages, 0 figures

References in corpus (5)

• Near-optimal compressed sensing guarantees for total variation minimization
• Necessary and sufficient conditions of solution uniqueness in ${\ell }_1$ minimization
• Robust analysis ${\ell }_1$-recovery from Gaussian measurements and total variation minimization
• Stable Recovery with Analysis Decomposable Priors
• Analysis ${\ell }_1$-recovery with frames and Gaussian measurements

Cited by in corpus (14)

• Testable uniqueness conditions for empirical assessment of undersampling levels in total variation-regularized x-ray CT
• Signal Recovery under Cumulative Coherence
• Joint Inference of Multiple Graphs from Matrix Polynomials
• Joint Network Topology Inference in the Presence of Hidden Nodes
• Basis Pursuit and Orthogonal Matching Pursuit for Subspace-preserving Recovery: Theoretical Analysis
• On the Q-linear convergence of forward-backward splitting method and uniqueness of optimal solution to Lasso
• Blind Identification of Invertible Graph Filters with Multiple Sparse Inputs
• RIP-based performance guarantee for low-tubal-rank tensor recovery
• Exact matrix completion based on low rank Hankel structure in the Fourier domain
• On robust width property for Lasso and Dantzig selector
• Restricted $q$-Isometry Properties Adapted to Frames for Nonconvex $l_q$-Analysis
• Weak Stability of ${\ell }_1$-minimization Methods in Sparse Data Reconstruction
• Deterministic Analysis of Weighted BPDN With Partially Known Support Information
• Estimating Network Processes via Blind Identification of Multiple Graph Filters