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

\(\ell_1\) minimizationcompressed sensingDantzig selectorlow-rank matrix recoverynuclear norm minimizationrestricted isometrysparse signal recovery

Mathematics Subject Classification ID

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

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 overcomplete representations in the presence of noise
• Stable Recovery of Sparse Signals and an Oracle Inequality
• Stable signal recovery from incomplete and inaccurate measurements
• The bounds of restricted isometry constants for low rank matrices recovery
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• 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

(95)

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

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)