Robust Mean Estimation in High Dimensions: An Outlier Fraction Agnostic and Efficient Algorithm
Robust Mean Estimation in High Dimensions: An Outlier Fraction Agnostic and Efficient Algorithm
复制标题
DOI：
10.1109/isit50566.2022.9834585
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Aditya Deshmukh;Jing Liu;V. Veeravalli
中科院分区：
文献类型：
--
作者：
Aditya Deshmukh;Jing Liu;V. Veeravalli
研究了高维数据点的鲁棒均值估计问题，其中一定比例（小于一半）的数据点可能被任意破坏。在压缩感知的激励下，鲁棒均值估计问题被表述为在数据点的第二矩约束下，离群指标向量的l0 -范数的最小化。然后将l0 -范数放宽为目标中的lp -范数（0 < p≤1），并证明了对于鲁棒均值估计问题，这些目标的全局最小值都是阶最优的，并且具有最优的崩溃点。此外，提出了一种计算上易于处理的迭代最小化和硬阈值算法，该算法输出总体均值的阶最优鲁棒估计。与大多数现有算法相比，所提出的算法（击破点≈0.3）不需要先验知识，并且对于p = 1具有近似线性的时间复杂度。合成和实际数据实验表明，该算法优于最先进的鲁棒均值估计方法。
The problem of robust mean estimation in high dimensions is studied, in which a certain fraction (less than half) of the datapoints can be arbitrarily corrupted. Motivated by compressive sensing, the robust mean estimation problem is formulated as the minimization of the ℓ0-‘norm’ of an outlier indicator vector, under a second moment constraint on the datapoints. The ℓ0-‘norm’ is then relaxed to the ℓp-norm (0 < p ≤ 1) in the objective, and it is shown that the global minima for each of these objectives are order-optimal and have optimal breakdown point for the robust mean estimation problem. Furthermore, a computationally tractable iterative ℓp-minimization and hard thresholding algorithm is proposed that outputs an order-optimal robust estimate of the population mean. The proposed algorithm (with breakdown point ≈0.3) does not require prior knowledge of the fraction of outliers, in contrast with most existing algorithms, and for p = 1 it has near-linear time complexity. Both synthetic and real data experiments demonstrate that the proposed algorithm outperforms state-of-the-art robust mean estimation methods.