# Learning a Latent Simplex in Input-Sparsity Time

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 55 references that are in the map.
- First posted on arXiv 17 May 2021.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [Bayesian estimation from few samples: community detection and related problems](https://mlsanity.com/paper/1710.00264/) (2017)
- [Robustly Learning any Clusterable Mixture of Gaussians](https://mlsanity.com/paper/2005.06417/) (2020)
- [Outlier-Robust Clustering of Non-Spherical Mixtures](https://mlsanity.com/paper/2005.02970/) (2020)
- [Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices](https://mlsanity.com/paper/1704.03371/) (2017)
- [Efficiently Learning Mixtures of Mallows Models](https://mlsanity.com/paper/1808.05731/) (2018)
- [A Tensor Approach to Learning Mixed Membership Community Models](https://mlsanity.com/paper/1302.2684/) (2013)
- [Scalable MCMC for Mixed Membership Stochastic Blockmodels](https://mlsanity.com/paper/1510.04815/) (2015)
- [Finding a latent k-simplex in O(k . nnz(data)) time via Subset Smoothing](https://mlsanity.com/paper/1904.06738/) (2019)
- [Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation](https://mlsanity.com/paper/1912.04177/) (2019)
- [Latent Simplex Position Model: High Dimensional Multi-view Clustering with Uncertainty Quantification](https://mlsanity.com/paper/1903.09029/) (2019)

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

- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Smoothed Separable Nonnegative Matrix Factorization](https://mlsanity.com/paper/2110.05528/) (2021)
- [Bounded Simplex-Structured Matrix Factorization: Algorithms, Identifiability and Applications](https://mlsanity.com/paper/2209.12638/) (2022)
- [Dual Simplex Volume Maximization for Simplex-Structured Matrix Factorization](https://mlsanity.com/paper/2403.20197/) (2024)
- [Improved Algorithm and Bounds for Successive Projection](https://mlsanity.com/paper/2403.11013/) (2024)
- [On the Robustness of the Successive Projection Algorithm](https://mlsanity.com/paper/2411.16195/) (2024)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)
- [Matrix Factorization Framework for Community Detection under the Degree-Corrected Block Model](https://mlsanity.com/paper/2601.06262/) (2026)
- [Random Separating Hyperplane Theorem and Learning Polytopes](https://mlsanity.com/paper/2307.11371/) (2023)
- [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)

We consider the problem of learning a latent k-vertex simplex Ksubsetℝd, given access to A∈ℝd× n, which can be viewed as a data matrix with n points that are obtained by randomly perturbing latent points in the simplex K (potentially beyond K). A large class of latent variable models, such as adversarial clustering, mixed membership stochastic block models, and topic models can be cast as learning a latent simplex. Bhattacharyya and Kannan (SODA, 2020) give an algorithm for learning such a latent simplex in time roughly O(k·textrmnnz(A)), where textrmnnz(A) is the number of non-zeros in A. We show that the dependence on k in the running time is unnecessary given a natural assumption about the mass of the top k singular values of A, which holds in many of these applications. Further, we show this assumption is necessary, as otherwise an algorithm for learning a latent simplex would imply an algorithmic breakthrough for spectral low rank approximation. At a high level, Bhattacharyya and Kannan provide an adaptive algorithm that makes k matrix-vector product queries to A and each query is a function of all queries preceding it. Since each matrix-vector product requires textrmnnz(A) time, their overall running time appears unavoidable. Instead, we obtain a low-rank approximation to A in input-sparsity time and show that the column space thus obtained has small sinTheta (angular) distance to the right top-k singular space of A. Our algorithm then selects k points in the low-rank subspace with the largest inner product with k carefully chosen random vectors. By working in the low-rank subspace, we avoid reading the entire matrix in each iteration and thus circumvent the Theta(k·textrmnnz(A)) running time.