Fundamental limits of detection in the spiked Wigner model

Abstract

We study the fundamental limits of detecting the presence of an additive rank-one perturbation, or spike, to a Wigner matrix. When the spike comes from a prior that is i.i.d. across coordinates, we prove that the log-likelihood ratio of the spiked model against the non-spiked one is asymptotically normal below a certain reconstruction threshold which is not necessarily of a "spectral" nature, and that it is degenerate above. This establishes the maximal region of contiguity between the planted and null models. It is known that this threshold also marks a phase transition for estimating the spike: the latter task is possible above the threshold and impossible below. Therefore, both estimation and detection undergo the same transition in this random matrix model. We also provide further information about the performance of the optimal test. Our proofs are based on Gaussian interpolation methods and a rigorous incarnation of the cavity method, as devised by Guerra and Talagrand in their study of the Sherrington--Kirkpatrick spin-glass model.

arXiv commentSubstantial text overlap with arXiv:1710.02903. This manuscript focuses on the LR fluctuations and the detection problem. The result is strengthened and the proof (execution of the interpolation and cavity methods) substantially simplified. Reflects more accurately the version to be published

References in corpus (22)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Recipes for metastable states in Spin Glasses
• Optimal detection of sparse principal components in high dimension
• Finite sample approximation results for principal component analysis: a matrix perturbation approach
• The largest eigenvalue of rank one deformation of large Wigner matrices
• The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations
• Limit theorems for sample eigenvalues in a generalized spiked population model
• Asymptotic power of sphericity tests for high-dimensional data
• Central limit theorems for eigenvalues in a spiked population model
• Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Effective potential in glassy systems: theory and simulations
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• Mutual Information in Rank-One Matrix Estimation
• Fluctuations of the free energy of the spherical Sherrington-Kirkpatrick model
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Phase Transitions in Sparse PCA
• Fluctuations of the free energy of the spherical Sherrington-Kirkpatrick model with ferromagnetic interaction
• Estimation in the spiked Wigner model: A short proof of the replica formula
• Sharp detection in PCA under correlations: all eigenvalues matter
• Detection limits in the high-dimensional spiked rectangular model
• Asymptotic normality and analysis of variance of log-likelihood ratios in spiked random matrix models

Cited by in corpus (13)

• An inference problem in a mismatched setting: a spin-glass model with Mattis interaction
• Subexponential-Time Algorithms for Sparse PCA
• Matrix factorization with neural networks
• Phase transition in random tensors with multiple independent spikes
• Contextual Stochastic Block Model: Sharp Thresholds and Contiguity
• Free energy fluctuations of the $2$-spin spherical SK model at critical temperature
• Weak Detection in the Spiked Wigner Model with General Rank
• Weak detection in the spiked Wigner model
• Detection of Signal in the Spiked Rectangular Models
• Spherical Integrals of Sublinear Rank
• Low-rank Matrix Estimation with Inhomogeneous Noise
• Finite-size relaxational dynamics of a spike random matrix spherical model
• Precise Error Rates for Computationally Efficient Testing