Geometric intuition for the Householder transformation

Question

I am studying QR decomposition.

Could you explain the geometric intuition for what the Householder transformation does in that context, and why it's sometimes referred to as the Householder reflection.

Answer 1

We start with a square matrix $M$ of dimension $n$. We can think of its $n$ columns as vectors in $\mathbb{R}^n$. We consider the hyperplane generated by the first column (for example the orthogonal complement of that vector). Next, we reflect each of the columns about this hyperplane. In symbols: $H_1M= [ H_1(v_1) \ldots H_1(v_n)]$, where on the RHS we use functional notation for $H_1$. Now, because $v_1$ is normal to the hyperplane, $H_1(v_1)$ looks simple. The rest of the vectors transform like:

That is we subtract twice their projections onto $v_1$ (this gives me the formula for householder reflections). Then we consider the $n-1$ dimensional submatrix of $H_1M:=M_2$, and repeat. The submatrix takes me into the hyperplane, since the first reflection leaves that plane invariant. What we are doing is changing the basis (since Reflections have $det \neq 0$) of the underlying space progressively so that the vectors have a nice representation (Thats what QR decomposition is, The Q contains the orthonormal vectors, while the R tracks all the changes we have made).

Answer 2

Assume that $V$ is an $n$-dimensional Euclidean space. Then, given an orthonormal basis $(e_i)_{i=1}^n$ and an arbitrary n-tuple of vectors $(u_i)_{i=1}^n$, there exists a sequence of $n$ isometries $H_1,...,H_n$ such that

• $H_i$ is either a hyperplane reflection or the identity;
• every vector of the form $$r_j=H_nH_{n-1}\dots H_1(u_j),\qquad j=1,\dots, n,$$ is a linear combination of the vectors $e_1,\dots, e_j$.

In other words, the matrix $R$ whose columns are the components of the vectors $r_j$ written over the basis $(e_i)_{i=1}^n$ is upper triangular. The isometries $H_1,\dots, H_n$ which are not identities (i.e. the hyperplane reflections) correspond to Householder matrices. The composition $$R=H_n\dots H_1A$$ directly yields the $QR$-decomposition of a given matrix $A$ (whose columns are the components of $u_j$ over the given basis).

The geometric interpretation of the $QR$-decomposition can be probably found in several places. I like the presentation in Geometric Methods and Applications by Jean Gallier (have a look at Section 7.3).