English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Tensor decomposition serves as a powerful primitive in statistics and machinelearning. In this paper, we focus on using power iteration to decompose anovercomplete random tensor. Past work studying the properties of tensor poweriteration either requires a non-trivial data-independent initialization, or isrestricted to the undercomplete regime. Moreover, several papers implicitlysuggest that logarithmically many iterations (in terms of the input dimension)are sufficient for the power method to recover one of the tensor components. Inthis paper, we analyze the dynamics of tensor power iteration from randominitialization in the overcomplete regime. Surprisingly, we show thatpolynomially many steps are necessary for convergence of tensor power iterationto any of the true component, which refutes the previous conjecture. On theother hand, our numerical experiments suggest that tensor power iterationsuccessfully recovers tensor components for a broad range of parameters,despite that it takes at least polynomially many steps to converge. To furthercomplement our empirical evidence, we prove that a popular objective functionfor tensor decomposition is strictly increasing along the power iteration path.Our proof is based on the Gaussian conditioning technique, which has beenapplied to analyze the approximate message passing (AMP) algorithm. The majoringredient of our argument is a conditioning lemma that allows us to generalizeAMP-type analysis to non-proportional limit and polynomially many iterations ofthe power method.

Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models