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

DOI10.1016/J.ACHA.2012.07.010MaRDI QIDQ2252129zbMATH OpenOpenAlexFDO

Authors Anru Zhang, T. Tony Cai

Publication date 16 July 2014

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

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

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)

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.

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

Cites work

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

Cited in

(84)

• Characterization of \(\ell_1\) minimizer in one-bit compressed sensing
• Weak stability of \(\ell_1\)-minimization methods in sparse data reconstruction
• A necessary and sufficient condition for sparse vector recovery via \(\ell_1-\ell_2\) minimization
• Sparse model uncertainties in compressed sensing with application to convolutions and sporadic communication
• Nonlinear frames and sparse reconstructions in Banach spaces
• The \( \ell _1 \)-analysis in phase retrieval with redundant dictionary
• On model-based RIP-1 matrices
• Convergence analysis of projected gradient descent for Schatten-\(p\) nonconvex matrix recovery
• A smoothing iterative method for quantile regression with nonconvex \(\ell_p\) penalty
• Sparsest representations and approximations of an underdetermined linear system
• Restricted isometry property for general \(p\)-norms
• Signal recovery under cumulative coherence
• 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
• Stability analysis of a class of sparse optimization problems
• High-order block RIP for nonconvex block-sparse compressed sensing
• Cardinality minimization, constraints, and regularization: a survey
• 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
• Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery
• A tight bound of hard thresholding
• Derandomized compressed sensing with nonuniform guarantees for _1 recovery
• Stable recovery of low-rank matrix via nonconvex Schatten \(p\)-minimization
• Regularization parameter selection for the low rank matrix recovery
• Stable signal recovery from phaseless measurements
• Sparse phase retrieval via ℓp (0 < p ≤ 1) minimization
• A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials
• 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
• Sparse recovery from extreme eigenvalues deviation inequalities
• A new sufficient condition for sparse vector recovery via \(\ell_1\)-\( \ell_2\) local minimization
• Low-rank matrix recovery via regularized nuclear norm minimization
• On the _1-norm invariant convex k-sparse decomposition of signals
• New bounds for RIC in compressed sensing
• Robust signal recovery for \(\ell_{1-2}\) minimization via prior support information
• Compressive sensing of high betweenness centrality nodes in networks
• The finite steps of convergence of the fast thresholding algorithms with \(f\)-feedbacks in compressed sensing
• Perturbation analysis of low-rank matrix stable recovery
• Compressed sensing for real measurements of quaternion signals
• Truncated $l_{1-2}$ Models for Sparse Recovery and Rank Minimization
• Recovery analysis for block \(\ell_p-\ell_1\) minimization with prior support information
• Stable recovery of sparse signals via \(\ell_p\)-minimization
• Stable Recovery of Sparsely Corrupted Signals Through Justice Pursuit De-Noising
• Sparse recovery on Euclidean Jordan algebras
• Optimal RIP bounds for sparse signals recovery via \(\ell_p\) minimization
• Low rank matrix recovery with adversarial sparse noise
• A generalization of Wirtinger flow for exact interferometric inversion
• A non-convex tensor rank approximation for tensor completion
• Stable recovery of signals with the high order D-RIP condition
• A perturbation inequality for concave functions of singular values and its applications in low-rank matrix recovery
• Random sampling and reconstruction of sparse time- and band-limited signals
• On support sizes of restricted isometry constants
• Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods
• Explicit matrices with the restricted isometry property: breaking the square-root bottleneck
• Stable recovery of sparse signals with coherent tight frames via \(l_p\)-analysis approach
• Error bounds for sparse and low-rank matrix approximation based on restricted isometric properties
• ROP: matrix recovery via rank-one projections
• Sparse Recovery via Partial Regularization: Models, Theory, and Algorithms
• Single snapshot DOA estimation by minimizing the fraction function in sparse recovery
• Recovery of low-rank matrices based on the rank null space properties
• Robust signal recovery via \(\ell_{1-2}/ \ell_p\) minimization with partially known support
• A survey on compressive sensing: classical results and recent advancements
• Improved RIP conditions for compressed sensing with coherent tight frames
• Estimation of q for $\ell _{q}$-minimization in signal recovery with tight frame
• Signal recovery under mutual incoherence property and oracle inequalities
• Smoothing Newton method for \(\ell^0\)-\(\ell^2\) regularized linear inverse problem
• Asymptotic analysis for extreme eigenvalues of principal minors of random matrices
• The restricted isometry property for signal recovery with coherent tight frames
• A hierarchical framework for recovery in compressive sensing
• Analysis non-sparse recovery for relaxed ALASSO
• RIP-based performance guarantee for low-tubal-rank tensor recovery
• Guarantees of fast band restricted thresholding algorithm for low-rank matrix recovery problem
• 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
• Discrete uncertainty principles and sparse signal processing
• Truncated sparse approximation property and truncated \(q\)-norm minimization
• Error localization of best \(L_1\) polynomial approximants
• Stable image reconstruction using transformed total variation minimization
• New conditions on stable recovery of weighted sparse signals via weighted l₁ minimization
• Stable recovery of approximately block \(k\)-sparse signals with partial block support information via weighted \(\ell_2/\ell_p\) (\(0 < p \leq 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

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)