Orthogonality & Least Squares

Study Sheet

Orthogonality & Least Squares

Projections, distance, and best fit

Projection and Best Approximation

Tip
The projection formula

The projection of u\mathbf u onto v\mathbf v is u⋅vv⋅v v\dfrac{\mathbf u\cdot\mathbf v}{\mathbf v\cdot\mathbf v}\,\mathbf v — the shadow u\mathbf u casts on the line through v\mathbf v. What is LEFT OVER, u−proj\mathbf u - \text{proj}, is perpendicular to v\mathbf v; its length is the distance to the line.

Concept
Least squares: closest, not exact

When Ax=bA\mathbf x = \mathbf b has no solution, solve ATA x^=ATbA^{\mathsf T}A\,\hat{\mathbf x} = A^{\mathsf T}\mathbf b instead: Ax^A\hat{\mathbf x} is the PROJECTION of b\mathbf b onto the column space — the best possible fit. Every regression line in statistics is this computation.

Example
The simplest regression

Fitting a constant cc to data 1,3,51, 3, 5 minimizes (c−1)2+(c−3)2+(c−5)2(c-1)^2 + (c-3)^2 + (c-5)^2; the derivative vanishes at the MEAN, c=3c = 3. Least squares generalizes the average — and orthogonality is why it works.

Side note
Significance: least squares built the modern world

Gauss invented least squares to find a lost asteroid (Ceres, 1801) — and today every regression, every GPS position fix (overdetermined satellite equations), and every curve fit in every lab runs the normal equations from this topic. Orthogonality is also why JPEG and MP3 work: signals are projected onto orthogonal cosine bases and the small components discarded.

Try it
Try it: a distance via projection

Find the distance from (5,1)(5, 1) to the line through the origin along (2,1)(2, 1). Work: coefficient c=10+14+1=115c = \tfrac{10 + 1}{4 + 1} = \tfrac{11}{5}; projection 115(2,1)\tfrac{11}{5}(2,1); remainder (5,1)−(225,115)=(35,−65)(5,1) - \left(\tfrac{22}{5}, \tfrac{11}{5}\right) = \left(\tfrac35, -\tfrac65\right); distance =9+3625=355= \sqrt{\tfrac{9+36}{25}} = \tfrac{3\sqrt5}{5}. Verify: remainder ⋅(2,1)=6−65=0\cdot (2,1) = \tfrac{6 - 6}{5} = 0 ✓.

Proofs & Why It Matters

Tip
Proof: the projection formula

Seek the multiple cvc\mathbf v of v\mathbf v making the remainder u−cv\mathbf u - c\mathbf v orthogonal to v\mathbf v: (u−cv)⋅v=0(\mathbf u - c\mathbf v)\cdot\mathbf v = 0 gives c=u⋅vv⋅vc = \dfrac{\mathbf u\cdot\mathbf v}{\mathbf v\cdot\mathbf v} in one step.

This cvc\mathbf v is also the CLOSEST point on the line: for any other multiple tvt\mathbf v, Pythagoras gives ∣u−tv∣2=∣u−cv∣2+∣cv−tv∣2≥∣u−cv∣2|\mathbf u - t\mathbf v|^2 = |\mathbf u - c\mathbf v|^2 + |c\mathbf v - t\mathbf v|^2 \ge |\mathbf u - c\mathbf v|^2. ■\blacksquare

Tip
Proof: the normal equations of least squares

The best x^\hat{\mathbf x} minimizes ∣Ax−b∣|A\mathbf x - \mathbf b|, i.e. makes Ax^A\hat{\mathbf x} the closest point to b\mathbf b in the column space. Closest means the error b−Ax^\mathbf b - A\hat{\mathbf x} is orthogonal to every column of AA (else sliding along that column would shrink it — the projection argument again).

Orthogonality to all columns at once is AT(b−Ax^)=0A^{\mathsf T}(\mathbf b - A\hat{\mathbf x}) = \mathbf 0, i.e. ATAx^=ATbA^{\mathsf T}A\hat{\mathbf x} = A^{\mathsf T}\mathbf b. Fitting a constant to data makes this one equation whose solution is the mean. ■\blacksquare

Going Deeper: Explanations & Worked Problems

Concept
Decomposing a vector: the along-and-across split

