Estimation of low-rank matrices via approximate message passing

DOI10.1214/20-AOS1958zbMATH Open1461.62070arXiv1711.01682MaRDI QIDQ2656598FDOQ2656598

Authors: Yanyan Li 

Publication date: 11 March 2021

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

Abstract: Consider the problem of estimating a low-rank matrix when its entries are perturbed by Gaussian noise. If the empirical distribution of the entries of the spikes is known, optimal estimators that exploit this knowledge can substantially outperform simple spectral approaches. Recent work characterizes the asymptotic accuracy of Bayes-optimal estimators in the high-dimensional limit. In this paper we present a practical algorithm that can achieve Bayes-optimal accuracy above the spectral threshold. A bold conjecture from statistical physics posits that no polynomial-time algorithm achieves optimal error below the same threshold (unless the best estimator is trivial). Our approach uses Approximate Message Passing (AMP) in conjunction with a spectral initialization. AMP algorithms have proved successful in a variety of statistical estimation tasks, and are amenable to exact asymptotic analysis via state evolution. Unfortunately, state evolution is uninformative when the algorithm is initialized near an unstable fixed point, as often happens in low-rank matrix estimation. We develop a new analysis of AMP that allows for spectral initializations. Our main theorem is general and applies beyond matrix estimation. However, we use it to derive detailed predictions for the problem of estimating a rank-one matrix in noise. Special cases of this problem are closely related---via universality arguments---to the network community detection problem for two asymmetric communities. For general rank-one models, we show that AMP can be used to construct confidence intervals and control false discovery rate. We provide illustrations of the general methodology by considering the cases of sparse low-rank matrices and of block-constant low-rank matrices with symmetric blocks (we refer to the latter as to the `Gaussian Block Model').

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

Recommendations

• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• Fundamental limits of symmetric low-rank matrix estimation
• Iterative reconstruction of rank-one matrices in noise
• Universality of approximate message passing algorithms
• Approximate message passing algorithms for rotationally invariant matrices

zbMATH Keywords

low-rank matrix estimationapproximate message passingspectral initialization

Mathematics Subject Classification ID

Bayesian inference (62F15) Asymptotic distribution theory in statistics (62E20) Estimation in multivariate analysis (62H12) Random matrices (probabilistic aspects) (60B20) Inference from stochastic processes and spectral analysis (62M15)

Cites Work

• Title not available (Why is that?)
• Spectral analysis of large dimensional random matrices
• On the distribution of the largest eigenvalue in principal components analysis
• Eigenvalues of large sample covariance matrices of spiked population models
• Generalized power method for sparse principal component analysis
• Community detection and stochastic block models: recent developments
• A Direct Approach to False Discovery Rates
• On consistency and sparsity for principal components analysis in high dimensions
• Truncated power method for sparse eigenvalue problems
• Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
• Markov chain Monte Carlo. Stochastic simulation for Bayesian inference.
• Optimal Transport
• The singular values and vectors of low rank perturbations of large rectangular random matrices
• Minimax risk over \(l_ p\)-balls for \(l_ q\)-error
• Sparse principal component analysis and iterative thresholding
• Large-scale inference. Empirical Bayes methods for estimation, testing, and prediction
• Learning the parts of objects by non-negative matrix factorization
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Minimax estimation via wavelet shrinkage
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Title not available (Why is that?)
• 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 isotropic semicircle law and deformation of Wigner matrices
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• Mutual Information and Minimum Mean-Square Error in Gaussian Channels
• Universality in polytope phase transitions and message passing algorithms
• Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Learning Theory
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• Fundamental limits of symmetric low-rank matrix estimation
• Phase transitions in semidefinite relaxations
• The projected power method: an efficient algorithm for joint alignment from pairwise differences
• Iterative reconstruction of rank-one matrices in noise
• Asymptotic mutual information for the balanced binary stochastic block model
• Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Bilinear Generalized Approximate Message Passing—Part I: Derivation
• Phase Transitions and Sample Complexity in Bayes-Optimal Matrix Factorization
• State evolution for approximate message passing with non-separable functions

Cited In (28)

• Approximate message passing with spectral initialization for generalized linear models*
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• A Unifying Tutorial on Approximate Message Passing
• Approximate message passing algorithms for rotationally invariant matrices
• State evolution for approximate message passing with non-separable functions
• Von Neumann entropy penalization and low-rank matrix estimation
• Fundamental limits of symmetric low-rank matrix estimation
• Fundamental limits of weak recovery with applications to phase retrieval
• Approximate Message Passing With Consistent Parameter Estimation and Applications to Sparse Learning
• Iterative reconstruction of rank-one matrices in noise
• Computational barriers to estimation from low-degree polynomials
• Universality of approximate message passing algorithms and tensor networks
• The decimation scheme for symmetric matrix factorization
• Fundamental limits of low-rank matrix estimation with diverging aspect ratios
• Universality of approximate message passing algorithms
• Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
• Approximate message passing with rigorous guarantees for pooled data and quantitative group testing
• On convergence of the cavity and Bolthausen's TAP iterations to the local magnetization
• On the TAP equations via the cavity approach in the generic mixed \(p\)-spin models
• Approximate message passing for orthogonally invariant ensembles: multivariate non-linearities and spectral initialization
• Statistically optimal firstorder algorithms: a proof via orthogonalization
• Submatrix localization via message passing
• Generalized TAP Free Energy
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Estimation of high-dimensional low-rank matrices
• Optimal combination of linear and spectral estimators for generalized linear models
• Universality of approximate message passing with semirandom matrices
• A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists

This page was built for publication: Estimation of low-rank matrices via approximate message passing

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