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.
Liste complète des métadonnées

Littérature citée [71 références]  Voir  Masquer  Télécharger
Contributeur : Emmanuelle De Laborderie <>
Soumis le : jeudi 26 janvier 2017 - 16:42:14
Dernière modification le : vendredi 4 janvier 2019 - 17:32:25
Document(s) archivé(s) le : vendredi 28 avril 2017 - 07:51:28


Fichiers produits par l'(les) auteur(s)


  • HAL Id : cea-01447222, version 1
  • ARXIV : 1701.00858


Thibault Lesieur, Florent Krzakala, Lenka Zdeborová. Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications. t17/011 64 pages, 12 figures. 2017. 〈cea-01447222〉



Consultations de la notice


Téléchargements de fichiers