Statistical and computational phase transitions in spiked tensor estimation
Thibault Lesieur†, Léo Miolane◇, Marc Lelarge◇, Florent Krzakala⋆、Lenka Zdeborová†
Abstract
We consider tensor factorization 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.
中文速览
低秩张量（low-rank tensor）分解在信号处理和机器学习中应用广泛，但人们一直不清楚它在统计上究竟能做到多好、现有算法又能做到哪一步。这篇论文在贝叶斯框架下，对带噪声的尖峰张量（spiked tensor）模型进行了严格的理论分析，推导出了互信息（mutual information）和最小均方误差（MMSE）的精确公式，并刻画出信息论和计算两个层面的相变边界。研究发现，当先验分布均值非零时，近似消息传递算法（Approximate Message Passing, AMP）能够在比以往认为大得多的参数范围内达到贝叶斯最优，"困难区域"（hard phase）因此大幅收缩，张量分解在实践中远没有此前所估计的那么难；但仍存在一个困难区域，AMP 无法在其中达到 MMSE，作者猜想任何多项式时间算法都无法在该区域超越 AMP。这一结果首次为一般秩、一般先验和一般噪声信道的张量估计问题提供了严格的信息论基准，厘清了统计极限与计算极限之间的差距。
原文 arXiv:1701.08010;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1701.08010v2