Oja's algorithm for graph clustering, Markov spectral decomposition, and risk sensitive control
| Autor: | Vivek S. Borkar, Sean P. Meyn |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2012 |
| Předmět: |
Cost
Stochastic Approximation Reversible Diffusion-Processes Positive-definite matrix Learning Algorithm Stochastic-Approximation Matrix decomposition Oja's rule Metastability Multiplicative Ergodic Theory Electrical and Electronic Engineering Eigenvalues and eigenvectors Mathematics Clustering coefficient Discrete mathematics Stationary distribution Markov chain Chains Eigenvalues Graph Algorithms Markov Chains Oja'S Algorithm Control and Systems Engineering Principal component analysis Spectral Theory Of Markov Chains Risk Sensitive Control Convergence Algorithm Asymptotics |
| Zdroj: | IndraStra Global. |
| ISSN: | 2381-3652 |
| DOI: | 10.1016/j.automatica.2012.05.016 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|