I need to calculate the inverse of a autocorrelation matrix

$$\mathbf R_{xx} = E\left\{\mathbf x \mathbf x^T\right\}$$

Where the samples $\mathbf x$ are $266000\times 1$ vectors, which means I'll have a $266000\times 266000$ matrix and need to invert it. But I only need the first 729 lines. The problem is, I have to find a classifier $\mathbf h$, where $$\mathbf h = \mathbf R_{xx}^{-1}\mathbf u$$

where $\mathbf R_{xx}$ is the autocorrelation matrix and $\mathbf u$ is a $266000\times 1$ vector.

I have $\mathbf u$ and I can calculate $\mathbf R_{xx}$, but I can't save it on memory (it's a matrix larger than 400GB and I only have 380GB available). I'm only interested in the first 729 lines of $\mathbf h$


2 Answers 2


Use a rank one Cholesky update approach.

  • 1
    $\begingroup$ Wow! Stan! Welcome! Would you mind expanding on that a bit? You can use LaTeX-style formulae here. The system is flagging this as "Low Quality" because it's a little... terse. :-) $\endgroup$
    – Peter K.
    Commented May 25, 2017 at 1:28
  • $\begingroup$ Well, I gave it a search and actually found a "solution", not using Cholesky but Schur Complement (that I came across searching by Cholesky). $\endgroup$ Commented May 26, 2017 at 5:09

To follow on Stan's comment. The intuition is that inverse of a (Hermitian) matrix can be computed via Cholesky decomposition but that you update that decomposition as you compute more lines of the inverse. I don't have an implementation handy but there is some info on the wiki

Another related idea along the lines of dimensionality reduction, if you are doing an $$ Ax = b $$ type least-square optimization (which it appears you are), is to use SVD and the pseudoinverse. Another link.

From http://www.cs.toronto.edu/~jepson/csc420/notes/introSVD.pdf enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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