"Tensor PCA", also known as the "spiked tensor model", is a simple statistical model for tensor-valued data wherein we seek to recover an unknown rank-1 tensor that has been corrupted by additive Gaussian noise. A striking feature of this model is that many "standard" out-of-the-box algorithms such as gradient descent and belief propagation are known to give sub-optimal performance; more sophisticated spectral methods and sum-of-squares can tolerate much lower signal-to-noise ratios (SNR).
In an attempt to "redeem" the belief propagation (BP) approach, we propose and analyze a new hierarchy of "higher-order" BP-type algorithms inspired by the "Kikuchi free energy" from statistical physics. Our algorithms and analysis are simpler than prior work while matching the best known tradeoff between runtime and SNR (achieved by sum-of-squares).
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.
Based on joint work with Ahmed El Alaoui and Cris Moore, available at https://arxiv.org/abs/1904.03858
Copyright. All Rights Reserved.