Unit 1.5 · about 5 h
55 / 324Projections, residuals and least squares
Least squares is a geometric approximation before it is a statistical estimator. That geometry explains both the normal equations and why a correct formula need not be the right computational method.
- derive
- implement
You can now
- Derive the normal equations from residual orthogonality, without differentiating a loss.
- Prove symmetry and idempotence of an orthogonal projection and explain uniqueness of the fitted vector.
- Implement projection and a full-column-rank least-squares solve using QR with shape and residual checks.
Covers
- Projection matrices and residual geometry
- Least squares, normal equations and stable solution routes
Study, in this order
3 steps
- Projection matrices and least squaresMIT 18.06 - Linear Algebra
Video Lecture 15, Projections onto subspaces; Lecture 16, Projection matrices and least squares
- Least squares via QRIntroduction to Applied Linear Algebra
Chapter 12, sections 12.1 to 12.3, printed pp. 225 to 234; Algorithm 12.1 on p. 232
Depth · Read the solution and QR algorithm, not the application examples in 12.4. Implement a triangular solve, not an explicit inverse.
- Alternative least-squares solution routesMIT 18.065 - Applied matrix bridge
Lecture 9, Four Ways to Solve Least Squares Problems
Depth · Compare the algebraic routes. Leave the near-collinear normal-equations-versus-QR experiment to Classical ML.
Focus on
- Split \(b=p+r\) with \(p\) in \(\operatorname{col}(A)\) and \(r\) perpendicular to \(\operatorname{col}(A)\). For any other fitted vector \(p+d\), Pythagoras gives \(\|b-(p+d)\|_2^2=\|r\|_2^2+\|d\|_2^2\).
- Residual orthogonality gives \(A^\top(b-Ax)=0\). Full column rank makes \(A^\top A\) invertible and the coefficient solution unique.
- \(P=A(A^\top A)^{-1}A^\top\) is a derivation formula. With an orthonormal column basis \(Q\), compute \(P=QQ^\top\) and solve \(Rx=Q^\top b\).
- \(P^2=P\) expresses projecting twice; \(P^\top=P\) expresses orthogonality. Idempotence alone allows oblique projections.
Reproduce closed-book
A and b as float64 arrays, no random draws: Q,R=np.linalg.qr(A,mode='reduced'); x=np.linalg.solve(R,Q.T@b); P=Q@Q.T. Measure norm(P-P_hand,'fro'), norm(P@P-P,'fro'), norm(P.T-P,'fro'), and norm(A.T@(b-A@x),2). The reference values are 5.7e-16, 5.7e-16, 0.0 and 5.5e-16; require each below 1e-12. The squared residual norm is approximately 0.3333333333333334, within 1e-12 of 1/3.Traps
- A small residual is not required at the optimum: an unattainable \(b\) leaves a nonzero orthogonal residual. Test \(A^\top r\) as well.
- Rank deficiency leaves the fitted vector unique but may leave infinitely many coefficient vectors. The inverse formula is then undefined.
- For \(P=\left[\begin{smallmatrix}1&1\\0&0\end{smallmatrix}\right]\), \(P^2=P\) but \(P^\top\) is not \(P\). It is not the nearest-point Euclidean projection.
Practice
18.06 Problem set 5: complementary projection
Problem set 5, Strang 4th ed., section 4.2, Problems 13 and 17
Compute the 4 by 4 projector, then prove that \(I-P\) is idempotent and identify the residual subspace for an orthogonal \(P\). Attempt before the official solutions. The section mini-project should also test your QR solver on a new full-rank matrix and a rank-deficient failure.
Self-test
-
Why is the orthogonal projection the unique nearest fitted vector?
Every alternative differs by \(d\) in the subspace. Orthogonality makes \(r^\top d=0\), so its squared error is \(\|r\|^2+\|d\|^2\). Positive definiteness makes the extra term positive unless \(d=0\). No column-rank assumption is needed for uniqueness of the fitted vector. -
Where is full column rank used in deriving the inverse formula?
For nonzero \(z\), independence gives \(Az\) nonzero, so \(z^\top A^\top Az=\|Az\|^2>0\). Thus \(A^\top A\) is invertible. Residual orthogonality gives normal equations even without this assumption. -
Why do symmetry and idempotence together imply an orthogonal projection?
Idempotence fixes every vector in \(\operatorname{im}(P)\) and puts \((I-P)b\) in \(\ker(P)\). For \(Pu\) in \(\operatorname{im}(P)\) and \(z\) in \(\ker(P)\), symmetry gives \((Pu)^\top z=u^\top Pz=0\). Thus the two pieces are orthogonal; neither condition alone supplies both facts. -
For full-column-rank \(A=QR\), why solve \(Rx=Q^\top b\)?
\(Q^\top(b-QRx)=0\) follows from residual orthogonality. \(Q^\top Q=I\) reduces it to \(Rx=Q^\top b\). Full column rank makes square triangular \(R\) invertible. This avoids forming \(A^\top A\).
Completion criterion
Stop when
You derive the normal equations and both projector identities, implement the QR solve, and explain why uniqueness of \(p\) is weaker than uniqueness of \(x\).
Mark passed, then open 1.6 Only mark this when you can do it without notes.Leads to
- 2.1 Least squares: residuals, normal equations and stable solvers Apply this derivation to solver choice on an ill-conditioned design.
- 1.7 SVD, pseudoinverse and low-rank approximation Remove the full-column-rank restriction with the pseudoinverse.
Comes after
- 1.3 The four subspaces, rank and solution setsProject an unattainable right-hand side onto the column space.
- 1.4 Inner products, norms, orthogonality and Gram-SchmidtUse orthonormal columns to construct a projection.
Resources for this unit
- MIT 18.06 - Linear Algebra Follow lectures 1-10, 14-17, 21-22, 25, 27, 29-31 and 33 with matching problems. This is the ordered first pass.
- MIT 18.065 - Applied matrix bridge Use lectures 3-10 after 18.06 for SVD, PCA, low-rank approximation, matrix norms and solver difficulty.
- Introduction to Applied Linear Algebra Sample Chapters 1-13 and the extra exercises for computational practice in fitting, least squares and pseudoinverses.
Also in this section
- MIT 6.042J - Proof strand Study textbook Chapters 1 and 3, §§4.1-4.4 and §§5.1-5.4 with matching Unit 1 problems. Leave the rest of the course.
- Mathematics for Machine Learning Use Chapters 2-4 and §10.2 to check notation or re-derive a result. Do not treat it as a second course.
- Essence of Linear Algebra Open only when a geometric picture is missing; it does not replace derivation or problem solving.
- NumPy broadcasting and matmul shape rules Read General broadcasting rules and Broadcastable arrays, then
matmulNotes for stacked matrices and one-dimensional promotion. These close the pool's array-semantics gap. - Fundamentals of Numerical Computation: conditioning and operation counts Python edition, section 2.8 through Residual and backward error for the fixed-matrix perturbation bound; section 2.5.3 for triangular-solve and LU flop counts. Use Exercise 2.8.7 for a condition-number proof, not the unseeded Hilbert experiment.