13 September 2011 Uniqueness conditions for low-rank matrix recovery
Author Affiliations +
Abstract
Low-rank matrix recovery addresses the problem of recovering an unknown low-rank matrix from few linear measurements. Nuclear-norm minimization is a tractable approach with a recent surge of strong theoretical backing. Analagous to the theory of compressed sensing, these results have required random measurements. For example, m ≥ Cnr Gaussian measurements are sufficient to recover any rank-r n x n matrix with high probability. In this paper we address the theoretical question of how many measurements are needed via any method whatsoever - tractable or not. We show that for a family of random measurement ensembles, m ≥ 4nr-4r2 measurements are sufficient to guarantee that no rank-2r matrix lies in the null space of the measurement operator with probability one. This is a necessary and sufficient condition to ensure uniform recovery of all rank-r matrices by rank minimization. Furthermore, this value of m precisely matches the dimension of the manifold of all rank-2r matrices. We also prove that for a fixed rank-r matrix, m ≥ 2nr - r2 + 1 random measurements are enough to guarantee recovery using rank minimization. These results give a benchmark to which we may compare the efficacy of nuclear-norm minimization.
© (2011) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Y. C. Eldar, Y. C. Eldar, D. Needell, D. Needell, Y. Plan, Y. Plan, } "Uniqueness conditions for low-rank matrix recovery", Proc. SPIE 8138, Wavelets and Sparsity XIV, 81380M (13 September 2011); doi: 10.1117/12.891933; https://doi.org/10.1117/12.891933
PROCEEDINGS
9 PAGES


SHARE
RELATED CONTENT

Local hub screening in sparse correlation graphs
Proceedings of SPIE (September 27 2013)
Wavelets and multiresolution analysis on sphere-like surfaces
Proceedings of SPIE (September 01 1995)
Localized frames and localizable operators
Proceedings of SPIE (September 20 2007)
Minimal-window time-frequency distributions
Proceedings of SPIE (November 02 1999)
Deterministic matrices with the restricted isometry property
Proceedings of SPIE (September 27 2011)

Back to Top