↑ arvau

Wikipedia / Householder transformation

In linear algebra, a Householder transformation (also known as a Householder reflection or elementary reflector) is a linear transformation that describes a reflection about a plane or hyperplane containing the origin. The Householder transformation was used in a 1958 paper by Alston Scott Householder.

Definition

Operator and transformation

The Householder operator may be defined over any finite-dimensional inner product space with inner product and unit vector as

is linear in its first argument, and antilinear is the complex conjugate.

, and normalize it directly in the Householder operator's expression:

Such an operator is linear and self-adjoint.

, note that the reflection hyperplane can be defined by its normal vector, a unit vector) that is orthogonal to the hyperplane. The reflection of a point about this hyperplane is the Householder transformation:

is the conjugate transpose.

Householder matrix

The matrix constructed from this transformation can be expressed in terms of an outer product as:

is known as the Householder matrix is the identity matrix.

Properties

The Householder matrix has the following properties:

Example

in each entry,

is

representing a coordinate in the 2D plane

coordinates, in other words we have

is normal to.

Applications

Geometric optics

In geometric optics, specular reflection can be expressed in terms of the Householder matrix (see ).

Numerical linear algebra

Note that representing a Householder matrix requires only the entries of a single vector, not of an entire matrix (which in most algorithms is never explicitly formed), thereby minimizing the required storage and memory references needed to use them.

Further, multiplying a Householder matrix by a vector does not involve a full matrix-vector multiplication, but rather only one vector dot product, and then one axpy operation. This means its arithmetic complexity is of the same order of two low-level BLAS-1 operations. Therefore, Householder matrices are extremely arithmetically efficient.

,

some small constant). In other words, multiplications by Householder matrices are also extremely backwards stable.

Since Householder transformations minimize storage, memory references, arithmetic complexity, and optimize numerical stability, they are widely used in numerical linear algebra, for example, to annihilate the entries below the main diagonal of a matrix, to perform QR decompositions and in the first step of the QR algorithm. They are also widely used for transforming to a Hessenberg form. For symmetric or Hermitian matrices, the symmetry can be preserved, resulting in tridiagonalization.

QR decomposition

Householder transformations can be used to calculate a QR decomposition, then our goal is to construct such Householder matrices that act upon the principal submatrices of that matrix, which has the form

has the block form

.

.

for all j>=i, then proceed to the next column.

is an n-dimensional vector with 1 in the i-th position and 0's elsewhere. (Note that we previously established that Householder transformations are unitary matrices, and since the multiplication of unitary matrices is itself a unitary matrix, this gives us the unitary matrix of the QR decomposition).

, respectively.

is real too. Thinking geometrically, we are looking for a plane so that the reflection about this plane happens to land directly on the basis vector. In other words, is a unit vector, this means that we must have

the largest is the one that should be used for greatest accuracy.

Now if we apply equation () back into equation (.

This completes the construction; however, in practice we want to avoid catastrophic cancellation in equation (, we choose, it makes little difference which sign is chosen.

Householder transformations can similarly be applied to a non-square complex matrix. The decompositions are somewhat different.

Tridiagonalization (Hessenberg)

Real symmetric matrix

This procedure is presented in Numerical Analysis by Burden and Faires for real symmetric matrices. In the non-symmetric case, it is still useful as a similar procedure can result in a Hessenberg matrix.

., which are:

:

, and

Then compute:

is its own inverse (involutory), this is a similarity transformation as follows:

Continuing in this manner, the tridiagonal and real symmetric matrix is formed. Since each Householder reflection is a similarity transformation, so is the overall transformation.

Hermitian matrix

Householder transformations can also transform a Hermitian matrix into a Hermitian tri-diagonal matrix. We follow the approach in the University of Connecticut paper except replace matrix transposes by matrix Hermitian conjugates for tri-diagonalization of complex Hermitian matrices rather than real symmetric matrices.

To start, let

is its Hermitian conjugate Hermitian sub-matrixhave the form

is the matrix transpose of the complex conjugate or Hermitian conjugate is a unitary hermitian involutory matrix. Then

and so this is a unitary similarity matrix transformation.

.

to obtain the tri-diagonalization by a succession of unitary Hermitian involutory similarity transformations. For instance, the following example real symmetric or Hermitian matrix is already so tri-diagonalized.

Since the product of unitary matrices is again a unitary matrix and since the similarity transformation of a similarity transformation is again a similarity transformation, the overall transformation is a unitary similarity transformation.

Examples

In this example, also from Burden and Faires, the given matrix is transformed to the similar tridiagonal matrix A3 by using the Householder method.

Following those steps in the Householder method, we have:

The first Householder matrix:

to form

As we can see, the final result is a tridiagonal symmetric matrix which is similar to the original one. The process is finished after two steps.

Quantum computation

As unitary matrices are useful in quantum computation, and Householder transformations are unitary, they are very useful in quantum computing. One of the central algorithms where they're useful is Grover's algorithm, where we are trying to solve for a representation of an oracle function represented by what turns out to be a Householder transformation:

is part of the bra-ket notation which we were using previously)

known as the Grover diffusion operator defined by

.

Computational and theoretical relationship to other unitary transformations

unitary transformation have unit modulus. This can be seen directly and swiftly:

Since arithmetic and geometric means are equal if the variables are constant (see inequality of arithmetic and geometric means), we establish the claim of unit modulus.

For the case of real valued unitary matrices we obtain orthogonal matrices. It follows rather readily (see Orthogonal matrix) that any orthogonal matrix can be decomposed into a product of 2-by-2 rotations, called Givens rotations, and Householder reflections. This is appealing intuitively since multiplication of a vector by an orthogonal matrix preserves the length of that vector, and rotations and reflections exhaust the set of (real valued) geometric operations that render invariant a vector's length.

The Householder transformation was shown to have a one-to-one relationship with the canonical coset decomposition of unitary matrices defined in group theory, which can be used to parametrize unitary operators in a very efficient manner.

Finally we note that a single Householder transform, unlike a solitary Givens transform, can act on all columns of a matrix, and as such exhibits the lowest computational cost for QR decomposition and tridiagonalization. The penalty for this "computational optimality" is, of course, that Householder operations cannot be as deeply or efficiently parallelized. As such Householder is preferred for dense matrices on sequential machines, whilst Givens is preferred on sparse matrices, and/or parallel machines.

See also

Notes

References

  • (Herein Householder Transformation is cited as a top 10 algorithm of this century)