# Segmented Least Squares

## Defining Subproblems
The problem of segmented least squares asks for defining a piecewise linear function that makes the best fit of our data points.
Let's assume that the function we are looking for consists of exactly $L$ pieces, its definition would look like.

$f(x) =
\left\{ \begin{array}{ll} \\ a_{L-1}*x+b_{L-1} \quad ;x \in \, \, ]k_{L-2},k_{L-1}] \\ \end{array} \right.$

So we splitted our axis into parts, and each part would be fitted with a single line. For instance the 2nd part of the plane would be fitted with a line with parameters $a_2,b_2$.

We start building our function from $-\infty$ to $+\infty$, we build our function part by part, so each time we select a contiguous subsequence of points that would decide the boundary for a single piece of our function and would be fitted with a single line using least squares.

Our subproblems will be $MIN(j)$ for all $j$ where $0 \leq j \leq n$

$MIN(j)$ denotes the minimum cost to build a piecewise function that covers the first $j$ points.

## Base Cases

$MIN(0)=0$
Since we are fitting 0 points, we don't need to draw any line, simple as that.
$MIN(1)=1$
The minimum cost to fit only the first point is 1, we can draw any line that passes through the first point.

## Recurrence
Each one of our problems would be fitting all points from the first point until let's say the $j_{th}$ point. What we only need to find is the part that the last piece of our function is covering, so we need to fix the leftmost point of this part (let it be the $i_{th}$ point) and our recurrence will look like.

$MIN(j)= \, min_{\, 1 \leq i \leq j} \, \, MIN(i-1) + e(i,j)+1$

## Pseudo-code

$MIN(N,Points[N])\{$
$\quad MIN[0]=0$
$\quad MIN[1]=1$
$\quad for \,\, j \leftarrow 2 \, \, to \, \, N\, \, do:$
$\quad \quad Min[j]=+\infty$
$\quad \quad for \,\, i \leftarrow 1 \, \, to \, \, j\, \, do:$
$\quad \quad \quad Min[j]=min(Min[j],Min[i-1]+e(i,j)+1)$
$\quad return \,\, MIN[N]$
$\}$

## Complexity
Notice that our calculations need 2 nested loops.
Total iterations is equal to $\frac {N*(N+1)}{2}$
On each iteration of these 2 nested loops we call the function $e(i,j)$ once.
Hence total complexity is $O(N^2 * C)$
where $C$ is the complexity of function $e$ when called for arbitrary 2 arguments.