Least Squares & Data Fitting

an overdetermined system

Suppose you measure how a spring stretches under several weights and you believe the relationship is a straight line: stretch = a + b*weight. Two clean measurements would fix the two unknowns a and b exactly. But you took ten measurements, each with a little noise, and no single line passes through all ten points. You now have ten equations in two unknowns — more demands than dials to turn. That is an overdetermined system: a linear system A x = b in which the matrix A has more rows (equations) than columns (unknowns).

Write it as A x = b where A is m-by-n with m > n. Each row is one equation; each column corresponds to one unknown in the vector x. Because there are more rows than columns, the right-hand side b almost never lies in the set of vectors that A x can produce (the column space of A), so there is usually NO exact solution — the system is inconsistent. Geometrically the columns of A span at most an n-dimensional slice of m-dimensional space, and a generic b pokes out of that slice. Instead of demanding A x = b exactly, we settle for making A x as close to b as we can, which leads straight to the least-squares problem.

Overdetermined systems are the normal state of affairs in data fitting, calibration, and statistics: you almost always have more data points than model parameters, precisely because extra data lets noise average out. The complementary case, m < n (an underdetermined system, more unknowns than equations), has infinitely many exact solutions and calls for a different idea — picking the minimum-norm one. Do not confuse 'no exact solution' with 'no answer': an overdetermined system has a perfectly good best-fit answer; it just is not an exact one.

Fit a line y = a + b x to three points (1, 2), (2, 2), (3, 4). Stacking the three equations gives A with rows (1, 1), (1, 2), (1, 3), and b = (2, 2, 4)^T, with x = (a, b)^T. There is no (a, b) hitting all three points (they are not collinear), so this 3-by-2 system is overdetermined and inconsistent — we will instead minimize ||A x - b||_2.

Three equations, two unknowns: more constraints than freedoms, so we settle for the best fit.

An overdetermined system is usually inconsistent, but not always — if b happens to lie exactly in the column space (noiseless, perfectly-fitting data), an exact solution exists and least squares returns it with zero residual.

Also called
overdetermined linear systemtall systemmore equations than unknowns超定方程組