# Improved Algorithm and Bounds for Successive Projection

arXiv: https://arxiv.org/abs/2403.11013 · HTML: https://mlsanity.com/paper/2403.11013/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 30 references that are in the map.
- First posted on arXiv 16 Mar 2024.

## Builds on (most cited first, 14 of 14)

- [A statistical interpretation of spectral embedding: the generalised random dot product graph](https://mlsanity.com/paper/1709.05506/) (2017)
- [Detecting Overlapping Communities in Networks Using Spectral Methods](https://mlsanity.com/paper/1412.3432/) (2014)
- [Mixed Membership Estimation for Social Networks](https://mlsanity.com/paper/1708.07852/) (2017)
- [Spectral State Compression of Markov Processes](https://mlsanity.com/paper/1802.02920/) (2018)
- [Using SVD for Topic Modeling](https://mlsanity.com/paper/1704.07016/) (2017)
- [Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization](https://mlsanity.com/paper/1310.2273/) (2013)
- [Non-negative Matrix Factorization via Archetypal Analysis](https://mlsanity.com/paper/1705.02994/) (2017)
- [Learning a Latent Simplex in Input-Sparsity Time](https://mlsanity.com/paper/2105.08005/) (2021)
- [Pairwise Covariates-adjusted Block Model for Community Detection](https://mlsanity.com/paper/1807.03469/) (2018)
- [Finding a latent k-simplex in O(k . nnz(data)) time via Subset Smoothing](https://mlsanity.com/paper/1904.06738/) (2019)
- [Smoothed Separable Nonnegative Matrix Factorization](https://mlsanity.com/paper/2110.05528/) (2021)
- [Successive Projection Algorithm Robust to Outliers](https://mlsanity.com/paper/1908.04109/) (2019)
- [Efficient Preconditioning for Noisy Separable NMFs by Successive Projection Based Low-Rank Approximations](https://mlsanity.com/paper/1710.00387/) (2017)
- [Inferences on Mixing Probabilities and Ranking in Mixed-Membership Models](https://mlsanity.com/paper/2308.14988/) (2023)

## Built on by (most cited first, 3 of 3)

- [On the Robustness of the Successive Projection Algorithm](https://mlsanity.com/paper/2411.16195/) (2024)
- [Fundamental Limits of Learning High-dimensional Simplices in Noisy Regimes](https://mlsanity.com/paper/2506.10101/) (2025)
- [Semi-supervised Vertex Hunting, with Applications in Network and Text Analysis](https://mlsanity.com/paper/2510.22526/) (2025)

## Abstract (arXiv)

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.