揭示了鲁棒子空间恢复在临界点的精确行为，证明算法在信号噪声比≥1时能准确收敛。
The Sharp Phase Transition of Tyler's M-Estimator for Robust Subspace Recovery
- 基于新稳定性条件，分析泰勒M估计器的迭代过程
- 在DS-SNR≥1时，算法可精确收敛至真实子空间
- 突破传统假设限制，适用于更广泛的数据场景
鲁棒子空间恢复（RSR）旨在从严重受异常值污染的数据集中识别出一个d维底层子空间。复杂性理论表明，问题的计算难度取决于维度归一化信噪比（DS-SNR）：当DS-SNR严格小于1时，问题为SSE-hard；当大于1时，在一般位置假设下可通过实用算法解决。然而，现有方法在临界点DS-SNR=1处的表现仍不明确。本文首次解析了泰勒M估计器（TME）在该临界边界的行为，确立了尖锐相变。具体而言，我们证明在新稳定性条件下，当DS-SNR≥1时，TME可精确收敛至真实子空间，且该条件比以往文献中的一般位置假设更宽松。分析基于主要化-最小化框架下的TME迭代分解。
原文摘要 · Abstract (English)
Robust Subspace Recovery (RSR) aims to identify an underlying d-dimensional subspace from a dataset heavily corrupted by outliers. Complexity-theoretic results establish a threshold for the problem's computational hardness based on the dimension-scaled signal-to-noise ratio (DS-SNR): the problem is SSE-hard when the DS-SNR is strictly less than 1, and solvable via practical algorithms when it is greater than 1 under general position assumptions. However, the exact behavior of practical algorithms at the critical boundary DS-SNR = 1 has remained unknown. This work resolves the behavior of Tyler's M-estimator (TME) at this critical boundary, consequently establishing a sharp phase transition. Specifically, we prove that TME converges exactly to the true subspace for DS-SNR \geq 1 under a new stability condition, which is less restrictive than the general position assumptions used in prior literature. Our analysis utilizes a decomposition of the TME iterates within a majorization-minimization framework.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。