Outlier-robust recovery of low-rank positive semidefinite matrices from magnitude measurements

Abstract

We address the problem of estimating a low-rank positive semidefinite (PSD) matrix from a set of magnitude measurements that are quadratic in the sensing vectors in the presence of arbitrary outliers. We propose a parameter-free algorithm that seeks the PSD matrix that minimizes the ℓ1-norm of the measurement residual. It is shown that the algorithm can exactly recover a rank-r PSD matrix of size-n from O (nr2) measurements with high probability, even when a fraction of the measurements is corrupted by arbitrary outliers. Furthermore, the recovery is also robust to bounded noise. When an upper bound of the rank of the PSD matrix is known a priori, we further propose a non-convex algorithm based on subgradient descent that demonstrates superior empirical performance.