  We study the problem of estimating a low-rank positive semidefinite (PSD)
matrix from a set of rank-one measurements using sensing vectors composed of
i.i.d. standard Gaussian entries, which are possibly corrupted by arbitrary
outliers. This problem arises from applications such as phase retrieval,
covariance sketching, quantum space tomography, and power spectrum estimation.
We first propose a convex optimization algorithm that seeks the PSD matrix with
the minimum $\ell_1$-norm of the observation residual. The advantage of our
algorithm is that it is free of parameters, therefore eliminating the need for
tuning parameters and allowing easy implementations. We establish that with
high probability, a low-rank PSD matrix can be exactly recovered as soon as the
number of measurements is large enough, even when a fraction of the
measurements are corrupted by outliers with arbitrary magnitudes. Moreover, the
recovery is also stable against bounded noise. With the additional information
of an upper bound of the rank of the PSD matrix, we propose another non-convex
algorithm based on subgradient descent that demonstrates excellent empirical
performance in terms of computational efficiency and accuracy.
