Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications

Abstract

This article is an extended version of previous work of the authors [40, 41] on low-rank matrix estimation in the presence of constraints on the factors into which the matrix is factorized. Low-rank matrix factorization is one of the basic methods used in data analysis for unsupervised learning of relevant features and other types of dimensionality reduction. We present a framework to study the constrained low-rank matrix estimation for a general prior on the factors, and a general output channel through which the matrix is observed. We draw a paralel with the study of vector-spin glass models - presenting a unifying way to study a number of problems considered previously in separate statistical physics works. We present a number of applications for the problem in data analysis. We derive in detail a general form of the low-rank approximate message passing (Low- RAMP) algorithm, that is known in statistical physics as the TAP equations. We thus unify the derivation of the TAP equations for models as different as the Sherrington-Kirkpatrick model, the restricted Boltzmann machine, the Hopfield model or vector (xy, Heisenberg and other) spin glasses. The state evolution of the Low-RAMP algorithm is also derived, and is equivalent to the replica symmetric solution for the large class of vector-spin glass models. In the section devoted to result we study in detail phase diagrams and phase transitions for the Bayes-optimal inference in low-rank matrix estimation. We present a typology of phase transitions and their relation to performance of algorithms such as the Low-RAMP or commonly used spectral methods.

64 pages, 12 figures

References in corpus (5)

• Phase transition in the detection of modules in sparse networks
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Mean-field message-passing equations in the Hopfield model and its generalizations
• Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering

Cited by in corpus (39)

• Algorithmic thresholds for tensor PCA
• Statistical and computational phase transitions in spiked tensor estimation
• Typology of phase transitions in Bayesian inference problems
• Disordered Systems Insights on Computational Hardness
• Mean-field inference methods for neural networks
• Bilinear Recovery using Adaptive Vector-AMP
• Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference
• The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
• Linear stability analysis for large dynamical systems on directed random graphs
• Statistical limits of dictionary learning: random matrix theory and the spectral replica method
• Glassy nature of the hard phase in inference problems
• Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• Approximate Survey Propagation for Statistical Inference
• A Deterministic and Generalized Framework for Unsupervised Learning with Restricted Boltzmann Machines
• High-dimensional rank-one nonsymmetric matrix decomposition: the spherical case
• The Overlap Gap Property in Principal Submatrix Recovery
• Statistical mechanics of low-rank tensor decomposition
• Matrix denoising: Bayes-optimal estimators via low-degree polynomials
• Estimating rank-one matrices with mismatched prior and noise: universality and large deviations
• Spectral Method for Multiplexed Phase Retrieval and Application in Optical Imaging in Complex Media
• The effect of priors on Learning with Restricted Boltzmann Machines
• Bayes-Optimal Estimation in Generalized Linear Models via Spatial Coupling
• Thresholds of descending algorithms in inference problems
• Analyticity of the energy in an Ising spin glass with correlated disorder
• Approximate Message Passing with Rigorous Guarantees for Pooled Data and Quantitative Group Testing
• Neural-prior stochastic block model
• Bayesian reconstruction of memories stored in neural networks from their connectivity
• Low-rank Matrix Estimation with Inhomogeneous Noise
• Dense Limit of the Dawid-Skene Model for Crowdsourcing and Regions of Sub-optimality of Message Passing Algorithms
• The planted XY model: thermodynamics and inference
• Asymptotic mutual information in quadratic estimation problems over compact groups
• Large Deviations of Semi-supervised Learning in the Stochastic Block Model
• Some observations on the ambivalent role of symmetries in Bayesian inference problems
• Automatic Hyperparameter Tuning in Sparse Matrix Factorization
• Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
• Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block model
• Linear Operator Approximate Message Passing (OpAMP)
• Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions