Householder transformation


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

H=I-2xxT,

where I is the identity matrixMathworldPlanetmath and we have used any normalized vector x with ||x||22=xTx=1.

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

[v1v2vm][c00]withc=±||v||2=±(i=1mvi2)1/2

One can verify that

x=f[v1-cv2vm]withf=12c(c-v1)

fulfils xTx=1 and that with H=I-2xxT one obtains the vector [c00]T.

To perform the decomposition of the m×n matrix A=QR (with mn) we construct an m×m matrix H(1) to change the m-1 elements of the first column to zero. Similarly, an m-1×m-1 matrix G(2) will change the m-2 elements of the second column to zero. With G(2) we produce the m×m matrix

H(2)=[1000G(2)0].

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

R=H(n)H(2)H(1)A.

R is upper triangular and the orthogonal matrix Q becomes

Q=H(1)H(2)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