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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [27 references]  Display  Hide  Download

https://hal-cea.archives-ouvertes.fr/cea-01555504
Contributor : Emmanuelle de Laborderie <>
Submitted on : Tuesday, July 4, 2017 - 11:28:30 AM
Last modification on : Thursday, March 21, 2019 - 1:20:51 PM

Links full text

Identifiers

  • 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. 2017. ⟨cea-01555504⟩

Share

Metrics

Record views

248