Statistical and computational phase transitions in spiked tensor estimation - Archive ouverte HAL Access content directly
Conference Papers Year :

Statistical and computational phase transitions in spiked tensor estimation

(1) , (2) , (2) , (3) , (1)
1
2
3

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.
Fichier principal
Vignette du fichier
Lesie1.pdf (710.82 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

cea-01555504 , version 1 (18-10-2022)

Identifiers

Cite

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⟩
226 View
1 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More