3

Suppose your are given a finite set $P$ of $n$ points $(x_i,y_i)$ with $x_0< x_1 <\ldots < x_n$. Denote by $f_P$ the function given by piecewise linear joining of these points.

Now suppose you are given $k<n$. I feel the following problem must have a well known algorithmic solution, but I am unable to use the right keywords to find it.

Given $k$, find a subset $S \subseteq P$ containing the endpoints with $|S|=k$, such that $f_S$ is the best fit to $f_P$ in eithter L1 or L2 sense i.e. such that

$$\int_{x_0}^{x_n} |f_P(x)-f_S(x)| dx $$ or $$ \int_{x_0}^{x_n} (f_P(x)-f_S(x))^2 dx $$

is minimal.

How are these optimization problems called? Are there fast algorithms. Does it help if you knew that $f_P$ had special properties. E.g. monotone or convex?

Let me add that in the application I have in mind $k$ is rather small compared to $n$, maybe something like 10 to 10000.

wood
  • 840

1 Answers1

2

They are called Piecewise Affine Approximations. In general the problem is non-convex, one problem formulation is something like

\begin{equation} \begin{array}{rcl} J&=&\sum_{i=1}^n \int_{S_i} |f(x)-L_i(x)|^2 dx\label{20130516:eq1}\\ \text{such that } \bigcup_{i=1}^n S_i&=&I \text{ and } \bigcap_{any\ two} S_i=\emptyset.\nonumber\\ L_i(x)&=&\frac{df}{dx}(x_i^*)(x-x_i^*)+f(x_i^*). \end{array} \end{equation}

I do not know of fast analytic algorithms, I typically discretize and use constrained least squares. One resource to get you started is Optimal Piecewise Affine Approximations of Nonlinear Functions Obtained from Measurements by Szucs, Kvasnica, and Fiskar.

riboch
  • 402