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)?
4
-
4$\begingroup$ 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". $\endgroup$– j.c.Commented Oct 29, 2014 at 14:58
-
$\begingroup$ 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). $\endgroup$– dennyCommented Oct 29, 2014 at 15:15
-
$\begingroup$ 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? $\endgroup$– Nate EldredgeCommented Oct 31, 2014 at 17:13
-
$\begingroup$ @NateEldredge, The $L^2$ distance between $f$ and $g$. $\endgroup$– dennyCommented Nov 1, 2014 at 10:20
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
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.
answered Oct 29, 2014 at 15:34
-
$\begingroup$ Thank you so much for explanation and article! This is exactly what I'm looking for. $\endgroup$– dennyCommented Oct 29, 2014 at 17:04
$\begingroup$
$\endgroup$
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.
answered Oct 31, 2014 at 9:24
$\begingroup$
$\endgroup$
0
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:
Yoshimoto et al 2003 http://www.sciencedirect.com/science/article/pii/S001044850300006X
Trejo-Caballero et al 2013 http://link.springer.com/chapter/10.1007%2F978-3-642-45111-9_5
Good luck!
$\begingroup$
$\endgroup$
This is a non-trivial issue, especially in multiple dimensions.
- It must be specified what is meant by "best": usually it is the surface between the two curves.
- It also depends if you want to ensure that, on the given fixed interval, you want the two functions to join at the boundaries.
- It usually involves an iterative algorithm.
One can find a good starting point with these two papers:
