08 - QR Decomposition

QR Decomposition

Let $A$ be a $m\times n$ matrix then

Exists orthogonal matrix $Q$ and upper triangular matrix $R$ such that

$$A=QR$$

If $m>n$ then

Thin QR is

$$A=QR$$

where

$Q\in {\mathbb{R}}^{m\times n}$ has orthonormal columns and same size as $A$
and $R\in {\mathbb{R}}^{n\times n}$ has the bottom $m-n$ rows being $0$

Full QR is

$$A=\left[\begin{array}{cc}{Q}_1& Q_2\end{array}\right]\left[\begin{array}{c}{R}_1\\ 0\end{array}\right]=Q_1{R}_1$$

where $Q_1$ is square orthogonal

Proof for Square Matrix

Let $u$ be the first column of $A$ then

Exists $w\in {\mathbb{R}}^n$ such that

$$H(w)u=\left[\begin{array}{c}\alpha \\ 0\\ ⋮\\ 0\end{array}\right]\equiv v$$

where $\alpha =\pm \sqrt{u^{T}u}$

Hence

$$H(w)A=\left[\begin{array}{cccc}\alpha & \times & \cdots & \times \\ 0& & & \\ ⋮& & B& \\ 0& & & \end{array}\right]$$

where $\times$ is a general entry

Similarly for $B$ there exists $\hat{w}\in {\mathbb{R}}^{n-1}$ such that

$$H(\hat{w})B=\left[\begin{array}{cccc}\beta & \times & \cdots & \times \\ 0& & & \\ ⋮& & C& \\ 0& & & \end{array}\right]$$

Hence

$$\left[\begin{array}{cccc}1& 0& \cdots & 0\\ 0& & & \\ ⋮& & H(\hat{w})& \\ 0& & & \end{array}\right]H(w)A=\left[\begin{array}{ccccc}\alpha & \times & \times & \cdots & \times \\ 0& \beta & \times & \cdots & \times \\ 0& 0& & & \\ ⋮& ⋮& & C& \\ 0& 0& & & \end{array}\right]$$

with in Block Form

$$\left[\begin{array}{cc}1& 0\\ 0& H(\hat{w})\end{array}\right]=H\left(\left[\begin{array}{c}0\\ \hat{w}\end{array}\right]\right)\equiv H(w_2)$$

Repeating this for the $n-1$ steps then

$$\underset{Q^T}{\underbrace{H(w_{n-1})\cdots H(w_2)H(w)A}}=\left[\begin{array}{cccc}\alpha & \times & \cdots & \times \\ 0& \beta & \cdots & \times \\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & \gamma \end{array}\right]\equiv R$$

where $R$ is upper triangular

As product of orthogonal matrices are orthogonal then $Q^T$ is orthogonal
Hence

$$Q^{T}A=R⟹A=QR$$