5
$\begingroup$

I am faced with the following problem :

Originally (at time $0$) I have a number of data samples $x^0_{1,\ldots,n}$ (normalised : $E[x] = 0, \operatorname{Var}[x] = 1$) from which I have calculated the covariance matrix $C^0 = X^T X$ (where $X$ is the matrix of data samples), and the corresponding determinant $|C^0|$ (I could also store all and any minors are necessary).

Given this information I would like to perform the following iterative process incurring the smallest computational cost possible :

At time $t+1$ I am presented with a new data sample $x^\text{t+1}_\text{new}$ (similarly normalised) which can replace any of my existing data samples. Thus if I discard example $x^t_k$ in favour of this new sample, I have a new covariance matrix $C^{t+1}_{k,\text{new}}$. I would like to calculate (given $C^0$, its minors and determinant) $\forall t$ $\operatorname{argmax}_k |C^{t+1}_{k,\text{new}}|$.

Note that at each time step $t+1$, if I decide to discard $x^t_k$ in favour of $x^{t+1}_\text{new}$ then $x^{t+1}_k = x^{t+1}_\text{new}$ .

My question is, is there a method to calculate the determinants without incurring a cost of $n^3$ per determinant per time step?

Thanks for the help.

$\endgroup$
1
  • 1
    $\begingroup$ You're not using the word "sample" correctly. You have one sample consisting of $n$ observations, not $n$ samples. $\endgroup$ Dec 6, 2023 at 18:41

1 Answer 1

4
$\begingroup$

First compute a Cholesky factorization of the covariance matrix. Now your tentative new covariance matrix is a rank-2 update of the old, $$ M_\text{new}=M_\text{old}+\frac{1}{n} x_\text{new} x_\text{new}^T-\frac{1}{n} x_\text{old} x_\text{old}^T. $$ You can use Sylvester's formula here to compute the determinant of the update; for this you'll only need to solve a linear system, which is $O(n^2)$ using your Cholesky factorization.

Then when your "replacement" take place for real you just have to update the Cholesky factorization, and there are algorithms to do that (low-rank updates of Cholesky factorization) in $O(n^2)$ as well. Check Matlab's cholupdate for instance.

So you pay $O(n^3)$ at the first step and then $O(n^2)$ per step.

EDIT: better and clearer algorithm

$\endgroup$

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.