Low rank matrix recovery from rank one measurements

We study the recovery of Hermitian low rank matrices X∈Cn×n from undersampled measurements via nuclear norm minimization. We consider the particular scenario where the measurements are Frobenius inner products with random rank-one matrices of the form ajaj⁎ for some measurement vectors a1,…,am, i.e., the measurements are given by bj=tr(Xajaj⁎). The case where the matrix X=xx⁎ to be recovered is of rank one reduces to the problem of phaseless estimation (from measurements bj=|〈x,aj〉|2) via the PhaseLift approach, which has been introduced recently. We derive bounds for the number m of measurements that guarantee successful uniform recovery of Hermitian rank r matrices, either for the vectors aj, j=1,…,m, being chosen independently at random according to a standard Gaussian distribution, or aj being sampled independently from an (approximate) complex projective t-design with t=4. In the Gaussian case, we require m≥Crn measurements, while in the case of 4-designs we need m≥Crnlog⁡(n). Our results are uniform in the sense that one random choice of the measurement vectors aj guarantees recovery of all rank r-matrices simultaneously with high probability. Moreover, we prove robustness of recovery under perturbation of the measurements by noise. The result for approximate 4-designs generalizes and improves a recent bound on phase retrieval due to Gross, Krahmer and Kueng. In addition, it has applications in quantum state tomography. Our proofs employ the so-called bowling scheme which is based on recent ideas by Mendelson and Koltchinskii.