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.



Determinant of an updated Covariance matrix
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](https://en.wikipedia.org/wiki/Matrix_determinant#Sylvester%2527s_determinant_theorem) 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


