Uniqueness conditions for low-rank matrix recovery

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-r n×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.