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)²]

And b = (∑_i y_i- a∑_i x_i)/n

However, our problem is different from the above mentioned which these (above) formulas solve.

Formulating our problem

Given a sequence of data points, we need to identify a few points in the sequence at which a discrete change occurs.–> In our specific case, a change from one linear approximation to another.

So, we have a set of points P = {(x₁,y₁),(x₂,y₂),…,(x_n,y_n)} with x₁ < x₂,…, x_n.

p_i denotes the point (x_i,y_i)

We must first partition P into some number of segments.

Each segment is a subset of P that represents a contiguous set of x-coordinates of the form {p_i,p_i+1,…,p_j-1,p_j} for some indices i≤j.

For each segment S in our partition P, we compute the line minimizing the error with respect to the points in S using the formula we found above(where we wrote the value of a and b in the line y = ax + b).

The penalty of a partition is defined to be the sum of:

The number of segments into which we partition P, times a fixed, given multiplier C>0.

For each segment, the error value of the optimal line through that segment.

Our goal is to find the a partition of minimum penalty.

INPUT: n, p₁,…,p_N, C

Segmented-Least-Squares()

M[0] = 0

e[0][0] = 0

for j = 1 to n

for i = 1 to j

e[i][j] = least square error for the segment p_i,…,p_j

for j = 1 to n

M[j] = min _{1 ≤ i ≤ j} (e[i][j] + c + M[i-1])

return M[n]

Just like the Weighted Interval Scheduling Problem, we need to find an algorithm that gives us the solution itself.
Algorithm to give for the solution itself

FindSegments(j):

if j = 0:

output nothing

else:

Find an i that minimizes e_i,j + C + M[i-1]

Output the segment {p_i, …, p_j} and the result of

FindSegments(i-1)

End if

The running time of the algorithm is O(n²) since filling in the array M[j] takes us O(n) time for each j.

I give this section 7/10.