The Kikuchi Hierarchy and Tensor PCA

Explore a conference talk on tensor PCA and the Kikuchi hierarchy, delving into advanced statistical methods for analyzing tensor-valued data. Learn about the challenges of recovering rank-1 tensors corrupted by Gaussian noise and discover why traditional algorithms like gradient descent and belief propagation underperform in this context. Examine a new hierarchy of higher-order belief propagation algorithms inspired by the Kikuchi free energy concept from statistical physics. Understand how these novel approaches match the best-known tradeoffs between runtime and signal-to-noise ratio, rivaling sum-of-squares methods. Gain insights into the potential for unifying statistical physics and sum-of-squares approaches in algorithm design, and explore the implications for optimal Bayesian inference algorithms. Follow the speaker's journey through high-dimensional statistics, statistical physics of inference, tensor PCA, and subexponential time algorithms, concluding with a summary of contributions and related work in this cutting-edge field of mathematical and computational research.