提出高效算法，实现非高斯椭球分布协方差的近最优鲁棒估计。
Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians
- 基于空间符号协方差估计，结合四次平方和松弛的谱滤波算法。
- 样本量 n=Õ(d²/ε²) 时，误差界为 O(ε log(1/ε))，逼近理论最优。
- 适用于高斯、椭球均匀分布及亚指数尾分布，首次突破高斯限制。
研究高维下椭球分布（即球对称分布的仿射变换）在强污染模型中的高效鲁棒协方差/散度矩阵估计问题，维度 d ≳ 1/ε²，ε 为恶意扰动比例。提出一种算法，在几乎最优样本数 n = Õ(d²/ε²) 下，多项式时间内计算出估计器 Ŝ，使得以高概率满足 ‖Σ⁻¹ᐟ²ŜΣ⁻¹ᐟ² − Id‖_F ≤ O(ε log(1/ε))。作为应用，首次获得可高效计算、近最优的非高斯扩展协方差估计器：对满足 Hanson–Wright 不等式的椭球分布（如高斯、椭球均匀分布），其误差与高斯情形相同；对具有亚指数尾的分布（如多元拉普拉斯），构造出满足谱范数界限 ‖Σ⁻¹ᐟ²ŜΣ⁻¹ᐟ² − Id‖ ≤ O(ε log(1/ε)) 的估计器。方法基于椭球分布空间符号的协方差估计，其中包含一种新颖的谱协方差滤波算法，融合协方差滤波与四次平方和松弛，可能对后续研究有独立价值。
原文摘要 · Abstract (English)
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/\varepsilon^2$, 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 $Σ$, and given a nearly optimal number of samples $n = \tilde{O}(d^2/\varepsilon^2)$, computes in polynomial time an estimator $\hatΣ$ such that, with high probability, \[ \left\| Σ^{-1/2} \hatΣ Σ^{-1/2} - Id \right\|_{\text F} \le 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 $\hatΣ$ of the covariance $Σ$ 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 $\hatΣ$ satisfying the spectral norm bound \[ \left\| Σ^{-1/2} \hatΣ Σ^{-1/2} - Id \right\| \le 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。