2
$\begingroup$

How can I do a Spline Fit with bounds on some derivations?

Problem

Given:

  • Set of data points $t_k, x_k$
  • Set of nodes $n_i$
  • order $D$ of the spline (in my case $D=5$)
  • lower and upper bounds $m_d$,$M_d$ on the $d$-th derivation for $1\le d \le r$ (in my case $r=3$)

Wanted:

The spline $f$ (of order $D$) with nodes $n_i$, that fits the data point best in terms of square errors (ie. $f$ minimizes $\sum_k{(f(t_k)-x_k)^2}$) under the condition that $m_d \le f \le M_d$ for $1 \le d \le r$

Discussion

Without the restriction on the derivations this is a well known procedure, refer for example to: http://www.geometrictools.com/Documentation/BSplineCurveLeastSquaresFit.pdf

Maybe this problem can be dealt with convex optimization, since the set of splines, that meet the restrictions, is convex and the function to be minimized is a quadratic form on the coefficients of the spline. But I don't know much about convex optimization, so I would be grateful for a reference on a text that fits best to the problem at hand.

For my purposes, it doesn't need to be a least square fit. A fit, that minimizes the maximum distance would be as useful or even better. Possible advantage: the maximum is a convex function. Disadvantage: the maximum is not partially differentiable in the coefficients.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

See section 6.5.2 of the book "Convex Optimization" by Stephen Boyd and Lieven Vandenberghe. It's available on the web as a pdf file or as a quite reasonably priced printed book from Cambridge University Press. See the book's web page at:

http://www.stanford.edu/~boyd/cvxbook/

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks a lot. It seems like that book and section covers my problem. Now I have to backtrace the book from page 330 to see how the calculations are actually done. $\endgroup$
    – Max Kubierschky
    Commented Nov 10, 2011 at 15:24
  • $\begingroup$ The material on algorithms for solving convex optimization problems is actually later in the book. However, I have to say that the coverage of algorithms for solving convex optimzation problems in Boyd and Vandenberghe is much less useful than the material on formulating convex optimization problems and the basic theory (optimality conditions, etc.) that is in this book. Frankly, you should try to implement your own solver. Rather, use a well supported package such as CVX to do the work. $\endgroup$
    – Brian Borchers
    Commented Nov 11, 2011 at 4:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .