Analysis of low rank matrix recovery via Mendelson´s small ball method

We study low rank matrix recovery from undersampled measurements via nuclear norm minimization. We aim to recover an n₁ x n₂ matrix X from m measurements (Frobenius inner products) 〈X, A_j〉, j = 1...m. We consider different scenarios of independent random measurement matrices A_j and derive bounds for the minimal number of measurements sufficient to uniformly recover any rank r matrix X with high probability. Our results are stable under passing to only approximately low rank matrices and under noise on the measurements. In the first scenario the entries of the A_j are independent mean zero random variables of variance 1 with bounded fourth moments. Then any X of rank at most r is stably recovered from m measurements with high probability provided that m ≥ Cr max{n₁, n₂}. The second scenario studies the physically important case of rank one measurements. Here, the matrix X to recover is Hermitian of size n × n and the measurement matrices A_j are of the form A_j = a_ja*_j for some random vectors a_j. If the a_j are independent standard Gaussian random vectors, then we obtain uniform stable and robust rank-r recovery with high probability provided that m ≥ crn. Finally we consider the case that the a_j are independently sampled from an (approximate) 4-design. Then we require m ≥ crn log n for uniform stable and robust rank-r recovery. In all cases, the results are shown via establishing a stable and robust version of the rank null space property. To this end, we employ Mendelson´s small ball method.