10
$\begingroup$

I have a dataset that is slowly changing, and I need to keep track of eigenvectors/eigenvalues of its covariance matrix.

I've been using scipy.linalg.eigh, but it's too expensive, and it doesn't use the fact that I already have a decomposition that's only slightly incorrect.

Can anyone suggest a better approach to deal with this problem?

$\endgroup$
  • 1
    $\begingroup$ How large is your data? Do you need the complete eigensystem, or only some of the largest eigenvalues? Do you need them exactly, or would an approximation do? $\endgroup$ – cfh Apr 24 '17 at 10:17
  • $\begingroup$ I need complete eigensystem. I found an algorithm for updating inverse of a matrix after small norm update using regression interpretation of inverse of covariance matrix, so I assumed something similar should exist for eigenvectors. $\endgroup$ – Yaroslav Bulatov Apr 24 '17 at 16:11
  • $\begingroup$ What do you do with that full eigendecomposition? There might be a better shortcut that does not go through it... And I reiterate cfh's question: "how large"? $\endgroup$ – Federico Poloni Apr 29 '17 at 10:56
  • $\begingroup$ I have 8k features and millions of datapoints, so covariance is approximate. This is to implement this algorithm. Gradient update depends on eigenvalues of certain covariance matrix, and this covariance matrix changes at each step $\endgroup$ – Yaroslav Bulatov Apr 29 '17 at 17:19
5
$\begingroup$

A naive approach is to use the eigenvalue solution of your matrix $A(t)$ as the initial guess of an iterative eigensolver for matrix $A(t + \delta t)$. You might use QR if you need the full spectrum, or the power method otherwise. This isn't an entirely robust approach, however, as the eigenvalues of a matrix aren't necessarily close to a nearly neighboring matrix (1), especially if its poorly conditioned (2).

A subspace tracking method is apparently more useful (3). An excerpt from (4):

The iterative computation of an extreme (maximal or minimum) eigen pair (eigenvalue and eigenvector) can date back to 1966 [72]. In 1980, Thompson proposed a LMS-type adaptive algorithm for estimating eigenvector, which correspond to the smallest eigenvalue of sample covariance matrix, and provided the adaptive tracking algorithm of the angle/frequency combing with Pisarenko’s harmonic estimator [14]. Sarkar et al. [73] used the conjugate gradient algorithm to track the variation of the extreme eigenvector which corresponds to the smallest eigenvalue of the covariance matrix of the slowly changing signal and proved its much faster convergence than Thompson’s LMS-type algorithm. These methods were only used to track single extreme value and eigenvector with limited application, but later they were extended for the eigen-subspace tracking and updating methods. In 1990, Comon and Golub [6] proposed the Lanczos method for tracking the extreme singular value and singular vector, which is a common method designed originally for determining some big and sparse symmetrical eigen problem $Ax = kx$ [74].

[6]: Comon, P., & Golub, G. H. (1990). Tracking a few extreme singular values and vectors in signal processing. In Processing of the IEEE (pp. 1327–1343).

[14]: Thompson, P. A. (1980). An adaptive spectral analysis technique for unbiased frequency

[72]: Bradbury, W. W., & Fletcher, R. (1966). New iterative methods for solutions of the eigenproblem. Numerical Mathematics, 9(9), 259–266.

[73]: Sarkar, T. K., Dianat, S. A., Chen, H., & Brule, J. D. (1986). Adaptive spectral estimation by the conjugate gradient method. IEEE Transactions on Acoustic, Speech, and Signal Processing, 34(2), 272–284.

[74]: Golub, G. H., & Van Load, C. F. (1989). Matrix computation (2nd ed.). Baltimore: The John Hopkins University Press.

I should also mention that solutions to symmetric matrices, such as what you must be solving given your use of scipy.linalg.eigh, are somewhat cheap. If you are only interested in a few eigenvalues, you might find speed improvements in your method as well. The Arnoldi method is often used in such situations.

$\endgroup$
  • 1
    $\begingroup$ thanks for the pointer, the QR algorithm seems like a good starting point $\endgroup$ – Yaroslav Bulatov Apr 26 '17 at 20:23
  • $\begingroup$ I don't think that the magnitude of the perturbation in the eigenvalues is related to the condition number. This because $A$ has the same eigenvalues as $A+\lambda I$, but a different condition number. $\endgroup$ – Federico Poloni Apr 29 '17 at 11:01
  • $\begingroup$ ps: linalg.eigh on a 4k-by-4k matrix is taking about 20 seconds (it only uses single core for some reason). I need about 0.25 second per update $\endgroup$ – Yaroslav Bulatov May 3 '17 at 16:47
7
$\begingroup$

There exist special techniques for updating the eigen-decomposition of time-dependent covariance matrices. Given a "prior" eigenvalue decomposition (say at some initial time $t^0$), these recursive algorithms lower the complexity of the spectrum update from $\mathcal{O}(N^3)$ (essentially the cost of a new eigendecomposition) to $\mathcal{O}(k N^2)$ where $N$ is the size of your matrix and $k$ is the rank of your update.

Here's a couple of relevant references:

Adaptive Eigendecomposition of Data Covariance Matrices Based on First-Order Perturbations (Champagne, IEEE TSP 42(10) 1994)

Recursive updating the eigenvalue decomposition of a covariance matrix (Yu, IEEE TSP, 39(5) 1991)

Online Principal Component Analysis in High Dimension: Which Algorithm to Choose? (Cardot and Degras)

A Stable And Fast Algorithm For Updating The Singular Value Decomposition (Gu and Eisenstadt, 1994)

$\endgroup$
  • $\begingroup$ unfortunately I don't have small rank updates, I have small norm updates of full rank $\endgroup$ – Yaroslav Bulatov Apr 24 '17 at 16:06
  • $\begingroup$ @YaroslavBulatov I'm not aware of an efficient algorithm that can handle small-norm full rank updates - best I could find was this reference, but it does not look very promising. There is of course a large body of literature on eigenvalue perturbation that you may want to look at (see the other answer). $\endgroup$ – GoHokies Apr 24 '17 at 19:12

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.