改进了凸包顶点提取算法在噪声下的误差界限，提升稳定性与适用性。
On the Robustness of the Successive Projection Algorithm
- 通过分析数据条件性，优化了逐次投影算法的误差上界。
- 在特殊情况下，误差上限降低至原结果的若干倍，显著提升精度。
- 提出新变体算法，通过数据平移提升鲁棒性，适合高维稀疏数据场景。
逐次投影算法（SPA）是学习一组 (r-1) 维数据点凸包顶点（即潜在单纯形）的核心方法，在数据科学中有广泛应用。本文重新审视了 SPA 及其若干变体在噪声下的鲁棒性。当 r ≥ 3 时，证明了现有误差界的紧致性；并对两种更稳健的预处理变体给出了紧致误差界。此外，在两类特殊情形下——首次提取顶点、或 r ≤ 2 时——提出了显著改进的误差界，改进因子与 r 个顶点的条件数成正比。进一步地，针对 Arora 等人（ICML 2013）提出的平移版 SPA，也在前两个顶点提取及 r ≤ 3 情况下提供了更强误差界。最后，提出一种新鲁棒变体，通过先对数据点进行平移和升维以最小化问题条件性。实验在合成数据上验证了理论结果。
原文摘要 · Abstract (English)
The successive projection algorithm (SPA) is a workhorse algorithm to learn the $r$ vertices of the convex hull of a set of $(r-1)$-dimensional data points, a.k.a. a latent simplex, which has numerous applications in data science. In this paper, we revisit the robustness to noise of SPA and several of its variants. In particular, when $r \geq 3$, we prove the tightness of the existing error bounds for SPA and for two more robust preconditioned variants of SPA. We also provide significantly improved error bounds for SPA, by a factor proportional to the conditioning of the $r$ vertices, in two special cases: for the first extracted vertex, and when $r \leq 2$. We then provide further improvements for the error bounds of a translated version of SPA proposed by Arora et al. (''A practical algorithm for topic modeling with provable guarantees'', ICML, 2013) in two special cases: for the first two extracted vertices, and when $r \leq 3$. Finally, we propose a new more robust variant of SPA that first shifts and lifts the data points in order to minimize the conditioning of the problem. We illustrate our results on synthetic data.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。