Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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
Inria de Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, DI-ENS - Département d'informatique de l'École normale supérieure
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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Emmanuelle de Laborderie Connect in order to contact the contributor
Submitted on : Tuesday, July 4, 2017 - 11:28:30 AM
Last modification on : Friday, October 15, 2021 - 1:41:13 PM

Links full text


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


Thibault Lesieur, Léo Miolane, Marc Lelarge, Florent Krzakala, Lenka Zdeborová. Statistical and computational phase transitions in spiked tensor estimation. 2017. ⟨cea-01555504⟩



Record views