Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials

Suppose we are given an n-dimensional order-3 symmetric tensor T ∈ (ℝn)⊗ 3 that is the sum of r random rank-1 terms. The problem of recovering the rank-1 components is possible in principle when r ≲ n2 but polynomial-time algorithms are only known in the regime r ≪ n3/2. Similar “statistical-computational gaps” occur in many high-dimensional inference tasks, and in recent years there has been a flurry of work on explaining the apparent computational hardness in these problems by proving lower bounds against restricted (yet powerful) models of computation such as statistical queries (SQ), sum-of-squares (SoS), and low-degree polynomials (LDP). However, no such prior work exists for tensor decomposition, largely because its hardness does not appear to be explained by a “planted versus null” testing problem.