Estimation of low-rank matrices via approximate message passing
From MaRDI portal
Publication:2656598
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').
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
Cites work
- A Direct Approach to False Discovery Rates
- Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising
- An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
- Asymptotic mutual information for the balanced binary stochastic block model
- Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
- Bilinear Generalized Approximate Message Passing—Part I: Derivation
- Community detection and stochastic block models: recent developments
- Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
- Eigenvalues of large sample covariance matrices of spiked population models
- Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
- Fundamental limits of symmetric low-rank matrix estimation
- Generalized power method for sparse principal component analysis
- scientific article; zbMATH DE number 720689 (Why is no real title available?)
- scientific article; zbMATH DE number 5204610 (Why is no real title available?)
- Iterative reconstruction of rank-one matrices in noise
- Large-scale inference. Empirical Bayes methods for estimation, testing, and prediction
- Learning the parts of objects by non-negative matrix factorization
- Learning Theory
- Markov chain Monte Carlo. Stochastic simulation for Bayesian inference.
- Minimax estimation via wavelet shrinkage
- Minimax risk over \(l_ p\)-balls for \(l_ q\)-error
- Mutual Information and Minimum Mean-Square Error in Gaussian Channels
- Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
- On consistency and sparsity for principal components analysis in high dimensions
- On the distribution of the largest eigenvalue in principal components analysis
- Optimal Transport
- Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
- Phase Transitions and Sample Complexity in Bayes-Optimal Matrix Factorization
- Phase transitions in semidefinite relaxations
- Sparse principal component analysis and iterative thresholding
- Spectral analysis of large dimensional random matrices
- State evolution for approximate message passing with non-separable functions
- State evolution for general approximate message passing algorithms, with applications to spatial coupling
- The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
- The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
- The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
- The isotropic semicircle law and deformation of Wigner matrices
- 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
- The projected power method: an efficient algorithm for joint alignment from pairwise differences
- The singular values and vectors of low rank perturbations of large rectangular random matrices
- Truncated power method for sparse eigenvalue problems
- Universality in polytope phase transitions and message passing algorithms
Cited in
(42)- Fundamental limits of symmetric low-rank matrix estimation
- Universality of approximate message passing algorithms
- On convergence of the cavity and Bolthausen's TAP iterations to the local magnetization
- Optimal combination of linear and spectral estimators for generalized linear models
- Approximate message passing algorithms for rotationally invariant matrices
- Computational barriers to estimation from low-degree polynomials
- Fundamental limits of weak recovery with applications to phase retrieval
- Approximate Message Passing With Consistent Parameter Estimation and Applications to Sparse Learning
- Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
- Von Neumann entropy penalization and low-rank matrix estimation
- Submatrix localization via message passing
- State evolution for approximate message passing with non-separable functions
- Approximate message passing with spectral initialization for generalized linear models*
- Iterative reconstruction of rank-one matrices in noise
- Estimation of high-dimensional low-rank matrices
- Estimation of (near) low-rank matrices with noise and high-dimensional scaling
- A Unifying Tutorial on Approximate Message Passing
- Generalized TAP Free Energy
- A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists
- Universality of approximate message passing with semirandom matrices
- Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
- The decimation scheme for symmetric matrix factorization
- On the TAP equations via the cavity approach in the generic mixed \(p\)-spin models
- Universality of approximate message passing algorithms and tensor networks
- Fundamental limits of low-rank matrix estimation with diverging aspect ratios
- Approximate message passing with rigorous guarantees for pooled data and quantitative group testing
- Approximate message passing for orthogonally invariant ensembles: multivariate non-linearities and spectral initialization
- Statistically optimal firstorder algorithms: a proof via orthogonalization
- Optimality of approximate message passing for spiked matrix models with rotationally invariant noise
- Linear operator approximate message passing (OpAMP)
- Approximate message passing for general non-symmetric random matrices
- Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models
- Rectangular rotational invariant estimator for high-rank matrix estimation
- Spectral estimators for structured generalized linear models via approximate message passing
- A leave-one-out approach to approximate message passing
- Precise error rates for computationally efficient testing
- Deflated HeteroPCA: overcoming the curse of ill-conditioning in heteroskedastic PCA
- Equivalence of approximate message passing and low-degree polynomials in rank-one matrix estimation
- Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions
- Uncertainty quantification for iterative algorithms in linear models with application to early stopping
- A nonasymptotic distributional theory of approximate message passing for sparse and robust regression
- Optimal recovery of correlated Erdős-Rényi graphs
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)
