The landscape of the spiked tensor model

We consider the problem of estimating a large rank-one tensor boldsymbol uotimes k∈(mathbb Rn)otimes 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 λ≥ C n(k-2)/4 and even powerful semidefinite programming relaxations appear to fail for 1ll λll n(k-2)/4. In order to elucidate this behavior, we consider the maximum likelihood estimator, which requires maximizing a degree-k homogeneous polynomial over the unit sphere in n dimensions. We compute the expected number of critical points and local maxima of this objective function and show that it is exponential in the dimensions n, and give exact formulas for the exponential growth rate. We show that (for λ larger than a constant) critical points are either very close to the unknown vector boldsymbol u, or are confined in a band of width Theta(λ-1/(k-1)) around the maximum circle that is orthogonal to boldsymbol u. For local maxima, this band shrinks to be of size Theta(λ-1/(k-2)). These `uninformative' local maxima are likely to cause the failure of optimization algorithms.