How do you solve an overdetermined system Ax = b when no exact solution exists?

## Why an exact solution is usually absent Call the system `Ax = b` with `A` an m-by-n matrix, `m` much larger than `n`. Each of the m rows is one equation and there are only n knobs to turn. The product `Ax` is a combination of the n columns of `A`, so as `x` ranges over everything, `Ax` sweeps out only an n-dimensional set inside m-dimensional space - the **column space** of `A`. A measured `b` carrying any noise at all will sit slightly off that set, and then no `x` solves the system exactly. This is the normal situation, not a pathology. ## A concrete case: sensor calibration Suppose you are calibrating a pressure sensor. You take 100 readings, and for each one you record the raw reading `y_i`, the reference pressure `p_i` from a trusted instrument, and the ambient temperature `t_i`. You believe the raw reading is approximately `a * p_i + c * t_i + d`. That is 100 equations in 3 unknowns `(a, c, d)`. `A` is the 100-by-3 matrix whose i-th row is `(p_i, t_i, 1)`, and `b` is the vector of 100 raw readings. Every reading carries measurement noise, so no triple `(a, c, d)` reproduces all 100 readings exactly, and elimination on the augmented system would produce a contradictory row. Demanding exactness is the wrong request. ## The reformulation Instead, choose `x` to minimise the sum of squared discrepancies: ``` minimise ||b - Ax||^2 = sum over i of (b_i - (Ax)_i)^2 ``` Squaring makes the objective smooth and, crucially, makes the minimiser characterised by a linear condition - which is why least squares is solvable in closed form while, say, minimising the sum of absolute discrepancies is not. ## The geometry, which is the answer worth giving `Ax` is confined to the column space. Among all points in that space, the one closest to `b` is the **orthogonal projection** of `b` onto it. Drop a perpendicular from `b` to the plane of reachable points; where it lands is `Ax*`, and the residual `r = b - Ax*` is the perpendicular itself. "Perpendicular to the plane" means perpendicular to every column of `A`, and stacking those n dot products gives ``` A^T (b - Ax) = 0 which rearranges to A^T A x = A^T b ``` These are the equations you solve. In the calibration example, `A^T A` is 3-by-3 and `A^T b` has 3 entries: a 100-equation problem with no solution has become a 3-equation problem with one. ## Existence and uniqueness of the least-squares answer The squared-residual objective is bounded below by zero and grows without bound in the reachable directions, so a minimiser always exists - `A^T A x = A^T b` is always consistent, no matter how badly `Ax = b` failed. Uniqueness is a separate question and depends on the columns of `A`. If the columns are linearly independent (full column rank), `A^T A` is invertible and the minimiser is unique. If two columns are identical or one is a combination of the others - say you recorded temperature in both Celsius and Fahrenheit - then infinitely many different `x` achieve exactly the same minimum residual. The projection point `Ax*` is still unique; only its coordinates are not. ## Reading the residual The residual carries diagnostic information. `A^T r = 0` should hold to numerical precision for a correctly computed answer, which makes it a cheap sanity check. Its length `||r||` measures how much of `b` the columns could not explain. If the residual is far larger than your known measurement noise, the model itself - the choice of columns - is wrong, not the arithmetic; if it is far smaller, you may be reproducing noise with too many columns. ## Practical cautions Forming `A^T A` explicitly is convenient but numerically delicate: the cross-product matrix is more sensitive to rounding than `A` itself, and factorization-based routes that work on `A` directly are preferred when the columns are close to dependent. Also keep the columns on comparable scales - a column in pascals next to a column in kelvin next to a column of ones makes the 3-by-3 system harder to solve accurately than it needs to be. ## What an interviewer listens for The phrase "minimise the residual" is only half an answer. The other half is the geometry: `Ax` lives in the column space, the best `Ax` is the projection of `b`, and the residual is orthogonal to every column - which is *why* `A^T A x = A^T b` is the right system rather than an algebraic trick pulled out of the air.