  We study the recovery of Hermitian low rank matrices $X \in \mathbb{C}^{n
\times 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 $a_j a_j^*$ for some
measurement vectors $a_1,...,a_m$, i.e., the measurements are given by $y_j =
\mathrm{tr}(X a_j a_j^*)$. The case where the matrix $X=x x^*$ to be recovered
is of rank one reduces to the problem of phaseless estimation (from
measurements, $y_j = |\langle x,a_j\rangle|^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 $a_j$, $j=1,...,m$, being chosen independently
at random according to a standard Gaussian distribution, or $a_j$ being sampled
independently from an (approximate) complex projective $t$-design with $t=4$.
In the Gaussian case, we require $m \geq C r n$ measurements, while in the case
of $4$-designs we need $m \geq Cr n \log(n)$. Our results are uniform in the
sense that one random choice of the measurement vectors $a_j$ 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, Kueng and Krahmer. 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.
