Adaptive eigendecomposition of data covariance matrices based on first-order perturbations

In this paper, new algorithms for adaptive eigendecomposition of time-varying data covariance matrices are presented. The algorithms are based on a first-order perturbation analysis of the rank-one update for covariance matrix estimates with exponential windows. Different assumptions on the eigenvalue structure lead to three distinct algorithms with varying degrees of complexity. A stabilization technique is presented and both issues of initialization and computational complexity are discussed. Computer simulations indicate that the new algorithms can achieve the same performance as a direct approach in which the exact eigendecomposition of the updated sample covariance matrix is obtained at each iteration. Previous algorithms with similar performance require O(LM²) complex operations per iteration, where L and M respectively denote the data vector and signal-subspace dimensions, and involve either some form of Gram-Schmidt orthogonalization or a nonlinear eigenvalue search. The new algorithms have parallel structures, sequential operation counts of order O(LM) or less, and do not involve any of the above steps. One particular algorithm can be used to update the complete signal-subspace eigenstructure in 5LM complex operations. This represents an order of magnitude improvement in computational complexity over existing algorithms with similar performance. Finally, a simplified local convergence analysis of one of the algorithms shows that it is stable and converges in the mean to the true eigendecomposition. The convergence is geometrical and is characterized by a single time constant