Phase Transitions and Sample Complexity in Bayes-Optimal Matrix Factorization

DOI10.1109/TIT.2016.2556702MaRDI QIDQ2976727zbMATH OpenOpenAlexWikidataFDO

Authors Yoshiyuki Kabashima, Florent Krzakala, Marc Mézard, Ayaka Sakata, Lenka Zdeborová

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

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

(22)

• Generalized approximate survey propagation for high-dimensional estimation ^*
• Approximate message passing with spectral initialization for generalized linear models*
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• Non-convex multi-species Hopfield models
• Approximate method of variational Bayesian matrix factorization/completion with sparse prior
• Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
• A Unifying Tutorial on Approximate Message Passing
• Fundamental limits of weak recovery with applications to phase retrieval
• Mean-field inference methods for neural networks
• Sparse representations, inference and learning
• Diagrammatics of free energies with fixed variance for high-dimensional data
• Universality of approximate message passing algorithms
• The decimation scheme for symmetric matrix factorization
• Optimality of approximate message passing for spiked matrix models with rotationally invariant noise
• Matrix denoising: Bayes-optimal estimators via low-degree polynomials
• On the TAP equations via the cavity approach in the generic mixed \(p\)-spin models
• Prediction errors for penalized regressions based on generalized approximate message passing
• Approximate matrix completion based on cavity method
• A leave-one-out approach to approximate message passing
• Rectangular rotational invariant estimator for high-rank matrix estimation
• Generalized TAP Free Energy
• Estimation of low-rank matrices via approximate message passing

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)