mlsanityData to 14 Oct 2026

On the Robustness of the Successive Projection Algorithm

arXiv 2411.16195 ↗First posted 25 Nov 2024math.NA cs.DS cs.LGcited by 3

Not on the map. Why?

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.

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

17 of 37 references.

References · 17

  1. 2017Estimating Mixed Memberships with Sharp Eigenvector Deviationscited by 22
  2. 2017Mixed Membership Estimation for Social Networkscited by 21
  3. 2020Simplex-Structured Matrix Factorization: Sparsity-based Identifiability and Provably Correct Algorithmscited by 21
  4. 2013Successive Nonnegative Projection Algorithm for Robust Nonnegative Blind Source Separationcited by 18
  5. 2013Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorizationcited by 13
  6. 2013Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimizationcited by 12
  7. 2013Hierarchical Clustering of Hyperspectral Images using Rank-Two Nonnegative Matrix Factorizationcited by 11
  8. 2021Learning a Latent Simplex in Input-Sparsity Timecited by 11
  9. 2021Probabilistic Simplex Component Analysiscited by 8
  10. 2022Estimating Higher-Order Mixed Memberships via the ℓ2,∞ Tensor Perturbation Boundcited by 8
  11. 2013Ellipsoidal Rounding for Nonnegative Matrix Factorization Under Noisy Separabilitycited by 7
  12. 2019Finding a latent k-simplex in O(k . nnz(data)) time via Subset Smoothingcited by 7
5 more
  1. 2021Smoothed Separable Nonnegative Matrix Factorizationcited by 5
  2. 2019Successive Projection Algorithm Robust to Outlierscited by 3
  3. 2021Refinement of Hottopixx Method for Nonnegative Matrix Factorization Under Noisy Separabilitycited by 3
  4. 2024Improved Algorithm and Bounds for Successive Projectioncited by 3
  5. 2014Enhancing Pure-Pixel Identification Performance via Preconditioningcited by 2

Built on by

Cited by year

Citing papers per year: 2025: 3.

3 papers.

  1. 2025Nonnegative matrix factorizations and related compositional models: Equivalence, identifiability, and an application on the grain-size analysis of sedimentscited by 1
  2. 2025Robustness of Minimum-Volume Nonnegative Matrix Factorization under an Expanded Sufficiently Scattered Conditioncited by 0
  3. 2025A Provably-Correct and Robust Convex Model for Smooth Separable NMFcited by 0