Title | ||
---|---|---|
Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications. |
Abstract | ||
---|---|---|
This article is an extended version of previous work of Lesieur et al (2015 IEEE Int. Symp. on Information Theory Proc. pp 1635-9 and 2015 53rd Annual Allerton Conf. on Communication, Control and Computing (IEEE) pp 680-7) 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 parallel 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 di. erent 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 Bayesoptimal 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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1088/1742-5468/aa7284 | JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT |
Keywords | Field | DocType |
analysis of algorithms,message-passing algorithms,statistical inference,cavity and replica method | Restricted Boltzmann machine,Dimensionality reduction,Quantum mechanics,Matrix (mathematics),Matrix decomposition,Algorithm,Low-rank approximation,Spectral method,State-transition matrix,Mathematics,Message passing | Journal |
Volume | ISSN | Citations |
abs/1701.00858 | 1742-5468 | 6 |
PageRank | References | Authors |
0.55 | 22 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Thibault Lesieur | 1 | 42 | 2.63 |
Florent Krzakala | 2 | 977 | 67.30 |
Lenka Zdeborová | 3 | 1190 | 78.62 |