Premium
The Landscape of the Spiked Tensor Model
Author(s) -
Arous Gérard Ben,
Mei Song,
Montanari Andrea,
Nica Mihai
Publication year - 2019
Publication title -
communications on pure and applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.12
H-Index - 115
eISSN - 1097-0312
pISSN - 0010-3640
DOI - 10.1002/cpa.21861
Subject(s) - mathematics , maxima , estimator , rank (graph theory) , polynomial , exponential function , tensor (intrinsic definition) , combinatorics , constant (computer programming) , maxima and minima , homogeneous polynomial , unit vector , gaussian , exponential growth , gaussian binomial coefficient , function (biology) , mathematical analysis , pure mathematics , statistics , matrix polynomial , programming language , biology , art history , art , physics , quantum mechanics , evolutionary biology , performance art , computer science , negative binomial distribution , poisson distribution
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 . 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 u or are confined in a band of width Θ( λ −1/( k − 1) ) around the maximum circle that is orthogonal to u . For local maxima, this band shrinks to be of size Θ( λ −1/( k − 2) ) . These “uninformative” local maxima are likely to cause the failure of optimization algorithms. © 2019 Wiley Periodicals, Inc.