Segmented Least Squares Problem

computation

Definition

Segmented Least Squares Problem

Given a set of $n$ points $(x_1,y_1),(x_2,y_2),\dots ,(x_n,y_n)$, sorted by their $x$-coordinates, the objective is to find a partition of these points into segments that minimise the loss function:

$$\text{Cost}=\underset{\text{Error}}{\underbrace{E}}+\underset{\text{Simplicity}}{\underbrace{C\cdot L}}$$

where:

• $E$ is the sum of squared errors over all segments. For a single segment points from index $i$ to $j$, the error is ${\sum }_{k=i}^j(y_k-(a{x}_k+b){)}^2$, where $y=ax+b$ is the best fit line for that segment
• $C$ is a predefined constant penalty for each segment
• $L$ is the total number of segments in the partition

Approaches

Dynamic Programming

This problem can be efficiently solved using dynamic programming:

$$OPT(j)=\{\begin{array}{ll}0& \text{if }j=0\\ {\min }_{1\le i\le j}\{OPT(i-i)+e(i,j)+c\}& \text{else}\end{array}$$

Time complexity: $O(n^3)$