Uniqueness conditions for low-rank matrix recovery
- Creators
- Eldar, Y. C.
- Needell, D.
- Plan, Y.
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-4r^2 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 – r^2 + 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.
Additional Information
© 2011 SPIE. We would like to thank Boris Bertman and Rohit Thomas for thoughtful discussions. This work was partially supported by the NSF DMS EMSW21-VIGRE grant.Attached Files
Published - 81380M_1.pdf
Files
Name | Size | Download all |
---|---|---|
md5:eca1a196846ce0276671f711e8583861
|
564.3 kB | Preview Download |
Additional details
- Eprint ID
- 71581
- Resolver ID
- CaltechAUTHORS:20161028-132335892
- EMSW21-VIGRE
- NSF
- Created
-
2016-10-28Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field
- Series Name
- Proceedings of SPIE
- Series Volume or Issue Number
- 8138