Phase Transitions and Sample Complexity in Bayes-Optimal Matrix Factorization
From MaRDI portal
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.
Cited in
(24)- Non-convex multi-species Hopfield models
- Universality of approximate message passing algorithms
- Fundamental limits of weak recovery with applications to phase retrieval
- Estimation of low-rank matrices via approximate message passing
- Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
- Approximate method of variational Bayesian matrix factorization/completion with sparse prior
- Approximate message passing with spectral initialization for generalized linear models*
- Mean-field inference methods for neural networks
- Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
- Generalized approximate survey propagation for high-dimensional estimation *
- A Unifying Tutorial on Approximate Message Passing
- Approximate matrix completion based on cavity method
- Prediction errors for penalized regressions based on generalized approximate message passing
- Generalized TAP Free Energy
- The decimation scheme for symmetric matrix factorization
- On the TAP equations via the cavity approach in the generic mixed \(p\)-spin models
- Matrix denoising: Bayes-optimal estimators via low-degree polynomials
- Optimality of approximate message passing for spiked matrix models with rotationally invariant noise
- Rectangular rotational invariant estimator for high-rank matrix estimation
- A leave-one-out approach to approximate message passing
- Sparse representations, inference and learning
- Diagrammatics of free energies with fixed variance for high-dimensional data
- Graphical model for factorization and completion of relatively high rank tensors by sparse sampling
- Overlap gap and computational thresholds in the square wave perceptron
This page was built for publication: Phase Transitions and Sample Complexity in Bayes-Optimal Matrix Factorization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976727)
