  Tensor decomposition serves as a powerful primitive in statistics and machine
learning. In this paper, we focus on using power iteration to decompose an
overcomplete random tensor. Past work studying the properties of tensor power
iteration either requires a non-trivial data-independent initialization, or is
restricted to the undercomplete regime. Moreover, several papers implicitly
suggest that logarithmically many iterations (in terms of the input dimension)
are sufficient for the power method to recover one of the tensor components. In
this paper, we analyze the dynamics of tensor power iteration from random
initialization in the overcomplete regime. Surprisingly, we show that
polynomially many steps are necessary for convergence of tensor power iteration
to any of the true component, which refutes the previous conjecture. On the
other hand, our numerical experiments suggest that tensor power iteration
successfully recovers tensor components for a broad range of parameters,
despite that it takes at least polynomially many steps to converge. To further
complement our empirical evidence, we prove that a popular objective function
for tensor decomposition is strictly increasing along the power iteration path.
Our proof is based on the Gaussian conditioning technique, which has been
applied to analyze the approximate message passing (AMP) algorithm. The major
ingredient of our argument is a conditioning lemma that allows us to generalize
AMP-type analysis to non-proportional limit and polynomially many iterations of
the power method.
