ALAFF Cholesky factorization and solving LLS

Skip to main content

\( \usepackage{array} \setlength{\oddsidemargin}{-0.0in} \setlength{\evensidemargin}{-0.0in} \setlength{\textheight}{8.75in} \setlength{\textwidth}{6.5in} \setlength{\topmargin}{-0.25in} \newcommand{\R}{\mathbb R} \newcommand{\Rm}{\mathbb R^m} \newcommand{\Rn}{\mathbb R^n} \newcommand{\Rnxn}{\mathbb R^{n \times n}} \newcommand{\Rmxn}{\mathbb R^{m \times n}} \newcommand{\Rmxm}{\mathbb R^{m \times m}} \newcommand{\Rmxk}{\mathbb R^{m \times k}} \newcommand{\Rkxn}{\mathbb R^{k \times n}} \newcommand{\C}{\mathbb C} \newcommand{\Cm}{\mathbb C^m} \newcommand{\Cmxm}{\mathbb C^{m \times m}} \newcommand{\Cnxn}{\mathbb C^{n \times n}} \newcommand{\Cmxn}{\mathbb C^{m \times n}} \newcommand{\Ckxk}{\mathbb C^{k \times k}} \newcommand{\Cn}{\mathbb C^n} \newcommand{\Ck}{\mathbb C^k} \newcommand{\Null}{{\cal N}} \newcommand{\Col}{{\cal C}} \newcommand{\Rowspace}{{\cal R}} \newcommand{\Span}{{\rm {Span}}} \newcommand{\rank}{{\rm rank}} \newcommand{\triu}{{\rm triu}} \newcommand{\tril}{{\rm tril}} \newcommand{\sign}{{\rm sign}} \newcommand{\FlaTwoByTwo}[4]{ \left( \begin{array}{c | c} #1 \amp #2 \\ \hline #3 \amp #4 \end{array} \right) } \newcommand{\FlaTwoByTwoSingleLine}[4]{ \left( \begin{array}{c c} #1 \amp #2 \\ #3 \amp #4 \end{array} \right) } \newcommand{\FlaTwoByTwoSingleLineNoPar}[4]{ \begin{array}{c c} #1 \amp #2 \\ #3 \amp #4 \end{array} } \newcommand{\FlaOneByTwo}[2]{ \left( \begin{array}{c | c} #1 \amp #2 \end{array} \right) } \newcommand{\FlaOneByTwoSingleLine}[2]{ \left( \begin{array}{c c} #1 \amp #2 \end{array} \right) } \newcommand{\FlaTwoByOne}[2]{ \left( \begin{array}{c} #1 \\ \hline #2 \end{array} \right) } \newcommand{\FlaTwoByOneSingleLine}[2]{ \left( \begin{array}{c} #1 \\ #2 \end{array} \right) } \newcommand{\FlaThreeByOneB}[3]{ \left( \begin{array}{c} #1 \\ \hline #2 \\ #3 \end{array} \right) } \newcommand{\FlaThreeByOneT}[3]{ \left( \begin{array}{c} #1 \\ #2 \\ \hline #3 \end{array} \right) } \newcommand{\FlaOneByThreeR}[3]{ \left( \begin{array}{c | c c} #1 \amp #2 \amp #3 \end{array} \right) } \newcommand{\FlaOneByThreeL}[3]{ \left( \begin{array}{c c | c} #1 \amp #2 \amp #3 \end{array} \right) } \newcommand{\FlaThreeByThreeBR}[9]{ \left( \begin{array}{c | c c} #1 \amp #2 \amp #3 \\ \hline #4 \amp #5 \amp #6 \\ #7 \amp #8 \amp #9 \end{array} \right) } \newcommand{\FlaThreeByThreeTL}[9]{ \left( \begin{array}{c c | c} #1 \amp #2 \amp #3 \\ #4 \amp #5 \amp #6 \\ \hline #7 \amp #8 \amp #9 \end{array} \right) } \newcommand{\diag}[1]{{\rm diag}( #1 )} \newcommand{\URt}{{\sc HQR}} \newcommand{\FlaAlgorithm}{ \begin{array}{|l|} \hline \routinename \\ \hline \partitionings \\ ~~~ \begin{array}{l} \partitionsizes \end{array} \\ {\bf \color{blue} {while}~} \guard \\ ~~~ \begin{array}{l} \repartitionings \end{array} \\ ~~~ \color{red} { \begin{array}{l} \hline \color{black} {\update} \\ \hline \end{array}} \\ ~~~ \begin{array}{l} \moveboundaries \end{array} \\ {\bf \color{blue} {endwhile}} \\ \hline \end{array} } \newcommand{\FlaAlgorithmWithInit}{ \begin{array}{|l|} \hline \routinename \\ \hline \initialize \\ \partitionings \\ ~~~ \begin{array}{l} \partitionsizes \end{array} \\ {\bf \color{blue} {while}~} \guard \\ ~~~ \begin{array}{l} \repartitionings \end{array} \\ ~~~ \color{red} { \begin{array}{l} \hline \color{black} {\update} \\ \hline \end{array}} \\ ~~~ \begin{array}{l} \moveboundaries \end{array} \\ {\bf \color{blue} {endwhile}} \\ \hline \end{array} } \newcommand{\FlaBlkAlgorithm}{ \begin{array}{|l|} \hline \routinename \\ \hline \partitionings \\ ~~~ \begin{array}{l} \partitionsizes \end{array} \\ {\bf \color{blue} {while}~} \guard \\ ~~~ {\bf choose~block~size~} \blocksize \\ ~~~ \begin{array}{l} \repartitionings \end{array} \\ ~~~ ~~~ \repartitionsizes \\ ~~~ \color{red} { \begin{array}{l} \hline \color{black} {\update} \\ \hline \end{array}} \\ ~~~ \begin{array}{l} \moveboundaries \end{array} \\ {\bf \color{blue} {endwhile}} \\ \hline \end{array} } \newcommand{\complexone}{ \begin{array}{|c|}\hline \!\pm\! \\ \hline \end{array}~ } \newcommand{\HQR}{{\rm HQR}} \newcommand{\QR}{{\rm QR}} \newcommand{\st}{{\rm \ s.t. }} \newcommand{\QRQ}{{\rm {\normalsize \bf Q}{\rm \tiny R}}} \newcommand{\QRR}{{\rm {\rm \tiny Q}{\bf \normalsize R}}} \newcommand{\deltaalpha}{\delta\!\alpha} \newcommand{\deltax}{\delta\!x} \newcommand{\deltay}{\delta\!y} \newcommand{\deltaz}{\delta\!z} \newcommand{\deltaw}{\delta\!w} \newcommand{\DeltaA}{\delta\!\!A} \newcommand{\meps}{\epsilon_{\rm mach}} \newcommand{\fl}[1]{{\rm fl( #1 )}} \newcommand{\becomes}{:=} \newcommand{\defrowvector}[2]{ \left(#1_0, #1_1, \ldots, #1_{#2-1}\right) } \newcommand{\tr}[1]{{#1}^T} \newcommand{\LUpiv}[1]{{\rm LU}(#1)} \newcommand{\maxi}{{\rm maxi}} \newcommand{\Chol}[1]{{\rm Chol}( #1 )} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Subsection 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 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 \widehat x = z \text{.}\) Cost: approximately \(n^2 \) flops.

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

Ponder This 5.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?