Calculate lines of the Inverse of Autocorrelation Matrix

Question

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$

Answer 1

Use a rank one Cholesky update approach.

Answer 2

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