On the output function in a Ginsburg’s machine

We give the form of the output function in Ginsburg’s machine in which the input and output dictionaries are abelian groups and the transition function is of a special form.     

The Landscape of the Spiked Tensor Model

We consider the problem of estimating a large rank-one tensor u ^⊗k ∈ (ℝⁿ)^⊗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.