{
  "id": "1904.03858",
  "version": "v1",
  "published": "2019-04-08T06:26:35.000Z",
  "updated": "2019-04-08T06:26:35.000Z",
  "title": "The Kikuchi Hierarchy and Tensor PCA",
  "authors": [
    "Alexander S. Wein",
    "Ahmed El Alaoui",
    "Cristopher Moore"
  ],
  "comment": "34 pages",
  "categories": [
    "cs.DS",
    "cs.LG",
    "stat.ML"
  ],
  "abstract": "For the tensor PCA (principal component analysis) problem, we propose a new hierarchy of algorithms that are increasingly powerful yet require 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 matrix, which generalizes the well-studied Bethe Hessian matrix 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 results hold for even-order tensors, and we conjecture that they also hold for odd-order tensors. 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-04-08T06:26:35.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68Q87",
      "F.2.2"
    ],
    "keywords": [
      "tensor pca",
      "kikuchi hierarchy",
      "statistical physics",
      "higher-order kikuchi free energies",
      "well-studied bethe hessian matrix"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 34,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}