Forums

Resampling/interpolation (uniform and non-uniform case)

Started by Alfred Bovin May 7, 2010
Steve Pope <spope33@speedymail.org> wrote:
(snip)
 
> Yes, that is what you get. If you use four sample points, you get > an interpolated point on the cubic polynomial that goes through > them.
Is it similar to spline interpolation? The popular cubic splines can also be done at higher orders, and that might be useful in this case.
> A "Lagrangian interpolator" specifically is a calculation that > uses a ratio of two polynomials, one of which is the derivative of > the other, as in N/D in the above example. It's a way of computing > a point on the target polynomial (e.g. on the cubic curve if you're > interpolating from four points), without having to compute the > coefficients of the polynomial.
> This shows up all over the place, such as in algebraic decoding > when computing error values.
-- glen
glen herrmannsfeldt  <gah@ugcs.caltech.edu> wrote:

>Steve Pope <spope33@speedymail.org> wrote:
[Lagrangian interpolation]
>> Yes, that is what you get. If you use four sample points, you get >> an interpolated point on the cubic polynomial that goes through >> them.
>Is it similar to spline interpolation?
Spline interpolators are more complex and are designed to avoid unaesthetic stuff like overshoots for some datasets. They are similar in that both Lagrange and Spline interpolators pass through the datapoints, as opposed to a least squares curve which does not. Steve
On May 7, 9:21&#2013266080;pm, spop...@speedymail.org (Steve Pope) wrote:
> glen herrmannsfeldt &#2013266080;<g...@ugcs.caltech.edu> wrote: > > >Steve Pope <spop...@speedymail.org> wrote: > > [Lagrangian interpolation] > > >> Yes, that is what you get. &#2013266080;If you use four sample points, you get > >> an interpolated point on the cubic polynomial that goes through > >> them. > >Is it similar to spline interpolation? &#2013266080; > > Spline interpolators are more complex and are designed to > avoid unaesthetic stuff like overshoots for some datasets. > > They are similar in that both Lagrange and Spline interpolators > pass through the datapoints, as opposed to a least squares > curve which does not.
but if the number of degrees of freedom and the number of data points are the same (and they are both polynomials), don't they have to be exactly the same? i know about B-splines and Hermite polynomial interpolation, unlike Lagrange, they might not go through all the points (maybe just the two adjacent points to the left and right). but i have been trying to understand what exactly they mean by a "cubic spline" if it isn't the polynomial that hits 4 points, 2 on the left and 2 on the right. maybe there is some edge conditions that are different. r b-j
On May 7, 7:46&#2013266080;pm, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On May 7, 9:21&#2013266080;pm, spop...@speedymail.org (Steve Pope) wrote: > > > > > > > glen herrmannsfeldt &#2013266080;<g...@ugcs.caltech.edu> wrote: > > > >Steve Pope <spop...@speedymail.org> wrote: > > > [Lagrangian interpolation] > > > >> Yes, that is what you get. &#2013266080;If you use four sample points, you get > > >> an interpolated point on the cubic polynomial that goes through > > >> them. > > >Is it similar to spline interpolation? &#2013266080; > > > Spline interpolators are more complex and are designed to > > avoid unaesthetic stuff like overshoots for some datasets. > > > They are similar in that both Lagrange and Spline interpolators > > pass through the datapoints, as opposed to a least squares > > curve which does not. > > but if the number of degrees of freedom and the number of data points > are the same (and they are both polynomials), don't they have to be > exactly the same? > > i know about B-splines and Hermite polynomial interpolation, unlike > Lagrange, they might not go through all the points (maybe just the two > adjacent points to the left and right). &#2013266080;but i have been trying to > understand what exactly they mean by a "cubic spline" if it isn't the > polynomial that hits 4 points, 2 on the left and 2 on the right. > maybe there is some edge conditions that are different. > > r b-j
Cubic splines are special cases in that the sum of second derivatives squared is minimized for any function. The cubic spline is calculated all at once whereas Lagrange interpolation can be calculated 4 points at a time. The second derivative of Lagrange interpolation is not guaranteed to be continuous whereas a cubic spline's second derivative is continuous. Peter Nachtwey
On 8 Mai, 00:46, "Alfred Bovin" <alf...@bovin.invalid> wrote:

