# Resampling/interpolation (uniform and non-uniform case)

Started by 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

-- 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.
>
>
> 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
```