Cholesky factorization of $A M A^T$ for $M$ PSD with known Cholesky factorization.

Question

In the context of my research, I am trying to efficiently compute/store a PSD matrix and the cholesky factorization might help.

Let $M\in\mathbb R^{n\times n}$ and $A\in\mathbb R^{m\times n}$ be such that $M$ has Cholesky decomposition $LL^T$ (or alternatively $M=LDL^T$ with $L$ lower triangular and diagonal equal to $1$ if simpler). The matrix $N=AMA^T$ is PSD and I want to compute its Cholesky decomposition (or $LDL^T$ decomposition). I am wondering if there is a fast way of doing this using the knowledge of $L$ and $A$ that doesn't require to decompose $ALL^TA^T$.

Any reference on the subject or intuition is most welcome, I don't have any solid lead.

Answer 1

Let $M \in \mathbb{R}^{n \times n}$ s.p.d. and $A \in \mathbb{R}^{m \times n}$ and define $N = AMA^T \in \mathbb{R}^{m \times m}$. Assume we have $L \in \mathbb{R}^{n \times n}$ with $M = L L ^T$. Then $$ N = AMA^T = ALL^TA^T = (AL)(AL)^T = K K ^T, $$ and we have found a the Cholesky factorization$N = K K^T$ with $K = AL$.

• Computing $AL$ needs $O(mn^2)$ operations.
• Computing the Cholesky factorization of $N$ directly needs $O(m^3)$ operations.

For $n\ll m$ there is a benefit in reusing the old factorization.

---

(We assume $m \le n$ in the following.)

The matrix $K$ is not a square matrix and not lower triangular so we have not computed a Cholesky factorization. However, there is a way to compute a cholesky factorization from $K$.

Compute a LQ decomposition of $K \in \mathbb{R}^{m \times n}$: $$ K = \overline{L} Q, $$ with $Q \in \mathbb{R}^{n \times n}$ orthogonal and $\overline{L} \in \mathbb{R}^{m \times n}$ lower triangular. The matrix $\overline{L}$ has the form $$ \overline{L} = \left(\begin{array} 1 \tilde{L} & \mathbf{0} \end{array}\right), $$ with $\tilde{L} \in \mathbb{R}^{m \times m}$ lower triangular and $ \mathbf{0} \in \mathbb{R}^{m \times (n -m)}$ the zero matrix.

Then, we get $$ N = KK^T = LQQ^TL^T = LL^T = \tilde{L} \tilde{L}^T, $$ which is a Cholesky factorization.

• Computing a LQ decomposition of $K$ needs $O(n m^2)$ operations.