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