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?
 A: 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.  
A: 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
A: 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: 


*

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

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

*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. 

*Otherwise, ... and so on
A: 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.
