2
$\begingroup$

$X_{1} = (A, b)$, where $X_{1}$ is a $n\times p$ matrix, $A$ is a $n\times (p-1)$ and $b$ is $n\times1$. update $b$ with $c$,Is there any update method to compute more efficiently?

$\endgroup$
  • $\begingroup$ Only the last column of $X_i$ changes each time, therefore only the elements in the first row or the last column of $X_i^\intercal X_i$ change. You should at least only re-compute those entries. Not sure if there there is a way to save on recomputing the full determinant unless each $a$, $b$, ... are related in some specific way. $\endgroup$ – Doug Lipinski Jul 25 '15 at 20:29
2
$\begingroup$

Consider the matrix $$ \begin{pmatrix}A^TA & x_{1:p-1} \\ w_{1:p-1} & z \end{pmatrix}. $$ In terms of minors $M_{ij}$ of the matrix $A^TA$ ($M_{ij}$ is the determinant of $A^TA$ with row $i$ and column $j$ removed), its determinant is $$ \sum_{i=1}^{p-1} (-1)^{p+i} x_i \sum_{j=1}^{p-1} (-1)^{p-1+j} w_j M_{ij} + z \,\mathrm{det} (A^TA) \\ = -\sum_{1\leq i,j\leq p-1} x_i (-1)^{i+j}M_{ij} w_j + z\,\mathrm{det}(A^TA). $$ (Using the cofactor expansion, applied twice: to the last column and to the last row.)

In your case, $x=A^Tb$, $z=b^Tb$ and $w=b^TA$ are known, so the determinant is $$ -(b^TA)C(A^Tb) + b^Tb\, \mathrm{det}(A^TA), $$ where $C = \big( (-1)^{i+j}M_{ij} \big)$ is the cofactor matrix of $A^TA$.

To evaluate the cofactor matrix, one can use the matrix inversion formula $$ (A^TA)^{-1} = \frac{1}{\mathrm{det}(A^TA)} C^T, $$ from which it follows that the determinant of $X^TX$ is $$ \big(b^Tb - b^TA(A^TA)^{-1}A^Tb\big)\,\mathrm{det}(A^TA). $$

Therefore, it is sufficient to precompute the matrix $(A^TA)^{-1}$ in time $O(p^3 + p^2n)$ using Cholesky factorization of $A^TA$, which also provides the determinant of $A^TA$, and then on each update evaluate one quadratic form in $A^Tb$ in time $O(p^2+pn)$. This is about $p$ times better than $O(p^3+p^2n)$ for computing the determinant directly. I think after this the efficiency would probably have to come from exploiting special structure of $A^T$ and $A^TA$.

$\endgroup$
  • $\begingroup$ A conceptually very similar approach would be to compute a Cholesky factorization of $X^{T}X$ and then use rank-one update/downdate formulas to update the factorization. The determinant would simply be the product of the diagonal entries of the Cholesky factorization (squared). These kinds of update formulas can often become numerically unstable after some number (say dozens) of iterations. $\endgroup$ – Brian Borchers Sep 18 '15 at 4:19
  • $\begingroup$ @BrianBorchers I don't think it's quite the same: there's no "update" in the last formula here, which doesn't depend on previous values of $b$ at all. $\endgroup$ – Kirill Sep 18 '15 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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