Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am faced with the following problem :

Originally (at time 0) I have a number of data samples $x^0_{1...n}$ (normalised : $E[x] = 0, 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^{t+1}_{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,new}$. I would like to calculate (given $C^0$, its minors and determinant) $\forall t$ $argmax_k |C^{t+1}_{k,new}|$.

Note that at each time step $t+1$, if I decide to discard $x^t_k$ in favour of $x^{t+1}_{new}$ then $x^{t+1}_k = x^{t+1}_{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.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

First compute a Cholesky factorization of the covariance matrix. Now your tentative new covariance matrix is a rank-2 update of the old, $$ M_{new}=M_{old}+\frac{1}{n}x_{new}x_{new}^T-\frac{1}{n}x_{old}x_{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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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