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
DI-ENS - Département d'informatique - ENS Paris, 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.
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 : Wednesday, June 8, 2022 - 12:50:03 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