Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians

We study the problem of \emph{computationally efficient} robust estimation of the covariance/scatter matrix of elliptical distributions---that is, affine transformations of spherically symmetric distributions---under the \emph{strong contamination model} in the high-dimensional regime $d \gtrsim 1/\varepsilon^2$, where $d$ is the dimension and $\varepsilon$ is the fraction of adversarial corruptions. We show that the structure inherent to elliptical distributions enables us to achieve estimation guarantees comparable to those known for the Gaussian case. We propose an algorithm that, under a {very mild assumption} on the effective rank of the scatter matrix $\Sigma$, and given a nearly optimal number of samples $n = \tilde{O}(d^2/\varepsilon^2)$, computes in polynomial time an estimator $\hat{\Sigma}$ satisfying $ \left\Vert \Sigma^{-1/2} \hat{\Sigma} \Sigma^{-1/2} - Id \right\Vert_{\text{F}} \le O(\varepsilon \log(1/\varepsilon)) . $ This matches the best known guarantees for the Gaussian setting. As an application of our result, we obtain \emph{efficiently computable, nearly optimal robust covariance estimators}, significantly generalizing prior results that were restricted to the Gaussian case or required, in particular, matching the Gaussian fourth moment. Specifically, for elliptical distributions satisfying the Hanson--Wright inequality (including Gaussians, uniform distributions over ellipsoids, and more generally elliptical distributions with Gaussian-type radial concentration), our estimator $\hat{\Sigma}$ 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), our covariance estimator $\hat{\Sigma}$ satisfies the spectral norm bound $ \left\Vert \Sigma^{-1/2} \hat{\Sigma} \Sigma^{-1/2} - Id \right\Vert \le O(\varepsilon \log(1/\varepsilon)) . $ Remarkably, despite the heavier tails of such distributions, the covariance can still be estimated at the same rate as in the Gaussian case---a phenomenon unique to high dimensions and absent in low-dimensional settings. Our approach is based on estimating the covariance of the \emph{spatial sign} (i.e., the projection onto the sphere) of elliptical distributions. As part of our framework, we develop a generalization of the standard covariance filtering algorithm that allows us to work with distributions whose fourth moment differs from that of the Gaussian distribution.