Householder transformation

Householder transformation

In 3-dimensional space a Householder transformation is basically a reflection of a vector or point about a plane. In general euclidean space it is in fact a linear transformation that describes a reflection about a hyperplane (which has to contain the origin).

The Householder transformation was introduced 1958 by Alston Scott Householder. It can be used to obtain a QR decomposition of a matrix.

Definition and properties

The reflection hyperplane can be defined by a unit vector v (a vector with length 1), that is orthogonal to the hyperplane.

If v is given as a column unit vector and I is the identity matrix the linear transformation described above is given by the Householder matrix (v^T denotes the transpose of the vector v)

Q = I − 2 vv^T.

The Householder matrix has the following properties:

it is symmetrical: Q = Q^T
it is orthogonal: Q^-1 = Q^T
therefore it is also involutary: Q² = I.

Furthermore, Q really reflects a point X (which we will identify with its position vector x) as describe above, since

Qx = x − 2 vv^Tx = x − 2 <v,x> v,

where < > denotes the dot product. Note that <v,x> is equal to the distance of X to the hyperplane.

Application: QR decomposition

Q can be used to reflect a vector in such a way that all coordinates but one disappear. Let x be an arbitary m-dimensional column vector of length |α| (for numerical reasons α should get the same sign as the first coordinate of x).

Then, where e₁ is the vector (1,0,...,0)^T, and || || the euclidean norm, set

u = x − αe₁,

v = u / ||u||,

Q = I - 2 vv^T.

Q is a Householder matrix and

Qx = (α,0,...,0)^T.

This can be used to gradually transform an m-by-n matrix A to upper triangular form. First, we multiply A with the Householder matrix Q₁ we obtain when we choose the first matrix column for x. This results in a matrix QA with zeros in the left column (except for the first line).

This can be repeated for A' resulting in a Housholder matrix Q'₂. Note that Q'₂ is smaller than Q₁. Since we want it really to operate on Q₁A instead of A' we need to expand it to the upper left, filling in a 1, or in general:

After t iterations of this process, t = min(m − 1, n),

R = Q_t...Q₂Q₁A

is a upper triangular matrix. So, with

Q = Q₁Q₂...Q_t,

A = QR is a QR decomposition of A.

This method is numerically stable.