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?

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
