Householder QR and least squares

For a nonzero vector x, choose α as minus the sign of its first component times its Euclidean norm, taking the sign of zero as positive. Form v=x−αe₁. The reflector H=I−2vvᵀ/(vᵀv) is symmetric and orthogonal, and maps x to αe₁. The chosen sign makes the first component of v a sum of like-signed magnitudes rather than a nearly cancelling difference. A zero column tail is handled separately; one need not divide by a zero reflector vector.

Apply such reflectors to successive trailing column segments of a rectangular matrix. Their product produces an upper trapezoidal form while their orthogonality preserves two-norms. An implementation stores reflector vectors and scale factors compactly, then applies their action to other vectors without forming a dense full Q. Scaled norm calculations are also important to avoid overflow or underflow in constructing reflectors. The symbolic formula describes the geometry, while stable norm evaluation and sign choice make that geometry numerically useful.

Let A have m rows, n columns, m at least n, and full column rank. Its thin QR factorization is A=Q₁R, where Q₁ has orthonormal columns and R is nonsingular upper triangular. Complete Q₁ to an orthogonal matrix Q=(Q₁,Q₂). Applying Qᵀ to Ax−b splits the squared norm into the squared triangular mismatch and the squared component Q₂ᵀb. The second term cannot be altered by any x. Setting the first term to zero gives the unique least-squares solution.

The normal equations AᵀAx=Aᵀb give the same exact minimizer under full column rank, but the two-norm condition number of AᵀA is the square of that of A. Forming this product in finite precision can therefore make weak column directions difficult to resolve. Householder QR is normwise backward stable under standard arithmetic assumptions, avoiding that explicit squaring step. It does not remove intrinsic sensitivity when data perturbations change nearly dependent columns or when the residual geometry makes the fitted coefficients sensitive.

For a rank-deficient matrix, R is not invertible and the previous triangular conclusion cannot be used unchanged. Column-pivoted QR can reveal approximate dependence and rearrange the important columns, while the SVD gives a direct singular-value view and a minimum-norm solution after a rank decision. Numerical rank depends on a tolerance tied to data uncertainty and scale; it is not simply the count of floating-point entries that happen to equal zero. A full-rank routine's assumptions should be checked before treating its output as a rank-aware answer.

After computing a least-squares solution, the residual generally is not zero. The correct optimality check is that it is orthogonal to the column space, so Aᵀr is small relative to appropriate scales. Report the residual norm because it records model mismatch or noise as well as numerical effects. A tiny optimality residual need not imply accurately determined coefficients when the design is ill conditioned. For repeated fits with the same design and different observations, the QR factors can be reused, making the stable factorization an efficient computational object.