用随机投影+鲁棒统计法，一通扫描就剔除异常行并恢复低秩结构
Robust Randomized Low-Rank Approximation with Row-Wise Outlier Detection
- 先用随机投影降维，保留正常数据几何特征
- 通过中位数和中位绝对偏差识别异常行，去除率超80%仍有效
- 单次遍历完成，适合海量数据，对恶意行干扰鲁棒
在行级对抗性污染下实现鲁棒低秩逼近可通过单次遍历的随机化方法完成，该方法通过阈值化投影范数检测并移除异常行。我们提出一种可扩展的非迭代算法，在存在行级对抗性污染时高效恢复底层低秩结构。首先利用Johnson-Lindenstrauss投影压缩数据，保持干净行的几何特性同时大幅降低维度。基于中位数和中位绝对偏差的鲁棒统计技术，可精确识别并移除具有异常高范数的异常行。后续的rank-k近似在单次遍历中达到近最优误差界，计算复杂度与样本数量线性相关。实证结果表明，将随机投影与鲁棒统计结合，即使在大量行被污染的情况下，也能实现高效且准确的分解。
原文摘要 · Abstract (English)
Robust low-rank approximation under row-wise adversarial corruption can be achieved with a single pass, randomized procedure that detects and removes outlier rows by thresholding their projected norms. We propose a scalable, non-iterative algorithm that efficiently recovers the underlying low-rank structure in the presence of row-wise adversarial corruption. By first compressing the data with a Johnson Lindenstrauss projection, our approach preserves the geometry of clean rows while dramatically reducing dimensionality. Robust statistical techniques based on the median and median absolute deviation then enable precise identification and removal of outlier rows with abnormally high norms. The subsequent rank-k approximation achieves near-optimal error bounds with a one pass procedure that scales linearly with the number of observations. Empirical results confirm that combining random sketches with robust statistics yields efficient, accurate decompositions even in the presence of large fractions of corrupted rows.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。