A Simplified Approach to Recovery Conditions for Low Rank Matrices
Preprint
Abstract
Recovering sparse vectors and low-rank matrices from noisy linear measurements has been the focus of much recent research. Various reconstruction algorithms have been studied, including $\ell_1$ and nuclear norm minimization as well as $\ell_p$ minimization with $p<1$. These algorithms are known to succeed if certain conditions on the measurement map are satisfied. Proofs of robust recovery for matrices have so far been much more involved than in the vector case. In this paper, we show how several robust classes of recovery conditions can be extended from vectors to matrices in a simple and transparent way, leading to the best known restricted isometry and nullspace conditions for matrix recovery. Our results rely on the ability to "vectorize" matrices through the use of a key singular value inequality.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Theory of Compressive Sensing via ℓ 1-Minimization: a Non-RIP Analysis and ExtensionsJournal of the Operations Research Society of China, 2013
- Iteratively reweighted least squares minimization for sparse recoveryCommunications on Pure and Applied Mathematics, 2009
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samplesApplied and Computational Harmonic Analysis, 2009
- Sparsest solutions of underdetermined linear systems via -minimization forApplied and Computational Harmonic Analysis, 2009
- Enhancing Sparsity by Reweighted ℓ 1 MinimizationJournal of Fourier Analysis and Applications, 2008
- Compressed sensing and best 𝑘-term approximationJournal of the American Mathematical Society, 2008
- Restricted isometry properties and nonconvex compressive sensingInverse Problems, 2008
- The restricted isometry property and its implications for compressed sensingComptes Rendus Mathématique, 2008
- Uncertainty principles and ideal atomic decompositionIEEE Transactions on Information Theory, 2001
- Topics in Matrix Analysis1991