Skip to main content

Subsection 3.3.2 Householder transformation

What we have discovered in this first video is how to construct a Householder transformation, also referred to as a reflector, since it acts like a mirroring with respect to the subspace orthogonal to the vector \(u \text{,}\) as illustrated in Figure 3.3.2.1.

PowerPoint source (Resources/Week03/HouseholderTransformation.pptx).

Figure 3.3.2.1. Given vector \(x \) and unit length vector \(u \text{,}\) the subspace orthogonal to \(u \) becomes a mirror for reflecting \(x \) represented by the transformation \((I - 2 u u^H )\text{.}\)
Definition 3.3.2.2.

Let \(u \in \Cn \) be a vector of unit length (\(\| u \|_2 = 1 \)). Then \(H = I - 2 u u^H \) is said to be a Householder transformation or (Householder) reflector.

We observe:

  • Any vector \(z \) that is perpendicular to \(u \) is left unchanged:

    \begin{equation*} ( I - 2 u u^H ) z = z - 2 u ( u^H z ) = z . \end{equation*}
  • Any vector \(x \) can be written as \(x = z + u^H x u \) where \(z \) is perpendicular to \(u \) and \(u^H x u \) is the component of \(x \) in the direction of \(u \text{.}\) Then

    \begin{equation*} \begin{array}{rcl} ( I - 2 u u^H ) x \amp=\amp ( I - 2 u u^H ) ( z + u^H x u ) = z + u^H x u - 2 u \begin{array}[t]{c} \underbrace{u^H z} \\ 0 \end{array} - 2 u u^H u^H x u \\ \amp=\amp z + u^H x u - 2 u^H x \begin{array}[t]{c} \underbrace{u^H u}\\ 1 \end{array} u = z - u^H x u. \end{array} \end{equation*}

This can be interpreted as follows: The space perpendicular to \(u \) acts as a "mirror": any vector in that space (along the mirror) is not reflected, while any other vector has the component that is orthogonal to the space (the component outside, orthogonal to, the mirror) reversed in direction, as illustrated in Figure 3.3.2.1. Notice that a reflection preserves the length of the vector.

Homework 3.3.2.1.

Show that if \(H \) is a reflector, then

  • \(H H = I \) (reflecting the reflection of a vector results in the original vector).

  • \(H = H^H \text{.}\)

  • \(H^H H = H H^H = I \) (a reflector is unitary).

Solution

Show that if \(H \) is a reflector, then

  • \(H H = I \) (reflecting the reflection of a vector results in the original vector).

    Solution:

    \begin{equation*} \begin{array}{l} ( I - 2 u u^H ) ( I - 2 u u^H ) \\ ~~~ = ~~~~ \\ I - 2 u u^H - 2 u u^H + 4 u \begin{array}[t]{c} \underbrace{ u^H u } \\ 1 \end{array} u^H\\ ~~~ = ~~~~ \\ I - 4 u u^H + 4 u u^H = I \end{array} \end{equation*}
  • \(H = H^H \text{.}\)

    Solution:

    \begin{equation*} \begin{array}{l} ( I - 2 u u^H )^H\\ ~~~ = ~~~~ \\ I - 2 (u^H)^H u^H\\ ~~~ = ~~~~ \\ I - 2 u u^H \end{array} \end{equation*}
  • \(H^H H = I \) (a reflector is unitary).

    Solution:

    \begin{equation*} \begin{array}{l} H^H H \\ ~~~ = ~~~~ \\ H H \\ ~~~ = ~~~~ \\ I \end{array} \end{equation*}

PowerPoint source (Resources/Week03/HouseholderTransformationAsUsed.pptx)

Figure 3.3.2.3. How to compute \(u\) given vectors \(x \) and \(y \) with \(\| x \|_2 = \| y \|_2 \text{.}\)

Next, let us ask the question of how to reflect a given \(x \in \Cn \) into another vector \(y \in \Cn \) with \(\| x \|_2 = \| y \|_2 \text{.}\) In other words, how do we compute vector \(u \) so that

\begin{equation*} ( I - 2 u u^H ) x = y. \end{equation*}

From our discussion above, we need to find a vector \(u \) that is perpendicular to the space with respect to which we will reflect. From Figure 3.3.2.3 we notice that the vector from \(y \) to \(x \text{,}\) \(v = x - y \text{,}\) is perpendicular to the desired space. Thus, \(u \) must equal a unit vector in the direction \(v \text{:}\) \(u = {v}/{\| v \|_2} \text{.}\)

