Subspace clustering in high-dimensions: Phase transitions & Statistical-to-Computational gap
The episode discusses a paper mapping subspace clustering in high-dimensional data. The authors define three regions—impossible, hard, and easy—where clustering is either impossible or computationally intractable for known efficient algorithms. Key findings reveal a statistical-to-computational gap that widens as data sparsity increases.