SME
Linear Algebra
Orthogonality and least squares
Use this for “Find the least-squares line through (0, 1), (1, 2), (2, 2), (3, 4).”
Chart
Least-squares line: y = 0.9x + 0.9
Residual = actual − predicted: 3 positive (above the line), 1 negative
Sum of squared residuals = 0.7
The least-squares line makes the sum of the squared residuals as small as it can be
This is an example. Type your own values to start a new problem.
n
Number of points
example
x₁
Point 1, x
example
y₁
Point 1, y
example
x₂
Point 2, x
example
y₂
Point 2, y
example
x₃
Point 3, x
example
y₃
Point 3, y
example
x₄
Point 4, x
example
y₄
Point 4, y
example
Σx
Sum of the x values
worked out (not typed)
Σy
Sum of the y values
worked out (not typed)
Σx²
Sum of the squares of x
worked out (not typed)
Σxy
Sum of each x times its y
worked out (not typed)
m
Slope of the line
worked out (not typed)
b
Intercept of the line
worked out (not typed)
‖y − Ax̂‖²
Squared error
worked out (not typed)
Formulas
Σx
=
the
sum
of
the
n
x
values
6 = the sum of the 4 x values
Σy
=
the
sum
of
the
n
y
values
9 = the sum of the 4 y values
Σx²
=
the
sum
of
the
n
squares
x
2
14
=
the
sum
of
the
4
squares
x
2
Σxy
=
the
sum
of
the
n
products
xy
18 = the sum of the 4 products xy
m
=
(
n
×
Σxy
−
Σx
×
Σy)
÷
(
n
×
Σx²
−
(Σx)
2
)
0.9
=
(4
×
18
−
6
×
9)
÷
(4
×
14
−
(6)
2
)
b
=
Σy −
m
× Σx
n
0.9
=
9 − 0.9 × 6
4
‖y
−
Ax̂‖²
=
the
sum
of
the
n
squared
residuals,
each
y
−
mx
−
b
0.7 = the sum of the 4 squared residuals, each y − 0.9x − 0.9
Assumptions
•
A’s rows are (xᵢ, 1) and b holds the yᵢ. Ax = b has no exact solution unless the points lie on one line.
•
AᵀA x̂ = Aᵀy makes Ax̂ the projection of y onto Col A, so the residual y − Ax̂ is orthogonal to every column.
•
AᵀA = [[Σx², Σx], [Σx, n]] and Aᵀy = (Σxy, Σy). The x values are not all the same.
Step-by-step
WE KNOW
n = 4, x₁ = 0, y₁ = 1, x₂ = 1, y₂ = 2, x₃ = 2, y₃ = 2, x₄ = 3, y₄ = 4
FIND
sum of the x values (Σx), sum of the y values (Σy), sum of the squares of x (Σx²), sum of each x times its y (Σxy), slope of the line (m), intercept of the line (b), squared error (‖y − Ax̂‖²)
Step 1 · Find sum of the x values (Σx)
Use Σx = the sum of the n x values
Add the x values: the off-diagonal entries of AᵀA.
Σx
=
x₁
+
x₂
+
x₃
+
x₄
Σx = 0 + 1 + 2 + 3
Σx = 3 + 3
Σx = 6
Step 2 · Find sum of the y values (Σy)
Use Σy = the sum of the n y values
Add the y values: the second entry of Aᵀy.
Σy
=
y₁
+
y₂
+
y₃
+
y₄
Σy = 1 + 2 + 2 + 4
Σy = 9
Step 3 · Find sum of the squares of x (Σx²)
Use Σx² = the sum of the n squares x²
Add the squares of the x values: the top left of AᵀA.
Σx²
=
x₁
2
+
x₂
2
+
x₃
2
+
x₄
2
Σx²
=
0
2
+
1
2
+
2
2
+
3
2
Σx² = 1 + 4 + 9
Σx² = 14
Step 4 · Find sum of each x times its y (Σxy)
Use Σxy = the sum of the n products xy
Add each x times its y: the first entry of Aᵀy.
Σxy
=
x₁
×
y₁
+
x₂
×
y₂
+
x₃
×
y₃
+
x₄
×
y₄
Σxy = 0 × 1 + 1 × 2 + 2 × 2 + 3 × 4
Σxy = 2 + 4 + 12
Σxy = 18
Step 5 · Find slope of the line (m)
Use m = (n × Σxy − Σx × Σy) ÷ (n × Σx² − (Σx)²)
Solve
[[Σx²,
Σx],
[Σx,
n
]]
×
(
m
,
b
)
=
(Σxy,
Σy)
for
m
by
Cramer’s
rule
(Σx²
is
the
sum
of
the
squares,
(Σx)
2
the
square
of
the
sum).
m
=
(4
×
18
−
6
×
9)
÷
(4
×
14
−
(6)
2
)
m
=
72 − 54
4 × 14 − 36
m
=
18
56 − 36
m
=
18
20
m
=
0.9
Step 6 · Find intercept of the line (b)
Use b = (Σy − m × Σx) ÷ n
The second normal equation, mΣx + nb = Σy: the line passes through the mean point.
b
=
9 − 0.9 × 6
4
Check: [[14, 6], [6, 4]] × ⟨0.9, 0.9⟩ = ⟨18, 9⟩
b
=
0.9
Step 7 · Find squared error (‖y − Ax̂‖²)
Use ‖y − Ax̂‖² = the sum of the n squared residuals, each y − mx − b
Each residual is the point’s y less the line’s y there. Square them and add: no other line gives less.
‖y
−
Ax̂‖²
=
(
y₁
−
m
×
x₁
−
b
)
2
+
(
y₂
−
m
×
x₂
−
b
)
2
+
(
y₃
−
m
×
x₃
−
b
)
2
+
(
y₄
−
m
×
x₄
−
b
)
2
‖y
−
Ax̂‖²
=
(1 − 0.9 × 0 − 0.9)
2
+
(2 − 0.9 × 1 − 0.9)
2
+
(2 − 0.9 × 2 − 0.9)
2
+
(4 − 0.9 × 3 − 0.9)
2
‖y
−
Ax̂‖²
=
(1 − 0.9)
2
+
(1.1 − 0.9)
2
+
(2 − 1.8 − 0.9)
2
+
(4 − 2.7 − 0.9)
2
‖y
−
Ax̂‖²
=
0.1
2
+
0.2
2
+
(0.2 − 0.9)
2
+
(1.3 − 0.9)
2
‖y
−
Ax̂‖²
=
0.1
2
+
0.2
2
+
(−0.7)
2
+
0.4
2
‖y − Ax̂‖² = 0.01 + 0.04 + 0.49 + 0.16
‖y − Ax̂‖² = 0.7
Check
Put the numbers back in. Both sides should match.
6 = 0 + 1 + 2 + 3 ✓
9 = 1 + 2 + 2 + 4 ✓
14
=
0
2
+
1
2
+
2
2
+
3
2
✓
18 = 0 × 1 + 1 × 2 + 2 × 2 + 3 × 4 ✓
0.9
=
(4
×
18
−
6
×
9)
÷
(4
×
14
−
(6)
2
)
✓
0.9
=
9 − 0.9 × 6
4
✓
0.7
=
(1 − 0.9 × 0 − 0.9)
2
+
(2 − 0.9 × 1 − 0.9)
2
+
(2 − 0.9 × 2 − 0.9)
2
+
(4 − 0.9 × 3 − 0.9)
2
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.