M5-T1 — Overdetermined and Underdetermined Systems

Learning objectives

After this lesson, you should be able to:

• Classify a system A x = b by the shape of A (tall, wide or square) and its rank.
• Explain why a tall system with noisy data is inconsistent and what that does to the idea of “solving” it.
• Describe the answer to ask for: least squares for tall systems, minimum norm for wide ones.
• Recognise both cases in sensor-fusion, calibration and redundancy problems.

Introduction and motivation

Collecting more measurements than you strictly need is how engineers beat noise. But the arithmetic does not forgive it: each extra equation demands that the unknowns satisfy another constraint, and with noisy data the constraints disagree. At the other extreme, a design with more actuators than degrees of freedom has many solutions, and the engineer must choose. The first situation is the subject of this whole module; the second was met in the previous module and returns in Module 6 and Module 8.

The intuition

Measure a distance three times and you get 9.8, 10.1 and 10.3 metres. As equations in the single unknown x: x = 9.8, x = 10.1, x = 10.3. No number satisfies all three. The system is overdetermined (more equations than unknowns) and inconsistent. Yet everybody knows what to do: take the average. That instinct, “the answer that is as close as possible to all the equations at once”, is least squares.

The opposite case is underdetermined: fewer equations than unknowns, so infinitely many solutions satisfy them exactly. There the question is not “what comes closest?” but “which of the exact solutions should I pick?”, and the standard answer is the shortest one.

Geometric and physical interpretation

Geometric view. A tall matrix A (m × n with m > n) maps an n-dimensional input space into an m-dimensional output space, so its column space is a thin slab inside R^m. A measurement vector b with noise is almost never exactly in that slab. A wide matrix (m < n) squashes a big input space onto a smaller output space, so many inputs share each output. Physical view. The slab is the set of measurement vectors that a perfectly noise-free sensor suite could produce. Noise pushes the real measurement off it, and the inconsistency of the equations is exactly the distance by which it missed.

The mathematics

m, n

the number of equations and the number of unknowns; A is m × n.

r

the rank of A.

x̂

the answer we choose (least-squares or minimum-norm).

The shapes

tall:    m > n   (overdetermined)       square:  m = n       wide:    m < n   (underdetermined)

What it means. Tall systems have too many constraints, wide ones too few. The rank decides the details: a tall matrix of full column rank has at most one solution when one exists; a wide matrix of full row rank always has solutions, infinitely many.

Consistency of a tall system

A x = b is solvable   ⇔   b in C(A)          dim C(A) = r ≤ n < m

What it means. The column space has dimension at most n, but b lives in R^m with m > n. A vector with noise in all m entries is almost never inside such a small subspace.

What to ask for

tall (no exact solution):     minimise ‖A x − b‖²                  (least squares)
wide (many exact solutions):   among all solutions, minimise ‖x‖²    (minimum norm)

What it means. Least squares picks the x whose prediction is as close as possible to the data. Minimum norm picks the smallest of the exact solutions. Both are projections, as the next lessons show.

Tall: no exact answer, so ask for the closest (least squares). Wide: many exact answers, so ask for the shortest (minimum norm).

Step-by-step derivation: why extra equations break exactness, and what the average is

Dimension count. The reachable right-hand sides form the column space, of dimension r ≤ min(m, n). If m > n, this is a proper subspace of R^m: it has measure zero, so a right-hand side drawn from noise lands in it with probability zero.

1. Take the single-unknown case. A = [1, 1, 1]ᵀ (m = 3, n = 1) and b = (b₁, b₂, b₃). The column space is the line through (1, 1, 1). It contains b only if all the b_i are equal.
2. Ask for the closest point. The squared mismatch is f(x) = (x − b₁)² + (x − b₂)² + (x − b₃)².
3. Set the derivative to zero: f′(x) = 2(x − b₁) + 2(x − b₂) + 2(x − b₃) = 0, so 3x = b₁ + b₂ + b₃.
4. Therefore x̂ = (b₁ + b₂ + b₃)/3, the average. Because f″(x) = 6 > 0, it is a minimum. Least squares generalises “take the average” to many unknowns and any matrix A.

The wide case. One equation a·x = c in two unknowns has a line of solutions. By the previous module, the shortest solution has no null-space component and equals the projection of the origin onto the line, x̂ = c a/(a·a). Wide systems always have solutions when A has full row rank, since then the column space is all of R^m.

A worked example: three distance readings and a line fit

Repeated readings. x = 9.8, x = 10.1, x = 10.3 have no exact solution. The least-squares answer is the mean, x̂ = (9.8 + 10.1 + 10.3)/3 = 10.0667 m.

A line through three points. Fit y = m x + c to (1, 1), (2, 2), (3, 2). The system has A = [[1, 1], [2, 1], [3, 1]] (columns: x and 1), b = (1, 2, 2) and unknowns (m, c): three equations and two unknowns.

1. Inconsistent? A line through the first two points has slope 1 and passes through the origin, giving 3 at x = 3, not 2. No line fits all three: the system is inconsistent.
2. The compromise (derived with the normal equations in the next lessons) is m = 0.5, c = 0.6667, the line y = 0.5x + 0.667. Its predictions are (1.167, 1.667, 2.167).
3. The leftovers (residuals) are b − A x̂ = (−0.167, 0.333, −0.167). They are small and sum to zero.

A wide system. x + y + z = 3 and x − y = 1 (from the last module) is underdetermined; of its infinitely many solutions, the shortest is (1.5, 0.5, 1).

Robotics application

LiDAR calibration and plane fitting. Thousands of points constrain the three parameters of a plane: a massively overdetermined problem, with noise ensuring no plane passes through every point. The answer is the plane minimising the squared distances; Modules 5 and 6 build exactly this.

Sensor fusion. Several sensors measuring the same state give an overdetermined system that is combined by (weighted) least squares, the principle behind the update step of a Kalman filter (Module 9).

Odometry and calibration. Estimating wheel radius and track width from many short runs, or a scale and offset for a range sensor, is a tall linear fit. See the Systems Engineering guide on calibrating wheel radius, separation and encoders in this site's Systems track.

Redundant robots. A robot with more actuators than task dimensions is a wide system; its Jacobian equation has infinitely many solutions, and the minimum-norm choice is the pseudoinverse solution of Module 8. See also nonlinear least squares, where every iteration solves a tall linear system.

Engineering implications and limitations

Practical rules

• Count rows and columns before choosing a method. Square systems use LU; tall systems use QR (or the SVD); wide systems use minimum-norm solvers. A generic solve will fail or give nonsense on non-square input.
• Inconsistency is expected, not an error. Do not abort because A x = b has no exact solution. Report the residual instead, and use it as a quality measure.
• More data helps only if it is independent. Rows that repeat the same direction raise the row count but not the rank; the problem stays poorly determined.
• Check the rank. A tall matrix that is rank-deficient has a whole family of least-squares answers; decide on a tie-breaking rule (minimum norm) or add data.
• Compare the residual with the noise. A residual much larger than the sensor noise signals a model error or an outlier, not just noise.

Limits

This lesson assumes the model is linear in the unknowns. Many robotics problems are nonlinear; they are solved by repeatedly linearising and solving a tall linear system (Gauss-Newton), so the linear case studied here is the engine inside the nonlinear one.

Common misconceptions

Engineering takeaways

1. A tall system (m > n) is overdetermined: with noisy data no x satisfies every equation, because b is not in the small column space.
2. A wide system (m < n) is underdetermined: if solvable, it has infinitely many solutions.
3. For a tall system ask for the least-squares answer (minimise ‖Ax − b‖²); for a wide one the minimum-norm answer.
4. The average of repeated measurements is the least-squares solution of the simplest tall system.
5. Residuals measure how far the data are from being consistent, and are a quality indicator.

References and further reading

Primary papers and authoritative documentation.

• Boyd and Vandenberghe, Introduction to Applied Linear Algebra (VMLS): the chapters on least squares and on underdetermined systems; the site did not load when we last checked
• MIT 18.06SC Linear Algebra (OCW): lectures on projections and least squares
• UCSD ECE276A: Sensing and Estimation in Robotics: estimation viewed as fitting a model to many measurements
• Michigan ROB 101: Computational Linear Algebra: overdetermined systems in a computational course

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

You know that the right question for tall systems is “which x makes the squared error smallest”. The next lesson turns that question into a precise formula.

Related content

Nothing below is required to finish this lesson.

• Before
  M4-T6: Quadratic Forms

  Write x-transpose A x for a symmetric matrix, picture its level curves as ellipses, and decide whether it is positive.