Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices

In this work, we revisit algorithms for Tensor PCA: given an order-r tensor of the form T = G + λ · v^⊗r where G is a random symmetric Gaussian tensor with unit variance entries and v is an unknown boolean vector in {±1}ⁿ, what’s the minimum λ at which one can distinguish T from a random Gaussian tensor and more generally, recover v? As a result of a long line of work, we know that for any ℓ ∈ N, there is a n^O(ℓ) time algorithm that succeeds when the signal strength λ ≳ √log n · n^−r/4 · ℓ¹/^2−r/4. The question of whether the logarithmic factor is necessary turns out to be crucial to understanding whether larger polynomial time allows recovering the signal at a lower signal strength. Such a smooth trade-off is necessary for tensor PCA being a candidate problem for quantum speedups. It was first conjectured and then, more recently, with an eye on smooth trade-offs, reiterated in a blogpost of Bandeira. In this work, we resolve these conjectures and show that spectral algorithms based on the Kikuchi hierarchy succeed whenever λ ≥ Θ_r(1) · n^−r/4 · ℓ^1/2-r/4 where Θ_r(1) only hides an absolute constant independent of n and ℓ. A sharp bound such as this was previously known only for ℓ ≤ 3r/4 via non-asymptotic techniques in random matrix theory inspired by free probability. Our main technical contribution is a new framework for proving spectral norm bounds on Kikuchi matrices that are tight up to an absolute constant. Along the way to our result, we also confirm a suspicion that Kikuchi matrices are, in general, not intrinsically free – a property necessary for the free probability-inspired techniques to work when ℓ grows beyond a fixed constant.