Given a $K$-vertex simplex in a $d$-dimensional space, suppose we measure $n$
points on the simplex with noise (hence, some of the observed points fall
outside the simplex). Vertex hunting is the problem of estimating the $K$
vertices of the simplex. A popular vertex hunting algorithm is successive
projection algorithm (SPA). However, SPA is observed to perform
unsatisfactorily under strong noise or outliers. We propose pseudo-point SPA
(pp-SPA). It uses a projection step and a denoise step to generate
pseudo-points and feed them into SPA for vertex hunting. We derive error bounds
for pp-SPA, leveraging on extreme value theory of (possibly) high-dimensional
random vectors. The results suggest that pp-SPA has faster rates and better
numerical performances than SPA. Our analysis includes an improved
non-asymptotic bound for the original SPA, which is of independent interest.

给定一个 $d$ 维空间中的 $K$ 个顶点的单纯形，我们在单纯形上用 $n$ 个带噪声的点进行测量（因此，观察到的点中有些点落在单纯形之外）。顶点搜索是估计单纯形的 $K$ 个顶点的问题。流行的顶点搜索算法是连续投影算法（SPA）。然而，SPA 在强噪声或异常值下表现不理想。我们提出了伪点 SPA（pp-SPA）。它使用投影步骤和去噪步骤生成伪点，并将它们馈入 SPA 进行顶点搜索。我们利用（可能是）高维随机向量的极值理论推导出 pp-SPA 的误差界限。结果表明，pp-SPA 比 SPA 具有更快的速率和更好的数值性能。我们的分析包括对原始 SPA 的改进非渐近界限，这具有独立的兴趣。