mlsanityData to 14 Oct 2026

A Smooth Computational Transition in Tensor PCA

arXiv 2509.09904 ↗First posted 12 Sep 2025math.ST cs.DS math.PRcited by 0

Not on the map. Why?

Abstract (arXiv)

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^-fracp4 where λ=Omega(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 citeHSS15 or based on the Kikuchi hierarchy in statistical physics citeWEM19. 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 citeKWB22.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 29 of its 49 references that are in the map. First posted on arXiv 12 Sep 2025.

Builds on

29 of 49 references.

References · 29

  1. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 85
  2. 2014A statistical model for tensor PCAcited by 72
  3. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  4. 2020Reducibility and Statistical-Computational Gaps from Secret Leakagecited by 51
  5. 2013Community detection thresholds and the weak Ramanujan propertycited by 47
  6. 2019Subexponential-Time Algorithms for Sparse PCAcited by 41
  7. 2020Computational Barriers to Estimation from Low-Degree Polynomialscited by 39
  8. 2013A Proof Of The Block Model Threshold Conjecturecited by 36
  9. 2015Tensor principal component analysis via sum-of-squares proofscited by 35
  10. 2022The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statisticscited by 31
  11. 2019Computational Hardness of Certifying Bounds on Constrained PCA Problemscited by 30
  12. 2015Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphscited by 26
17 more
  1. 2014Testing for high-dimensional geometry in random graphscited by 25
  2. 2022Random graph matching at Otter's threshold via counting chandelierscited by 25
  3. 2021Testing network correlation efficiently via counting treescited by 22
  4. 2021Optimal Spectral Recovery of a Planted Vector in a Subspacecited by 21
  5. 2020Optimal Low-Degree Hardness of Maximum Independent Setcited by 16
  6. 2019The Kikuchi Hierarchy and Tensor PCAcited by 15
  7. 2021The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomialscited by 14
  8. 2017Optimal hypothesis testing for stochastic block models with growing degreescited by 13
  9. 2023Low-Degree Hardness of Detection for Correlated ErdHos-R'enyi Graphscited by 11
  10. 2016Average-case Hardness of RIP Certificationcited by 10
  11. 2024Tensor cumulants for statistical inference on invariant distributionscited by 8
  12. 2020Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamicscited by 7
  13. 2023Detection of Dense Subhypergraphs by Low-Degree Polynomialscited by 7
  14. 2024A computational transition for detecting correlated stochastic block models by low-degree polynomialscited by 6
  15. 2024Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphscited by 4
  16. 2025Randomstrasse101: Open Problems of 2024cited by 3
  17. 2024Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphscited by 2

Built on by

Not cited yet.