Why reduce the objective?
Suppose each of a very large number of observations has features. Collect the feature rows in and the responses in . We seek a vector minimizing . When is much larger than , the data may not fit in memory, although a matrix does. A useful summary should allow us to process each row once and still recover the same least-squares problem. This unit builds such a summary using QR; it complements the earlier scalar line-fitting pipeline.
Orthogonal decomposition
Assume initially that . The summary we want is defined by the property it must have, not by the way it is computed.
Definition 4.2.1
(Thin QR factorization and least-squares summary)
Let with and .
- A thin QR factorization writes , where has orthonormal columns () and is upper triangular. It exists even if is rank deficient, although then is singular.
- A least-squares summary of is a triple with upper triangular, and such that for every .
The next lemma shows that a thin QR factorization produces a summary directly.
Lemma 4.2.2
(Orthogonal splitting of the residual)
Let be a thin QR factorization, and set and . Then, for every ,
Proof
(The cross term vanishes)
Write
Since and , we have , so the residual is perpendicular to every column of . The vector lies in the span of those columns. The two terms are therefore orthogonal, whatever is, and Pythagoras gives . Finally for every , which turns the first term into .
This is stronger than merely preserving the minimizer: the full objective and its minimum value survive. In exact arithmetic, ; in floating-point arithmetic that subtraction may lose accuracy when the residual is small. Applying the same orthogonal transformations to and accumulating the discarded components' squared norms avoids relying on that subtraction, though rounding error still exists.
If has full column rank, is invertible and the unique minimizer satisfies ; use triangular back substitution, not an explicit inverse. The smallest loss is . If rank is deficient, (1) remains true, but can be inconsistent or have infinitely many solutions. In general minimize and add to obtain the minimum loss; alone need not be that minimum. A rank-revealing QR or SVD can identify numerical rank and provide a prescribed solution, such as the minimum-norm one; plain unpivoted back substitution does not automatically do that.
Common mistake
(Back-substituting with a singular triangular factor)
With two identical feature columns, every thin QR factor has the form , because the second column of already lies in the span of the first. Back substitution then meets the equation : it has no solution when and infinitely many when . Dividing by the zero pivot, or by a tiny pivot produced by rounding, gives a meaningless coefficient vector. Check the rank, or use a rank-revealing method, before treating as uniquely solvable.
A block algorithm and its invariant
Read the first block with at least rows and its responses . Compute its thin QR, , and set , . Maintain . For each subsequent block , factor the stacked matrix and transform the stacked response:
Replace the old summary with the new one. Here has orthonormal columns, including when the stacked matrix is rank deficient. In a practical Householder implementation, apply reflectors to the response instead of materializing the whole .
Proposition 4.2.3
(Objective-preserving streaming invariant)
After any number of processed blocks, let denote their concatenation. In exact arithmetic the maintained summary satisfies, for every ,
Proof
(Induction over the processed blocks)
The first block satisfies the identity by the lemma (1). Suppose it holds before another block . The squared norm of a stacked vector is the sum of the squared norms of its parts, so for every
Apply (1) to the stacked matrix and the stacked response : the last squared norm equals . Adding gives exactly as specified above. Induction proves the claim.
The induction is short, but each of its two equalities carries a different hypothesis.
Proof X-ray
Where the hypotheses enter the induction
The first equality only stacks rows: the new block is appended once, and the old data are replaced by the inductive hypothesis. That replacement is legitimate because the hypothesis holds for every , as a function, not just at a minimizer. A summary that kept only the old minimizer could not be combined with a new block, since the minimizer of a sum of two losses is not determined by the two separate minimizers. The second equality is the lemma applied to the stacked matrix, which has at least rows because the old already has ; the lemma needs orthonormal columns, not full rank, so rank-deficient blocks are allowed. The argument closes because the new constant is the old constant plus the energy discarded at this step. What can break it is the data, not the algebra: a block included twice adds its squared residual twice and changes the objective.
The same identity supports a tree reduction: summarize disjoint blocks of at least rows independently, stack two summaries' matrices and vectors, perform QR, and add their two values and the newly discarded energy. The tree and sequential summaries may have different and signs in , yet their objectives agree in exact arithmetic. Floating-point results can depend on the reduction order.
Concept lensAlgebraic
The summary is the triangular factor of the augmented matrix
Append as an extra column. When , a thin QR factorization of the augmented matrix is
So is just its triangular factor , with the square of the last diagonal entry. Equivalently, that factor satisfies , which packs the three identities checked in the worked example. Streaming the summary is updating the QR factor of one block of rows at a time.
Worked example
Worked example 4.2.4
(Three observations, two features)
Take rows , and with responses . The first two rows give , , . After adding the third row, one valid summary is
To check it independently, and . Also . These three identities establish (1) by expanding both sides. Back substitution gives . The three residuals are , hence the loss is , matching .
The same update rule merges two summaries that were computed separately, as in a tree reduction.
Worked example 4.2.5
(Merging two scalar summaries)
Two disjoint blocks summarize to and . Stack them: the matrix is and the response is . Its thin QR has and , so . The newly discarded energy is , and the merged constant is . The merged summary is .
Check directly: the total objective is , which equals . The minimizer is and the minimum is . The from the second block must be retained.
The last example is the degenerate case in which the stacked matrix is rank deficient.
Worked example 4.2.6
(A rank-deficient block)
Let and . The first column has norm , so ; the second column equals the first, so a thin QR may complete with and take
Identity (1) reads , so every pair with is optimal and the minimum is zero. Back substitution stops at , which leaves free. Writing , the squared norm is uniquely minimized at the minimum-norm minimizer .
Cost, conditioning and a counterexample
With a block of rows, a dense Householder QR of the stack takes arithmetic operations. Holding the stack and response takes numbers, plus the summary; dense QR of all rows is when . With blocks the sequential stacked factorizations have an upper bound , including the repeated work on the summary rows. These are arithmetic and working-storage models, not wall-clock guarantees: input bandwidth, communication, implementation and sparsity matter. Block sizes affect overhead, and a sparse matrix need not remain sparse after factorization.
Forming and is another compact reduction, but for full-column-rank , the spectral condition number obeys . This follows because the eigenvalues of are the squares of the singular values of . Squaring a large condition number can magnify sensitivity and roundoff; QR avoids explicitly forming the normal matrix, though it cannot remove the original problem's sensitivity. Exact identities here are not a numerical-error guarantee for every implementation.
Counterexample mode
A summary without the residual constant
Claim: the pair is enough to report the least-squares fit. Let and . Then , , and . Dropping still produces the correct minimizer , because there, but it reports a minimum loss of zero, whereas the residuals give loss . After a merge the error persists: every discarded constant is lost. The repaired statement is that the summary is the triple , as in the definition.
A good fit of the data also does not certify the coefficients.
Common mistake
(Reading a small residual as accurate coefficients)
Take and with a small . The exact solution is , yet the vector has residual and loss . A tiny loss is therefore compatible with coefficients that are wrong by order one when the features are nearly dependent. Judge coefficient accuracy through conditioning, not through the residual alone.
Practice and complete solutions
Quick check
(For and , find , , and the minimizer.)
A single block of two rows: compute one thin QR factorization.
Solution · Answer
Choose , so , , and . Thus and the minimum loss is ; indeed the residuals at are .
Quick check
(Can the maintained constant decrease when a new block is processed?)
Look at the update rule for .
Solution · Answer
No. The update is , and a squared norm is nonnegative, so . A decrease in a computed value signals rounding trouble or a bookkeeping error, such as overwriting instead of adding to it.
Quick check
(The largest and smallest singular values of a full-rank matrix are and . Find and .)
Use the relation between the singular values of and the eigenvalues of .
Solution · Answer
. The extreme eigenvalues of are and , so . This comparison does not assert an actual error without an error analysis and data.