Oja's algorithm for graph clustering and Markov spectral decomposition

V. Borkar; S.P. Meyn

3rd International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Oja's algorithm for graph clustering and Markov spectral decomposition

Download508 downloads

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.4108/ICST.VALUETOOLS2008.4600,
    author={V. Borkar and S.P. Meyn},
    title={Oja's algorithm for graph clustering and Markov spectral decomposition},
    proceedings={3rd International ICST Conference on Performance Evaluation Methodologies and Tools},
    publisher={ICST},
    proceedings_a={VALUETOOLS},
    year={2010},
    month={5},
    keywords={Graph algorithms Oja’s algorithm stochastic approximation Markov chains spectral theory of Markov chains 2000 AMS Subject Classification: 05C85 94C15 68W20 62L20 60J22 60J10 37A30 92B20},
    doi={10.4108/ICST.VALUETOOLS2008.4600}
}

V. Borkar
S.P. Meyn
Year: 2010
Oja's algorithm for graph clustering and Markov spectral decomposition
VALUETOOLS
ICST
DOI: 10.4108/ICST.VALUETOOLS2008.4600

V. Borkar¹^,*, S.P. Meyn²^,*

1: School of Technology and Computer Science, Tata Institute of Fundamental Research, Homi, Bhabha Road, Mumbai 400005, India.
2: Department of Electrical and Computer Engg. and the Coordinated Sciences Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA.

*Contact email: borkar@tifr.res.in, meyn@uiuc.edu

Abstract

Given a positive definite matrix M and an integer Nm ≥ 1, 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 and Markov spectral decomposition are surveyed, along with numerical results.

Keywords: Graph algorithms Oja’s algorithm stochastic approximation Markov chains spectral theory of Markov chains 2000 AMS Subject Classification: 05C85 94C15 68W20 62L20 60J22 60J10 37A30 92B20

Published: 2010-05-16
Publisher: ICST

: http://dx.doi.org/10.4108/ICST.VALUETOOLS2008.4600