Remark 3.3.2.4.

In subsequent discussion we will prefer to give Householder transformations as \(I - u u^H /\tau \text{,}\) where \(\tau = {u^Hu}/{2} \) so that \(u \) needs no longer be a unit vector, just a direction. The reason for this will become obvious later.

When employing Householder transformations as part of a QR factorization algorithm, we need to introduce zeroes below the diagonal of our matrix. This requires a very special case of Householder transformation.

As we compute the QR factorization via Householder transformations, we will need to find a Householder transformation \(H \) that maps a vector \(x \) to a multiple of the first unit basis vector (\(e_0 \)). We discuss first how to find \(H \) in the case where \(x \in \Rn \text{.}\) We seek \(v \) so that \(( I - \frac{2}{v^T v} v v^T ) x = \pm \| x \|_2 e_0 \text{.}\) Since the resulting vector that we want is \(y = \pm \| x \|_2 e_0 \text{,}\) we must choose \(v = x - y = x \mp \| x \|_2 e_0 \text{.}\)

Example 3.3.2.5.

Show that if \(x \in \Rn \text{,}\) \(v = x \mp \| x \|_2 e_0 \text{,}\) and \(\tau = v^T v / 2 \) then \(( I - \frac{1}{\tau} v v^T ) x= \pm \| x \|_2 e_0 \text{.}\)

Solution

This is surprisingly messy... It is easier to derive the formula than it is to check it. So, we won't check it!

In practice, we choose \(v = x + \sign( \chi_1 ) \| x \|_2 e_0 \) where \(\chi_1 \) denotes the first element of \(x \text{.}\) The reason is as follows: the first element of \(v \text{,}\) \(\nu_1 \text{,}\) will be \(\nu_1 = \chi_1 \mp \| x \|_2 \text{.}\) If \(\chi_1 \) is positive and \(\| x \|_2 \) is almost equal to \(\chi_1 \text{,}\) then \(\chi_1 - \| x \|_2 \) is a small number and if there is error in \(\chi_1 \) and/or \(\| x \|_2 \text{,}\) this error becomes large relative to the result \(\chi_1 - \| x \|_2 \text{,}\) due to catastrophic cancellation. Regardless of whether \(\chi_1 \) is positive or negative, we can avoid this by choosing \(v = x + \sign( \chi_1 ) \| x \|_2 e_0 \text{:}\)

\begin{equation*} v : = x + \sign( \chi_1 ) \| x \|_2 e_0 = \left( \begin{array}{c} \chi_1 \\ \hline x_2 \end{array} \right) + \left( \begin{array}{c} \sign( \chi_1 ) \| x \|_2 \\ 0 \end{array} \right) = \left( \begin{array}{c} \chi_1 + \sign( \chi_1 ) \| x \|_2 \\ x_2 \end{array} \right). \end{equation*}
Remark 3.3.2.6.

This is a good place to clarify how we index in this course. Here we label the first element of the vector \(x \) as \(\chi_1 \text{,}\) despite the fact that we have advocated in favor of indexing starting with zero. In our algorithms that leverage the FLAME notation (partitioning/repartitioning), you may have noticed that a vector or scalar indexed with \(1 \) refers to the "current column/row" or "current element". In preparation of using the computation of the vectors \(v \) and \(u\) in the setting of such an algorithm, we use \(\chi_1\) here for the first element from which these vectors will be computed, which tends to be an element that is indexed with \(1 \text{.}\) So, there is reasoning behind the apparent insanity.

Ponder This 3.3.2.2.

Consider \(x \in \R^2 \) as drawn below:

and let \(u \) be the vector such that \(( I - u u^H / \tau ) \) is a Householder transformation that maps \(x \) to a vector \(\rho e_0 = \rho \left( \begin{array}{c} 1 \\ 0 \end{array} \right) \text{.}\)

  • Draw a vector \(\rho e_0 \) to which \(x \) is "mirrored."

  • Draw the line that "mirrors."

  • Draw the vector \(v \) from which \(u \) is computed.

  • Repeat for the "other" vector \(\rho e_0 \text{.}\)

Computationally, which choice of mirror is better than the other? Why?