File Exchange

image thumbnail

Free-knot spline approximation

version 1.19.0.0 (100 KB) by Bruno Luong
Least squares approximation of 1D data using free-knots spline

12 Downloads

Updated 30 Nov 2016

View Version History

View License

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.

Cite As

Bruno Luong (2020). Free-knot spline approximation (https://www.mathworks.com/matlabcentral/fileexchange/25872-free-knot-spline-approximation), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (26)

Matthew Boring

Bruno Luong

Michael, have you look at the code testBSFK with caseid == 2, there is a constraint of zeros slope at x==0 (line 91).
Just replace x by respectively the left and right points, and you might even add the same constraints for the second derivative

Michal Kvasnicka

Bruno, could you kindly add any simple example how to apply specific constraints: zero 1st derivative before and after data points? I need to hold 1st derivative equal zero outside of data interval.

Daliang Shen

Monika Jozsa

Nikolaos Psyrras

Long Cheng

Martin

Dear Bruno,

I want to force the spline to be straight line between the first fixed knot and the second one.
Is this possible?

Gaute Hope

How do you prefer this work to be cited?

Gaute Hope

fasfa

Thank you, any possible modification to make it work for k=1? if not, do you know any other method for constant piece wise approximation?

Bruno Luong

To Fasta:

Yes for k=1; the gradient wrt knots are dirac like, and the gradient method used by here cannot handle it correctly.

Yes, it's a major work to extend to 2D.

fasfa

Hello,
I think there is an error when you use piecewise constant (k=1). The results are not the expected. Is it ok?

Also I would like to know if it would be very difficult to modify it and use it for surfaces instead of lines (1D -> 2D).
Thanks!

Chi-Fu

Markus

Hi,

I´m always getting the following warning message:

Warning: Options LargeScale = 'off' and Algorithm = 'trust-region-reflective'
conflict. Ignoring Algorithm and running active-set algorithm. To run
trust-region-reflective, set LargeScale = 'on'. To run active-set without this
warning, set Algorithm = 'active-set'.

What am I doing wrong?

Bruno Luong

Richard,

not exactly like you want but you can enforce the y-value between two knots to be zero:

x=linspace(0,2*pi,100);
y = sin(x);
y = y + 0.1*randn(size(y));

nknots = 5;
lo = -inf(1,nknots);
up = +inf(1,nknots);
lo(3) = 0;
up(3) = 0;
shape = struct('p',0,'lo',lo,'up',up);
options = struct('shape', shape,'animation', 1, 'knotremoval','none');
BSFK(x,y,4,nknots,[],options);

Richard

Brilliant package Bruno. Quick question.

I know you can fix any given knot, but is it possible to fix a given not to a y-value but let the least squares find the best x-value for it?

I'm using 4 knots/3 lines to represent my data but I would always like the 3rd knot to have y=0. While this condition is met some of the time (by chance) ideally I would like to enforce it.

Bruno Luong

Nima, it is not rotational invariant. Because the fit is carried out using the least-squares to the ordinate data (y) only.

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

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

Bruno Luong

Michael, I'll reply in the appropriate place (minmaxfilt)

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]

Bruno Luong

Just discover an issue with continuous regularization. In the mean time, please use the discrete regularization

Bruno Luong

Periodic spline is now available

x yuij

MATLAB Release Compatibility
Created with R2009b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!