Fundamental limits of detection in the spiked Wigner model

DOI10.1214/19-AOS1826zbMATH Open1450.62073arXiv1806.09588OpenAlexW2810555534MaRDI QIDQ2196197FDOQ2196197

Authors: Ahmed El Alaoui, Florent Krzakala, Michael Jordan 

Publication date: 28 August 2020

Published in: The Annals of Statistics (Search for Journal in Brave)

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.

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

Recommendations

• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• Optimal signal detection in some spiked random matrix models: likelihood ratio tests and linear spectral statistics
• Statistical limits of spiked tensor models
• Limits of spiked random matrices. I
• Phase transition in random tensors with multiple independent spikes

zbMATH Keywords

hypothesis testingcontiguitySherrington-Kirkpatrick modelrandom matrix modelsspin-glassesreplica-symmetry

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Gaussian processes (60G15) Hypothesis testing in multivariate analysis (62H15) Central limit and other weak theorems (60F05)

Cites Work

• On the distribution of the largest eigenvalue in principal components analysis
• Eigenvalues of large sample covariance matrices of spiked population models
• Concentration inequalities. A nonasymptotic theory of independence
• On consistency and sparsity for principal components analysis in high dimensions
• Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
• Finite sample approximation results for principal component analysis: A matrix perturbation approach
• Some hypothesis tests for the covariance matrix when the dimension is large compared to the sample size
• Optimal detection of sparse principal components in high dimension
• Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization
• On sample eigenvalues in a generalized spiked population model
• Title not available (Why is that?)
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Signal detection in high dimension: the multispiked case
• Broken replica symmetry bounds in the mean field spin glass model
• Asymptotic power of sphericity tests for high-dimensional data
• Mean field models for spin glasses. Volume I: Basic examples.
• Some rigorous results on the Sherrington-Kirkpatrick spin glass model.
• The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations
• The largest eigenvalue of rank one deformation of large Wigner matrices
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• The largest eigenvalue of small rank perturbations of Hermitian random matrices
• Title not available (Why is that?)
• Statistical Physics of Spin Glasses and Information Processing
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Central limit theorems for eigenvalues in a spiked population model
• Deformed ensembles of random matrices
• Contiguity and non-reconstruction results for planted partition models: the dense case
• Fluctuations of the free energy of the spherical Sherrington-Kirkpatrick model with ferromagnetic interaction
• Superconcentration and related topics
• Fluctuations of the free energy of the spherical Sherrington-Kirkpatrick model
• Fundamental limits of symmetric low-rank matrix estimation
• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• Asymptotic mutual information for the balanced binary stochastic block model
• Sharp detection in PCA under correlations: all eigenvalues matter

Cited In (13)

• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Subexponential-time algorithms for sparse PCA
• The adaptive interpolation method for proving replica formulas. Applications to the Curie–Weiss and Wigner spike models
• Optimal signal detection in some spiked random matrix models: likelihood ratio tests and linear spectral statistics
• Rapid evaluation of the spectral signal detection threshold and Stieltjes transform
• Fundamental limits of symmetric low-rank matrix estimation
• High‐dimensional limit theorems for SGD: Effective dynamics and critical scaling
• The decimation scheme for symmetric matrix factorization
• Phase transition in random tensors with multiple independent spikes
• Free energy fluctuations of the two-spin spherical SK model at critical temperature
• High-dimensional asymptotics of Langevin dynamics in spiked matrix models
• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists

This page was built for publication: Fundamental limits of detection in the spiked Wigner model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196197)