This is an old revision of the document!
6.3. Segmented Least Squares: Multi-way Choices
With this problem, at each step we have a polynomial number of possibilities to consider the structure of the optimal solution.
The Problem
Suppose our data consists of a set P of n points in the plane,:
(x1y1),(x2y2),…,(xnyn), where x1 < x2,…,< xn
Given a line L with equation y = ax + b, we say that an “error” of L with respect to P is the sum of all of its squared distances to the points in P:
Error(L,P) = ∑ from i =1 to n (yi - axi- b) 2
Thus naturally, we are bound to finding the line with minimum error.
The solution turns out to be a line y = ax + b, where:
a = [(n∑i xiyi) - (∑ixi)(∑i yi)]/[(n∑i xi2) - (∑i xi)2]
And b = (∑i yi- a∑i xi)/n