Statistical and computational phase transitions in spiked tensor estimation

Thibault Lesieur 1 Léo Miolane 2 Marc Lelarge 2 Florent Krzakala 3 Lenka Zdeborová 1
2 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
Abstract : We consider tensor factorizations using a generative model and a Bayesian approach. We compute rigorously the mutual information, the Minimal Mean Square Error (MMSE), and unveil information-theoretic phase transitions. In addition, we study the performance of Approximate Message Passing (AMP) and show that it achieves the MMSE for a large set of parameters, and that factorization is algorithmically "easy" in a much wider region than previously believed. It exists, however, a "hard" region where AMP fails to reach the MMSE and we conjecture that no polynomial algorithm will improve on AMP.
Type de document :
Pré-publication, Document de travail
t17/108. 8 pages, 3 figures, 1 table. 2017
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal-cea.archives-ouvertes.fr/cea-01555504
Contributeur : Emmanuelle De Laborderie <>
Soumis le : mardi 4 juillet 2017 - 11:28:30
Dernière modification le : mercredi 30 mai 2018 - 01:20:35

Lien texte intégral

Identifiants

  • HAL Id : cea-01555504, version 1
  • ARXIV : 1701.08010

Citation

Thibault Lesieur, Léo Miolane, Marc Lelarge, Florent Krzakala, Lenka Zdeborová. Statistical and computational phase transitions in spiked tensor estimation. t17/108. 8 pages, 3 figures, 1 table. 2017. 〈cea-01555504〉

Partager

Métriques

Consultations de la notice

184