Sharp Analysis of Power Iteration for Tensor PCA
Yuchen Wu Kangjie Zhou
We investigate the power iteration algorithm for the tensor PCA model
introduced in Richard and Montanari (2014). Previous work studying the
properties of tensor power iteration is either limited to a constant number of
iterations, or requires a non-trivial data-independent initialization. In this
paper, we move beyond these limitations and analyze the dynamics of randomly
initialized tensor power iteration up to polynomially many steps. Our
contributions are threefold: First, we establish sharp bounds on the number of
iterations required for power method to converge to the planted signal, for a
broad range of the signal-to-noise ratios. Second, our analysis reveals that
the actual algorithmic threshold for power iteration is smaller than the one
conjectured in literature by a polylog(n) factor, where n is the ambient
dimension. Finally, we propose a simple and effective stopping criterion for
power iteration, which provably outputs a solution that is highly correlated
with the true signal. Extensive numerical experiments verify our theoretical
results.