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)

1 IPHT - Institut de Physique Théorique - UMR CNRS 3681
2 DYOGENE - Dynamics of Geometric Networks
3 LPS - Laboratoire de Physique Statistique de l'ENS

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.

Domains: Statistics Theory [stat.TH]; Information Theory [math.IT]

Thibault Lesieur, Léo Miolane, Marc Lelarge, Florent Krzakala, Lenka Zdeborová. Statistical and computational phase transitions in spiked tensor estimation. ISIT 2017 - IEEE International Symposium on Information Theory, Jun 2017, Aachen, Germany. pp.511 - 515, ⟨10.1109/ISIT.2017.8006580⟩. ⟨cea-01555504⟩