curve correction by new point

Hi, There is a curve that for every 5 seconds, a new point is obtained for correcting the curve. By "polyfit" command, it has to start from first stage and consider all points (before points and the new point). I want to consider only the new point affection (correction the curve). In other word, for saving time I need to consider only the curve and new point for obtaining new corrected curve and not need to consider before points and new point to 'polyfit' them. can anybody help me?

[Star Strider]

What you are doing is known as sequential parameter estimation.

I did an exercise on it in a biomedical engineering graduate school course using a book co-authored by the author of this paper ‘SEQUENTIAL METHODS IN PARAMETER ESTIMATION’ so I suggest it to you as likely the best place to start.

I could not find any File Exchange contributions on sequential parameter estimation.

[mohammad]

Thanks Star Strider, Is this method for estimating continuation parts of the curve by using new obtained point? For example in t=0 (time is zero) i have 4 points (p1,p2,p3,p4). So, in t=0 i can estimate a curve by polyfit(p1,p2,p3,p4). In t=1 i receive 2 new points (p5,p6) and now i must estimate a better and accurate curve by using these two new points. One way is polyfit(p1,p2,p3,p4,p5,p6) but because of time saving in my program, i can not use that. Please help me to find a way for making accurate my last curve (in t=0)by using 2 new point (in t=1). Thanks

[Star Strider]

My pleasure.

It doesn’t use polyfit. It uses a linear or nonlinear model that you program. It estimates the parameters sequentially, and assuming they each approach some limit, gives the option of stopping the estimation when the relative change in the parameter updates as each data set is included, is less than some predetermined threshold.

[mohammad]

Thanks again. So in this method, does the curve update when a new point is received?

[Star Strider]

The parameter estimates for the curve update, so the equation for your curve updates with them. The code for the curve itself doesn’t change.

[mohammad]

could i find ready code for this?

[Star Strider]

You might if you search the Internet. I wrote the code for it in FORTRAN about 30 years ago, and those files are long gone.

[Yugal Gupta]

Dear Mohammad,

Do You have written code for your problem,"Curve correction by new point "? Actually, the same problem I have to handle. Can you help me?

Thanks in advance.

Answer 1

[John D'Errico]

This something you could do with a QR update or insert. There is a qrinsert code in MATLAB.

However, you will find that polyfit is pretty fast, and that unless you have thousands of points, that the update will be a waste of time. Note that just doing an update still means you will need to write the code for an updated solution. So you will need to essentially write polyfit anyway.

You would do as well you just write your own simple polyfit code, that does not do the extra computations that polyfit does. The time gained there will be far more significant than what you will gain from the qr update.

The point is, if you don't need the other stuff that polyfit generates and returns, then not computing it will save you time. And a simplified polyfit is trivial to write.

For example, if k is the order polynomial you will fit, and x and y are vectors of the same length...

simplepolyfit = @(x,y,k) bsxfun(@power,x(:),k:-1:0)\y(:);

So it does no error checking. It does not return R^2, or any other parameters of interest.

x = randn(1000,1);
y = rand(1000,1);

polyfit(x,y,1)
ans =
   -0.0019974      0.50881

simplepolyfit(x,y,1)
ans =
   -0.0019974
      0.50881

The two codes return the same numbers. And the simple version does use a nicely numerically stable routine to compute the solution. If it matters, changing simplepolyfit to return a row vector is a trivial thing to do, so it would be completely consistent with polyfit. This will do it:

simplepolyfit = @(x,y,k) (bsxfun(@power,x(:),k:-1:0)\y(:))';

How about the time for these codes to run?

timeit(@() simplepolyfit(x,y,1))
ans =
    0.0001349

timeit(@() polyfit(x,y,1))
ans =
   0.00091916

But on the above simple example, it ran 7 times faster than polyfit, a significant gain in time.

Or you can write a function that will also compute a few minor additional parameters, like residual errors, etc, and still see a gain in time.

[mohammad]

really thanks John, but i must write this code in C++ and number of points are too many. so i cant consider previous points to update the curve

[John D'Errico]

Well, then it is time for you to learn how to fit a polynomial to data, and it is time for you to learn tools such as a qr update, which will allow you to do the computations efficiently. You have not even told us the order of polynomial you will be fitting, so I can't help you more. You will be able to find some of the linear algebra tools you will need in the C version of Lapack. Do some reading.

Answer 2

[Yugal Gupta]

Dear Mohammad,

Do You have written code for your problem,"Curve correction by new point "? Actually, the same problem I have to handle. Can you help me?

Thanks in advance.