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.

Intro
High-Dimensional Statistics
Statistical Physics of Inference
Sum of Squares (Sos) Hierarchy
Tensor PCA (Principal Component Analysis)
Algorithms for Tensor PCA
Subexponential Time Algorithms
Aside Low Degree Likelihood Ratio
Our Contributions
The Algorithm
Intuition for Symmetric Difference Matric
Related Work
Summary