
Proceedings Paper
Uniqueness conditions for low-rank matrix recoveryFormat | Member Price | Non-Member Price |
---|---|---|
$17.00 | $21.00 |
Paper 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.
Paper Details
Date Published: 13 September 2011
PDF: 9 pages
Proc. SPIE 8138, Wavelets and Sparsity XIV, 81380M (13 September 2011); doi: 10.1117/12.891933
Published in SPIE Proceedings Vol. 8138:
Wavelets and Sparsity XIV
Manos Papadakis; Dimitri Van De Ville; Vivek K. Goyal, Editor(s)
PDF: 9 pages
Proc. SPIE 8138, Wavelets and Sparsity XIV, 81380M (13 September 2011); doi: 10.1117/12.891933
Show Author Affiliations
Y. C. Eldar, Technion-Israel Institute of Technology (Israel)
D. Needell, Stanford Univ. (United States)
D. Needell, Stanford Univ. (United States)
Y. Plan, California Institute of Technology (United States)
Published in SPIE Proceedings Vol. 8138:
Wavelets and Sparsity XIV
Manos Papadakis; Dimitri Van De Ville; Vivek K. Goyal, Editor(s)
© SPIE. Terms of Use
