mlsanityData to 14 Oct 2026

Improved Algorithm and Bounds for Successive Projection

arXiv 2403.11013 ↗First posted 16 Mar 2024cs.LG math.ST stat.THcited by 3

Not on the map. Why?

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.

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

14 of 30 references.

References · 14

  1. 2017A statistical interpretation of spectral embedding: the generalised random dot product graphcited by 55
  2. 2014Detecting Overlapping Communities in Networks Using Spectral Methodscited by 22
  3. 2017Mixed Membership Estimation for Social Networkscited by 21
  4. 2018Spectral State Compression of Markov Processescited by 18
  5. 2017Using SVD for Topic Modelingcited by 14
  6. 2013Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorizationcited by 13
  7. 2017Non-negative Matrix Factorization via Archetypal Analysiscited by 11
  8. 2021Learning a Latent Simplex in Input-Sparsity Timecited by 11
  9. 2018Pairwise Covariates-adjusted Block Model for Community Detectioncited by 8
  10. 2019Finding a latent k-simplex in O(k . nnz(data)) time via Subset Smoothingcited by 7
  11. 2021Smoothed Separable Nonnegative Matrix Factorizationcited by 5
  12. 2019Successive Projection Algorithm Robust to Outlierscited by 3
2 more
  1. 2017Efficient Preconditioning for Noisy Separable NMFs by Successive Projection Based Low-Rank Approximationscited by 1
  2. 2023Inferences on Mixing Probabilities and Ranking in Mixed-Membership Modelscited by 1

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 2.

3 papers.

  1. 2024On the Robustness of the Successive Projection Algorithmcited by 3
  2. 2025Fundamental Limits of Learning High-dimensional Simplices in Noisy Regimescited by 2
  3. 2025Semi-supervised Vertex Hunting, with Applications in Network and Text Analysiscited by 0