  Power iteration has been generalized to solve many interesting problems in
machine learning and statistics. Despite its striking success, theoretical
understanding of when and how such an algorithm enjoys good convergence
property is limited. In this work, we introduce a new class of optimization
problems called scale invariant problems and prove that they can be efficiently
solved by scale invariant power iteration (SCI-PI) with a generalized
convergence guarantee of power iteration. By deriving that a stationary point
is an eigenvector of the Hessian evaluated at the point, we show that scale
invariant problems indeed resemble the leading eigenvector problem near a local
optimum. Also, based on a novel reformulation, we geometrically derive SCI-PI
which has a general form of power iteration. The convergence analysis shows
that SCI-PI attains local linear convergence with a rate being proportional to
the top two eigenvalues of the Hessian at the optimum. Moreover, we discuss
some extended settings of scale invariant problems and provide similar
convergence results for them. In numerical experiments, we introduce
applications to independent component analysis, Gaussian mixtures, and
non-negative matrix factorization. Experimental results demonstrate that SCI-PI
is competitive to state-of-the-art benchmark algorithms and often yield better
solutions.
