MATH 240

Mon. November 25th, 2019


QR Factorization

If AA is an m×nm\times n matrix with linearly independent columns, then AA can be factored as QRQR, where QQ is an m×nm\times n matrix whose columns form an orthonormal basis for ColA\text{Col}A, and RR is an n×nn\times n upper triangular invertible matrix with positive entries on its diagonal.

Ex. A=(100110111111)A=\begin{pmatrix} 1&0&0\\1&1&0\\1&1&1\\1&1&1 \end{pmatrix}


Step 1: Use Gram-Schmidt to find an orthogonal basis for ColA\text{Col}A. (We already did this for this set of vectors last Friday.)

ColA=span{v1,v2,v3}\text{Col}A=\text{span}\{v_1,v_2,v_3\} where v1=(1111),v2=(3111),v3=(0231313)v_1=\begin{pmatrix} 1\\1\\1\\1 \end{pmatrix},v_2=\begin{pmatrix} -3\\1\\1\\1 \end{pmatrix},v_3=\begin{pmatrix} 0\\-\frac{2}{3}\\\frac{1}{3}\\\frac{1}{3} \end{pmatrix}

Step 2: Normalize these vectors and collect them into a matrix to form QQ.

Q=(123120121122612112161211216)Q=\begin{pmatrix} \frac{1}{2}&-\frac{3}{\sqrt{12}}&0\\\frac{1}{2}&\frac{1}{\sqrt{12}}&-\frac{2}{\sqrt{6}}\\\frac{1}{2}&\frac{1}{\sqrt{12}}&\frac{1}{\sqrt{6}}\\ \frac{1}{2}&\frac{1}{\sqrt{12}}&\frac{1}{\sqrt{6}} \end{pmatrix}

Because the columns of QQ are orthonormal, QTQ=IQ^TQ=I.
Thus QTA=QT(QR)=(QTQ)R=RQ^TA=Q^T(QR)=(Q^TQ)R=R.

Step 3: Calculate QTAQ^TA.

R=QTA=(232103122120026)R=Q^TA=\begin{pmatrix} 2&\frac{3}{2}&1\\0&\frac{3}{\sqrt{12}}&\frac{2}{\sqrt{12}}\\0&0&\frac{2}{\sqrt{6}} \end{pmatrix}


Least Squares

Idea. Given an inconsistent system Ax=bAx=b (i.e. no solutions), find x^\hat{x} such that Ax^A\hat{x} is as close to bb as possible.

In other words, we want to find the point Ax^A\hat{x} in the column space of AA that is closest to bb.

Definition. If AA is an m×nm\times n matrix and bb is in Rm\R^m, a least squares solution of Ax=bAx=b is an x^\hat{x} in Rn\R^n such that bAx^bAx\lVert b-A\hat{x} \rVert \leq \lVert b-Ax \rVert for all xx in Rn\R^n.


Finding a solution to a least squares problem

Let AA be an m×nm\times n matrix.

Q1: What is the point in the column space of AA that is closest to bb?
A1: The projection of bb onto ColA\text{Col}A.

Take b^=projA(b)\hat{b}=\text{proj}_A(b).

Q2: What space will the least squares solution xx be from?
A2: Rn\R^n.

Now all we have to do is solve Ax=b^Ax=\hat{b}, which we know must be consistent since b^\hat{b} is in ColA\text{Col}A. (However, there may be infinitely many solutions.)


Note that any column of AA (say aja_j) is orthogonal to the component of b^\hat{b} (which is bAxb-Ax), so aj(bAx)=0a_j\cdot(b-Ax)=0.

ajT(bAx)=0a_j^T(b-Ax)=0
AT(bAx)=0A^T(b-Ax)=0