arXiv:2509.09904v1 Announce Type: cross
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 geq 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}.