4.3 Cholesky Decomposition
The Cholesky decomposition is a square-root-like factorization for symmetric, positive definite matrices. It generalizes the concept of a square root from numbers to matrices.
Theorem 4.5 Cholesky Decomposition: A symmetric, positive definite matrix \(\mathbf{A} \in \mathbb{R}^{n \times n}\) can be factorized as: \[ \mathbf{A} = L L^\top, \] where \(L\) is a lower-triangular matrix with positive diagonal entries. The matrix \(L\) is called the Cholesky factor of \(\mathbf{A}\) and is unique.
Example 4.14 For \[ \mathbf{A} = \begin{bmatrix} a_{11} & a_{21} & a_{31} \\ a_{21} & a_{22} & a_{32} \\ a_{31} & a_{32} & a_{33} \end{bmatrix}, \quad L = \begin{bmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{bmatrix}, \] the components of \(L\) are computed as: \[ \begin{aligned} l_{11} &= \sqrt{a_{11}}, & l_{22} &= \sqrt{a_{22} - l_{21}^2}, & l_{33} &= \sqrt{a_{33} - (l_{31}^2 + l_{32}^2)}, \\ l_{21} &= \frac{a_{21}}{l_{11}}, & l_{31} &= \frac{a_{31}}{l_{11}}, & l_{32} &= \frac{a_{32} - l_{31}l_{21}}{l_{22}}. \end{aligned} \]
Example 4.15 Let \[ \mathbf{A} = \begin{bmatrix} 4 & 2 & 2 \\ 2 & 5 & 1 \\ 2 & 1 & 3 \end{bmatrix} \] We want to find a lower triangular matrix \(\mathbf{L}\) such that \[ \mathbf{A} = \mathbf{L}\mathbf{L}^T. \]
Assume \[ \mathbf{L} = \begin{bmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{bmatrix}. \] By multiplying \(\mathbf{L}\mathbf{L}^T\) and comparing entries with \(\mathbf{A}\), we obtain: \[\begin{align*} l_{11}^2 = 4 &\Rightarrow l_{11} = 2 & 2l_{21} = 2 &\Rightarrow l_{21} = 1\\ 2l_{31} = 2 &\Rightarrow l_{31} = 1 &1^2 + l_{22}^2 = 5 &\Rightarrow l_{22} = 2 \\ 1(1) + 2l_{32} = 1 &\Rightarrow l_{32} = 0 & 1^2 + 0^2 + l_{33}^2 = 3 &\Rightarrow l_{33} = \sqrt{2} \end{align*}\]
Therefore, \[ \mathbf{L} = \begin{bmatrix} 2 & 0 & 0 \\ 1 & 2 & 0 \\ 1 & 0 & \sqrt{2} \end{bmatrix} \]
and
\[ \mathbf{L}^T = \begin{bmatrix} 2 & 1 & 1 \\ 0 & 2 & 0 \\ 0 & 0 & \sqrt{2} \end{bmatrix}, \] and \[ \mathbf{A} = \mathbf{L}\mathbf{L}^T. \]
Cholesky decompositions provide an efficient computation of determinants: \(\det(\mathbf{A}) = \prod_i l_{ii}^2\). They are also important to provide numerical stability in machine learning algorithms
Example 4.16 Find the determinant of \[ \mathbf{A} = \begin{bmatrix} 4 & 2 & 2 \\ 2 & 5 & 1 \\ 2 & 1 & 3 \end{bmatrix}. \]
Since \[ \mathbf{A} = \mathbf{L}\mathbf{L}^T, \] we have \[ \det(\mathbf{A}) = \det(\mathbf{L}\mathbf{L}^T) = \det(\mathbf{L}) \det(\mathbf{L}^T) =(2 \times 2 \times \sqrt{2}) \times (2 \times 2 \times \sqrt{2}) = 32. \]
Exercises
Exercise 4.20 Let \(\mathbf{A} = \begin{bmatrix}9 & 6 \\ 6 & a \end{bmatrix}\), \(a > 4\). Verify that this matrix satisfies the criteria for the Cholesky decomposition and find it. Hint, you are going to have to derive the equations yourself.
Exercise 4.21 Compute the Cholesky decomposition for \[\mathbf{A} = \begin{bmatrix} 1&0&0\\0&1&0\\0&0&1 \end{bmatrix}.\]
Exercise 4.22 Compute the Cholesky decomposition for \[\mathbf{A} = \begin{bmatrix} 5&0&0\\0&10&0\\0&0&0.17 \end{bmatrix}.\]
Exercise 4.23 Compute the Cholesky decomposition for \[\mathbf{A} = \begin{bmatrix} 2&-1&0\\-1&2&-1\\0&-1&2 \end{bmatrix}.\]
Exercise 4.24 Compute the Cholesky decomposition for \[\mathbf{A} = \begin{bmatrix} 25&15&-5\\15&18&0\\-5&0&11 \end{bmatrix}.\]
Exercise 4.25 Show that if \(\mathbf{A}\) is a symmetric, positive definite matrix, then \[det(\mathbf{A}) = det(\mathbf{L})^2= \left(\prod_{i=1}^n l_{ii}\right)^2,\] where \(\mathbf{L}\) is the Cholesky factor of \(\mathbf{A}\). Verify each step.
Exercise 4.26