Uniqueness conditions for low-rank matrix recovery

Y. C. Eldar; D. Needell; Y. Plan

doi:10.1117/12.891933

13 September 2011 Uniqueness conditions for low-rank matrix recovery

Y. C. Eldar, D. Needell, Y. Plan

Proceedings Volume 8138, Wavelets and Sparsity XIV; 81380M (2011) https://doi.org/10.1117/12.891933
Event: SPIE Optical Engineering + Applications, 2011, San Diego, California, United States

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² 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² + 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.

Citation Download Citation

Y. C. Eldar, D. Needell, and Y. Plan "Uniqueness conditions for low-rank matrix recovery", Proc. SPIE 8138, Wavelets and Sparsity XIV, 81380M (13 September 2011); https://doi.org/10.1117/12.891933

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available