The Landscape of the Spiked Tensor Model

By Gérard Ben Arous, Song Mei, Andrea Montanari, Mihai Nica. Communications on Pure and Applied Mathematics, 2017

142 citations recorded by the source corpus.

We consider the problem of estimating a large rank‐one tensor u⊗k ∈ (ℝn)⊗k, k ≥ 3, in Gaussian noise. Earlier work characterized a critical signal‐to‐noise ratio λ  Bayes = O(1) above which an ideal estimator achieves strictly positive correlation with the unknown vector of interest. Remarkably, no polynomial‐time algorithm is known that achieved this goal unless λ ≥ Cn(k − 2)/4, and even powerful semidefinite programming relaxations appear to fail for 1 ≪ λ ≪ n(k − 2)/4.

Subfields: Computational Mathematics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/a280bd8e38db2fdf55049fc0f8ac41255778fdec