Phase transitions in spiked matrix estimation: information-theoretic analysis
read the original abstract
We study here the so-called spiked Wigner and Wishart models, where one observes a low-rank matrix perturbed by some Gaussian noise. These models encompass many classical statistical tasks such as sparse PCA, submatrix localization, community detection or Gaussian mixture clustering. The goal of these notes is to present in a unified manner recent results (as well as new developments) on the information-theoretic limits of these spiked matrix models. We compute the minimal mean squared error for the estimation of the low-rank signal and compare it to the performance of spectral estimators and message passing algorithms. Phase transition phenomena are observed: depending on the noise level it is either impossible, easy (i.e. using polynomial-time estimators) or hard (information-theoretically possible, but no efficient algorithm is known to succeed) to recover the signal.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
Sharp Phase Transitions in Estimation with Low-Degree Polynomials
New techniques establish sharp lower bounds ruling out low-degree polynomial estimation at the BBP and Kesten-Stigum thresholds for planted submatrix, dense subgraph, spiked Wigner, and stochastic block models.
-
BBP transition and the leading eigenvector of the spiked Wigner model with inhomogeneous noise
For a spiked Wigner model with power-law inhomogeneous noise variances, the BBP transition is non-monotonic and inhomogeneous noise can enhance signal detectability.
-
Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
The low-degree likelihood ratio method predicts computational hardness of hypothesis testing problems, with new connections to spectral methods and a lower bound for tensor PCA.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.