A QR factorization solves least-squares problems without explicitly forming . To turn that idea into an algorithm, we need an economical way to zero many entries while preserving Euclidean lengths. A Householder reflector does exactly that with a single vector.
Reflecting a vector to an axis
Definition 4.2.1
(Householder reflector)
For nonzero the Householder reflector is
It reflects across the hyperplane orthogonal to .
Theorem 4.2.2
(Reflector properties and reflection to the first axis)
Let and let be as in (1). Then and , hence and for every . Moreover, given nonzero , set and choose when , otherwise. With
all but the first entry of are zero.
Proof
(Computing from two inner products)
Write , so and is symmetric with . Hence and . For (2), , so and . The first component of has magnitude , so and . Therefore . The rule for makes the sign unambiguous. If , no reflector is needed.
Proof X-ray
Why choose this sign?
The proof is valid for either sign, and in exact arithmetic would also give a reflector. What the sign changes is the size of : with both inner products are multiples of , which is never small, so the division in is safe. The first component of has magnitude , so forming it does not subtract nearly equal positive numbers. For with small , the chosen vector starts with , close to . The alternative starts with , of order and vulnerable to cancellation.
This sign choice protects a crucial subtraction, but does not by itself prove a complete floating-point backward-error theorem. Robust norm computation and scaling still matter when components are extremely large or small.
Building and applying QR
At column of with , a reflector is applied only to rows , turning the current column tail into a multiple of . This yields the factorization stated next.
Theorem 4.2.3
(Householder QR factorization)
Let with . There are reflectors , some of which may equal , such that
with upper triangular. If has full column rank, then is nonsingular, and the least-squares solution solves , with residual norm .
Proof
(Induction over the columns)
Suppose that after steps the matrix is zero below the diagonal in its first columns. Let be the part of column in rows . If , build from by (2) and put ; this is again a reflector, with the vector padded by zeros, and it acts only on rows . The first columns are zero in those rows, so they are unchanged, while column becomes zero below its diagonal. If , take . After step the matrix has the form with upper triangular. Each is symmetric and orthogonal, so is orthogonal and . Orthogonality preserves rank, so and full column rank makes nonsingular. Finally, , which is minimal exactly when .
A zero column tail can be skipped; the identity still holds with that . To apply a reflector to a matrix block , compute . The vector can be stored instead of the dense . Applying the same reflectors to in their construction order produces without explicitly forming . Updating the trailing blocks costs arithmetic operations for , whereas constructing a dense full is unnecessary for this solve.
Worked examples
Worked example 4.2.4
(Reflecting a vector with positive first entry)
For , , and . Formula (1) gives
The negative leading entry is intentional. A later diagonal-sign convention can change it if desired, but orthogonality and the least-squares solution do not require a positive diagonal.
Worked example 4.2.5
(A least-squares problem with two reflectors)
Let and . The first column has , , and , so . For the second column we have , so . Hence
The tail has and a negative first entry, so and the vector acting on rows is , with . It maps the tail to , so .
For : , so . For its tail, and . Thus . Back substitution in gives and then , so , with residual norm .
Check: the normal equations hold for , and has norm . The diagonal of has mixed signs, which does not matter.
Worked example 4.2.6
(The sign branch for a negative first entry)
Take . Now , so , and , with . Then
The other choice also gives an exact reflector in exact arithmetic, with , but its first component is the difference . For the same pattern is the cancellation described in the X-ray above.
Counterexample mode
A zero pivot is not a complete rank diagnosis
For , the first column tail is zero, yet has rank one. Skipping that reflector does not make the whole matrix zero. In finite precision, a small diagonal entry by itself is not a universal numerical-rank certificate; pivoting or singular values and a stated tolerance may be needed.
Common mistakes
Common mistake
(Applying the reflectors to b in the wrong order)
To get the reflector must act first. In the two-reflector example, applying first and then gives instead of , and back substitution would then return instead of .
Common mistake
(Forming the dense reflector)
Building as an matrix and multiplying costs for a block with columns. The formula costs only and needs just the vector .
Practice with solutions
Quick check
(Compute a reflector for using the stated sign convention.)
Decide first; remember the rule for .
Solution · Answer
, , , so and .
Quick check
(Why does applying preserve ?)
Compute .
Solution · Answer
Because : .
Quick check
(In (3), in what order are reflectors applied to to obtain ?)
Read from the right.
Solution · Answer
Apply first, then , and so on through .
Quick check
(Must a Householder QR factorization have positive diagonal entries in ?)
Look at the first example above.
Solution · Answer
No; the diagonal entries of can be negative, and signs can be adjusted separately if a convention requires them.