Statistical and computational phase transitions in spiked tensor estimation

Abstract

We consider tensor factorizations using a generative model and a Bayesian approach. We compute rigorously the mutual information, the Minimal Mean Squared 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.

17 pages, 3 figures, 1 table

References in corpus (2)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications

Cited by in corpus (17)

• What are higher-order networks?
• The adaptive interpolation method for proving replica formulas. Applications to the Curie-Weiss and Wigner spike models
• Estimation in the spiked Wigner model: A short proof of the replica formula
• Disordered Systems Insights on Computational Hardness
• Data-driven emergence of convolutional structure in neural networks
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• Phase transitions in the $q$-coloring of random hypergraphs
• Statistical mechanics of low-rank tensor decomposition
• Phase transition in random tensors with multiple independent spikes
• Classical and Quantum Algorithms for Tensor Principal Component Analysis
• Sparse random tensors: Concentration, regularization and applications
• Strong replica symmetry for high-dimensional disordered log-concave Gibbs measures
• Mutual information for low-rank even-order symmetric tensor estimation
• Streaming Bayesian inference: theoretical limits and mini-batch approximate message-passing
• On the free energy of vector spin glasses with non-convex interactions
• Efficient inference in stochastic block models with vertex labels
• Multilayer hypergraph clustering using the aggregate similarity matrix