Householder QR decomposition (source code)

= Householder QR decomposition
{c}
{wiki}

= Householder QR factorization
{c}
{synonym}

A <Householder QR decomposition> introduces zeros below successive diagonal entries using <orthogonal> reflections. For a nonzero real column segment $x$, set $\sigma=1$ when $x_1\ge0$ and $\sigma=-1$ otherwise, and define
$$
v=x+\sigma\|x\|_2e_1,\qquad H=I-2\frac{vv^T}{v^Tv}.
$$
Then $H^TH=I$ and $Hx=-\sigma\|x\|_2e_1$. The sign choice avoids subtracting nearly equal numbers when constructing $v$. If the segment is zero, skip the reflection.

For $A\in\mathbb R^{m\times n}$ with $m\ge n$, apply the first reflection to all rows, the second to rows $2,\ldots,m$, and so on, extending each by an identity on the earlier rows. This gives
$$
R=H_n\cdots H_1A,\qquad Q=H_1\cdots H_n,\qquad A=QR,
$$
where $Q$ is <orthogonal> and $R$ consists of an $n\times n$ <upper triangular matrix> above $m-n$ zero rows. The reflections are stored through their defining <vectors>, so a full dense $Q$ need not be formed.<Fundamentals of Numerical Computation by Tobin A. Driscoll and others>[Section 3.4, Householder reflections and successive triangularization]{ref}

For full column rank, the top $n\times n$ block of $R$ is invertible and <back substitution> solves the transformed <least squares> problem. Orthogonal transformations preserve the <Euclidean norm>, making this route useful when the <normal equations> would square a large <condition number>.