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 bas ed on a first-order perturbation analysis of the rank-one update for c ovariance matrix estimates with exponential windows. Different assumpt ions on the eigenvalue structure lead to three distinct algorithms wit h varying degrees of complexity. A stabilization technique is presente d and both issues of initialization and computational complexity are d iscussed. Computer simulations indicate that the new algorithms can ac hieve the same performance as a direct approach in which the exact eig endecomposition of the updated sample covariance matrix is obtained at each iteration. Previous algorithms with similar performance require O(LM(2)) complex operations per iteration, where L and M respectively denote the data vector and signal-subspace dimensions, and involve eit her some form of Gram-Schmidt orthogonalization or a nonlinear eigenva lue search. The new algorithms have parallel structures, sequential op eration counts of order O(LM)(2) or less, and do not involve any of th e above steps. One particular algorithm can be used to update the comp lete signal-subspace eigenstructure in 5LM complex operations. This re presents an order of magnitude improvement in computational complexity over existing algorithms with similar performance. Finally, a simplif ied local convergence analysis of one of the algorithms shows that it is stable and converges in the mean to the true eigendecomposition. Th e convergence is geometrical and is characterized by a single time con stant.