# On the Robustness of the Successive Projection Algorithm

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 37 references that are in the map.
- First posted on arXiv 25 Nov 2024.

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

- [Estimating Mixed Memberships with Sharp Eigenvector Deviations](https://mlsanity.com/paper/1709.00407/) (2017)
- [Mixed Membership Estimation for Social Networks](https://mlsanity.com/paper/1708.07852/) (2017)
- [Simplex-Structured Matrix Factorization: Sparsity-based Identifiability and Provably Correct Algorithms](https://mlsanity.com/paper/2007.11446/) (2020)
- [Successive Nonnegative Projection Algorithm for Robust Nonnegative Blind Source Separation](https://mlsanity.com/paper/1310.7529/) (2013)
- [Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization](https://mlsanity.com/paper/1310.2273/) (2013)
- [Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization](https://mlsanity.com/paper/1302.4385/) (2013)
- [Hierarchical Clustering of Hyperspectral Images using Rank-Two Nonnegative Matrix Factorization](https://mlsanity.com/paper/1310.7441/) (2013)
- [Learning a Latent Simplex in Input-Sparsity Time](https://mlsanity.com/paper/2105.08005/) (2021)
- [Probabilistic Simplex Component Analysis](https://mlsanity.com/paper/2103.10027/) (2021)
- [Estimating Higher-Order Mixed Memberships via the ℓ2,∞ Tensor Perturbation Bound](https://mlsanity.com/paper/2212.08642/) (2022)
- [Ellipsoidal Rounding for Nonnegative Matrix Factorization Under Noisy Separability](https://mlsanity.com/paper/1309.5701/) (2013)
- [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)
- [Refinement of Hottopixx Method for Nonnegative Matrix Factorization Under Noisy Separability](https://mlsanity.com/paper/2109.02863/) (2021)
- [Improved Algorithm and Bounds for Successive Projection](https://mlsanity.com/paper/2403.11013/) (2024)
- [Enhancing Pure-Pixel Identification Performance via Preconditioning](https://mlsanity.com/paper/1406.5286/) (2014)

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

- [Nonnegative matrix factorizations and related compositional models: Equivalence, identifiability, and an application on the grain-size analysis of sediments](https://mlsanity.com/paper/2512.22282/) (2025)
- [Robustness of Minimum-Volume Nonnegative Matrix Factorization under an Expanded Sufficiently Scattered Condition](https://mlsanity.com/paper/2511.04291/) (2025)
- [A Provably-Correct and Robust Convex Model for Smooth Separable NMF](https://mlsanity.com/paper/2511.07109/) (2025)

## Abstract (arXiv)

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 ≥ 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 ≤ 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 ≤ 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.