Tensor principal component analysis is a problem of high-dimensional estimation known to exhibit a diverging information-computation gap, where the performance of the best known polynomial-time algorithms is a far distance away from what is information-theoretically possible.    

Within the so-called random spiked tensor model, the Sum of Squares hierarchy together with spectral algorithms derived from it, is able to achieve a very precise, and currently best known, tradeoff between runtime and statistical power for this problem. 

In this talk I will describe a hierarchy of spectral algorithms based on a radically different paradigm originating from variational inference, which happens to achieve the exact same tradeoff as the SOS hierarchy. The random matrices involved in this algorithm are simpler to analyze due to their special algebraic-combinatorial structure relating to the Bose-Mesner algebra. These matrices hint at an interesting random matrix model, which may be worthy of study for its own sake. 

This is based on joint work with Cris Moore and Alex Wein.