# Minimize the number of points in a piecewise linear approximation

I have $m$ data points $(x_i,y_i)$ in a given interval. I would like to find a piecewise linear function $f(x)$ that approximate these $m$ points with a minimum number of points $n$ so that my approximation error is below a tolerance $\epsilon$.

My $m$ points:

The function $f$ is a piecewise linear function defined with $n$ points $(x_a^{i},y_a^{i})$. For $n=4$, it would look like:

Approximation error:

$$\frac{1}{m} \sum_{1\le i\le m}(y_i-f(x_i))^2 \leq\epsilon$$

To solve that problem I need to find, for a given $n$, a way to obtain the optimal set of points $(x_a^{i},y_a^{i})$. I can try to minimize my approximation error with gradient descent, but the function is non-convex, so it might not converge to the global optimum.

If I solve the previous step, I can simply simply run the algorithm from $n=1,2,3,...$ and stop when my approximation error drops below $\epsilon$

I sounds like a rather common problem that perhaps already has a solution. Do you know of one, or can you propose an approach to that problem?

• The Douglas-Peucker algorithm can be used to find an approximation such that $\max_i(y_i-f(x_i))\le\epsilon$ instead.
– user856
Aug 29, 2016 at 18:32
• To deal with $\sum_i (y_i-f(x_i))^2$ instead, you could consider a complete graph on vertices $\{1,2,\ldots,m\}$; assign each edge $(i,j)$ a cost $w_{ij}=\sum_{i<k<j} (y_k-f_{ij}(x_k))^2$, where $f_{ij}$ is the linear approximation between $(x_i,y_i)$ and $(x_j,k_j)$; then find the shortest path from $1$ to $m$ using only $n-1$ edges.
– user856
Aug 29, 2016 at 18:37
• @Rahul, Thanks! I think the Douglas-Peucker algorithm might actually be a suitable solution to my problem. I also like very much your graph-based approach for the squared error. Note that in both approaches one drawback is that the $(x_a^{i},y_a^{i})$ are picked among the $(x_{i},y_{i})$, which might not be optimal. I am also thinking that I could use the Douglas-Peucker solution to initialize a gradient descent algorithm much closer to the global optimum... Aug 29, 2016 at 21:06
• Seems to me that Douglas-Peucker, by fitting to certain input points exactly, fails to find better solutions that miss all points (as in OP's illustration). Feb 20, 2020 at 16:39
• this can be phrased as a mixed integer optimization problem, which can be solved for limited $n$ Jun 20, 2020 at 22:05

I would approach the problem in the following way.

Take the interval containing the first three points. Compute the correlation coefficient $$\rho$$.
- if $$\rho$$ is not good enough, take just the first two points , mark them as to be in the 1st interval, and move to examine next three. - elif $$\rho$$ is quite good, add a fourth point and recompute the coefficient; continue till $$\rho$$ remains good;
Repeat till partitioning all the points into contiguous intervals with good correlation.

You just have to consider what to do with the points at the border of the intervals :
- you can keep the intervals disjointed;
- or you can retake the last point into the computation of the correlation for the next, so overlapping the intervals.

Here is the way that looks obvious to me; maybe someone wiser will point out how it's inefficient, or fails on perverse input.

Consider the $$(a,b)$$ plane in which each point represents a function $$y=ax+b$$. Each of your inputs, with its tolerances, defines a band in that plane. An intersection of such bands is a convex polygon.

So, starting at the left, pile on the constraints until this polygon vanishes, and then back up by one. Your first line is represented by a point anywhere in this polygon; you may as well use its centroid, or the average of its corners.

Then do it again, starting with the last point "covered" by the first line. Your $$(x_a^2,y_a^2)$$ is, of course, the intersection of the first two solution lines.

It could be interesting to see if starting from the right gives a different result.

(My aesthetic preference would be to use all maximal compatible subsequences, but it's not my question.)

Edit: This is the main idea of the following paper and is discussed here

• Can this concept be extended to piecewise polynomials of degree n with k continuous derivatives? Jan 5, 2023 at 4:50

It isn't simple because the piecewise linear function depends on the break points in a non differentiable way (it is however continuous). And thing get ugly if you varies the number of breaks.

It is much simpler to compute the best approximation for fixed breaks. Thus, a simple heuristic would be following:

1. Start with the linear best approximation $f_0$ on say $[a,b]$ (that is only two breaks). If the error is sufficiently small, stop.

2. Otherwise, add a break $c$ (for example in the middle) and compute the best approximation $f_1$. If the error is sufficiently small, stop.

3. Otherwise, compare the error of $f_1$ on $[a,c]$ and $[c,b]$. Choose the subinterval with the larger error, say $[a,c]$, and add a new break in $[a,c]$. Compute the best approximation $f_2$. If the error is sufficiently small, stop.

4. Otherwise, ... and so on

I don't know if it converges to a minimum, but once I made a function to "convert" GPS points into a road.

To do so I took a rectangular region whose side is the double of the tolerance accumulating points as long as the rectangle could contain all of them. At this point I started with another rectangle containing at least the last point of the former rectangle.