We study the problem of estimating the covariance matrix of a
high-dimensional distribution when a small constant fraction of the samples can
be arbitrarily corrupted. Recent work gave the first polynomial time algorithms
for this problem with near-optimal error guarantees for several natural
structured distributions. Our main contribution is to develop faster algorithms
for this problem whose running time nearly matches that of computing the
empirical covariance.
Given $N = \tilde{\Omega}(d^2/\epsilon^2)$ samples from a $d$-dimensional
Gaussian distribution, an $\epsilon$-fraction of which may be arbitrarily
corrupted, our algorithm runs in time
$\tilde{O}(d^{3.26})/\mathrm{poly}(\epsilon)$ and approximates the unknown
covariance matrix to optimal error up to a logarithmic factor. Previous robust
algorithms with comparable error guarantees all have runtimes
$\tilde{\Omega}(d^{2 \omega})$ when $\epsilon = \Omega(1)$, where $\omega$ is
the exponent of matrix multiplication. We also provide evidence that improving
the running time of our algorithm may require new algorithmic techniques.

本文研究了协方差矩阵的估计问题，当仅有小部分样本被恶意更改时，我们提出了一种运行时间接近计算经验协方差且具有最佳误差保证的算法，该算法适用于高维分布，能处理高斯分布等深度分布结构及矩阵乘法指数中的病态情形。

高维稳健协方差估计的快速算法

Faster Algorithms for High-Dimensional Robust Covariance Estimation

We analyse the reconstruction error of principal component analysis (PCA) and
prove non-asymptotic upper bounds for the corresponding excess risk. These
bounds unify and improve existing upper bounds from the literature. In
particular, they give oracle inequalities under mild eigenvalue conditions. The
bounds reveal that the excess risk differs significantly from usually
considered subspace distances based on canonical angles. Our approach relies on
the analysis of empirical spectral projectors combined with concentration
inequalities for weighted empirical covariance operators and empirical
eigenvalues.

文章研究 PCA 的重构误差，并证明了相关超额风险的非渐进上界。这些界限统一并改进了文献中的现有上界。特别地，它们在较小的特征值条件下提供了 oracle 不等式。这些界限揭示了超额风险与基于标准角度的子空间距离有明显差异。我们的方法基于经验谱投影仪的分析，结合加权经验协方差算子和经验特征值的集中不等式。