Robust Gaussian Covariance Estimation via Nonconvex Optimization

We study the problem of estimating the covariance matrix of a high-dimensional Gaussian distribution when an $ϵ$-fraction of the samples are arbitrarily corrupted. We focus on developing nonconvex formulations that can be optimized using standard first-order methods. We first introduce a new objective function for the one-dimensional setting and prove that every approximate first-order stationary point yields a near-optimal estimate of the true variance. We then extend this objective and its analysis to high dimensions and propose a heuristic algorithm based on a tractable relaxation. We demonstrate empirically that our algorithm achieves performance comparable to that of existing robust covariance estimation algorithms.