Placing $n$ linear functions so that it is best fit to another function in integral norm sense? 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?
 A: 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\}$$


*

*First term enforces model fit to function.

*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):

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

