QR factorization

$A=QR$
where:

• $A$ is $m\times n$
• $R$ is square upper triangular matrix
• $Q$ is Orthogonal matrix
  Features:
• QR factorization always exists but may not unique
• QR factorization only exists when Determinant is $0$ and all diagonal elements $>0$.

given by $numpy.linalg.qr$

Steps

Gram-Schmidt

most intuitive but not stable
ref: https://kwokanthony.medium.com/important-decomposition-in-linear-algebra-detailed-explanation-on-qr-decomposition-by-classical-3f8f5425915f

1. for column $\overrightarrow{a_i}$ in $A$, calculate $u_i=a_i-({\sum }_{j=1}^{i-1}pro{j}_{u_{j-1}}{a}_j)=a_i-({\sum }_{j=1}^{i-1}\frac{a_j\cdot u_{j-1}}{u_{j-1}\cdot u_{j-1}}{a}_j)$.
2. then $q_i=\frac{u_i}{||u_i||}$ which is column in $Q$
3. repeat for all columns to get $Q$.
4. $R=Q^{T}A$.

Householder

ref: https://kwokanthony.medium.com/detailed-explanation-with-example-on-qr-decomposition-by-householder-transformation-5e964d7f7656

cost $O(n^3)$

Steps

1. init $R_0=A$
2. for column $\overrightarrow{a_i}$ in $A$, calculate $\overrightarrow{v_i}=\overrightarrow{a_i}\pm ||\overrightarrow{a_i}|{|}_2{e}_i$ where $e_1$ is standard basis. Choose the sign to avoid cancellation.
3. $w_i=\frac{\overrightarrow{v_i}}{||\overrightarrow{v_i}||}$, $Q_i=I-2w_i{w}_i^T$ and $R_i=Q_i{R}_{i-1}$.
4. keep this calculation column by column with only consider sub-matrix until $R_i$ is upper right triangle matrix.
5. $Q=\prod Q_i$, $R$ is last result of $R_i$.

2x2 example

$$A=\left[\begin{array}{cc}3& 7\\ 4& 2\end{array}\right]$$ $$\overrightarrow{v_1}=\left[\begin{array}{c}3\\ 4\end{array}\right]\pm \sqrt{9+16}\left[\begin{array}{c}1\\ 0\end{array}\right]=\left[\begin{array}{c}8\\ 4\end{array}\right]$$ $$w_1=\frac{1}{\sqrt{64+26}}\left[\begin{array}{c}8\\ 4\end{array}\right]$$ $$Q_1=I-2w_1{w}_1^T=\left[\begin{array}{cc}-3/5& -4/5\\ -4/5& 3/5\end{array}\right]$$

Then

$$R_1=Q_1{R}_0=Q_{1}A=\left[\begin{array}{cc}-5& -\frac{29}{5}\\ 0& -\frac{22}{5}\end{array}\right]$$

Since $R$ is already in right upper triangle matrix. We are done with $R=R_1$ and

$$Q=Q_1=\left[\begin{array}{cc}-\frac{3}{5}& -\frac{4}{5}\\ -\frac{4}{5}& \frac{3}{5}\end{array}\right]$$

It’s consist with

>>> numpy.linalg.qr(np.matrix("3,7;4,2"))  
QRResult(Q=matrix([[-0.6, -0.8],  
       [-0.8,  0.6]]), R=matrix([[-5. , -5.8],  
       [ 0. , -4.4]]))

Givens

ref: https://kwokanthony.medium.com/detailed-explanation-with-example-on-qr-decomposition-by-givens-rotation-6e7bf664fbdd

$$G=\left[\begin{array}{cc}\cos (\theta )& -\sin (\theta )\\ \sin (\theta )& \cos (\theta )\end{array}\right]$$

For higher dimensions, we need to use sth like

$$G_{xy}=\left[\begin{array}{ccc}\cos (\theta )& -\sin (\theta )& 0\\ \sin (\theta )& \cos (\theta )& 0\\ 0& 0& 1\end{array}\right]$$ $$G_{yz}=\left[\begin{array}{ccc}1& 0& 0\\ 0& \cos (\theta )& -\sin (\theta )\\ 0& \sin (\theta )& \cos (\theta )\end{array}\right]$$ $$G_{xz}=\left[\begin{array}{ccc}\cos (\theta )& 0& -\sin (\theta )\\ 0& 1& 0\\ \sin (\theta )& 0& \cos (\theta )\end{array}\right]$$

depend on which dimension.

Steps

1. For column $a_i$ in $A$, use $G$ to build it to consist with right upper triangle matrix
2. e.g. if we need to remove 2nd element in $3\times 3$ matrix, we need to use $G_{xy}$ with $cos(\theta )=\frac{x}{r}$ and $\sin (\theta )=-\frac{y}{r}$ where $x$ is 1st element and $y$ is the 2nd, and $r=\sqrt{x^2+y^2}$.
3. Then get $A_i=A_{i-1}G$. Then check if we need to remove another element (like 3rd element) as well.
4. Repeat this for all columns.
5. $Q=\prod G_i^T$, $R$ is the last $A_i$.

Costs

if $A$ is upper Hessenberg matrix, it only requires $n$ Givens rotation.
otherwise $O(n^2)$.