## Unit3.3.2Householder 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. 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{.}$
###### Definition3.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*}

These observations can be interpreted as follows: The space perpendicular to $u$ acts as a "mirror": a vector that is an element in that space (along the mirror) is not reflected. However, if a vector has a component that is orthogonal to the mirror, that component is reversed in direction, as illustrated in Figure 3.3.2.1. Notice that a reflection preserves the length of a vector.

###### Homework3.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*} 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{.}$

###### Remark3.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{.}$

###### Example3.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 \\ \hline 0 \end{array} \right) = \left( \begin{array}{c} \chi_1 + \sign( \chi_1 ) \| x \|_2 \\ \hline x_2 \end{array} \right). \end{equation*}
###### Remark3.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 This3.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?