Phase transitions and sample complexity in Bayes-optimal matrix factorization

Abstract

We analyse the matrix factorization problem. Given a noisy measurement of a product of two matrices, the problem is to estimate back the original matrices. It arises in many applications such as dictionary learning, blind matrix calibration, sparse principal component analysis, blind source separation, low rank matrix completion, robust principal component analysis or factor analysis. It is also important in machine learning: unsupervised representation learning can often be studied through matrix factorization. We use the tools of statistical mechanics - the cavity and replica methods - to analyze the achievability and computational tractability of the inference problems in the setting of Bayes-optimal inference, which amounts to assuming that the two matrices have random independent elements generated from some known distribution, and this information is available to the inference algorithm. In this setting, we compute the minimal mean-squared-error achievable in principle in any computational time, and the error that can be achieved by an efficient approximate message passing algorithm. The computation is based on the asymptotic state-evolution analysis of the algorithm. The performance that our analysis predicts, both in terms of the achieved mean-squared-error, and in terms of sample complexity, is extremely promising and motivating for a further development of the algorithm.

50 pages, 10 figures

References in corpus (8)

• An overview of low-rank matrix recovery from incomplete observations
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Adaptive Damping and Mean Removal for the Generalized Approximate Message Passing Algorithm
• Exact Recovery of Sparsely-Used Dictionaries
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• On Convergence of Approximate Message Passing
• Variational Free Energies for Compressed Sensing
• Local stability and robustness of sparse dictionary learning in the presence of noise

Cited by in corpus (51)

• Machine learning and the physical sciences
• An overview of low-rank matrix recovery from incomplete observations
• Statistical physics of inference: Thresholds and algorithms
• Bayes-Optimal Joint Channel-and-Data Estimation for Massive MIMO with Low-Precision ADCs
• Matrix-Calibration-Based Cascaded Channel Estimation for Reconfigurable Intelligent Surface Assisted Multiuser MIMO
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Parametric Bilinear Generalized Approximate Message Passing
• Finite Sample Analysis of Approximate Message Passing Algorithms
• Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding
• Mean-field inference methods for neural networks
• Super-Resolution Blind Channel-and-Signal Estimation for Massive MIMO with One-Dimensional Antenna Array
• Bilinear Recovery using Adaptive Vector-AMP
• Non-Convex Multi-species Hopfield models
• Multi-Layer Bilinear Generalized Approximate Message Passing
• Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
• Statistical limits of dictionary learning: random matrix theory and the spectral replica method
• Statistical Mechanics of High-Dimensional Inference
• Joint Device Activity Detection, Channel Estimation and Signal Detection for Massive Grant-free Access via BiGAMP
• A Note on Alternating Minimization Algorithm for the Matrix Completion Problem
• Matrix factorization with neural networks
• Deep learning via message passing algorithms based on belief propagation
• Non-negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
• Matrix denoising: Bayes-optimal estimators via low-degree polynomials
• Macroscopic Analysis of Vector Approximate Message Passing in a Model Mismatch Setting
• Semi-Blind Cascaded Channel Estimation for Reconfigurable Intelligent Surface Aided Massive MIMO
• Phase diagram of matrix compressed sensing
• Prediction Errors for Penalized Regressions based on Generalized Approximate Message Passing
• Streaming Bayesian inference: theoretical limits and mini-batch approximate message-passing
• An equivalence between high dimensional Bayes optimal inference and M-estimation
• On the TAP equations via the cavity approach in the generic mixed $p$-spin models
• Reconfigurable Intelligent Surface for Massive Connectivity
• Boolean Matrix Factorization and Noisy Completion via Message Passing
• Empirical Bayes PCA in high dimensions
• An Overview of Multi-Processor Approximate Message Passing
• Approximate Method of Variational Bayesian Matrix Factorization/Completion with Sparse Prior
• Generalized Approximate Survey Propagation for High-Dimensional Estimation
• Some observations on the ambivalent role of symmetries in Bayesian inference problems
• Approximate matrix completion based on cavity method
• Automatic Hyperparameter Tuning in Sparse Matrix Factorization
• Grant-Free Access via Bilinear Inference for Cell-Free MIMO with Low-Coherent Pilots
• Blind calibration for compressed sensing: State evolution and an online algorithm
• Construction of optimal spectral methods in phase retrieval
• Statistical mechanics of extensive-width Bayesian neural networks near interpolation
• Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolation
• Diagrammatics of free energies with fixed variance for high-dimensional data
• Universality of Approximate Message Passing Algorithms
• Statistical physics of deep learning: Optimal learning of a multi-layer perceptron near interpolation
• Replica Analysis for Generalized Linear Regression with IID Row Prior