Record Details

Oja's algorithm for graph clustering, Markov spectral decomposition, and risk sensitive control

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Oja's algorithm for graph clustering, Markov spectral decomposition, and risk sensitive control
 
Creator BORKAR, V
MEYN, SP
 
Subject Graph algorithms
Oja's algorithm
Stochastic approximation
Markov chains
Spectral theory of Markov chains
Multiplicative ergodic theory
Risk sensitive control
REVERSIBLE DIFFUSION-PROCESSES
STOCHASTIC-APPROXIMATION
LEARNING ALGORITHM
METASTABILITY
CONVERGENCE
COST
ASYMPTOTICS
EIGENVALUES
CHAINS
 
Description Given a positive definite matrix M and an integer N-m >= 1, Oja's subspace algorithm will provide convergent estimates of the first N-m 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. Recall that this means that the stationary distribution satisfies the detailed balance equations (Meyn & Tweedie, 2009). Equivalently, the statistics of the process in steady state do not change when time is reversed. Stability and convergence of Oja's algorithm are established under conditions far milder than that assumed in previous work. Applications to graph clustering, Markov spectral decomposition, and multiplicative ergodic theory are surveyed, along with numerical results. (C) 2012 Elsevier Ltd. All rights reserved.
 
Publisher PERGAMON-ELSEVIER SCIENCE LTD
 
Date 2014-10-17T04:24:56Z
2014-10-17T04:24:56Z
2012
 
Type Article
 
Identifier AUTOMATICA, 48(10)2512-2519
http://dx.doi.org/10.1016/j.automatica.2012.05.016
http://dspace.library.iitb.ac.in/jspui/handle/100/15942
 
Language en