We consider the problem of estimating a large rank-one tensor ${boldsymbol u}^{otimes k}in({mathbb R}^{n})^{otimes k}$, $kge 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 $lambdage C n^{(k-2)/4}$ and even powerful semidefinite programming relaxations appear to fail for $1ll lambdall 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.
Download