Householder transformation

This entry describes the Householder transformation $u=Hv$, the most frequently used algorithm for performing QR decomposition. The key object here is the Householder matrix $H$, a symmetric and orthogonal matrix of the form

$$H=I-2x{x}^T,$$

where $I$ is the identity matrix and we have used any normalized vector $x$ with ${||x||}_2^2=x^{T}x=1$.

The Householder transformation zeroes the last $m-1$ elements of a column vector below the first element:

$$\left[\begin{array}{c}\hfill v_1\hfill \\ \hfill v_2\hfill \\ \hfill \mathrm{⋮}\hfill \\ \hfill v_m\hfill \end{array}\right]\to \left[\begin{array}{c}\hfill c\hfill \\ \hfill 0\hfill \\ \hfill \mathrm{⋮}\hfill \\ \hfill 0\hfill \end{array}\right]\text{with}c=\pm {||v||}_2=\pm {\left(\sum _{i=1}^m{v}_i^2\right)}^{1/2}$$

One can verify that

$$x=f\left[\begin{array}{c}\hfill v_1-c\hfill \\ \hfill v_2\hfill \\ \hfill \mathrm{⋮}\hfill \\ \hfill v_m\hfill \end{array}\right]\text{with}f=\frac{1}{\sqrt{2c(c-v_1)}}$$

fulfils $x^{T}x=1$ and that with $H=I-2x{x}^T$ one obtains the vector .

To perform the decomposition of the $m\times n$ matrix $A=QR$ (with $m\ge n$) we construct an $m\times m$ matrix $H^{(1)}$ to change the $m-1$ elements of the first column to zero. Similarly, an $m-1\times m-1$ matrix $G^{(2)}$ will change the $m-2$ elements of the second column to zero. With $G^{(2)}$ we produce the $m\times m$ matrix

After $n$ such orthogonal transformations ($n-1$ times in the case that $m=n$), we let

$$R=H^{(n)}\mathrm{\cdots }{H}^{(2)}{H}^{(1)}A.$$

$R$ is upper triangular and the orthogonal matrix $Q$ becomes

$$Q=H^{(1)}{H}^{(2)}\mathrm{\cdots }{H}^{(n)}.$$

In practice the $H^{(i)}$ are never explicitly computed.

References

• Originally from The Data Analysis Briefbook(http://rkb.home.cern.ch/rkb/titleA.htmlhttp://rkb.home.cern.ch/rkb/titleA.html)