QR factorization

There is another matrix factorization that is sometimes very useful, the so-called QR decomposition,

$$A = Q \left[ \begin{array}{c} R \\ 0 \end{array} \right] \;\;\;... ...n \Re^{m \times n} (m \geq n), Q \in \Re^{m \times m}, R \in \Re^{n \times n}$$ (13.44)

Here $R$ is upper triangular, while $Q$ is orthogonal, that is,

$$Q^t Q = I$$ (13.45)

where $Q^t$ is the transpose matrix of $Q$. The standard algorithm for the QR decomposition involves successive Householder transformations. The Householder algorithm reduces a matrix A to the triangular form R by $n-1$ orthogonal transformations. An appropriate Householder matrix applied to a given matrix can zero all elements in a column of the matrix situated below a chosen element. Thus we arrange for the first Householder matrix $P_1$ to zero all elements in the first column of $A$ below the first element. Similarly $P_2$ zeroes all elements in the second column below the second element, and so on up to $P_{n-1}$. The Householder matrix $P$ has the form:

$$P = 1 -2 w w^t$$ (13.46)

where $w$ is a real vector with $\Vert w \Vert^2 =1$. The matrix $P$ is orthogonal, because $P^2 = (1 - 2 w w^t ) (1 -2w w^t ) = 1 - 4 w w^t + 4w (w^t w) w^t = 1$. Therefore $P = P^{-1}$. But $P^t = P$, and so $P^t = P^{-1}$, proving orthogonality. Let's rewrite $P$ as

$$P =1 - \frac{u u^t}{ H} \; \; H = \frac{1}{2} \Vert u \Vert _2$$ (13.47)

and $u$ can now be any vector. Suppose $x$ is the vector composed of the first column of $A$. Choose $u = x \mp \Vert x\Vert e_1$ where $e_1$ is the unit vector $[1,0, \ldots, 0]^t$ , and the choice of signs will be made later. Then

$$P x = x - \frac{u}{H} (x \mp \Vert x \Vert e_1)^t x$$

$$= x - \frac{2u ( \Vert x \Vert^2 \mp \Vert x \Vert x_1) }{ 2 \Vert x \Vert^2 \mp 2 \Vert x \Vert x_1 }$$

$$= x -u$$

$$= \mp \Vert x \Vert e_1$$

This shows that the Householder matrix P acts on a given vector $x$ to zero all its elements except the first one. To reduce a symmetric matrix $A$ to triangular form, we choose the vector $x$ for the first Householder matrix to be the first column. Then the lower $n-1$ elements will be zeroed:

$$P_1 A = A'= \left[ \begin{array}{c\vert c} a'_{11} & \\ 0 & \\ \vdots & \raisebox{.5cm}{\em irrelevant} \\ 0 & \end{array} \right]$$ (13.48)

If the vector $x$ for the second Householder matrix is the lower $n-1$ elements of the second column, then the lower $n-2$ elements will be zeroed:

$$\left[ \begin{array}{c\vert c} 1 & 0 \ldots 0 \\ \hline 0 & \\ ... ...ts & \vdots & \raisebox{.5cm}{\em irrelevant} \\ 0 & 0 & \end{array} \right]$$ (13.49)

Where $P_2 \in \Re^{(n-1) \times (n-1)}$ and the quantity $a''_{22}$ is simply plus or minus the magnitude of the vector $[\; a'_{22} \; \cdots \; a'_{n2} \; ]^t$. Clearly a sequence of $n-1$ such transformation will reduce the matrix A to triangular form $R$. Instead of actually carrying out the matrix multiplications in $P A$, we compute a vector $$p:= \frac{A u}{H}$$. Then $$P A= (1 - \frac{u u^t}{H}) A= A -u p^t$$. This is a computationally useful formula. We have the following: $A=P_1 \ldots P_{n-1} R$. We will thus form $Q=P_1 \ldots P_{n-1}$ by recursion after all the $P$'s have been determined:

$$Q_{n-1} = P_{n-1}$$

$$Q_j = P_j Q_{j+1} \; \; \; \; j=n-2,\ldots, 1$$

$$Q = Q_1$$

No extra storage is needed for intermediate results but the original matrix is destroyed.