Subspace clustering in high-dimensions: Phase transitions & Statistical-to-Computational gap
Not on the map. Why?
Abstract (arXiv)
A simple model to study subspace clustering is the high-dimensional k-Gaussian mixture model where the cluster means are sparse vectors. Here we provide an exact asymptotic characterization of the statistically optimal reconstruction error in this model in the high-dimensional regime with extensive sparsity, i.e. when the fraction of non-zero components of the cluster means ρ, as well as the ratio α between the number of samples and the dimension are fixed, while the dimension diverges. We identify the information-theoretic threshold below which obtaining a positive correlation with the true cluster means is statistically impossible. Additionally, we investigate the performance of the approximate message passing (AMP) algorithm analyzed via its state evolution, which is conjectured to be optimal among polynomial algorithm for this task. We identify in particular the existence of a statistical-to-computational gap between the algorithm that require a signal-to-noise ratio λalg ≥ k / √α to perform better than random, and the information theoretic threshold at λit ≈ √-k ρ logρ / √α. Finally, we discuss the case of sub-extensive sparsity ρ by comparing the performance of the AMP with other sparsity-enhancing algorithms, such as sparse-PCA and diagonal thresholding.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 19 of its 38 references that are in the map. First posted on arXiv 26 May 2022.
Builds on
19 of 38 references.
References · 19
- 2021The Intrinsic Dimension of Images and Its Impact on Learningcited by 315
- 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 116
- 2017Estimation of Low-Rank Matrices via Approximate Message Passingcited by 41
- 2020Phase retrieval in high dimensions: Statistical and computational phase transitionscited by 39
- 2020The estimation error of general first order methodscited by 33
- 2016Mutual information for symmetric rank-one matrix estimation: A proof of the replica formulacited by 26
- 2019The spiked matrix model with generative priorscited by 20
- 2019Exact asymptotics for phase retrieval and compressed sensing with random generative priorscited by 20
- 2018Fundamental limits of detection in the spiked Wigner modelcited by 18
- 2020Optimal Combination of Linear and Spectral Estimators for Generalized Linear Modelscited by 15
- 2016Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clusteringcited by 13
- 2020Computationally efficient sparse clusteringcited by 12
7 more
- 2013Minimax Theory for High-dimensional Gaussian Mixtures with Sparse Mean Separationcited by 11
- 2018Detection limits in the high-dimensional spiked rectangular modelcited by 8
- 2014Detection and Feature Selection in Sparse Mixture Modelscited by 6
- 2014Efficient Sparse Clustering of High-Dimensional Non-spherical Gaussian Mixturescited by 6
- 2015Phase Transitions for High Dimensional Clustering and Related Problemscited by 6
- 2018Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrievalcited by 6
- 2019Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversariescited by 5
Built on by
Citing papers per year: 2024: 1.
1 paper.