spline interpolation
April 9, 2009 8:56 PM
please help me understand spline interpolation
Hello,
I would like to try using spline interpolation to interpolate the missing parts of a clipped wave which you can see here
I have found a tutorial on cubic splines here, but not being familar with all the terminology and the notation used, some of it is slipping past me, and am hoping that someone can point me to something that covers the same topic with a bit more context and background for the uninitiated
cheers
mat
Hello,
I would like to try using spline interpolation to interpolate the missing parts of a clipped wave which you can see here
I have found a tutorial on cubic splines here, but not being familar with all the terminology and the notation used, some of it is slipping past me, and am hoping that someone can point me to something that covers the same topic with a bit more context and background for the uninitiated
cheers
mat
Sherman, set the Wayback Machine for 75 years ago.
Here's how splines used to work: You took a piece of plywood and drew a square grid on it. For each data point you mounted a swiveling post with a horizontal hole through it. Then you ran a stiff piece of wire (say, the kind they use for high notes in pianos) through all the holes in turn. The wire tended to bend, but not too much because it's pretty stiff, and thus would form a reasonably clean curve that passed through all the points.
That is what the word "spline" used to mean. What it means now is a computer algorithm that simulates that wire.
A spline is guaranteed to pass through all the data points which are handed to it. That's both a virtue and a flaw; like any tool it has to be used appropriately. Your application isn't one of those it's appropriate for.
Since it always passes through every data point handed to it, it's also going to pass through all the data points at the top and bottom which represent the clipping. It cannot bypass them and draw a curve above and below; splines don't work that way.
If you were to eliminate those data points from the data set, then the spline would rise and fall outside the range of the real data points, but it probably wouldn't reproduce the original sine wave. Another thing they used to do was to pull on the wire to create a tighter shape, or let it loose to let it curve more. Modern splines include a parameter that controls the simulated stress on the simulated wire, but it's not usually user-adjustable, and usually tighter than you'd need it to be. So it would be round on top and on bottom, but not shaped like a sine wave. (Just eyeballing it, looks like the unclipped peak was probably three times the clipping point, and it just doesn't seem like a spline would do that.)
posted by Chocolate Pickle at 9:39 PM on April 9, 2009
Here's how splines used to work: You took a piece of plywood and drew a square grid on it. For each data point you mounted a swiveling post with a horizontal hole through it. Then you ran a stiff piece of wire (say, the kind they use for high notes in pianos) through all the holes in turn. The wire tended to bend, but not too much because it's pretty stiff, and thus would form a reasonably clean curve that passed through all the points.
That is what the word "spline" used to mean. What it means now is a computer algorithm that simulates that wire.
A spline is guaranteed to pass through all the data points which are handed to it. That's both a virtue and a flaw; like any tool it has to be used appropriately. Your application isn't one of those it's appropriate for.
Since it always passes through every data point handed to it, it's also going to pass through all the data points at the top and bottom which represent the clipping. It cannot bypass them and draw a curve above and below; splines don't work that way.
If you were to eliminate those data points from the data set, then the spline would rise and fall outside the range of the real data points, but it probably wouldn't reproduce the original sine wave. Another thing they used to do was to pull on the wire to create a tighter shape, or let it loose to let it curve more. Modern splines include a parameter that controls the simulated stress on the simulated wire, but it's not usually user-adjustable, and usually tighter than you'd need it to be. So it would be round on top and on bottom, but not shaped like a sine wave. (Just eyeballing it, looks like the unclipped peak was probably three times the clipping point, and it just doesn't seem like a spline would do that.)
posted by Chocolate Pickle at 9:39 PM on April 9, 2009
Yeah, you don't want to interpolate that. How about just fitting a sinusoid?
posted by mr_roboto at 9:43 PM on April 9, 2009
posted by mr_roboto at 9:43 PM on April 9, 2009
I would do the following to reconstitute the wave if we're assuming the wave is perfectly periodic (it repeats exactly every 200 days or so) but not simply as sine wave (as suggested by mr_roboto):
- remove the clipped points and the weird stuff at the beginning
- get a power spectrum of what's left (using something like a lomb scargle periodogram since the waveform is now unevenly sampled)
- interpolate the missing points from that
I'll give it a try right now…
posted by Ginkgo at 9:57 PM on April 9, 2009
- remove the clipped points and the weird stuff at the beginning
- get a power spectrum of what's left (using something like a lomb scargle periodogram since the waveform is now unevenly sampled)
- interpolate the missing points from that
I'll give it a try right now…
posted by Ginkgo at 9:57 PM on April 9, 2009
I couldn't get it to work. I think the data probably isn't as periodic as it looks.
posted by Ginkgo at 10:59 PM on April 9, 2009
posted by Ginkgo at 10:59 PM on April 9, 2009
Seconding mr_roboto.
I would drop the bad data points, then fit the rest to a sinusoid. I don't know how to do it in Sage. In Mathematica it would be
FindFit[data, a Sin[b x + c], {a, b, c}, x]
Adjust your model (a*Sin[b x + c]) as required.
posted by hAndrew at 11:13 PM on April 9, 2009
I would drop the bad data points, then fit the rest to a sinusoid. I don't know how to do it in Sage. In Mathematica it would be
FindFit[data, a Sin[b x + c], {a, b, c}, x]
Adjust your model (a*Sin[b x + c]) as required.
posted by hAndrew at 11:13 PM on April 9, 2009
For decades the best reference on how actually to use splines has been Carl de Boor's A Practical Guide to Splines. If you get the original edition you can enjoy the old-school equations created on a typewriter. I believe parts of the revised edition are on Google Books; any good math or physics library should have it.
posted by drdanger at 11:19 PM on April 9, 2009
posted by drdanger at 11:19 PM on April 9, 2009
Seconding that splines will not restore that waveform. It also is not sinusoidal. It could have slipped into a sinusoidal oscillation right where it starts clipping, but all the peaks before that point are non-sinusoidal peaks. There is simply no way to undo clipping, you could as well try to unscramble an egg. If you have non-clipped measurements of the same phenomenon, from some other source, you could try to infer what the unclipped waveform would have looked like, but this would be extremely unreliable. Such a large amount of this measurement series is clipped, that you will most likely have a hard time doing anything useful with it.
This is all based on my experience working with digital audio, not statistics, so I could be missing something here. In audio terms, you could run it through a sharp low-pass filter or do an analysis of the rate of change based on zero crossings, but splines won't help much with either of these. There is also polynomial interpolation (I think some spline interpolation might be using short polynomial segments?), where you try to match the data you have up to a n-term polynomial, this is IIRC a trial and error method, and in corner cases can get you very odd results that are very far from the original waveform, but happen to match the known datapoints.
posted by idiopath at 11:49 PM on April 9, 2009
This is all based on my experience working with digital audio, not statistics, so I could be missing something here. In audio terms, you could run it through a sharp low-pass filter or do an analysis of the rate of change based on zero crossings, but splines won't help much with either of these. There is also polynomial interpolation (I think some spline interpolation might be using short polynomial segments?), where you try to match the data you have up to a n-term polynomial, this is IIRC a trial and error method, and in corner cases can get you very odd results that are very far from the original waveform, but happen to match the known datapoints.
posted by idiopath at 11:49 PM on April 9, 2009
(I think some spline interpolation might be using short polynomial segments?)
The way I learned spline interpolation in college (20 years ago) was exactly this. Use a polynomial for each connect-the-dots segment. Connect them all together and you have your spline.
The only further difficulty was to smooth the transitions between each segment. This was done by ensuring that the first and second derivatives of each polynomail pair were equal at the point where they meet.
This is obviously an oversimplification. Finding the polynomials is the hard part. Each one has to match at least three data points AND have specific first and second derivatives at two distict points. The math for this is non-trivial.
posted by stubby phillips at 5:28 AM on April 10, 2009
The way I learned spline interpolation in college (20 years ago) was exactly this. Use a polynomial for each connect-the-dots segment. Connect them all together and you have your spline.
The only further difficulty was to smooth the transitions between each segment. This was done by ensuring that the first and second derivatives of each polynomail pair were equal at the point where they meet.
This is obviously an oversimplification. Finding the polynomials is the hard part. Each one has to match at least three data points AND have specific first and second derivatives at two distict points. The math for this is non-trivial.
posted by stubby phillips at 5:28 AM on April 10, 2009
Finding the polynomials is the hard part. Each one has to match at least three data points AND have specific first and second derivatives at two distict points. The math for this is non-trivial.
Eh, it's pretty trivial. For cubic splines, it's a linear problem that reduces to solving an (n-1) x (n-1) tridiagonal matrix (given n data points). You have two free parameters: the second derivitives of the first and last polymomial at the first and last data points. These are typically set to zero to yield the so-called natural cubic spline.
posted by mr_roboto at 2:34 PM on April 10, 2009
Eh, it's pretty trivial. For cubic splines, it's a linear problem that reduces to solving an (n-1) x (n-1) tridiagonal matrix (given n data points). You have two free parameters: the second derivitives of the first and last polymomial at the first and last data points. These are typically set to zero to yield the so-called natural cubic spline.
posted by mr_roboto at 2:34 PM on April 10, 2009
Thank you for the advice and suggestions,
(n-1) x (n-1) tridiagonal matrix (given n data points) sounds like something i would like to try. Could someone suggest a resource where I can learn what this means and how to use it.
cheers
mathew
posted by compound eye at 3:01 AM on April 12, 2009
(n-1) x (n-1) tridiagonal matrix (given n data points) sounds like something i would like to try. Could someone suggest a resource where I can learn what this means and how to use it.
cheers
mathew
posted by compound eye at 3:01 AM on April 12, 2009
This thread is closed to new comments.
I am awful at math
posted by Inspector.Gadget at 8:59 PM on April 9, 2009