Sharp RIP bound for sparse signal and low-rank matrix recovery

DOI10.1016/J.ACHA.2012.07.010zbMATH Open1310.94021arXiv1302.1236OpenAlexW1967357291MaRDI QIDQ2252129FDOQ2252129

Authors: Anru Zhang, T. Tony Cai 

Publication date: 16 July 2014

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Abstract: This paper establishes a sharp condition on the restricted isometry property (RIP) for both the sparse signal recovery and low-rank matrix recovery. It is shown that if the measurement matrix $A$ satisfies the RIP condition $delt{a}_k^A<1/3$, then all $k$-sparse signals $$ can be recovered exactly via the constrained $el{l}_1$ minimization based on $$. Similarly, if the linear map $calM$ satisfies the RIP condition $delt{a}_r^{calM}<1/3$, then all matrices $X$ of rank at most $r$ can be recovered exactly via the constrained nuclear norm minimization based on $b=calM(X)$. Furthermore, in both cases it is not possible to do so in general when the condition does not hold. In addition, noisy cases are considered and oracle inequalities are given under the sharp RIP condition.

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

Recommendations

• Optimal RIP bounds for sparse signals recovery via \(\ell_p\) minimization
• The restricted isometry property and its implications for compressed sensing
• Stable recovery of signals with the high order D-RIP condition
• A sharp RIP condition for orthogonal matching pursuit
• On model-based RIP-1 matrices

zbMATH Keywords

compressed sensinglow-rank matrix recoveryDantzig selector\(\ell_1\) minimizationnuclear norm minimizationsparse signal recoveryrestricted isometry

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Nonlinear programming (90C30) Ill-posedness and regularization problems in numerical linear algebra (65F22)

Cites Work

• Nearly unbiased variable selection under minimax concave penalty
• Ideal spatial adaptation by wavelet shrinkage
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• Decoding by Linear Programming
• Stable recovery of sparse overcomplete representations in the presence of noise
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Stable signal recovery from incomplete and inaccurate measurements
• Compressed sensing
• Uncertainty principles and ideal atomic decomposition
• Restricted Isometry Constants Where $\ell ^{p}$ Sparse Recovery Can Fail for $0≪ p \leq 1$
• The restricted isometry property and its implications for compressed sensing
• Shifting Inequality and Recovery of Sparse Signals
• New Bounds for Restricted Isometry Constants
• Sharp MSE bounds for proximal denoising
• New bounds on the restricted isometry constant \(\delta _{2k}\)
• On Recovery of Sparse Signals Via $\ell _{1}$ Minimization
• Stable Recovery of Sparse Signals and an Oracle Inequality
• The bounds of restricted isometry constants for low rank matrices recovery

Cited In (76)

