I have covariance matrix known to be

$$K = \sum_{i=1}^Nx_ix_i^T$$

where the dimension of $x$ is big (like $50000$) so I don't want to really compute any outer-product to expand it as a full matrix. Also, I know this covariance matrix is sparse

Since K is guaranteed to be positive-definite, there is a unique Cholesky decomposition :

$$K = L^TL$$

Two questions:

  1. is there a way to update $L$ sequentially (update Cholesky factor after seeing each data point).

  2. is there approximation of Cholesky that keeps $L$ sparse or low-rank to save memory ?


1 Answer 1


This reminds me of approximation for the covariance matrix in Gaussian Process, to keep it small, when we see a lot of data. If you want to find the decomposition, after seeing new data, the naive way is to just do it again. But one can keep a small subset of the data (the sparsity assumption), and use the remaining data to perform the matrix decomposition. See this recent work: http://www.comp.nus.edu.sg/~lowkh/pubs/uai2013.pdf

  • $\begingroup$ that was like a really mathy paper , the core idea is ICF, is it? $\endgroup$
    – Jing
    Nov 29, 2013 at 11:21
  • $\begingroup$ By ICF you mean Incomplete Cholesky Factorization? If so, not really. Most of them is based on the idea that, they project the points in a lower dimensional space. I think, in general, the question you're asking, is not trivial. $\endgroup$
    – Daniel
    Nov 30, 2013 at 8:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .