next up previous contents
Next: A simple direct optimizer: Up: Annexes Previous: Cholesky decomposition.   Contents

QR factorization

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

$\displaystyle 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,

$\displaystyle 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:

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

$\displaystyle P =1 - \frac{u u^t}{ H} \; \;$    with $\displaystyle 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
$\displaystyle P x$ $\displaystyle =$ $\displaystyle x - \frac{u}{H} (x \mp \Vert x \Vert e_1)^t x$  
  $\displaystyle =$ $\displaystyle 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 }$  
  $\displaystyle =$ $\displaystyle x -u$  
  $\displaystyle =$ $\displaystyle \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:

$\displaystyle 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:

$\displaystyle \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 $ \displaystyle p:=
\frac{A u}{H}$. Then $ \displaystyle 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:
$\displaystyle Q_{n-1}$ $\displaystyle =$ $\displaystyle P_{n-1}$  
$\displaystyle Q_j$ $\displaystyle =$ $\displaystyle P_j Q_{j+1}
\; \; \; \; j=n-2,\ldots, 1$  
$\displaystyle Q$ $\displaystyle =$ $\displaystyle Q_1$  

No extra storage is needed for intermediate results but the original matrix is destroyed.
next up previous contents
Next: A simple direct optimizer: Up: Annexes Previous: Cholesky decomposition.   Contents
Frank Vanden Berghen 2004-04-19