• A new sufficient condition for sparse vector recovery via ℓ1 − ℓ2 local minimization
• Recovery analysis for block ℓp − ℓ1 minimization with prior support information
• Low rank matrix recovery with adversarial sparse noise*
• THE RESTRICTED ISOMETRY PROPERTY FOR SIGNAL RECOVERY WITH COHERENT TIGHT FRAMES
• A Generalization of Wirtinger Flow for Exact Interferometric Inversion
• Robust signal recovery for ℓ _1–2 minimization via prior support information
• High-order block RIP for nonconvex block-sparse compressed sensing
• Cardinality minimization, constraints, and regularization: a survey
• Stable recovery of sparse signals with coherent tight frames via lp-analysis approach
• Stable Recovery of Sparsely Corrupted Signals Through Justice Pursuit De-Noising
• Robust signal recovery via \(\ell_{1-2}/ \ell_p\) minimization with partially known support
• Estimation of q for $\ell _{q}$-minimization in signal recovery with tight frame
• Guarantees of fast band restricted thresholding algorithm for low-rank matrix recovery problem
• Stable recovery of approximately block \(k\)-sparse signals with partial block support information via weighted \(\ell_2/\ell_p\) (\(0 < p \leq 1\)) minimization
• Explicit Matrices with the Restricted Isometry Property: Breaking the Square-Root Bottleneck
• Nonlinear frames and sparse reconstructions in Banach spaces
• The \( \ell _1 \)-analysis in phase retrieval with redundant dictionary
• Convergence analysis of projected gradient descent for Schatten-\(p\) nonconvex matrix recovery
• Sparsest representations and approximations of an underdetermined linear system
• A smoothing iterative method for quantile regression with nonconvex \(\ell_p\) penalty
• Random Sampling and Reconstruction of Sparse Time- and Band-Limited Signals
• Signal recovery under cumulative coherence
• Stability analysis of a class of sparse optimization problems
• Sparse recovery in probability via \(l_q\)-minimization with Weibull random matrices for \(0 < q\leq 1\)
• Robust sparse recovery via a novel convex model
• On the Schatten \(p\)-quasi-norm minimization for low-rank matrix recovery
• Stable recovery of low-dimensional cones in Hilbert spaces: one RIP to rule them all
• Stable recovery of low-rank matrix via nonconvex Schatten \(p\)-minimization
• Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery
• Regularization parameter selection for the low rank matrix recovery
• Sparse Model Uncertainties in Compressed Sensing with Application to Convolutions and Sporadic Communication
• Sparse phase retrieval via ℓp (0 < p ≤ 1) minimization
• A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials
• Stable signal recovery from phaseless measurements
• A null-space-based weightedl₁minimization approach to compressed sensing
• Stable restoration and separation of approximately sparse signals
• Convergence of projected Landweber iteration for matrix rank minimization
• Optimal \(D\)-RIP bounds in compressed sensing
• Low-rank matrix recovery via regularized nuclear norm minimization
• On the \(\ell_1\)-norm invariant convex \(k\)-sparse decomposition of signals
• New bounds for RIC in compressed sensing
• Compressive sensing of high betweenness centrality nodes in networks
• Perturbation analysis of low-rank matrix stable recovery
• The finite steps of convergence of the fast thresholding algorithms with \(f\)-feedbacks in compressed sensing
• Compressed sensing for real measurements of quaternion signals
• Truncated $l_{1-2}$ Models for Sparse Recovery and Rank Minimization
• Optimal RIP bounds for sparse signals recovery via \(\ell_p\) minimization
• Error Localization of Best $L_{1}$ Polynomial Approximants
• Stable Image Reconstruction Using Transformed Total Variation Minimization
• Stable recovery of sparse signals via \(\ell_p\)-minimization
• A non-convex tensor rank approximation for tensor completion
• Weak Stability of ℓ₁-Minimization Methods in Sparse Data Reconstruction
• A perturbation inequality for concave functions of singular values and its applications in low-rank matrix recovery
• Characterization of ℓ1 minimizer in one-bit compressed sensing
• On support sizes of restricted isometry constants
• Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods
• ROP: matrix recovery via rank-one projections
• Sparse Recovery via Partial Regularization: Models, Theory, and Algorithms
• Recovery of low-rank matrices based on the rank null space properties
• Single snapshot DOA estimation by minimizing the fraction function in sparse recovery
• A survey on compressive sensing: classical results and recent advancements
• Improved RIP conditions for compressed sensing with coherent tight frames
• Smoothing Newton method for \(\ell^0\)-\(\ell^2\) regularized linear inverse problem
• Asymptotic analysis for extreme eigenvalues of principal minors of random matrices
• A Tight Bound of Hard Thresholding
• A hierarchical framework for recovery in compressive sensing
• RIP-based performance guarantee for low-tubal-rank tensor recovery
• On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels
• A note on block-sparse signal recovery with coherent tight frames
• Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery
• Truncated sparse approximation property and truncated \(q\)-norm minimization
• Discrete uncertainty principles and sparse signal processing
• New conditions on stable recovery of weighted sparse signals via weighted \(l_1\) minimization
• Recovery of signals under the condition on RIC and ROC via prior support information
• Sparse signal reconstruction based on multiparameter approximation function with smoothed \(\ell_0\) norm
• A necessary and sufficient condition for sparse vector recovery via \(\ell_1-\ell_2\) minimization

This page was built for publication: Sharp RIP bound for sparse signal and low-rank matrix recovery

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