{"ID":2871629,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.09904","arxiv_id":"2509.09904","title":"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 \\geq 3$ is a fixed integer, we show that when the signal-to-noise ratio is $λn^{-\\frac{p}{4}}$ where $λ=Ω(1)$, our algorithm succeeds and runs in time $n^{C+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 \\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}.","short_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 $λn^{-\\frac{p}{4}}$ where $λ=Ω(1)$, our algorithm succeeds and runs in time $n^{C+o(1)}$...","url_abs":"https://arxiv.org/abs/2509.09904","url_pdf":"https://arxiv.org/pdf/2509.09904v1","authors":"[\"Zhangsong Li\"]","published":"2025-09-12T00:21:20Z","proceeding":"math.ST","tasks":"[\"math.ST\",\"cs.DS\",\"math.PR\",\"stat.ML\"]","methods":"[]","has_code":false}