Return to Revisions

I strongly doubt any efficient algorithm exists for even approximately finding the maximizer in general. With slightly different notation, your problem is the same as the problem of "tensor principal component analysis" (tensor PCA). See the definition on page 2 of https://arxiv.org/pdf/1411.1076.pdf There, a reference is given that an exact solution is NP-hard. Further, that paper considers a statistical model in which the tensor is a sum of a rank-1 symmetric tensor (i.e., a tensor which is of the form $v^{\otimes k}$ for some vector $v$ where $k$ is the number of indices of the tensor) plus a random tensor with entries that are i.i.d. Gaussian up to the requirement of symmetry. In that case, at low noise (i.e., the Gaussian random tensor has small variance), there are polynomial algorithms which (with high probability) allow one to recover the vector $v$ up to some error, given the tensor as input. The simplest of these algorithms uses an eigendecomposition of a matrix, and the eigenvector with leading eigenvalue is close to $v^{\otimes k/2}$. As the noise increases, it is conjectured that there is a regime where no polynomial time algorithm can approximately recover $v$, even though approximate recovery is information-theoretically possible. At even larger noise, recovery becomes information-theoretically impossible.