Eldar, Y. C. and Needell, D. and Plan, Y. (2011) Uniqueness conditions for low-rank matrix recovery. In: Wavelets and Sparsity XIV. Proceedings of SPIE. No.8138. Society of Photo-Optical Instrumentation Engineers , Bellingham, WA, Art. No. 81380M. ISBN 978-0-81948-748-3. https://resolver.caltech.edu/CaltechAUTHORS:20161028-132335892
![]() |
PDF
- Published Version
See Usage Policy. 551Kb |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20161028-132335892
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.
Item Type: | Book Section | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| |||||||||
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. | |||||||||
Funders: |
| |||||||||
Subject Keywords: | rank-minimization, nuclear norm minimization, low-rank matrix recovery, random matrices, compressed sensing | |||||||||
Series Name: | Proceedings of SPIE | |||||||||
Issue or Number: | 8138 | |||||||||
Record Number: | CaltechAUTHORS:20161028-132335892 | |||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20161028-132335892 | |||||||||
Official Citation: | Y. C. Eldar ; D. Needell ; Y. Plan; Uniqueness conditions for low-rank matrix recovery. Proc. SPIE 8138, Wavelets and Sparsity XIV, 81380M (September 13, 2011); doi:10.1117/12.891933 | |||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
ID Code: | 71581 | |||||||||
Collection: | CaltechAUTHORS | |||||||||
Deposited By: | Tony Diaz | |||||||||
Deposited On: | 28 Oct 2016 20:32 | |||||||||
Last Modified: | 03 Oct 2019 16:08 |
Repository Staff Only: item control page