Title: The landscape of the spiked tensor model,
Abstract: We consider the problem of estimating a large rank-one tensor ${\boldsymbol
u}^{\otimes k}\in({\mathbb R}^{n})^{\otimes k}$, $k\ge 3$ in Gaussian noise.
Earlier work characterized a critical signal-to-noise ratio $\lambda_{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 $\lambda\ge C n^{(k-2)/4}$ and even
powerful semidefinite programming relaxations appear to fail for $1\ll
\lambda\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 $\lambda$ 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(\lambda^{-1/(k-1)})$ around the maximum
circle that is orthogonal to ${\boldsymbol u}$. For local maxima, this band
shrinks to be of size $\Theta(\lambda^{-1/(k-2)})$. These `uninformative' local
maxima are likely to cause the failure of optimization algorithms.