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.