0-1 Phase Transitions in Sparse Spiked Matrix Estimation

Published in

arXiv.org(2019)

External Links:

Generate Graph

TL;DR

It is proved that explicit low-dimensional variational formulas for the asymptotic mutual information between the spike and the observed noisy matrix in suitable sparse limits imply sharp 0-1 phase transitions for theAsymPTotic minimum mean-square-error.

Abstract

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. A similar phase transition was analyzed recently in the context of sparse high-dimensional linear regression (compressive sensing).

Authors

Jean Barbier

1 papers

N. Macris

1 papers

References40 items

The overlap gap property in principal submatrix recovery

Hamilton–Jacobi equations for finite-rank matrix inference

Mutual Information for Low-Rank Even-Order Symmetric Tensor Factorization

The All-or-Nothing Phenomenon in Sparse Linear Regression

The adaptive interpolation method for proving replica formulas. Applications to the Curie–Weiss and Wigner spike models

0-1 Phase Transitions in Sparse Spiked Matrix Estimation

Published in

arXiv.org(2019)

External Links:

Generate Graph

TL;DR

Abstract

Authors

Jean Barbier

1 papers

N. Macris

1 papers

References40 items

The overlap gap property in principal submatrix recovery

Hamilton–Jacobi equations for finite-rank matrix inference

Mutual Information for Low-Rank Even-Order Symmetric Tensor Factorization

The All-or-Nothing Phenomenon in Sparse Linear Regression

The adaptive interpolation method for proving replica formulas. Applications to the Curie–Weiss and Wigner spike models

The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference

Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models

Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure

Phase transitions in spiked matrix estimation: information-theoretic analysis

Detection limits in the high-dimensional spiked rectangular model

Estimation in the Spiked Wigner Model: A Short Proof of the Replica Formula

Finite Size Corrections and Likelihood Ratio Fluctuations in the Spiked Wigner Model

The layered structure of tensor estimation and its mutual information

Fundamental limits of low-rank matrix estimation

High Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transtition

Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications

Fundamental limits of symmetric low-rank matrix estimation

Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula

Finite-sample analysis of Approximate Message Passing

Mutual information in rank-one matrix estimation

Sum-of-Squares Lower Bounds for Sparse PCA

Statistical and computational trade-offs in estimation of sparse principal components

Optimal estimation and rank detection for sparse spiked covariance matrices

Information-theoretically optimal sparse PCA

Sparse PCA via Covariance Thresholding

DO SEMIDEFINITE RELAXATIONS SOLVE SPARSE PCA UP TO THE INFORMATION LIMIT

Complexity Theoretic Lower Bounds for Sparse Principal Component Detection

Optimal estimation and rank detection for sparse spiked covariance matrices

The dynamics of message passing on dense graphs, with applications to compressed sensing

Estimation in Gaussian Noise: Properties of the Minimum Mean-Square Error

Message-passing algorithms for compressed sensing

Exact Solution of the Gauge Symmetric p-Spin Glass Model on a Complete Graph

Sparse Principal Components Analysis

High-dimensional analysis of semidefinite relaxations for sparse principal components

The Largest Eigenvalue of Rank One Deformation of Large Wigner Matrices

Mutual information and minimum mean-square error in Gaussian channels

The largest eigenvalue of small rank perturbations of Hermitian random matrices

Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices

On the distribution of the largest eigenvalue in principal components analysis

Field of Study

MathematicsComputer SciencePhysics

Journal Information

Name

ArXiv

Volume

abs/1911.05030

Venue Information

Name

arXiv.org

Type

URL

https://arxiv.org

Alternate Names

ArXiv