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.
Interpolation matrix
Started by ●March 2, 2009
Reply by ●March 2, 20092009-03-02
On Mar 2, 9:40�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. > > � 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.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
Reply by ●March 2, 20092009-03-02
<cincydsp@gmail.com> wrote:>On Mar 2, 9:40�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. >> >> � 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.>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
Reply by ●March 3, 20092009-03-03
On Mar 2, 10:51�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. �(It is a > little long to type in and post.)Indeed, the idea is to precompute W. Do you have a reference for the Lagrangian interpolator solution? I have access to a pretty good 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 receiver/amplifier design and I've been asked to evaluate the 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.
Reply by ●March 3, 20092009-03-03
On Mar 2, 9:40�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. > > � 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.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
Reply by ●March 3, 20092009-03-03
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.
Reply by ●March 3, 20092009-03-03
Dave <Confused.Scientist@gmail.com> wrote:>On Mar 2, 10:51�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. �(It is a >> little long to type in and post.)>Indeed, the idea is to precompute W. Do you have a reference for the >Lagrangian interpolator solution? I have access to a pretty good >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
Reply by ●March 3, 20092009-03-03
<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.pdfThanks. 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
Reply by ●March 3, 20092009-03-03
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.
Reply by ●March 3, 20092009-03-03
On Mar 3, 12:27�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. �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? > > SteveHello Steve, Yes the barycentric form is numerically superior to the standard Lagrangian form. Ideally they will both give the same results. Clay
