4
$\begingroup$

I've thought about this problem for days but could not find a good answer.

Given Cholesky decomposition of a symmetric positive semidefinite matrix $A = LL^T$. Now, suppose that we delete the $i$-th row and the $i$-th column of $A$ to obtain $A'$ ($A'$ is also a symmetric positive semidefinite matrix), and the Cholesky decomposition of this new matrix is $A' = L'(L')^T$.

Is there any efficient way to obtain $L'$ from $L$?

Note: In case we delete the last row and the last column of $A$, the problem becomes simple, we just delete the last row and last column of $L$ to obtain $L'$. Other cases, for me, are not trivial.

Thank you so much.

$\endgroup$
  • $\begingroup$ Have you tried just deleting the $i$th row and $i$th column of $L$ to see if that works? Honestly, not sure but it seems like it's worth a numerical experiment. $\endgroup$ – Omnomnomnom Aug 18 '16 at 19:55
  • $\begingroup$ I tried. That didn't work. $\endgroup$ – Tiep Vu Aug 18 '16 at 21:02
3
$\begingroup$

Let $$C\equiv \left[\begin{array}{ccc}C_{11} & C_{12} & C_{13} \\ C_{12}^T & C_{22} & C_{23}\\C_{13}^T & C_{23}^T & C_{33} \end{array}\right] = \left[\begin{array}{ccc}L_{11} & 0 & 0 \\ L_{21} & l_{22} & 0\\L_{31} & L_{32} & L_{33} \end{array}\right]\left[\begin{array}{ccc}L_{11} & 0 & 0 \\ L_{21} & l_{22} & 0\\L_{31} & L_{32} & L_{33} \end{array}\right]^T$$ be the Cholesky factorization of the matrix $C$ and let $$\bar{C}\equiv \left[\begin{array}{ccc}C_{11} & 0 & C_{13} \\ 0 & 0 & 0\\C_{13}^T & 0 & C_{33} \end{array}\right] = \left[\begin{array}{ccc}\bar{L}_{11} & 0 & 0 \\ \bar{L}_{21} & \bar{l}_{22} & 0\\\bar{L}_{31} & \bar{L}_{32} & \bar{L}_{33} \end{array}\right]\left[\begin{array}{ccc}\bar{L}_{11} & 0 & 0 \\ \bar{L}_{21} & \bar{l}_{22} & 0\\\bar{L}_{31} & \bar{L}_{32} & \bar{L}_{33} \end{array}\right]^T$$ be the Cholesky factorization of the matrix $\bar{C}$ obtained from the matrix $C$ by zeroing $i$-th row and column. Then $\bar{L}_{11} = L_{11}$, $\bar{L}_{21} = 0$, $\bar{L}_{31} = L_{31}$, $\bar{l}_{22} = 0$, $\bar{L}_{32} = 0$ and $$\begin{align}C_{33} &= L_{31}L_{31}^T + L_{32}L_{32}^T + L_{33}L_{33}^T \\ C_{33} &= L_{31}L_{31}^T + \bar{L}_{33}\bar{L}_{33}^T\end{align}$$ Thus $$\bar{L}_{33}\bar{L}_{33}^T = L_{33}L_{33}^T + L_{32}L_{32}^T\tag{1}$$ since $L_{32}$ is a vector, (1) gives a rank-1 update of the Cholesky factorization $L_{33}L_{33}^T$. Now removing $i$-th row and column of $\bar{C}$ is trivial.

Rank-1 update of the Cholesky factorization is a standard procedure and can be done efficiently in $O(k^2)$ operations, where $k$ is size of the matrix $L_{33}$.

$\endgroup$

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.