Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
A suggestion: look at the 2-by-2 and 3-by-3 cases. Figure out what the appropriate Householders would look like, and consider what happens when you apply them to appropriate entities... say, points in the plane or in space. –  J. M. Dec 17 '10 at 9:20

2 Answers 2

up vote 1 down vote accepted

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: alt text

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.