Download All

Code covered by the BSD License  

Highlights from
Free-knot spline approximation

4.5

4.5 | 2 ratings Rate this file 30 Downloads (last 30 days) File Size: 102.04 KB File ID: #25872
image thumbnail

Free-knot spline approximation

by Bruno Luong

 

17 Nov 2009 (Updated 05 Jul 2011)

Least squares approximation of 1D data using free-knots spline

| Watch this File

File Information
Description

The purpose of this function is to provide a flexible and robust fit to one-dimensional data using free-knot splines. The knots are free and able to cope with rapid change in the underlying model. Knot removal strategy is used to fit with only a small number of knots.

Optional L2-regularization on the derivative of the spline function can be used to enforce the smoothness.

Shape preserving approximation can be enforced by specifying the lower and upper bounds of the derivative(s) of the spline function on sub-intervals. Furthermore specific values of the spline function and its derivative can be specified on a set of discrete data points.

I did not test QUADPROG engine, but I have implemented it. Any feedback is welcome.
Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
Pseudo-inverse, Multiple same-size linear solver, Min/Max filter

MATLAB release MATLAB 7.9 (2009b)
Other requirements optimization toolbox or QP solvers available at: http://sigpromu.org/quadprog/index.html (QPC) http://www.mat.univie.ac.at/~neum/software/minq/ QPC solver is strongly recommended.
Tags for This File  
Everyone's Tags
Tags I've Applied
Add New Tags Please login to tag files.
Comments and Ratings (8)
09 Jan 2010 x yuij  
01 Jun 2010 Bruno Luong

Periodic spline is now available
08 Jun 2010 Bruno Luong

Just discover an issue with continuous regularization. In the mean time, please use the discrete regularization
30 Sep 2010 Michael Teo

Does it handle NaN data?

ePeriod = 3;
aData = [ 5;1;3;NaN;8;2;3;NaN;1;9 ];
minmaxfilt(eData, ePeriod, 'max', 'valid')];

Actual output:
[5;3;3;NaN;8;3;3]

If we take NaN as a empty data, the expected output is:
[5;3;8;8;8;3;3]
03 Oct 2010 Bruno Luong

Michael, I'll reply in the appropriate place (minmaxfilt)
23 Jun 2011 Doug Weathers

Hi Bruno,

Nice package, many great features!

I am having a problem with the 'startingknots' parameter.

When I type this:

test=bsfk(x,y,2,[],[],struct('display',1,'animation',1,'startingknots',polyX))

I get this:

BSFK starts
??? Error using ==> sparse
Sparse matrix sizes must be non-negative integers less than MAXSIZE as defined by
COMPUTER. Use HELP COMPUTER for more details.

Error in ==> BSFK>BuildDineqMat at 1623
        D = sparse(row,col,val,m,n);

Error in ==> BSFK>UpdateConstraints at 2039
    [D LU X] = BuildDineqMat(t, knotidx, k, shape);

Error in ==> BSFK>InitPenalization at 2077
smoothing = UpdateConstraints(smoothing, t, shape, pntcon, periodic);

Error in ==> BSFK at 393
    smoothing = InitPenalization(y, t, k, d, lambda, p, regmethod, ...

However, if I use 'chebyschev' instead of a vector of starting knots, it works. But it misses some important knots.

Any ideas?

Thanks,

Doug
23 Jan 2012 Nima Zarif

Hey Bruno thanks for the awesome package, it works great!
I just have one problem, is this approximation rotation invariant? Since when I intentionally rotate my data points the knots are completely different with increased fit error compared to the baseline profile! please let me know if I am doing sth wrong
26 Jan 2012 Bruno Luong

Nima, it is not rotational invariant. Because the fit is carried out using the least-squares to the ordinate data (y) only.
Please login to add a comment or rating.
Updates
18 Nov 2009

Update description, more options added to control the fit, discrete regularization
19 Nov 2009

Remove NaN data before fitting, change TRY/CATCH ME syntax for better compatibility (tested under 2006B), estimate automatic of the noise standard deviation
28 Nov 2009

Change title and description
04 Dec 2009

A major enhancement with shape preserving splines
08 Dec 2009

Point-wise constraints. Discover an error of the Jacobian formula in [Schutze/Schwetlick 97] paper, modify the calculation accordingly. This concern only the constrained fitting.
09 Dec 2009

Correct another bug in the Jacobian calculation (constrained case)
09 Dec 2009

Change the description.
10 Dec 2009

Singular constraints will issue a warning (instead of an error). Refine the Gauss-Newton direction. Fix few minor bugs.
14 Dec 2009

Correct a bug in UpdateConstraints that did not update the knot positions. Precasting data to double. Update more frequently the scaling matrix. Reduce the Lagrange's tolerance to detect active set of QPC solver
18 Mar 2010

fixed small bug when calling QP engine minqdef
10 Apr 2010

fix a bug with parsing k and nknots
Spline order can be as low as k=1 (piecewise constant fit)
31 May 2010

New feature: Periodic spline
01 Jun 2010

Remove some redundant code, modify test program
07 Jun 2010

A more robust conversion in pp form is implemented
07 Jun 2010

Fix a small bug (eigs with 'sa' option requires true symmetric matrix, which is now always the case by symmetrizing)
10 Jun 2010

Fix the bug for continuous regularization
05 Jul 2011

Fix the bug when starting knots are provided
Tag Activity for this File
Tag Applied By Date/Time
fitting Bruno Luong 17 Nov 2009 13:09:10
bspline Bruno Luong 17 Nov 2009 13:09:10
free knots Bruno Luong 17 Nov 2009 13:09:10
data compression Bruno Luong 17 Nov 2009 13:09:10
knot removal Bruno Luong 17 Nov 2009 13:09:10
least squares Bruno Luong 18 Nov 2009 10:17:14
shape preserving Bruno Luong 04 Dec 2009 09:49:00
spline Bruno Luong 10 Dec 2009 12:09:06
bspline Jon 09 Mar 2010 09:50:15
free knots Jon 09 Mar 2010 12:39:13
fitting michael golinski 28 Dec 2010 14:49:06
bspline ARYAN 28 Apr 2011 11:07:27

Contact us at files@mathworks.com