# The Kikuchi Hierarchy and Tensor PCA

arXiv: https://arxiv.org/abs/1904.03858 · HTML: https://mlsanity.com/paper/1904.03858/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Apr 2019.

## Built on by (most cited first, 15 of 15)

- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Tensor cumulants for statistical inference on invariant distributions](https://mlsanity.com/paper/2404.18735/) (2024)
- [Optimal Spectral Transitions in High-Dimensional Multi-Index Models](https://mlsanity.com/paper/2502.02545/) (2025)
- [On free energy barriers in Gaussian priors and failure of cold start MCMC for high-dimensional unimodal distributions](https://mlsanity.com/paper/2209.02001/) (2022)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Semidefinite programs simulate approximate message passing robustly](https://mlsanity.com/paper/2311.09017/) (2023)
- [Computational Thresholds in Multi-Modal Learning via the Spiked Matrix-Tensor Model](https://mlsanity.com/paper/2506.02664/) (2025)
- [Over-parametrization via Lifting for Low-rank Matrix Sensing: Conversion of Spurious Solutions to Strict Saddle Points](https://mlsanity.com/paper/2302.07828/) (2023)
- [Community detection with the Bethe-Hessian](https://mlsanity.com/paper/2411.02835/) (2024)
- [Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models](https://mlsanity.com/paper/2412.21155/) (2024)
- [Selective Multiple Power Iteration: from Tensor PCA to gradient-based exploration of landscapes](https://mlsanity.com/paper/2112.12306/) (2021)
- [A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs](https://mlsanity.com/paper/2204.10881/) (2022)
- [Overcomplete Tensor Decomposition via Koszul-Young Flattenings](https://mlsanity.com/paper/2411.14344/) (2024)
- [Permutation recovery of spikes in noisy high-dimensional tensor estimation](https://mlsanity.com/paper/2412.14650/) (2024)
- [A Smooth Computational Transition in Tensor PCA](https://mlsanity.com/paper/2509.09904/) (2025)

## Abstract (arXiv)

For the tensor PCA (principal component analysis) problem, we propose a new hierarchy of increasingly powerful algorithms with increasing runtime. Our hierarchy is analogous to the sum-of-squares (SOS) hierarchy but is instead inspired by statistical physics and related algorithms such as belief propagation and AMP (approximate message passing). Our level-ℓ algorithm can be thought of as a linearized message-passing algorithm that keeps track of ℓ-wise dependencies among the hidden variables. Specifically, our algorithms are spectral methods based on the Kikuchi Hessian, which generalizes the well-studied Bethe Hessian to the higher-order Kikuchi free energies. It is known that AMP, the flagship algorithm of statistical physics, has substantially worse performance than SOS for tensor PCA. In this work we 'redeem' the statistical physics approach by showing that our hierarchy gives a polynomial-time algorithm matching the performance of SOS. Our hierarchy also yields a continuum of subexponential-time algorithms, and we prove that these achieve the same (conjecturally optimal) tradeoff between runtime and statistical power as SOS. Our proofs are much simpler than prior work, and also apply to the related problem of refuting random k-XOR formulas. The results we present here apply to tensor PCA for tensors of all orders, and to k-XOR when k is even. Our methods suggest a new avenue for systematically obtaining optimal algorithms for Bayesian inference problems, and our results constitute a step toward unifying the statistical physics and sum-of-squares approaches to algorithm design.