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)

Title	Householder transformation
Canonical name	HouseholderTransformation
Date of creation	2013-03-22 12:06:07
Last modified on	2013-03-22 12:06:07
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	10
Author	mathcam (2727)
Entry type	Algorithm
Classification	msc 15A57
Classification	msc 65F25
Synonym	Householder reflection
Synonym	Householder matrix
Related topic	GramSchmidtOrthogonalization