Optimality and sub-optimality of PCA. I: Spiked random matrix models

DOI10.1214/17-AOS1625zbMath1404.62065arXiv1807.00891WikidataQ129368170 ScholiaQ129368170MaRDI QIDQ1800806

Alexander S. Wein, Amelia Perry, Ankur Moitra, Afonso S. Bandeira

Publication date: 24 October 2018

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

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

zbMATH Keywords

principal component analysishypothesis testingphase transitionrandom matrixcontiguitypower envelopespiked covariancedeformed Wigner modelGaussian Wigner model

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Hypothesis testing in multivariate analysis (62H15) Random matrices (probabilistic aspects) (60B20)

Related Items (38)

Free energy fluctuations of the two-spin spherical SK model at critical temperature ⋮ Iterative algorithm for discrete structure recovery ⋮ Statistical inference for principal components of spiked covariance matrices ⋮ An extension of the angular synchronization problem to the heterogeneous setting ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods ⋮ Lower bounds for invariant statistical models with applications to principal component analysis ⋮ Strong replica symmetry in high-dimensional optimal Bayesian inference ⋮ Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method ⋮ An information-percolation bound for spin synchronization on general graphs ⋮ Statistical thresholds for tensor PCA ⋮ Statistical limits of spiked tensor models ⋮ Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis ⋮ Free energy subadditivity for symmetric random Hamiltonians ⋮ A unified approach to synchronization problems over subgroups of the orthogonal group ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fundamental limits of detection in the spiked Wigner model ⋮ Entrywise eigenvector analysis of random matrices with low expected rank ⋮ The noise-sensitivity phase transition in spectral group synchronization over compact groups ⋮ Spiked multiplicative random matrices and principal components ⋮ Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method ⋮ Long random matrices and tensor unfolding ⋮ High‐dimensional limit theorems for SGD: Effective dynamics and critical scaling ⋮ A CLT for the LSS of large-dimensional sample covariance matrices with diverging spikes ⋮ Notes on computational-to-statistical gaps: predictions using statistical physics ⋮ TAP free energy, spin glasses and variational inference ⋮ Uniform Bounds for Invariant Subspace Perturbations ⋮ Near-Optimal Bounds for Phase Synchronization ⋮ Fundamental limits of symmetric low-rank matrix estimation ⋮ Phase transition in random tensors with multiple independent spikes ⋮ Sparse equisigned PCA: algorithms and performance bounds in the noisy rank-1 setting ⋮ Random matrix theory and its applications ⋮ Phase transition in the spiked random tensor with Rademacher prior ⋮ Algorithmic thresholds for tensor PCA ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ A Unifying Tutorial on Approximate Message Passing ⋮ Bose–Einstein-like condensation of deformed random matrix: a replica approach

Cites Work

• Sparse principal component analysis and iterative thresholding
• Minimax bounds for sparse PCA with noisy high-dimensional data
• Asymptotic power of sphericity tests for high-dimensional data
• Optimal detection of sparse principal components in high dimension
• Detection of correlations
• Reconstruction and estimation in the planted partition model
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• Angular synchronization by eigenvectors and semidefinite programming
• Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
• The largest eigenvalue of small rank perturbations of Hermitian random matrices
• Community detection in sparse random networks
• Finite sample approximation results for principal component analysis: A matrix perturbation approach
• The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations
• Spectral analysis of large dimensional random matrices
• Entropy and the central limit theorem
• On the distribution of the largest eigenvalue in principal components analysis
• Broken replica symmetry bounds in the mean field spin glass model
• Higher criticism for detecting sparse heterogeneous mixtures.
• On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix
• Consistency of sparse PCA in high dimension, low sample size contexts
• On finite rank deformations of Wigner matrices
• Detection boundary in sparse regression
• Optimal estimation and rank detection for sparse spiked covariance matrices
• Computational barriers in minimax submatrix detection
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Sharp detection in PCA under correlations: all eigenvalues matter
• Detection of an anomalous cluster in a network
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Sparse PCA: optimal rates and adaptive estimation
• Signal detection in high dimension: the multispiked case
• The largest eigenvalue of rank one deformation of large Wigner matrices
• Estimation and confidence sets for sparse normal mixtures
• Eigenvalues of large sample covariance matrices of spiked population models
• Community detection in dense random networks
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Nonconvex Phase Synchronization
• Sparse PCA via Covariance Thresholding
• Phase transitions in semidefinite relaxations
• Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
• An Introduction to Random Matrices
• Almost all regular graphs are hamiltonian
• Forecasting Using Principal Components From a Large Number of Predictors
• Asymptotic mutual information for the balanced binary stochastic block model
• Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Cramer-Rao bounds for synchronization of rotations
• Random matrices: The Universality phenomenon for Wigner ensembles
• On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• The Generalized Dynamic Factor Model
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Optimality and sub-optimality of PCA. I: Spiked random matrix models