If you're using Python,
scipy.interpolate.LSQUnivariateSpline
can easily handle 1M points:
""" LSQUnivariateSpline( x, y, user knots ) """
# http://docs.scipy.org/doc/scipy/reference/generated/scipy.interpolate.LSQUnivariateSpline.html
# cf https://github.com/scipy/scipy/issues/2611 many knots -> all NaN
from __future__ import division
import sys
from time import time
import numpy as np
import pylab as pl
from scipy.interpolate import LSQUnivariateSpline
__date__ = "2013-08-02 aug denis"
# LSQSpline nx points, interpolate at nsample --
nx = 1e6
nsample = 1000
ncycle = 1
noise = .5
nknot = 5
plot = 0
seed = 0
exec( "\n".join( sys.argv[1:] )) # run this.py nx= ... from sh or ipython
np.set_printoptions( 1, threshold=100, edgeitems=10, suppress=True )
np.random.seed(seed)
nx = int(nx)
title = "scipy.interpolate.LSQUnivariateSpline nx %d noise %.2g %d knots" % (
nx, noise, nknot )
print 80 * "-"
print title
def func( x ):
return np.sin( 2*np.pi * ncycle * x )
x = np.sort( np.random.uniform( size=nx ))
xs = np.linspace( 0, 1, nsample )
y = func(x) + noise * np.random.randn(nx)
#...............................................................................
knots = np.linspace( xs[1], xs[-2], nknot )
# knots = np.linspace( xs[0], xs[-1], nknot )
# ValueError: Interior knots t must satisfy Schoenberg-Whitney conditions
t0 = time()
spline = LSQUnivariateSpline( x, y, knots, k=3 )
ys = spline(xs) # interpolate at xs
print "%.2g sec setup + interpolate %d points" % (time() - t0, nsample)
print "y interpolated:", ys
yexact = func(xs)
averr = np.fabs( ys - yexact ).mean()
print "av |yspline - yexact| %.2g" % averr
if plot:
pl.title( title )
pl.plot( ys, label="spline" )
pl.plot( yexact, label="exact" )
# pl.plot( ys - func(xs), label="diff" )
pl.legend()
pl.show()
Without Python (what language are you using ?),
start with knots [ 0 .2 .4 .6 .8 1]
and fit 5 separate cubics in each interval --
least-squares fit [1 x x^2 x^3].
If the ends are close enough at .2 .4 .6 .8, you're done.
If not, set up a global least-squares with 5 * 4 columns in all,
plus dummy points at and near the knots with weights 1000000 to force
continuity and smoothness there.
If the points x
are very non-uniformly spaced, use non-uniform intervals, e.g.
np.percentile( x, [0,20,40,60,80,100] )
.
If you really want L1 approximation, I believe a cheap near-L1
can be done by iterative L2 with weighting; ask a new question on that.
Hope this helps.
You might ask on stackoverflow, see
https://stackoverflow.com/search?q=[spline]+knots ,
and of course
google "spline (intro|tutorial) user-knots" .
Let's count the conditions: $N+1$ points for $N$ intervals. Resulting in $4N$ coefficients of $N$ cubic polynomials. On the side of the equations we get
- $2N$ prescribed function values
- $N-1$ continuity conditions for the first derivative
- $N-1$ continuity conditions for the second derivative
- the third derivative is piecewise constant, so there must be jumps, no equations.
Which still leaves us with a difference of $2$ degrees of freedom. One usually imposes conditions on the first and last point, for instance a zero second derivative
Best Answer
Of course, your way will work. The only thing matters is whether it is going to be fast enough.
To create a cubic spline interpolating $N$ points, you can go with a global approach or a local approach. The global approach (such as the natural cubic spline) will need to solve an $N$ x $N$ matrix but will give you a $C^2$ continuous spline. The local approach (such as Catmull-Rom spline) is much faster performance wise (no need to solve a matrix) but will only give you a $C^1$ continuous spline (which will have $C^2$ discontinuity at the data points). You certainly don't want to have a spline that has $C^2$ discontinuity at the data points where you want to estimate curvature. However, solving an $N$ x $N$ matrix might become too slow for your purpose. So, there are a few alternatives here:
Each method will have different computation cost and result in different estimate for curvatures. You just have to find out which one suits you the best on your own.