A Smooth Computational Transition in Tensor PCA

We propose an efficient algorithm for tensor PCA based on counting a specific family of weighted hypergraphs. For the order-p tensor PCA problem where p ≥ 3 is a fixed integer, we show that when the signal-to-noise ratio is λn-p/4 where $λ=Ω(1)$, our algorithm succeeds and runs in time nC+o(1) where $C=C(λ)$ is a constant depending on $λ$. This algorithm improves a poly-logarithmic factor compared to previous algorithms based on the Sum-of-Squares hierarchy {HSS15} or based on the Kikuchi hierarchy in statistical physics {WEM19}. Furthermore, our result shows a smooth tradeoff between the signal-to-noise ratio and the computational cost in this problem, thereby confirming a conjecture posed in {KWB22}.