Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization

DOI10.1109/TIT.2018.2810020zbMath1401.94065arXiv1607.05222MaRDI QIDQ4682810

Jess Banks, Moore, Cristopher, Nicolas Verzelen, Jiaming Xu, R. V. Vershinin

Publication date: 19 September 2018

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1607.05222

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Measures of information, entropy (94A17) Statistical aspects of information-theoretic topics (62B10)

Related Items (15)

Sparse high-dimensional linear regression. Estimating squared error and a phase transition ⋮ An information-percolation bound for spin synchronization on general graphs ⋮ Statistical thresholds for tensor PCA ⋮ Statistical limits of spiked tensor models ⋮ Free Energy Wells and Overlap Gap Property in Sparse PCA ⋮ Fundamental limits of detection in the spiked Wigner model ⋮ Notes on computational-to-statistical gaps: predictions using statistical physics ⋮ Fundamental limits of symmetric low-rank matrix estimation ⋮ Convex optimization for the densest subgraph and densest submatrix problems ⋮ Optimality and sub-optimality of PCA. I: Spiked random matrix models ⋮ The overlap gap property in principal submatrix recovery ⋮ The all-or-nothing phenomenon in sparse linear regression ⋮ Sharp optimal recovery in the two component Gaussian mixture model ⋮ Consistency of invariance-based randomization tests ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio

This page was built for publication: Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization