The Kikuchi Hierarchy and Tensor PCA
  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-$\ell$ algorithm
can be thought of as a linearized message-passing algorithm that keeps track of
$\ell$-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.
