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.
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.
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).
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
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).