5.3 Least Squares Problems · Linear Algebra Refresher

Overdetermined systems are usually inconsistent, and 'no solution' is a useless answer for real data. Least squares asks the next best question: which

x^

makes

A x^

as close to

b

as possible?

Definition · Least squares solution

For

A

of size

m \times n

(

m > n

) and

b \in R^{m}

, a least squares solution

x^

minimises the residual

r (x) = b - A x

in the sense that

∥ r (x^) ∥

is as small as possible.

Geometrically: $A x$ ranges over the column space $R (A)$ as $x$ varies, so we're asking for the point of $R (A)$ closest to $b$ — the orthogonal projection $p$ . The minimising residual is perpendicular to $R (A)$ , i.e. lies in $R (A)^{⊥} = N (A^{T})$ :

A^{T} (b - A x^) = 0 ⟺ A^{T} A x^= A^{T} b

Theorem 5.3.2

The normal equations are always consistent, and every solution is a least squares solution. If

rank (A) = n

then

A^{T} A

is nonsingular and

x^= (A^{T} A)^{- 1} A^{T} b

is the unique least squares solution.

If $rank (A) < n$ there are infinitely many $x^$ , but they all give the same projection $p = A x^$ .

Fitting data by least squares

1
Write the model with unknown coefficients
Line: $y = c_{0} + c_{1} x$ . Quadratic: $y = c_{0} + c_{1} x + c_{2} x^{2}$ . The unknowns are the $c_{i}$ , and the model must be linear in the coefficients — $y = c_{0} e^{c_{1} x}$ is not, directly.
2
Build $A$ by plugging each data point into the model
Row $i$ holds the values that multiply each coefficient at $x_{i}$ ; $b$ holds the observed $y_{i}$ .
$A = 11 ⋮ 1 x_{1} x_{2} ⋮ x_{m}, b = y_{1} y_{2} ⋮ y_{m}$
3
Form $A^{T} A$ and $A^{T} b$ , then solve
$A^{T} A$ is small ( $n \times n$ ) and symmetric; solve by elimination.
4
Check the residual is orthogonal to the columns of $A$
For a fit with a constant term, the first column of $A$ is all ones, so the residuals must sum to zero. That's a fast free check.

Curve fitting is always the same three moves: build

A

from the model, solve the normal equations, interpret the coefficients.

Worked example

Best-fit line through three points

0/4 steps

Find the least squares line

y = c_{0} + c_{1} x

through

(0, 1)

(3, 4)

(6, 5)

!Exam trap

x^

is not unique when

rank (A) < n

, but the projection

p = A x^

always is. If a question asks for the closest point in

R (A)

, the answer is unique regardless; if it asks for the coefficients, uniqueness needs full column rank.

Check your work

Least squares via the normal equations

Enter the augmented matrix (A | b) — one row per equation, last column is b. Everything stays exact because AᵀA and Aᵀb are rational.

Augmented (A | b)

A =

1	1
-2	3
2	-1

b =

Normal equations AᵀA x̂ = Aᵀb

9	-7
-7	11

x̂ =

83/50

71/50

p = Ax̂ =

77/25

47/50

19/10

‖r‖ ≈ 0.1414

If the last column of A is a column of x-powers, these are the coefficients of the best-fit polynomial, in the order the columns appear.

Check yourself

The least squares solution of an overdetermined system

A x = b

is found by solving:

T / F

A

m \times n

with

rank (A) = n

, the least squares solution is unique and equals

(A^{T} A)^{- 1} A^{T} b

T / F

The projection matrix

P = A (A^{T} A)^{- 1} A^{T}

satisfies

P^{2} = P

5.3Least Squares Problems

What you must be able to do

Fitting data by least squares

Best-fit line through three points

Least squares via the normal equations

Check yourself