> random offsets > determined by unpredictable initial conditions. I can, however, get rather > precise time stamps for every measurement. > > For example I can get readings > from sensor1 at 0.0, 0.1, 0.2, 0.3, ... sec > from sensor 2 at 0.0, 0.07, 0.17, 0.27, ... sec > from sensor 3 at 0.08, 0.18, 0.28, 0.38, ... sec > > My idea is then to reconstruct the x(t)'s with standard windows sinc > interpolation and then resample at 10 Hz at the same time points for all > three signal. What will work, won't it?
You are addressing the wrong question. The problem here is not that the three channels are sampled at different rates, but that they are not synced up. Except for that first unpredictable delay, the rates are 10 Hz all over. The time stamps don't matter, as there is no telling how far down the instrumentation chain they were added to the data points. Instead of asking how to reseample three channels to the same rate, you should ask how to sync up the three channels. There are at least two ways of doing this: 1) Correlate the data from the various channels, and use relative delays to match up shared features in the data 2) Investigate the measurement system to estimate system delays in the data flow. Rune
Rune Allnor <allnor@tele.ntnu.no> wrote:
> On 8 Mai, 00:46, "Alfred Bovin" <alf...@bovin.invalid> wrote:
>> random offsets determined by unpredictable initial conditions. >> I can, however, get rather precise time stamps for every measurement.
(snip)
> You are addressing the wrong question. The problem here is not that > the three channels are sampled at different rates, but that they are > not synced up. Except for that first unpredictable delay, the rates > are 10 Hz all over. The time stamps don't matter, as there is no > telling how far down the instrumentation chain they were added > to the data points.
More specifically, it says precise, but not accurate...
> Instead of asking how to reseample three channels to the same rate, > you should ask how to sync up the three channels. There are at least > two ways of doing this:
> 1) Correlate the data from the various channels, and use relative > delays to match up shared features in the data
> 2) Investigate the measurement system to estimate system delays in > the data flow.
3) Accept that the sample time deviation adds noise to the data. With the appropriate statistical distribution, that might not be so bad. -- glen
On Fri, 7 May 2010 23:37:26 -0700 (PDT), Rune Allnor <allnor@tele.ntnu.no>
wrote:

>> random offsets >> determined by unpredictable initial conditions. I can, however, get rather >> precise time stamps for every measurement. >> >> For example I can get readings >> from sensor1 at 0.0, 0.1, 0.2, 0.3, ... sec >> from sensor 2 at 0.0, 0.07, 0.17, 0.27, ... sec >> from sensor 3 at 0.08, 0.18, 0.28, 0.38, ... sec
<...>
>You are addressing the wrong question. The problem here is not that >the three channels are sampled at different rates, but that they are >not synced up. Except for that first unpredictable delay, the rates >are 10 Hz all over. The time stamps don't matter, as there is no >telling how far down the instrumentation chain they were added >to the data points.
I think that you made the important distinction, Rune. Basically, if all three signals are perfectly periodic then there is no way to know the time relationship between them. This is not only because "there is no telling how far down the instrumentation chain [the time stamps] were added to the data points," but also because there is no way to know the propagation delay between whatever created the signals and whatever sampled them. However, being periodic, the signals can all be phase-aligned by trivial phase delay operations upon their Fourier Series. On the other hand, if the signals are non-periodic, and have specific time-domain features that appear at different times in the three signal representations, then the situation becomes a synchronization problem, not a phase-alignment problem. And the way to synchronize the three signal representations is by exploiting those time-domain features, by correlation or some other time-domain technique. Once the relative time delay between the three channels has been established, then they can be approximately aligned either by interpolation or by phase delay operations upon their Fourier Transforms. Greg
On 5/8/2010 9:25 AM, Greg Berchin wrote:
> On Fri, 7 May 2010 23:37:26 -0700 (PDT), Rune Allnor<allnor@tele.ntnu.no> > wrote: > >>> random offsets >>> determined by unpredictable initial conditions. I can, however, get rather >>> precise time stamps for every measurement. >>> >>> For example I can get readings >>> from sensor1 at 0.0, 0.1, 0.2, 0.3, ... sec >>> from sensor 2 at 0.0, 0.07, 0.17, 0.27, ... sec >>> from sensor 3 at 0.08, 0.18, 0.28, 0.38, ... sec > > <...> > >> You are addressing the wrong question. The problem here is not that >> the three channels are sampled at different rates, but that they are >> not synced up. Except for that first unpredictable delay, the rates >> are 10 Hz all over. The time stamps don't matter, as there is no >> telling how far down the instrumentation chain they were added >> to the data points. > > I think that you made the important distinction, Rune. Basically, if all three > signals are perfectly periodic then there is no way to know the time > relationship between them. This is not only because "there is no telling how > far down the instrumentation chain [the time stamps] were added to the data > points," but also because there is no way to know the propagation delay between > whatever created the signals and whatever sampled them. However, being > periodic, the signals can all be phase-aligned by trivial phase delay operations > upon their Fourier Series. > > On the other hand, if the signals are non-periodic, and have specific > time-domain features that appear at different times in the three signal > representations, then the situation becomes a synchronization problem, not a > phase-alignment problem. And the way to synchronize the three signal > representations is by exploiting those time-domain features, by correlation or > some other time-domain technique. Once the relative time delay between the > three channels has been established, then they can be approximately aligned > either by interpolation or by phase delay operations upon their Fourier > Transforms.
The unpredictable delay in one of the channels is the first defect that needs to be worked out. It may be inconsequential. The delay from request to receipt is not what matters. The important interval is the delay from request to sampling instant. For all that's known, it might be constant. (The right software could make it constant.) If the hardware properly band limits the signals and the individual channels are sampled regularly enough, the needed information is all there, and there's more than one way to extract it. Jerry -- "I view the progress of science as ... the slow erosion of the tendency to dichotomize." --Barbara Smuts, U. Mich. &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
Vladimir Vassilevsky wrote:

