Subspace clustering in high-dimensions: Phase transitions \& Statistical-to-Computational gap. (arXiv:2205.13527v1 [stat.ML])

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 $\rho$, as well as the ratio $\alpha$ between the number of
samples and the dimension are fixed, while the dimension diverges. We identify
the information-theoretic threshold …

arxiv clustering computational gap ml statistical transitions