# 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-2xx^{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:

 $\begin{bmatrix}v_{1}\\ v_{2}\\ \vdots\\ v_{m}\end{bmatrix}\rightarrow\begin{bmatrix}c\\ 0\\ \vdots\\ 0\end{bmatrix}\text{with}\;c=\pm||v||_{2}=\pm\left(\sum_{i=1}^{m}v_{i}^{2}% \right)^{1/2}$

One can verify that

 $x=f\begin{bmatrix}v_{1}-c\\ v_{2}\\ \vdots\\ v_{m}\end{bmatrix}\text{with}\;f=\frac{1}{\sqrt{2c(c-v_{1})}}$

fulfils $x^{T}x=1$ and that with $H=I-2xx^{T}$ one obtains the vector $\begin{bmatrix}c&0&\cdots&0\end{bmatrix}^{T}$.

To perform the decomposition of the $m\times n$ matrix $A=QR$ (with $m\geq 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

 $H^{(2)}=\begin{bmatrix}1&0&\cdots&0\\ 0&&&\\ \vdots&&G^{(2)}&\\ 0&&&\end{bmatrix}.$

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

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

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

 $Q=H^{(1)}H^{(2)}\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 HouseholderTransformation 2013-03-22 12:06:07 2013-03-22 12:06:07 mathcam (2727) mathcam (2727) 10 mathcam (2727) Algorithm msc 15A57 msc 65F25 Householder reflection Householder matrix GramSchmidtOrthogonalization