改进的RANSAC算法，能同时抗噪声和对抗性干扰。
RANSAC Revisited: An Improved Algorithm for Robust Subspace Recovery under Adversarial and Noisy Corruptions
- 分两阶段设计，修复传统RANSAC在噪声下的弱点
- 在低维子空间恢复中实现近最优样本效率
- 适合高噪声、强对抗干扰场景下的鲁棒建模
本文研究在强对抗性污染和高斯噪声共存情况下的鲁棒子空间恢复（RSR）问题。给定少量含噪声的数据，其中部分被自适应且强对抗性的攻击者篡改，目标是恢复一个低维子空间，使其近似包含大部分未受污染样本，误差与高斯噪声水平成正比。现有方法常因计算开销大或依赖严格分布假设而难以适用于真实对抗环境。为此，我们重新审视经典随机采样一致性（RANSAC）算法，其虽对对抗异常值有强鲁棒性，但牺牲了效率及对高斯噪声和模型误设的鲁棒性。我们提出两阶段算法RANSAC+，精准识别并修正标准RANSAC的失效模式。所提方法在理论上同时抵御高斯噪声与对抗性污染，实现近最优样本复杂度，无需预先知道子空间维度，且比现有RANSAC类方法更高效。
原文摘要 · Abstract (English)
In this paper, we study the problem of robust subspace recovery (RSR) in the presence of both strong adversarial corruptions and Gaussian noise. Specifically, given a limited number of noisy samples -- some of which are tampered by an adaptive and strong adversary -- we aim to recover a low-dimensional subspace that approximately contains a significant fraction of the uncorrupted samples, up to an error that scales with the Gaussian noise. Existing approaches to this problem often suffer from high computational costs or rely on restrictive distributional assumptions, limiting their applicability in truly adversarial settings. To address these challenges, we revisit the classical random sample consensus (RANSAC) algorithm, which offers strong robustness to adversarial outliers, but sacrifices efficiency and robustness against Gaussian noise and model misspecification in the process. We propose a two-stage algorithm, RANSAC+, that precisely pinpoints and remedies the failure modes of standard RANSAC. Our method is provably robust to both Gaussian and adversarial corruptions, achieves near-optimal sample complexity without requiring prior knowledge of the subspace dimension, and is more efficient than existing RANSAC-type methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。