03. QR Factorisation

Orthogonal Matrix

Let $Q$ be a real square matrix then

$Q$ is orthogonal if

$$Q^T=Q^{-1}$$

which holds if and only if

$$Q^{T}Q=I=Q{Q}^T$$

Link to original

Orthogonality of Product of Orthogonal Matrices

Let $S,T$ be orthogonal matrices then

$$ST\text{ is orthogonal}$$

Proof

As $S,T$ are orthogonal then

$$S^T=S^{-1}\text{ and }{T}^T=T^{-1}$$

Then

$$(ST{)}^T(ST)=T^T{S}^{T}ST=T^T(S^{T}S)T=T^{T}T=I$$

Link to original

Scalar Inner Product

Let

$$x=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right]\text{ and }y\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_n\end{array}\right]$$

in ${\mathbb{R}}^n$ then

$$x^{T}y=y^{T}x=\sum _{i=1}^n{x}_i{y}_i\in \mathbb{R}$$

Link to original

Orthogonality of Vectors

Let $x,y\in {\mathbb{R}}^n$ then

$x,y$ are orthogonal if

$$x^{T}y=0$$

Link to original

Orthogonal Set

Let $\{u_1,u_2,\cdots ,u_r\}$ be a set of vectors where $u_k\in {\mathbb{R}}^n$ for all $k$ then

$\{u_1,u_2,\cdots ,u_r\}$ is a orthogonal set if

$$u_i^T{u}_j=0\text{ for all }i,j\in \{1,2,\cdots ,r\}\text{ where }i\ne j$$

Link to original

Columns of an Orthogonal Matrix form an Orthogonal Set lemma

Let $Q$ be an orthogonal matrix with columns $q_1,q_2,\cdots ,q_n$ then

$\{q_1,q_2,\cdots ,q_n\}$ is an orthogonal set and an orthonormal basis for ${\mathbb{R}}^n$

Proof

Suppose

$$Q=[q_1\mid q_2\mid \cdots \mid q_n]$$

so $q_j$ is the $j$-th column of $Q$ then

$$Q^{T}Q=I=\left[\begin{array}{c}{q}_1^T\\ q_2^T\\ ⋮\\ q_n^T\end{array}\right]\left[\begin{array}{cccc}{q}_1& q_2& \cdots & q_n\end{array}\right]=\left[\begin{array}{cccc}1& 0& \cdots & 0\\ 0& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1\end{array}\right]$$

Comparing $(i,j)$-th entry then

$$q_i^T{q}_j={\delta }_{ij}$$

Hence $\{q_1,q_2,\cdots ,q_n\}$ is an orthonormal set

As $q_i^T{q}_i=1$ then it is also an orthonormal set
Let $x\in {\mathbb{R}}^n$ then

$$x=Q{Q}^{T}x=Qc\text{ where }c=Q^{T}x=$$

Hence

$$x=\sum _{i=1}^n{c}_i{q}_i$$

Link to original

Orthogonal Matrices don't affect Scalar Product

Let $P$ be a $n\times n$ orthogonal matrix
Let $u\in {\mathbb{R}}^n$

Let $v=Pu$ then

$$u^{T}u=v^{T}v$$

Proof

$$v^{T}v=(Pu{)}^T(PU)=u^T(P^{T}P)u=u^{T}u$$

Link to original

Outer Product

Let $x,y\in {\mathbb{R}}^n$ then

Outer Product of $x$ and $y$ is

$$x{y}^T=\left[\begin{array}{cccc}{x}_1{y}_1& x_1{y}_2& \cdots & x_1{y}_n\\ x_2{y}_1& x_2{y}_2& \cdots & x_2{y}_n\\ ⋮& ⋮& \ddots & ⋮\\ x_n{y}_1& x_n{y}_2& \cdots & x_n{y}_n\end{array}\right]$$

Link to original

Householder Matrix

For $w\in {\mathbb{R}}^n$ where $w\ne 0$ then

Household reflector $H(w)\in {\mathbb{R}}^{n\times n}$ is

$$H(w)=I-\frac{2}{w^{T}w}w{w}^T$$

Link to original

Property of Householder Reflectors

For $w\in {\mathbb{R}}^n$ where $w\ne 0$ then

$H(w)$ is symmetric orthogonal

Proof

Symmetric

$$(H(w){)}^T={\left(I-\frac{2}{w^{T}w}w{w}^T\right)}^T=I^T-\frac{2}{w^{T}w}(w{w}^T{)}^T=I-\frac{2}{w^{T}w}w{w}^T=H(w)$$

Orthogonality

$$\begin{array}{rl}H(w)H(w{)}^T& =\left(I-\frac{2}{w^{T}w}w{w}^T\right)\left(I-\frac{2}{w^{T}w}w{w}^T\right)\\ & =I-\frac{4}{w^{T}w}+\frac{4}{w^{T}w}w(w^{T}w)w^T\\ & =I\end{array}$$

Link to original

Householder Transformation

Let $u\in {\mathbb{R}}^n$ 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}$

Proof

As $H(w)$ is orthogonal then $v^{T}v=u^{T}u$ so ${\alpha }^2=u^{T}u$ hence choice of $\alpha$

Let $w=\gamma (u-v)$ where $\gamma \ne 0$ then

$$\begin{array}{rl}{w}^{T}w& ={\gamma }^2(u-v{)}^T(u-v)={\gamma }^2(u^{T}u-2u^{T}v+v^{T}v)\\ & ={\gamma }^2(u^{T}u-2u^{T}v+u^{T}u)\\ & =2\gamma u^T(\gamma (u-v))\\ & =2\gamma w^{T}u\end{array}$$

Hence

$$H(w)u=\left(I-\frac{2}{w^{T}w}w{w}^T\right)u=u-\frac{2w^{T}u}{w^{T}w}w=u-\frac{1}{\gamma }w=u-(u-v)=v$$

Link to original

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$$

Link to original