Compressed Sensing and Affine Rank Minimization under Restricted Isometry

Abstract

This paper establishes new restricted isometry conditions for compressed sensing and affine rank minimization. It is shown for compressed sensing that ${\delta }_k^A+{\theta }_{k,k}^A<1$ guarantees the exact recovery of all $k$ sparse signals in the noiseless case through the constrained ${\ell }_1$ minimization. Furthermore, the upper bound 1 is sharp in the sense that for any $\epsilon >0$, the condition ${\delta }_k^A+{\theta }_{k,k}^A<1+\epsilon$ is not sufficient to guarantee such exact recovery using any recovery method. Similarly, for affine rank minimization, if ${\delta }_r^{\mathcal{M}}+{\theta }_{r,r}^{\mathcal{M}}<1$ then all matrices with rank at most $r$ can be reconstructed exactly in the noiseless case via the constrained nuclear norm minimization; and for any $\epsilon >0$, ${\delta }_r^{\mathcal{M}}+{\theta }_{r,r}^{\mathcal{M}}<1+\epsilon$ does not ensure such exact recovery using any method. Moreover, in the noisy case the conditions ${\delta }_k^A+{\theta }_{k,k}^A<1$ and ${\delta }_r^{\mathcal{M}}+{\theta }_{r,r}^{\mathcal{M}}<1$ are also sufficient for the stable recovery of sparse signals and low-rank matrices respectively. Applications and extensions are also discussed.

to appear in IEEE Transactions on Signal Processing

Cited by in corpus (9)

• An overview of low-rank matrix recovery from incomplete observations
• $L_{1/2}$ Regularization: Convergence of Iterative Half Thresholding Algorithm
• ROP: Matrix recovery via rank-one projections
• Leveraging the Restricted Isometry Property: Improved Low-Rank Subspace Decomposition for Hybrid Millimeter-Wave Systems
• Improved Analyses for SP and CoSaMP Algorithms in Terms of Restricted Isometry Constants
• Signal Recovery under Cumulative Coherence
• Recovery of signals under the high order RIP condition via prior support information
• Density matrix and fidelity estimation of multiphoton entanglement via phaselift
• On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization