Least squares — normal equations, QR approach: Visual walkthrough

Step 1 — The vectors we are handed

WHAT. We have a bunch of "measurements" stacked into one tall list of numbers $b$ , and a machine $A$ that turns unknown dials $x$ into a prediction $A x$ .

A vector is just an arrow: a list of numbers that also points somewhere. $b = (b_{1}, b_{2}, \dots, b_{m})$ is a point in $m$ -dimensional space.
$A$ is a matrix: a rectangular grid of numbers with $m$ rows and $n$ columns, written $A \in R^{m \times n}$ . "Tall" means $m > n$ — more equations (rows) than unknowns (columns).
$x = (x_{1}, \dots, x_{n})$ are the unknowns — the dials we get to twist.

WHY. We want $A x = b$ exactly. But with more equations than dials, the target $b$ usually cannot be hit. So we must define "as close as possible" before we can chase it.

PICTURE. In the figure, $b$ (plum) floats in space. As we twist the dials $x$ , the tip of $A x$ (orange) can only reach a flat sheet — never quite touching $b$ .

Figure — Least squares — normal equations, QR approach

Step 2 — Where can $A x$ actually go? (the column space)

WHAT. Split $A$ into its columns $a_{1}, \dots, a_{n}$ (each column is itself an arrow in $m$ -space). Then $A x = x_{1} col 1 a_{1} + x_{2} col 2 a_{2} + \dots + x_{n} col n a_{n} .$ Every term here scales a column-arrow by a dial number and adds them up. Twisting the dials sweeps out all possible mixtures of the columns.

That set of all mixtures is the column space $Col (A)$ — see Column Space and Rank. It is a flat sheet (a subspace) through the origin.

WHY. Whatever we do, $A x$ lives inside this sheet. So "closest reachable point to $b$ " means "closest point of the sheet to $b$ ." This turns an algebra problem into a geometry problem.

PICTURE. The two columns $a_{1}$ (teal) and $a_{2}$ (orange) span a tilted plane. Every reachable prediction $A x$ is a dot somewhere on that plane; $b$ hovers off it.

Step 3 — "Closest" means shortest arrow — measured how?

