# Construct the best piece-wise linear continuous function fitting given curve

How to construct the optimal piece-wise linear continuous function fitting given curve and given number of knots (optimal knots positions also must be determined by this method)?

• You should give some more details. What do you mean by optimal? I also don't know what you mean by "fitting given curve and given number of knots". – j.c. Oct 29 '14 at 14:58
• I mean best approximation on whole function domain. "fitting given curve and given number of knots" - I mean constructing continuous piecewise linear function for given curve (actually sets of points). Number of knots of this continuous piecewise linear function is restricted by some fixed value N but their positions must be optimal (give the best approximation). – denny Oct 29 '14 at 15:15
• What is your metric for "best approximation"? Given continuous $f$, you want to find a continuous piecewise linear $g$ with $n$ knots that minimizes... what? The uniform distance between $f$ and $g$? The $L^2$ distance? Something else? – Nate Eldredge Oct 31 '14 at 17:13
• @NateEldredge, The $L^2$ distance between $f$ and $g$. – denny Nov 1 '14 at 10:20

If the number and position of the knots are fixed, then the problem is a linear least squares problem for determining the coefficients of linear B-Splines (cf e.g http://en.wikipedia.org/wiki/B-spline); if the knot-positions also have to be determined, then the problem becomes non-linear, but is also studied in approximation theory.

This article seems to fit your needs: "Fixed- and Free-knot Univariate Least Squares Data Approximation by Polynomial Splines" by Maurice Cox, Peter Harris and Paul Kenward (http://www.dtic.mil/dtic/tr/fulltext/u2/p013744.pdf)

A heuristic for finding a good knot-placement would be to start with an approximation for evenly spaced knots and then move them to the places, where the error is maximal.
The placing of the knots to the places where the error is maximal can then repeated as long as subsequent approximations with the new knot-placements yield better error measures.

• Thank you so much for explanation and article! This is exactly what I'm looking for. – denny Oct 29 '14 at 17:04

There is also a different method, that comes to mind:
let the function to be approximated be defined on the finite interval $[a,b]$, then, defining as basis-functions the "wedges" connecting points $$A:=(a,0); B:=(b,0); C:=(a+\lambda(b-a),1); \lambda\in[0,1]$$ in the order $(A,C,B)$, then one could

• generate sufficiently many of those basis functions (including the ones for $\lambda=0$ and for $\lambda=1$),

• set up a least squares problem for the values of the generated basis functions

• calculated the problem's $SVD$ and,

• take the $k$ principal components as an approximation for the sought linearization with free knot-placement (cf e.g. http://www.ime.unicamp.br/~marianar/MI602/material%20extra/svd-regression-analysis.pdf)

Caveat: this is a pure idea and would thus need some checking of e.g. complexity and/or numerical stability.

Due to their limited support (i.e. arguments, for which they are non-zero), B-Splines do not allow the technique of principal component analysis.

As @Manfred mentioned, if knots are fixed the problem is linear $\chi^2$ minimization problem. With a linear least squares you find unique coefficients $a^i$ for a b-spline representation $f(x) = \sum_i a^i B_{i,k}(x)$ of your data.

For the case where the knots are also variables, one of the best approaches is to use an evolutionary algorithm (Genetic Algorithm) in order to determine the optimum knot position for a b-spline basis. Note that once the knots are specified, the coefficients have a unique $\chi^2$ solution, so they do not need to be variables (without that meaning one cannot design an algorithm where everything is a variable). Caution must be taken on the suitable choice of fitness function: most of the times BIC or GCV are acceptable/good choices.

In general it is computationally much (much...) cheaper to construct a new b-spline basis rather than apply algorithms to modify knots (you also need to modify coefficients $a_i$), so I wouldn't advise the second. It is rather long to write full details on how such an algorithm can be implemented, but you can find ideas in the following papers:

1. Yoshimoto et al 2003 http://www.sciencedirect.com/science/article/pii/S001044850300006X

2. Trejo-Caballero et al 2013 http://link.springer.com/chapter/10.1007%2F978-3-642-45111-9_5

Good luck!