## Unit5.4.5Cholesky factorization and solving LLS

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

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

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 5.4.1.1 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 \hat x = z \text{.}$ Cost: approximately $n^2$ flops.

for a total of, approximately, $m n^2 + n^3/3$ flops.

###### Ponder This5.4.5.1.

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?