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.

Suppose our data consists of a set P of n points in the plane,:

(x₁y₁),(x₂y₂),…,(x_ny_n), where x₁ < x₂,…,< x_n

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} (y_i - ax_i- b) ²

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 x_iy_i) - (∑_ix_i)(∑_i y_i)]/[(n∑_i x_i²) - (∑_i x_i)²]