A Smooth Computational Transition in Tensor PCA

Abstract

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\ge 3$ is a fixed integer, we show that when the signal-to-noise ratio is $\lambda n^{-\frac{p}{4}}$ where $\lambda =\Omega (1)$, our algorithm succeeds and runs in time $n^{C+o(1)}$ where $C=C(\lambda )$ is a constant depending on $\lambda$. This algorithm improves a poly-logarithmic factor compared to previous algorithms based on the Sum-of-Squares hierarchy \cite{HSS15} or based on the Kikuchi hierarchy in statistical physics \cite{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 \cite{KWB22}.

49 pages, 2 figures