Improved Algorithm and Bounds for Successive Projection
Jiashun Jin Zheng Tracy Ke Gabriel Moryoussef Jiajun Tang Jingming Wang
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.