Research map / Learning theory and algorithms / Clustering
Subspace clustering in high-dimensions: Phase transitions & Statistical-to-Computational gap
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Bayes-optimal estimator rather than random guessing | Sparse k-Gaussian mixture in the proportional high-dimensional limit · Sparse k-Gaussian mixture | reconstruction possibility: \lambda_{\text{it}} \approx \sfrac{\sqrt{-k \rho \log{\rho}}}{\sqrt{\alpha}}; \lambda_{\text{alg}} = \sfrac{k}{\sqrt{\al | Mixed |
| Decrease the nonzero density \rho | AMP for sparse k-Gaussian mixture clustering · Extensive sparsity | algorithmic reconstruction threshold: \lambda_{\text{alg}} = \frac{k}{\sqrt{\alpha}} | Hurt |
| Increase the number of clusters k | Sparse k-Gaussian mixture clustering · Large-rank and small finite sparsity | statistical-to-computational gap: \lambda_{\text{it}} \approx \sqrt{\frac{-k \rho \log{\rho}}{\alpha}}; \lambda_{\text{alg}} = \frac{k}{\sqrt{\alpha}} | Hurt |
| Impose a sparsity constraint in the spectral algorithm | PCA for sparse subspace clustering · Sparse clustering phase diagram | reconstruction performance | Helped |
| Use DT or SPCA with extremely sparse means | Two-class Gaussian mixture clustering · Sub-extensive sparsity below the BBP threshold | correlation with true classes: s \lesssim \sqrt{n} | Helped |
| Increase the number of nonzero components beyond the very sparse regime | DT and SPCA · Two-class Gaussian mixture, below the BBP threshold | correlation with true classes: s \lesssim \sqrt{n} | Hurt |
| Use uninformed initialization instead of informative initialization | AMP · Hard phase | correlation with true cluster assignments | Hurt |
| Apply damping to AMP iterations | AMP at increasing sparsity · Sparse clustering simulations | iteration convergence | Helped |
Closest papers by meaning
- Stochastic Sparse Subspace Clustering (CVPR 2020 · similarity 0.91)
- Subspace Clustering With Priors via Sparse Quadratically Constrained Quadratic Programming (CVPR 2016 · similarity 0.89)
- Robust Subspace Clustering With Independent and Piecewise Identically Distributed Noise Modeling (CVPR 2019 · similarity 0.89)
- Heterogeneous Sufficient Dimension Reduction and Subspace Clustering (ICML 2025 · similarity 0.88)
- Achieving Optimal Clustering in Gaussian Mixture Models with Anisotropic Covariance Structures (NeurIPS 2024 · similarity 0.87)
- Fast and Provable Algorithms for Sparse PCA with Improved Sample Complexity (ICML 2025 · similarity 0.87)
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.