An adaptive stochastic approximation algorithm for simultaneous diagonalization of matrix sequences with applications

We describe an adaptive algorithm based on stochastic approximation theory for the simultaneous diagonalization of the expectations of two random matrix sequences. Although there are several conventional approaches to solving this problem, there are many applications in pattern analysis and signal detection that require an online (i.e., real-time) procedure for this computation. In these applications, we are given two sequences of random matrices {A_k } and {B_k} as online observations, with lim_k→∞E[A_k]=A and lim_k→∞E[B_k]=B, where A and B are real, symmetric and positive definite. For every sample (A_k, B_k), we need the current estimates Φ_k and Λ_k, respectively of the eigenvectors Φ and eigenvalues Λ of A^-1 B. We have described such an algorithm where Φ_k and Λ_k converge provably with probability one to Φ and Λ respectively. A novel computational procedure used in the algorithm is the adaptive computation of A^-½. Besides its use in the generalized eigen-decomposition problem, this procedure can be used on its own in several feature extraction problems. The performance of the algorithm is demonstrated with an example of detecting a high-dimensional signal in the presence of interference and noise, in a digital mobile communications problem. Experiments comparing computational complexity and performance demonstrate the effectiveness of the algorithm in this real-time application