2019

0-1 phase transitions in sparse spiked matrix estimation

Barbier, Jean, Macris, Nicolas

Understand

We consider statistical models of estimation of a rank-one matrix (the spike) corrupted by an additive gaussian noise matrix in the sparse limit.

In this limit the underlying hidden vector (that constructs the rank-one matrix) has a number of non-zero components that scales sub-linearly with the total dimension of the vector, and the signal strength tends to infinity at an appropriate speed.
We prove explicit low-dimensional variational formulas for the asymptotic mutual information between the spike and the observed noisy matrix in suitable sparse limits.
For Bernoulli and Bernoulli-Rademacher distributed vectors, and when the sparsity and signal strength satisfy an appropriate scaling relation, these formulas imply sharp 0-1 phase transitions for the asymptotic minimum mean-square-error.

Built on

On the distribution of the largest eigenvalue in principal components analysis
I. M. Johnstone et al · 2001
Earlier work this paper cites.
Mutual information and minimum mean-square error in gaussian channels
D. Guo, S. Shamai, and S. Verdu · 2005
Earlier work this paper cites.
Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
J. Baik, G. B. Arous, and S. Péché · 2005
Earlier work this paper cites.
The largest eigenvalue of small rank perturbations of hermitian random matrices
S. Péché · 2006
Earlier work this paper cites.
The largest eigenvalue of rank one deformation of large wigner matrices
D. Féral and S. Péché · 2007
Earlier work this paper cites.
Sparse principal components analysis
Original
I. Johnstone and A. Lu · 2009
Earlier work this paper cites.
Message-passing algorithms for compressed sensing
D. L. Donoho, A. Maleki, and A. Montanari · 2009
Earlier work this paper cites.
Exact solution of the gauge symmetric p-spin glass model on a complete graph
S. B. Korada and N. Macris · 2009
Earlier work this paper cites.
High-dimensional analysis of semidefinite relaxations for sparse principal components
A. A. Amini and M. J. Wainwright · 2009
Earlier work this paper cites.
The dynamics of message passing on dense graphs, with applications to compressed sensing
M. Bayati and A. Montanari · 2011
Earlier work this paper cites.
Estimation in gaussian noise: Properties of the minimum mean-square error
D. Guo, Y. Wu, S. S. Shitz, and S. Verdú · 2011
Earlier work this paper cites.
Complexity theoretic lower bounds for sparse principal component detection
Q. Berthet and P. Rigollet · 2013
Earlier work this paper cites.
Information-theoretically optimal sparse pca
Y. Deshpande and A. Montanari · 2014
Earlier work this paper cites.

Similar

Optimal estimation and rank detection for sparse spiked covariance matrices
T. Cai, Z. Ma, and Y. Wu · 2015
Cited alongside, same era.
Do semidefinite relaxations solve sparse pca up to the information limit?
R. Krauthgamer, B. Nadler, and D. Vilenchik · 2015
Cited alongside, same era.
Sum-of-squares lower bounds for sparse pca
T. Ma and A. Wigderson · 2015
Cited alongside, same era.
Mutual information in rank-one matrix estimation
F. Krzakala, J. Xu, and L. Zdeborová · 2016
Cited alongside, same era.
Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
J. Barbier, M. Dia, N. Macris, F. Krzakala, T. Lesieur, and L. Zdeborová · 2016
Cited alongside, same era.
Sparse pca via covariance thresholding
Y. Deshpande and A. Montanari · 2016
Cited alongside, same era.
Statistical and computational trade-offs in estimation of sparse principal components
T. Wang, Q. Berthet, and R. J. Samworth · 2016
Cited alongside, same era.
High dimensional regression with binary coefficients. estimating squared error and a phase transtition
D. Gamarnik and I. Zadik · 2017
Cited alongside, same era.
Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
T. Lesieur, F. Krzakala, and L. Zdeborová · 2017
Cited alongside, same era.
Fundamental limits of low-rank matrix estimation: The non-symmetric case
L. Miolane · 2017
Cited alongside, same era.
The Layered Structure of Tensor Estimation and its Mutual Information
J. Barbier, N. Macris, and L. Miolane · 2017
Cited alongside, same era.
Finite size corrections and likelihood ratio fluctuations in the spiked wigner model
Original
A. E. Alaoui, F. Krzakala, and M. I. Jordan · 2017
Cited alongside, same era.

Then

The adaptive interpolation method: a simple scheme to prove replica formulas in bayesian inference
J. Barbier and N. Macris · 2018
Later among the works it cites.
Estimation in the spiked wigner model: a short proof of the replica formula
A. El Alaoui and F. Krzakala · 2018
Later among the works it cites.
Optimality and sub-optimality of pca i: Spiked random matrix models
A. Perry, A. S. Wein, A. S. Bandeira, A. Moitra, et al · 2018
Later among the works it cites.
Detection limits in the high-dimensional spiked rectangular model
A. E. Alaoui and M. I. Jordan · 2018
Later among the works it cites.
Reducibility and computational lower bounds for problems with planted sparse structure
M. Brennan, G. Bresler, and W. Huleihel · 2018
Later among the works it cites.
Finite sample analysis of approximate message passing algorithms
C. Rush and R. Venkataramanan · 2018
Later among the works it cites.
Phase transitions in spiked matrix estimation: information-theoretic analysis
Original
L. Miolane · 2018
Later among the works it cites.
The all-or-nothing phenomenon in sparse linear regression
Original
G. Reeves, J. Xu, and I. Zadik · 2019
Closest in time.
The adaptive interpolation method for proving replica formulas. applications to the curie–weiss and wigner spike models
J. Barbier and N. Macris · 2019
Closest in time.
Mutual information for low-rank even-order symmetric tensor factorization
Original
J. Barbier, C. Luneau, and N. Macris · 2019
Closest in time.
Hamilton-jacobi equations for finite-rank matrix inference
Original
J.-C. Mourrat · 2019
Closest in time.
The overlap gap property in principal submatrix recovery
Original
D. Gamarnik, A. Jagannath, and S. Sen · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…