> For the complete documentation index, see [llms.txt](https://muhans-notebook.gitbook.io/computational-optimization/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://muhans-notebook.gitbook.io/computational-optimization/qr-factorization.md).

# QR Factorization

* numerical method (standard) for LS probs
* properties of QR
* numerical benefits
* computation

In general, $$\lVert(a,b)\rVert^2=(a,b)^T(a,b)=a^Ta+b^Tb=\lVert a\rVert^2+\lVert b\rVert^2$$

### Linear Least Squares

$$\min \frac{1}{2}\lVert Ax-b\rVert^2\_2$$

if A has full col rank ($$m>n$$) then $$X\_{LS}$$ uniquely solves Normal Equation’s

$$A^TAx\_{LS} = A^Tb$$

$$x\_{LS} = (A^TA)^{-1}A^Tb$$

$$\bar{y}=Ax\_{LS}=A(A^TA)^{-1}A^Tb$$ (projector onto $$range(A)$$)

“Conditioning” of a matrix determines the accuracy of a linear system solve: $$cond(M)=\frac{\lambda\_{max}(M)}{\lambda\_{min}(M)}$$

If $$M$$ is not square:

$$cond(M)=\frac{\nabla{max}(M)}{\nabla{min}(M)}$$, where $$\nabla$$ is the gradient

For $$M = A^TA$$, $$\nabla(M) = \nabla(A^TA)=\nabla(A)^2$$

$$\lambda\_i(A^TA)=\nabla\_i(A)^2$$

With $$Q$$ be orthogonal basis for $$range(A)$$

$$\underbrace{Q^T}*{n \times m}\underbrace{Q}*{m \times n}=\underbrace{I}\_{n\times n}$$

$$P$$ is an orthogonal projector onto $$range(P)$$ if

1. $$P^2=P$$ idempotent
2. $$P=P^T$$ symmetric

Take $$P=QQ^T$$: $$range(P)=range(Q)=range(A)$$

$$P^2=QQ^TQQ^T=QQ^T=P$$

$$range(Q) = range(A)$$

$$Q=\[q\_1,q\_2,…,q\_n]$$

$$span{q\_1,…,q\_n}=span{a\_1,…,a\_n}$$

Every matrix $$A\_{m\times n}$$ has a QR Factorization:

$$A=Q\begin{bmatrix} R \ 0 \end{bmatrix}$$, where $$Q$$ is orthogonal ($$QQ^T=Q^TQ=I$$) and R=upper triangular

<figure><img src="https://596692103-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FuVC1Ieh2j1XfxqLWFoSa%2Fuploads%2FhOMkQqgyBsLFL2HgVAHS%2FUntitled.png?alt=media&amp;token=194b42e6-30f3-4372-a7c4-27faeb741689" alt=""><figcaption></figcaption></figure>

$$Q$$ is orthogonal (and square)

$$Q^TQ=Q^TQ=I\_m$$

$$Q\_1$$ is orthonormal (not orthogonal)

$$Q\_1^TQ\_1=I\_n$$

$$Q\_1Q\_1^T \ne I\_m$$

orthonormal matrices are rotations:

1. for any vector $$x \in \R^n$$, $$\lVert Q\_1x\rVert\_2=\lVert x\rVert\_2$$ ⇒ $$\lVert Q\_1x\rVert^2=x^TQ\_1^TQ\_1x=x^Tx=\lVert x\rVert^2$$
2. any $$y \in \R^m$$, $$(Qx)^T(Qy)=x^TQ^TQy=x^Ty$$

### Solving Least Squares

$$\underset{x}{\min}\lVert Ax-b\rVert^2$$

$$\begin{aligned} \lVert Ax-b \rVert ^2 &=\lVert Q^T(Ax-b)\rVert ^2 \ &=\lVert Q^TAx-Q^Tb\rVert ^2 \ &=\lVert \begin{bmatrix} Rx\ \hdashline \ 0\end{bmatrix}-\begin{bmatrix} Q^T\_1b\ \hdashline \ Q^T\_2 b\end{bmatrix}\rVert ^2 \ &= \lVert Rx-Q^Tb\rVert^2+\lVert Q^T\_2b\rVert^2\end{aligned}$$

$$A = Q\begin{bmatrix}R \ 0\end{bmatrix}$$

Multiply both sides on the left with $$Q^T$$

$$Q^TA=\underbrace{Q^TQ}\_I\begin{bmatrix}R\0\end{bmatrix}$$

$$\begin{bmatrix}Q^T\_1A\Q\_2^TA\end{bmatrix}=\begin{bmatrix}R\0\end{bmatrix}$$

$$Q\_1^TA=R$$

$$Q\_2^TA=0$$

$$R\_1x=Q\_1^Tb$$ ⇒ solving least squares using QR

$$\begin{aligned}Cond(A) &= Cond(Q,R)\ &= Cond(R)\end{aligned}$$