WHAT. The gap between target and prediction is the residual: $r = target b - prediction A x .$ Its length is the Euclidean norm $∥ r ∥ = r_{1}^{2} + r_{2}^{2} + \dots + r_{m}^{2} .$ Under the square root each miss $r_{i}$ is squared (so signs can't cancel) and summed — this is just Pythagoras in $m$ dimensions.

WHY square the length instead of using the raw length? We will minimise $∥ r ∥^{2}$ (drop the square root). WHY is that legal and nicer? Because $∥ r ∥^{2} = r_{1}^{2} + \dots + r_{m}^{2}$ is a plain polynomial in the entries — a smooth, gently curved bowl whose minimum we can find by clean linear algebra, with no square root to carry around. And since squaring is an increasing function on lengths ( $\geq 0$ ), the same $x$ that makes the length smallest also makes its square smallest — we lose nothing by minimising the square.

PICTURE. Watch the residual arrow (plum) shrink and swing as the prediction dot slides across the plane. There is one position where it is shortest.

Step 4 — The shortest arrow is the perpendicular one

WHAT. Claim: the residual is shortest exactly when it stands perpendicular to the plane $Col (A)$ . This is the key geometric fact behind Orthogonal Projection.

WHY. Suppose the residual leaned even a little bit along the plane. Then that leaning component points in a direction we can actually reach (it is inside $Col (A)$ ). Slide the prediction dot a hair in that direction and the miss gets shorter — so we were not at the minimum. The only arrow you cannot shorten by sliding within the plane is the one with zero component in the plane — i.e. straight up, perpendicular.

PICTURE. Two candidate residuals: a slanted one (still shortenable, orange dashes) and the perpendicular winner (plum). The right-angle mark shows the winner meeting the plane at $9 0^{\circ}$ .

Step 5 — Turning "perpendicular" into equations

WHAT. "Perpendicular to the plane" means perpendicular to every spanning column $a_{j}$ . Two arrows are perpendicular when their dot product is zero — the dot product $a_{j}^{⊤} r = a_{1 j} r_{1} + \dots + a_{mj} r_{m}$ measures how much they line up; zero means they don't line up at all.

$column j as a row a_{j}^{⊤} r, the residual (b - A \hat{x}) = 0 for every j = 1, \dots, n .$

WHY. A plane is fully pinned down by its spanning arrows. If $r$ is perpendicular to each column, it is perpendicular to every mixture of them — the whole plane. So $n$ little equations capture the geometry exactly.

PICTURE. The residual makes a right angle with $a_{1}$ and with $a_{2}$ simultaneously — the two right-angle marks.

Step 6 — Stack the equations: the Normal Equations appear

WHAT. Writing all $n$ dot-product equations in one line means stacking the columns as the rows of $A^{⊤}$ (the transpose, $A$ flipped so its columns become rows): $A^{⊤} (b - A \hat{x}) = 0 .$ Distribute the $A^{⊤}$ over the subtraction: $target, seen by columns A^{⊤} b - prediction, seen by columns A^{⊤} A \hat{x} = 0 .$

WHY may we distribute? Because matrix multiplication distributes over addition, $A^{⊤} (u - v) = A^{⊤} u - A^{⊤} v$ — multiplying a sum is the same as multiplying each piece and then combining. Here that lets us split the single perpendicularity statement into a "target part" $A^{⊤} b$ and a "prediction part" $A^{⊤} A \hat{x}$ that we can rearrange separately. Move one term across: $A^{⊤} A \hat{x} = A^{⊤} b$

Term by term: $A^{⊤} A$ is a small $n \times n$ square matrix (its entry $(i, j)$ is the dot product $a_{i}^{⊤} a_{j}$ of two columns); $A^{⊤} b$ is a short $n$ -vector (entry $j$ is $a_{j}^{⊤} b$ ). We turned a tall impossible system into a short square solvable one.

WHY. This is now $n$ equations in $n$ unknowns — square, and (when the columns are independent) uniquely solvable.

PICTURE. The tall $A$ collapses into the compact square $A^{⊤} A$ ; the diagram shows the shrink.

Step 7 — The QR shortcut (same answer, safer arithmetic)

WHAT. Instead of forming $A^{⊤} A$ , factor $A = QR$ (via QR Factorization / Gram-Schmidt Process), where $Q$ has orthonormal columns ( $Q^{⊤} Q = I$ , the identity) and $R$ is upper triangular (zeros below the diagonal). Substituting into the normal equations: $(QR)^{⊤} (QR) \hat{x} = (QR)^{⊤} b \Rightarrow R^{⊤} = I Q^{⊤} Q R \hat{x} = R^{⊤} Q^{⊤} b \Rightarrow R^{⊤} R \hat{x} = R^{⊤} Q^{⊤} b .$

Why we may cancel $R^{⊤}$ . In the thin (reduced) QR of a full-column-rank $A$ , the matrix $R$ is $n \times n$ square, and its diagonal entries are the nonzero lengths produced during Gram–Schmidt — so $det R \neq = 0$ and $R$ is invertible. A product of invertible matrices is invertible, so $R^{⊤}$ is invertible too. Multiplying both sides on the left by $(R^{⊤})^{- 1}$ legally removes it: $R \hat{x} = Q^{⊤} b$

Term by term: $Q^{⊤} b$ reads off $b$ 's coordinates in the perfect right-angle frame $Q$ ; $R$ being triangular means the last unknown pops out alone, then the next by back-substitution.

WHY bother? First, what does "safer" mean? Picture the machine $A$ stretching space: it stretches some directions a lot and others a little. A singular value of $A$ is one such stretch factor — the amount $A$ lengthens a particular unit input direction (the biggest one, $σ_{m a x}$ , is the most $A$ can ever stretch a unit arrow; the smallest, $σ_{m i n}$ , the least). The condition number $κ (A) = σ_{m a x} / σ_{m i n}$ (see Condition Number) is the ratio of biggest to smallest stretch — a single number measuring how much the matrix amplifies rounding error. Big $κ$ = touchy arithmetic. The trouble with the normal equations is that forming $A^{⊤} A$ squares every singular value (its stretch factors are the $σ_{i}^{2}$ ), so $κ (A^{⊤} A) = κ (A)^{2}$ : a mildly touchy $A$ becomes badly touchy. QR never builds $A^{⊤} A$ , so it keeps the sensitivity at $κ (A)$ — while giving the identical $\hat{x}$ .

PICTURE. The messy tilted columns of $A$ get straightened into the clean perpendicular axes of $Q$ ; projecting onto square axes is effortless.

Step 8 — Every case, cleanly split

WHAT. To leave nothing out, cross two independent yes/no questions:

Independent columns? (full column rank vs rank-deficient) — decides if $A^{⊤} A$ is invertible.
Is $b$ reachable? ( $b \in Col (A)$ vs not) — decides whether the smallest residual is exactly $0$ or merely nonzero.

That gives four boxes, all covered:

	$b$ reachable ( $r = 0$ )	$b$ unreachable ( $r \neq = 0$ )
Independent columns	Unique $\hat{x}$ solving $A \hat{x} = b$ exactly; least squares reproduces the exact solution.	Unique $\hat{x} = (A^{⊤} A)^{- 1} A^{⊤} b$ ; the healthy projection case.
Dependent columns	Residual is $0$ , but infinitely many $\hat{x}$ give it — a whole flat family of exact solutions.	Infinitely many minimisers all sharing the same nonzero best shadow $A \hat{x}$ .

WHY. These four boxes are mutually exclusive and together exhaust every possibility (columns independent or not $\times$ target reachable or not), so a reader can never hit a scenario we skipped.

The zero degenerate limit ( $A = 0$ ). This sits in the "dependent columns" row: the prediction is stuck at the origin, the residual is just $b$ , and any $\hat{x}$ is a minimiser. Nothing to fit.

Whenever a row says "infinitely many," the fair, canonical pick is the shortest $\hat{x}$ , delivered by the Pseudoinverse (Moore-Penrose).

PICTURE. Left: fat healthy plane, unique drop (independent columns). Right: collapsed thin plane, a whole line of dial-settings landing on the same shadow (dependent columns).

The one-picture summary

Everything above is one gesture: drop $b$ perpendicularly onto the plane of reachable predictions; the foot of that drop is $A \hat{x}$ ; the drop-arrow is the residual.

The final schematic below distils the retelling into one flow: target → drop → foot → miss, with the two formulas hanging off it.

Recall Feynman retelling — the whole walkthrough in plain words

You are trying to hit a floating dot $b$ , but your gun can only fire onto a tilted table top (the column space) — the dot hangs above it, out of reach. So you aim for the spot on the table nearest the dot. Which spot? Drop a plumb line straight down from the dot to the table; where it lands is your best shot $A \hat{x}$ , and the plumb line itself is the miss (the residual). "Straight down" is the whole secret: a plumb line stands at right angles to the table, so its miss is at right angles to every direction you could have aimed. Writing "at right angles to every column" in symbols is $A^{⊤} (b - A \hat{x}) = 0$ , which tidies into $A^{⊤} A \hat{x} = A^{⊤} b$ . QR is the same drop done with a cleaner set of measuring sticks (perfect right-angle axes $Q$ ), so your calculator doesn't fumble the arithmetic: $R \hat{x} = Q^{⊤} b$ . And if the table is secretly just a line (dependent columns), lots of aim-settings land on the same spot — you pick the gentlest one.

Active Recall

Why is the shortest residual the perpendicular one?

Any component of the residual lying inside the plane could be removed by sliding the prediction, shortening the miss — so at the minimum the residual has zero in-plane component, i.e. it is perpendicular.

Turn "residual ⊥ every column" into one matrix equation.

A^{⊤} (b - A \hat{x}) = 0

, i.e.

A^{⊤} A \hat{x} = A^{⊤} b

What does

ar g min_{x} g (x)

mean?

The input

x

that makes

g

smallest (not the smallest value of

g

itself).

Why may we cancel

R^{⊤}

in the QR derivation?

In the thin QR of a full-rank

A

R

is square with nonzero diagonal, hence invertible; so

R^{⊤}

is invertible and can be multiplied away.

What is a singular value, and why does it matter here?

A stretch factor of

A

;

κ (A) = σ_{m a x} / σ_{m i n}

, and forming

A^{⊤} A

squares each

σ_{i}

, so

κ (A^{⊤} A) = κ (A)^{2}

What happens when the columns of

A

are dependent?

A^{⊤} A

is singular; infinitely many

\hat{x}

minimise the residual, and the minimum-norm one comes from the pseudoinverse.