A quick recap on Householder reflectors

Introduction

The Householder transformation is one of the elementary linear transformations that can be applied in vector spaces. It is often used to perform matrix transformations in an efficient way - for example when performing QR decomposition or SVD decomposition of matrices. It can also be used to solve the linear least squares problem too.

The transformation represents the reflection of about a hyperplane that goes through the origin and is usually characterized by the planes normal vector. Recall that a reflection of a point $x$ at the hyperplane defined by the normal vector $v$ can be calculated by

In this case $v^{*}$ is the conjugate transpose of $v$. Note that it has been assumed that $v$ is a column unit vector. One can imagine this to work by first determining the shadow or projection of the vector from $0$ to the point $x$ onto $v$. Subtracting this once from $x$ yields the component of the location vector of $x$ that is orthogonal to $v$ - i.e. the component in the plane. If we now want to reflect on the plane we just subtract the orthogonal component a second time.a

The inner product $\langle x, v \rangle$ yields the length but not the direction along the normal $v$. To get a vector again it’s multiplied by $v$ again. The second form of the projection that one sees above has the advantage of always being left multiplied on $x$:

Definition

Using matrix formalism we can define a transformation for any vector yielding another vector exactly using the above formula

We recall that $v^{*}$ is the conjugate transpose so it’s result will be a matrix. We can also add normalization of the vectors to our formula:

This now yields the definition of our reflector matrix

A very simple Python method to evaluate the Householder transformation matrix for a vector $v$ can be given by:

import numpy as np

def householder(v):
    return np.identity(len(v)) - 2 * np.outer(v, v) / (np.linalg.norm(v) ** 2)

Properties

• The reflector is Hermitian: $H = H^{*}$. This obviously works due to symmetry of the dot product $v * v^{*}$
• The reflector is Unitary: $H^{-1} = H^{*}$
• The transformation is involutory: $H^{-1} = H$

Zeroing matrix columns

One of the most useful applications of householder transformations is the zeroing of matrix elements (for example in QR decomposition and SVD decomposition).

Lets take a look at the action of the Householder reflector on a single vector:

Lets assume we want to zero out all elements but the first in $x$. We now utilize the basis vector $e_1$ that points into the same direction as the first element of $x$ and has the same length - but all zero components for the remaining entries:

Then we calculate the vector $v$ as difference between $x$ and $e_1$:

This vector also gets normalized:

Now we form the Householder reflector as defined above:

To zero out the matrix or vector column we then just multiply our matrix or vector with our Householder transformation:

As one can see in the table below this procedure zeros out the columns below the diagonal of our matrix. When we want to recover the input we just have to chain all of our transformations and right multiply with the matrices:

Taking a look at the error deviation matrix yields the zero matrix:

Using Householder reflectors to zero rows

One can simply use the same method with Householder reflectors to zero out full rows in a matrix. We just have to change to norm of the basis vector to the norm of our row vector and left multiply our matrix by our transformations.

As one can see this in the example run below this procedure zeros out the rows above the diagonal of our matrix. When we want to recover the input we just have to chain all of our transformations and left multiply with the matrices:

Taking a look at the error deviation matrix yields the zero matrix:

References

• Numerical Linear Algebra by Lloyd N. Trefethen and David Bau is a very valuable reference for linear algebra
• StatLect has an excellent article on Householder reflectors with complex matrices
• The CS 6120 lecture on Matrix Computations at Cornell university has some very interesting notes in lecture 16

This article is tagged: Math, Programming, Physics, How stuff works, Computational linear algebra