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 n , 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

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 [SOKB25]. It was first conjectured by [WAM19] and then, more recently, with an eye on smooth trade-offs, reiterated in a blogpost of Bandeira [Ban24b,Ban24a].

In this work, we resolve these conjectures and show that spectral algorithms based on the Kikuchi hierarchy

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 [BCSvH24].

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 [BCSvH24] to work when ℓ grows beyond a fixed constant.