Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians

We study the problem of computationally efficient robust estimation of the covariance/scatter matrix of elliptical distributions -- that is, affine transformations of spherically symmetric distributions -- under the strong contamination model in the high-dimensional regime d gtrsim 1/varepsilon2, where d is the dimension and varepsilon is the fraction of adversarial corruptions. We propose an algorithm that, under a very mild assumption on the scatter matrix Sigma, and given a nearly optimal number of samples n = tildeO(d2/varepsilon2), computes in polynomial time an estimator hatSigma such that, with high probability, [ left| Sigma-1/2 hatSigma Sigma-1/2 - Id right|text F ≤ O(varepsilon log(1/varepsilon)),. ] As an application of our result, we obtain the first efficiently computable, nearly optimal robust covariance estimators that extend beyond the Gaussian case. Specifically, for elliptical distributions satisfying the Hanson--Wright inequality (such as Gaussians and uniform distributions over ellipsoids), our estimator hatSigma of the covariance Sigma achieves the same error guarantee as in the Gaussian case. Moreover, for elliptical distributions with sub-exponential tails (such as the multivariate Laplace distribution), we construct an estimator hatSigma satisfying the spectral norm bound [ left| Sigma-1/2 hatSigma Sigma-1/2 - Id right| ≤ O(varepsilon log(1/varepsilon)),. ] Our approach is based on estimating the covariance of the spatial sign of elliptical distributions. The estimation proceeds in several stages, one of which involves a novel spectral covariance filtering algorithm. This algorithm combines covariance filtering techniques with degree-4 sum-of-squares relaxations, and we believe it may be of independent interest for future applications.