# Interpolation matrix

Started by March 2, 2009
```I'm trying to define a couple of common signal interpolation/
resampling methods as a matrix operation, i.e.

y = W z

where,

y is the interpolated data vector of dimension m x 1
W is the interpolation matrix of dimension m x l
z is the original data vector of dimension l x 1

I've worked out W for linear and nearest neighbour interpolation
(easy) and I was wondering if more complicated approaches (cubic,
quintic, Shannon, Lanczos) can be defined analytically?  I don't
expect they are trivial to type out but I'd be grateful if anyone can
point me to a suitable text.

Thanks.
```
```On Mar 2, 9:40&#2013266080;pm, Dave <Confused.Scient...@gmail.com> wrote:
> I'm trying to define a couple of common signal interpolation/
> resampling methods as a matrix operation, i.e.
>
> &#2013266080; y = W z
>
> where,
>
> &#2013266080; y is the interpolated data vector of dimension m x 1
> &#2013266080; W is the interpolation matrix of dimension m x l
> &#2013266080; z is the original data vector of dimension l x 1
>
> I've worked out W for linear and nearest neighbour interpolation
> (easy) and I was wondering if more complicated approaches (cubic,
> quintic, Shannon, Lanczos) can be defined analytically? &#2013266080;I don't
> expect they are trivial to type out but I'd be grateful if anyone can
> point me to a suitable text.
>
> Thanks.

Seems to me that it would be problematic to define higher-order
polynomial interpolation in terms of linear equations. Are you trying
to take advantage of a high-performance linear algebra library on your
target system or something?

Jason
```
``` <cincydsp@gmail.com> wrote:

>On Mar 2, 9:40&#2013266080;pm, Dave <Confused.Scient...@gmail.com> wrote:

>> I'm trying to define a couple of common signal interpolation/
>> resampling methods as a matrix operation, i.e.
>>
>> &#2013266080; y = W z
>>
>> where,
>>
>> &#2013266080; y is the interpolated data vector of dimension m x 1
>> &#2013266080; W is the interpolation matrix of dimension m x l
>> &#2013266080; z is the original data vector of dimension l x 1

>> I've worked out W for linear and nearest neighbour interpolation
>> (easy) and I was wondering if more complicated approaches (cubic,
>> quintic, Shannon, Lanczos) can be defined analytically? &#2013266080;I don't
>> expect they are trivial to type out but I'd be grateful if anyone can
>> point me to a suitable text.

>Seems to me that it would be problematic to define higher-order
>polynomial interpolation in terms of linear equations. Are you trying
>to take advantage of a high-performance linear algebra library on your
>target system or something?

If I'm understanding this approach, W could be precomputed
based on the fractional position of the point being interpolated
(that is, where it sits between two abscissas).  For any
given application there would be a finite number of W's (assuming
you're doing a rational interpolation) and you
could precompute them all.  It then becomes linear.

There is a closed form for the required elements of W for
a Lagrangian interpolator of arbitrary order.  (It is a
little long to type in and post.)

Steve
```
```On Mar 2, 10:51&#2013266080;pm, spop...@speedymail.org (Steve Pope) wrote:

> There is a closed form for the required elements of W for
> a Lagrangian interpolator of arbitrary order. &#2013266080;(It is a
> little long to type in and post.)

Indeed, the idea is to precompute W.  Do you have a reference for the
university library but have been unable to find an analytic solution
that I can cite.

Computationally, I realize this is probably not the most efficient way
to resample a single data vector.  The reason for wanting to find W is
that the signal is corrupt with additive Gaussian noise.
Unfortunately, noise in adjacent channels is correlated due to a poor
correlation after resampling, i.e. Cov' = W^T Cov W, and co-addition
of the signals.  I've done this numerically using a simulink model but
I was asked if I could approach the problem with algebra and see what
comes out.
```
```On Mar 2, 9:40&#2013266080;pm, Dave <Confused.Scient...@gmail.com> wrote:
> I'm trying to define a couple of common signal interpolation/
> resampling methods as a matrix operation, i.e.
>
> &#2013266080; y = W z
>
> where,
>
> &#2013266080; y is the interpolated data vector of dimension m x 1
> &#2013266080; W is the interpolation matrix of dimension m x l
> &#2013266080; z is the original data vector of dimension l x 1
>
> I've worked out W for linear and nearest neighbour interpolation
> (easy) and I was wondering if more complicated approaches (cubic,
> quintic, Shannon, Lanczos) can be defined analytically? &#2013266080;I don't
> expect they are trivial to type out but I'd be grateful if anyone can
> point me to a suitable text.
>
> Thanks.

Hello Dave,

Yes this can be easily done. Here is an excerp from a document I wrote
a while back that includes this process. I hope this answers your
question.

http://www.claysturner.com/polyresample.pdf

IHTH,
Clay S. Turner

```
```Here's a more extensive treatment of barycentric interpolation:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.5097

Martin

--
Quidquid latine scriptum est, altum videtur.
```
```Dave  <Confused.Scientist@gmail.com> wrote:

>On Mar 2, 10:51&#2013266080;pm, spop...@speedymail.org (Steve Pope) wrote:

>> There is a closed form for the required elements of W for
>> a Lagrangian interpolator of arbitrary order. &#2013266080;(It is a
>> little long to type in and post.)

>Indeed, the idea is to precompute W.  Do you have a reference for the
>university library but have been unable to find an analytic solution
>that I can cite.

I'll type it in.  Abscissas spaced by one, point of interest p
lying in (0,1), n-point interpolation:

f(p) = (sum over k) A(n,k,p) * f[k]

if n even, k =  -(n-2)/2 ... n/2

if n odd, k = -(n-1)/2 ... (n-2)/2

if n even, A(n,k,p) =

(-1)^(n/2 + k) * (prod over t=1..n)(p + n/2 - t)
__________________________________________________

((n-2)/2 + k)! (n/2 - k)! (p-k)

if n odd, A(n,k,p) =

(-1)^((n-1)/2 + k) * (prod over t=0..n-1)(p + (n-1)/2 - t)
__________________________________________________

((n-1)/2 + k)! ((n-1)/2 - k)! (p-k)

From:

Abrahamowitz and Stegun, _Handbook of Mathematical Functions_,
National Bureau of Standards, 4th printing December 1965, Ch. 25.

This should work, but let me know if it doesn't seem to be correct.

Steve
```
```<clay@claysturner.com> wrote:

>Here is an excerp from a document I wrote
>a while back that includes this process. I hope this answers your
>question.

>http://www.claysturner.com/polyresample.pdf

Thanks.  I have a question: is the "barycentric" form a
better-behaved numerical formula for the same interpolator
as a standard Lagrangian, or is it a different interpolator function?

Steve
```
```Steve Pope wrote:

> I have a question: is the "barycentric" form a better-behaved
> numerical formula for the same interpolator as a standard
> Lagrangian, or is it a different interpolator function?

It's the same interpolator, but tamer and cheaper to compute.

Martin

--
Quidquid latine scriptum est, altum videtur.
```
```On Mar 3, 12:27&#2013266080;pm, spop...@speedymail.org (Steve Pope) wrote:
> <c...@claysturner.com> wrote:
> >Here is an excerp from a document I wrote
> >a while back that includes this process. I hope this answers your
> >question.
> >http://www.claysturner.com/polyresample.pdf
>
> Thanks. &#2013266080;I have a question: is the "barycentric" form a
> better-behaved numerical formula for the same interpolator
> as a standard Lagrangian, or is it a different interpolator function?
>
> Steve

Hello Steve,

Yes the barycentric form is numerically superior to the standard
Lagrangian form. Ideally they will both give the same results.

Clay

```