Oja’s algorithm for graph clustering and Markov spectral decomposition

Vivek Borkar and Sean Meyn

Presentation at Valuetools 2008

 


Abstract: Given a positive definite matrix M and an integer Nm > 0, Oja's subspace algorithm will provide convergent estimates of the first Nm eigenvalues of M along with the corresponding eigenvectors. It is a common approach to principal component analysis. This paper introduces a normalized stochastic-approximation implementation of Oja's subspace algorithm, as well as new applications to the spectral decomposition of a reversible Markov chain. Stability and convergence are established under conditions far milder than assumed in previous work. Applications to graph clustering, Markov spectral decomposition, and multiplicative ergodic theory are surveyed, along with numerical results.

Reference:
@inproceedings{bormey08a,
Author = {Borkar, V. and Meyn, S.},
Booktitle = {Proceedings of the {Third International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS 2008). Athens, Greece}},
Title = {Oja's Algorithm for Graph Clustering and {Markov} Spectral Decomposition},

Site Meter