The projection formula does more than find shadows — it SPLITS any u\mathbf u into two orthogonal pieces relative to a direction v\mathbf v: the part along, projvu=u⋅vv⋅vv\text{proj}_{\mathbf v}\mathbf u = \tfrac{\mathbf u\cdot\mathbf v}{\mathbf v\cdot\mathbf v}\mathbf v, and the part across, u−projvu\mathbf u - \text{proj}_{\mathbf v}\mathbf u, which is orthogonal to v\mathbf v by construction. Pythagoras then bookkeeps the lengths: ∣u∣2=∣along∣2+∣across∣2|\mathbf u|^2 = |\text{along}|^2 + |\text{across}|^2. The "across" length IS the distance from the point to the line — that is where the point-to-line distance formula comes from. Iterating the split against several directions in turn is Gram–Schmidt: peel off the component along each previously built direction, keep what remains, normalize — manufacturing an orthogonal basis from any basis, one subtraction at a time.

Reminder — Distance and midpoint:  d=(x2−x1)2+(y2−y1)2,M=(x1+x22, y1+y22)d=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}, \qquad M=\left(\frac{x_1+x_2}{2},\ \frac{y_1+y_2}{2}\right)
Reminder — The Pythagorean theorem:  a2+b2=c2a^2+b^2=c^2
Example
Worked: project, split, and measure — one example, all the way

Take u=(3,4)\mathbf u = (3, 4) and direction v=(1,1)\mathbf v = (1, 1).

Step 1 — the coefficient: c=u⋅vv⋅v=3+41+1=72c = \dfrac{\mathbf u\cdot\mathbf v}{\mathbf v\cdot\mathbf v} = \dfrac{3 + 4}{1 + 1} = \dfrac72.

Step 2 — the along part: 72(1,1)=(72,72)\tfrac72(1,1) = \left(\tfrac72, \tfrac72\right).

Step 3 — the across part: (3,4)−(72,72)=(−12,12)(3,4) - \left(\tfrac72,\tfrac72\right) = \left(-\tfrac12, \tfrac12\right); check orthogonality: (−12)(1)+12(1)=0\left(-\tfrac12\right)(1) + \tfrac12(1) = 0 ✓.

Step 4 — distance from (3,4)(3,4) to the line y=xy = x: the across length, 14+14=22\sqrt{\tfrac14 + \tfrac14} = \tfrac{\sqrt2}{2} — matching the point-to-line formula ∣3−4∣2\tfrac{|3-4|}{\sqrt2} ✓.

Step 5 — Pythagoras audit: (722)2+(22)2=492+12=25=∣u∣2\left(\tfrac{7\sqrt2}{2}\right)^2 + \left(\tfrac{\sqrt2}{2}\right)^2 = \tfrac{49}{2} + \tfrac12 = 25 = |\mathbf u|^2 ✓. Five steps, three self-checks — the decomposition verifies itself.

Example
Worked: an actual least-squares line, normal equations and all

Fit y=mx+cy = mx + c to the points (0,1),(1,3),(2,5)(0, 1), (1, 3), (2, 5)... which happen to be collinear — so fit (0,1),(1,2),(2,4)(0,1), (1,2), (2,4) instead.

Step 1 — the (unsolvable) system: c=1c = 1, m+c=2m + c = 2, 2m+c=42m + c = 4, i.e. A=(011121)A = \begin{pmatrix}0&1\\1&1\\2&1\end{pmatrix}, b=(1,2,4)\mathbf b = (1,2,4).

Step 2 — normal equations ATAx^=ATbA^{\mathsf T}A\hat{\mathbf x} = A^{\mathsf T}\mathbf b: compute ATA=(5333)A^{\mathsf T}A = \begin{pmatrix}5&3\\3&3\end{pmatrix} and ATb=(107)A^{\mathsf T}\mathbf b = \begin{pmatrix}10\\7\end{pmatrix}.

Step 3 — solve: 5m+3c=105m + 3c = 10 and 3m+3c=73m + 3c = 7; subtracting, 2m=32m = 3, m=32m = \tfrac32, then c=7−4.53=56c = \tfrac{7 - 4.5}{3} = \tfrac56.

Step 4 — the fitted line y=32x+56y = \tfrac32x + \tfrac56 predicts 56,73,236\tfrac56, \tfrac{7}{3}, \tfrac{23}{6}; residuals 16,−13,16\tfrac16, -\tfrac13, \tfrac16 sum to 00 — as they must, since orthogonality of the error to the all-ones column is literally one of the normal equations.