Affordable Access

Publisher Website

Uniqueness conditions for low-rank matrix recovery

Authors
Publisher
Elsevier Inc.
Volume
33
Issue
2
Identifiers
DOI: 10.1016/j.acha.2012.04.002
Keywords
  • Rank Minimization
  • Nuclear-Norm Minimization
  • Low-Rank Matrix Recovery
  • Random Matrices
  • Compressed Sensing

Abstract

Abstract Low-rank matrix recovery addresses the problem of recovering an unknown low-rank matrix from few linear measurements. There has been a large influx of literature deriving conditions under which certain tractable methods will succeed in recovery, demonstrating that m⩾Cnr Gaussian measurements are often sufficient to recover any rank-rn×n matrix. 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 and m⩾2nr−r2+1 measurements are sufficient to guarantee strong recovery and weak recovery, respectively, by rank minimization. These results give a benchmark to which we may compare the efficacy of tractable methods such as nuclear-norm minimization.

There are no comments yet on this publication. Be the first to share your thoughts.