13 September 2011 Uniqueness conditions for low-rank matrix recovery
Author Affiliations +
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


Compressed sensing of autoregressive processes
Proceedings of SPIE (September 04 2009)
Grassmannians in frame theory
Proceedings of SPIE (September 30 2011)
Deterministic matrices with the restricted isometry property
Proceedings of SPIE (September 27 2011)

Back to Top