Let $\mathbf{C}$ be a $n \times n$ covariance matrix and assume that the LDL' Cholesky decomposition can be obtained efficiently. Can we take advantage of this to obtain a fast eigenvalue decomposition of $\mathbf{C}$?

As an example, $\mathbf{C}$ is the covariance of a discrete-time Gaussian Process (GP) having a state-space representation or that of a partially observed continuous-time state-space GP. Using Kalman filtering, the Cholesky decomposition can then be obtained with $O(n)$ operations instead of $O(n^3)$ for the general case. The eigenvalue decomposition is required to investigate the Karuhnen-Loève expansion of the GP.

To be more formal, the decomposition is $\mathbf{C} = \mathbf{L}\mathbf{D}\mathbf{L}^\top$ where $\mathbf{L}$ is lower triangular with ones on its diagonal and $\mathbf{D}$ is diagonal say $\text{diag}(\mathbf{d})$. We can assume that we have a function or a routine which for a given vector $\mathbf{y}$ with length $n$ computes efficiently the "innovation" vector $\mathbf{e} := \mathbf{L}^{-1}\mathbf{y}$ along with its variance vector $\mathbf{d}$. These two elements allow the evaluation of the likelihood for the GP example. Using this function we want to find the eigenvectors and eigenvalues.

  • $\begingroup$ Fwiw, scholar.google Cholesky eigenvalue -> a paper "Mathias, Fast accurate eigenvalue computations using the Cholesky factorization, 1996"; I don't understand the conditions offhand. $\endgroup$ – denis Jan 29 at 11:32
  • $\begingroup$ Thanks @denis. This is a step forward and I should read this. $\endgroup$ – Yves Jan 29 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.