How to update a whitening matrix online, for streaming data?

Question

For whitening, we need to calculate the inverse of the covariance matrix which is computationally expensive. While we can reduce the complexity by finding the inverse of square root of the eigenvalue matrix (which is diagonal), but even finding the whole eigenvector matrix is still expensive when the input matrix is of very high dimension. Now consider a scenario in which we would like to do the same whitening for streaming high dimensional data. Is there any method to update the whitening matrix with streaming data, once we have calculated that matrix for the first time?

Answer 1

You might try updating the inverse of your matrix. If $A$ is your matrix at time $t$, and this changes by a small amount $B$, then $$ (A + B)^{-1} \approx A^{-1} + A^{-1} B A^{-1}$$ However, matrix inversion has the same asymptotic complexity as matrix multiplication, so this may not be helpful unless $B$ is sparse.

EDIT: It's probably better to update the covariance matrix and its inverse as each new data point appears. Suppose your data are the column vectors $X_n$, $n = 1,2,3, \ldots$. If $\mu_n$ and $\Sigma_n$ are the mean vector and covariance matrix (in the version with denominator $n-1$) of the first $n$ data points, we have $$ \eqalign{\mu_{n+1} &= \dfrac{n \mu_n + X_{n+1}}{n+1}\cr \Sigma_{n+1} &= \dfrac{n-1}{n} \Sigma_n + \dfrac{1}{n+1} \left(X_{n+1} - \mu_n)(X_{n+1} - \mu_n)^T\right) }$$ This is a rank-$1$ update of a multiple of $\Sigma_n$, so by the Sherman-Morrison formula $$ \Sigma_{n+1}^{-1} = \frac{n}{n-1} \Sigma_n^{-1} - \frac{n}{n-1} \frac{\Sigma_n^{-1} (X_{n+1} - \mu_n) (X_{n+1} - \mu_n)^T \Sigma_n^{-1}} {\dfrac{n^2-1}{n} + (X_{n+1}-\mu_n)^T \Sigma_n^{-1} (X_{n+1} - \mu_n)}$$ We can compute this as $$\eqalign{Y &= X_{n+1} - \mu_n\cr Z &= \Sigma_n^{-1} Y\cr \Sigma_{n+1}^{-1} &= \dfrac{n}{n-1} \Sigma_n^{-1} - \dfrac{n}{n-1} \dfrac{Z Z^T}{\dfrac{n^2-1}{n} + Y^T Z}}$$ Note that this only involves matrix-vector and vector-vector multiplications, so it's much faster than matrix-matrix multiplication.