A new look at the power method for fast subspace tracking

A class of fast subspace tracking methods such as the Oja method, the proje ction approximation subspace tracking (PAST) method, and the novel informat ion criterion (NIC) method can be viewed as power-based methods. Unlike man y non-power-based methods such as the Given's rotation based URV updating m ethod and the operator restriction algorithm, the power-based methods with arbitrary initial conditions are convergent to the principal subspace of a vector sequence under a mild assumption. This paper elaborates on a natural version of the power method. The natural power method is shown to have the fastest convergence rate among the power-based methods. Three types of imp lementations of the natural power method are presented in detail, which req uire respectively O(n(2)p), O(np(2)), and O(np) flops of computation at eac h iteration (update), where n. is the dimension of the vector sequence and p is the dimension of the principal subspace. All of the three implementati ons are shown to be globally convergent under a mild assumption. The O(np) implementation of the natural power method is shown to be superior to the O (np) equivalent of the Oja, PAST, and NIC methods. Like all power-based met hods, the natural power method can be easily modified via subspace deflatio n to track the principal components and, hence, the rank of the principal s ubspace. (C)1999 Academic Press.