> > Good problem. You can proceed in two ways: > > 1. Build a fixed time grid with fine step in time, so a sample time > could be assumed at the nearest point of the grid. Do sinc interpolation > in this grid. > > 2. Use a polynomial interpolation x(t). Lagrange interpolation through > unequally spaced points would be the simplest; however that requires a > solution of linear system of equations at every step. > > > Vladimir Vassilevsky > DSP and Mixed Signal Design Consultant > http://www.abvolt.com
1. What you can do is interpolate with the sinc that matches the sample rate - not one that matches the finer grid. Of course, that introduces artifacts at the other sample points unless you solve a system of equations that forces a solution of the sum of sincs to be equal to the sample values over some number of sample intervals. It's easier to think about with a Dirichlet - which may be justified. And, it may be a good place to use a 1/4 1/2 1/4 sum of sincs so that the tails decay faster. Yeah it perturbs the data some but the number of equations could be smaller I think. And, of course, this is just a lowpass filter either brick wall or raised cosine...... It never occurred to me but uniform samples of a suitably bandlimited function with added temporal jitter thereafter must introduce higher frequencies by virtue of the jitter - if you pay attention to the times. I think others have suggested this: just ignore the absolute given times of the samples if they started out to be uniformly spaced - and then adjust for the time shift alone. Fred
On May 8, 1:30=A0am, pnachtwey <pnacht...@gmail.com> wrote:
> On May 7, 7:46=A0pm, robert bristow-johnson <r...@audioimagination.com> > wrote: > > > On May 7, 9:21=A0pm, spop...@speedymail.org (Steve Pope) wrote: > > > > glen herrmannsfeldt =A0<g...@ugcs.caltech.edu> wrote: > > > > >Steve Pope <spop...@speedymail.org> wrote: > > > > [Lagrangian interpolation] > > > > >> Yes, that is what you get. =A0If you use four sample points, you g=
et
> > > >> an interpolated point on the cubic polynomial that goes through > > > >> them. > > > >Is it similar to spline interpolation? =A0 > > > > Spline interpolators are more complex and are designed to > > > avoid unaesthetic stuff like overshoots for some datasets. > > > > They are similar in that both Lagrange and Spline interpolators > > > pass through the datapoints, as opposed to a least squares > > > curve which does not. > > > but if the number of degrees of freedom and the number of data points > > are the same (and they are both polynomials), don't they have to be > > exactly the same? > > > i know about B-splines and Hermite polynomial interpolation, unlike > > Lagrange, they might not go through all the points (maybe just the two > > adjacent points to the left and right). =A0but i have been trying to > > understand what exactly they mean by a "cubic spline" if it isn't the > > polynomial that hits 4 points, 2 on the left and 2 on the right. > > maybe there is some edge conditions that are different. > > > Cubic splines are special cases in that the sum of second derivatives > squared is minimized for any function. =A0The cubic spline is calculated > all at once whereas Lagrange interpolation can be calculated 4 points > at a time. =A0The second derivative of Lagrange interpolation is not > guaranteed to be continuous whereas a cubic spline's second derivative > is continuous.
well, even the first derivative of Lagrange cannot be guaranteed to be continuous, only the zeroeth derivative. but, for 3rd-order Hermite, the first derivative of Hermite interpolation is continuous. there is some kind of "osculating" polynomials that can be continuous to the second derivative, but, even though there are only 4 points, i think their order is higher than 3rd-order. how can cubic splines be continuous to the second derivative, hit the two adjacent points (on the left and right of the interpolated segment), and be only 3rd order? r b-j