Research map / Learning theory and algorithms / Sample complexity
Improved algorithm and bounds for successive projection
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes pseudo-point SPA (pp-SPA), which projects data onto a best-fit hyperplane and denoises by neighborhood averaging before successive projection, and gives sharper non-asymptotic and extreme-value-based error bounds for vertex hunting.
Problem
Vertex hunting on a noisy simplex: estimating the K vertices from n noisy points, where the successive projection algorithm (SPA) is sensitive to noise and outliers and is biased outward.
Approach
Combine a hyperplane projection (SVD-based, to K-1 dimensions) with a neighborhood-averaging denoise step that produces pseudo-points, then run SPA; a geometric proof yields a sharper bound for SPA depending on s_{K-1}(V) rather than s_K(V).
Key results
- Toy example: the improved SPA bound gives max error <= 18.7 versus 2151.3 from the prior bound (Lemma-based), with g_new = 6.577e2 vs g = 4.3025e4.
- Theory: pp-SPA error rate is sqrt(2c0 log n) when d/n is small versus SPA's sqrt(max{d, 2log n}), improving by factor sqrt(log n / d) when d >> log n.
- Simulations (K=3, d=2 to 50): pp-SPA outperforms SPA, P-SPA, D-SPA and robust-SPA for d>10 and d<=10 regimes described.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use pp-SPA instead of SPA | SPA · d >> log(n) | vertex-hunting error bound: factor of \sqrt{\log(n)/d} | Helped |
| use pp-SPA instead of SPA | SPA · d = O(log(n)) | error-bound order (β_new): c_0 | Helped |
| add hyperplane projection (ablation) | SPA · d >> log(n) | vertex-hunting error bound: factor of \sqrt{\log(n)/d} | Helped |
| add hyperplane projection (ablation) | SPA · d = O(log(n)) | error-bound order (β_new) | Helped |
| add denoising after projection (ablation) | P-SPA · three of the four dimension regimes in the table | error-bound order (β_new): c_0<1 | Helped |
| add denoising in the original, unprojected space (ablation) | SPA · d << sqrt(log(n)) | error-bound order (β_new): constant factor | Helped |
| skip hyperplane projection (ablation) | D-SPA · d >> log(n) | numerical vertex-hunting error | Hurt |
| combine hyperplane projection and denoising | SPA · Experiments 1–3 | average vertex-hunting error | Helped |
Surprising findings
- D-SPA (denoise without projection) underperforms robust-SPA when d>10, indicating denoising original high-dimensional data is ineffective.
Limitations
- Assumes Gaussian (or subGaussian) noise; results extended only informally to subGaussian.
- Theoretical rates require conditions like K=o(log n / log log n), d=o(sqrt n), and sigma sqrt(log n)/s_{K-1}(tilde V) -> 0.
- Denoise parameters N and Delta are heuristic in practice (N=3, Delta = max||Y_i - Ybar||/5).
Experimental setup
Datasets: simulated data from Gaussian noise model
Benchmarks: simulated vertex hunting experiments
Metrics: max vertex estimation error
Baselines: SPA robust-SPA P-SPA D-SPA
Builds on: successive projection algorithm Mixed-SCORE Topic-SCORE
Closest papers by meaning
- Learning a Latent Simplex in Input Sparsity Time (ICLR 2021 · similarity 0.83)
- Semi-supervised Vertex Hunting, with Applications in Network and Text Analysis (NeurIPS 2025 · similarity 0.83)
- Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.83)
- Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point (NeurIPS 2025 · similarity 0.81)
- Debiasing Random Oblique Projections for Subsampled OLS and Fast CUR in High Dimensions (NeurIPS 2026 · similarity 0.80)
- Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.