Skip to main content

Unit 5.4.5 Cholesky factorization and solving LLS

Recall from Section 4.2 that the solution \(\widehat x \in \C^n \) to the linear least-squares (LLS) problem

\begin{equation} \| b - A \widehat x \|_2 = \min_{x \in \C^n} \| b - A x \|_2 \label{chapter05-cholesky-lls-eqn-1}\tag{5.4.2} \end{equation}

equals the solution to the normal equations

\begin{equation*} \begin{array}[t]{c} \underbrace{ A^H A }\\ B \end{array} \widehat x = \begin{array}[t]{c} \underbrace{A^H b} \\ y \end{array} . \end{equation*}

Since \(A^H A \) is Hermitian, it would be good to take advantage of that special structure to factor it more cheaply. If \(A^H A \) were HPD, then the Cholesky factorization can be employed. Fortunately, from Homework we know that if \(A \) has linearly independent columns, then \(A^H A \) is HPD. Thus, the steps required to solve the LLS problem (5.4.2) when \(A \in \Cmxn \) Are

  • Form \(B = A^H A \text{.}\) Cost: approximately \(m n^2 \) flops.

  • Factor \(B = L L^H \) (Cholesky factorization). Cost: approximately \(n^3/3 \) flops.

  • Compute \(y = A^H b \text{.}\) Cost: approximately \(2 m n\) flops.

  • Solve \(L z = y \text{.}\) Cost: approximately \(n^2 \) flops.

  • Solve \(L^H \widehat x = z \text{.}\) Cost: approximately \(n^2 \) flops.

for a total of, approximately, \(m n^2 + n^3/3 \) flops.

Ponder This

Consider \(A \in \C^{m \times n} \) with linearly independent columns. Recall that \(A \) has a QR factorization, \(A = Q R \) where \(Q \) has orthonormal columns and \(R \) is an upper triangular matrix with positive diagonal elements. How are the Cholesky factorization of \(A^H A \) and the QR factorization of \(A \) related?