Placing $n$ linear functions so that it is best fit to another function in integral norm sense?

Question

Say we want to build a function which is piecewise linear $$f(x) = \sum_{\forall k} (H(x-x_k)-H(x-x_{k+1}))l_k(x)\\l_k(x) = c_{k1}x+c_{k2}$$

And also so that it fits best possibly some function $x\to g(x)$: $$l_k,x_k=\min_{l_k,x_k}\left\{\int_a^b |f(x)-g(x)|dx\right\}$$

Please note that the line end point coordinates $x_k$ we can decide for ourselves.

---

I've made some numerical approaches which seem promising on this, but how can one approach it algebraically/analytically?

Answer 1

Using a CMA-ES setup with ($\lambda = 20,\mu = 3$) over a test function

$$ f(x) = \text{If}\left[x<2.2 (x-2)^2+14,\text{If}\left[x<6.5 \sin \left(\frac{3}{2} (x+4)\right)+2,-\frac{(x-6)^2}{0.3}-4\right]\right] $$

with a chromosome composed of $2n+1$ parameters asigned as follows

$$ \phi_x = \{\Delta x_1,\cdots,\Delta x_n\}\\ \phi_y = \{y_1,\cdots,y_{n+1}\} $$

Here $\Delta x_k = x_k-x_{x-1}$ for $k = 1,\cdots, n$ with $x_0$ as the lower number in the smoothing interval $[x_{min},x_{max}]$ so $x_0 = x_{min}$. Then $x_k = x_0+\sum_{j=1}^k\Delta x_j$ uses the pairs $\{x_k,y_k\}$ to construct a reference step-wise linear basis to proceed the integration process and the fitness is calculated as

$$ \sum_{k=1}^{n}\int_{x_k}^{x_{k+1}}|f(x)-g_k(\phi_x,\phi_y,x)|dx $$

with

$$ g_k(\phi_x,\phi_y,x)=y_k + \frac{(y_{k+1}-y_k)}{(x_{k+1}-x_k)}(x-x_k) $$

Follows a series of outcomes for established $n$ values

$(n = 4)$

$(n=5)$

$(n=6)$

$(n=7)$

$(n=8)$

$(n=9)$

$(n=10)$

Follows also a typical medium fitness progress curve

Answer 2

One numerical approach we can take is to discretize the function into $N$ samples, construct a polynomial basis for each sample, and create a reweighted linear least squares problem:

$${\bf c_i} = \min_{\bf c} \left\{\|{\bf W_{1,i}}({\bf (\Phi\otimes 1_N) c}-{\bf f})\|_F^2 + \|{\bf W_{2,i}(D\otimes I_N)c}\|_F^2+\|{\bf (R\otimes I_N)c}\|_F^2\right\}$$

1. First term enforces model fit to function.
2. Second term enforces derivative ($\bf D$) of coefficients over time to be low. Remember we need an interval of points to have same coefficients within whole interval in order to be represented by model.

$${\bf W_{1,i}} = \max{[|({\bf \Phi \otimes 1_N)c_{i-1} - f}|^{k_1},1]}$$

$${\bf W_{2,i}} = \frac{1}{\max{[|({\bf D \otimes I_N)c_{i-1}}|^{k_2},1]}}$$

Lastly, we need $\bf R$ to punish any coefficients except for constant and linear terms.

Of course lots of details are left out, we need to normalize matrices and add parameters and tune a little bit of this and a little bit of that.

Example of a solution after 6 iterations:

The re-weighting in the iteration here is crucial to be able to achieve such flat lines as just one linear least squares punishes 2-norm and very rarely achieves sparse solutions. We can see how the interval of constant coefficients correspond to a unique line (red is the output of algorithm, trying to fit the blue function):