Next | Prev | Up | Top | JOS Index | JOS Pubs | JOS Home | Search

Appendix: Relation between Sinc and Lagrange Interpolation

Lagrange interpolation is a well known, classical technique for interpolation [#!Hildebrand!#]. It is also called Waring-Lagrange interpolation, since Waring actually published it 16 years before Lagrange [#!Meijering02!#, p. 323]. Given a set of n+1 known samples f(xk), [画像:$k=0,1,2,\ldots,n$], the problem is to find the unique order n polynomial y(x) which interpolates the samples. The solution can be expressed as a linear combination of elementary nth order polynomials:

[画像:\begin{displaymath} y(x) = \sum_{k=0}^n l_k(x)f(x_k) \end{displaymath}] (17)

where
[画像:\begin{displaymath} l_k(x) \isdef { (x - x_0) \cdots (x - x_{k-1}) (x - x_{k+1}) \cdots (x - x_n) \over (x_k - x_0) \cdots (x_k - x_{k-1}) (x_k - x_{k+1}) \cdots (x_k - x_n) } \end{displaymath}] (18)

From the numerator of the above definition, we see that lk(x) is an order n polynomial having zeros at all of the samples except the kth. The denominator is simply the constant which normalizes its value to 1 at xk. Thus, we have
[画像:\begin{displaymath} l_k(x_j) = \delta_{kj} \isdef \left\{\begin{array}{ll} 1, & j=k \\ 0, & j\neq k \\ \end{array} \right. \end{displaymath}] (19)

In other words, the polynomial lk is the kth basis polynomial for constructing a polynomial interpolation of order n over the n+1 sample points xk.

In the case of an infinite number of equally spaced samples, with spacing $x_{k+1}-x_k = \Delta,ドル the Lagrangian basis polynomials converge to shifts of the sinc function, i.e.,

[画像:\begin{displaymath} l_k(x) = \mbox{sinc}\left(x-k\Delta\over\Delta\right), \quad k=\ldots,-2,-1,0,1,2,\ldots \end{displaymath}] (20)

where
[画像:\begin{displaymath} \mbox{sinc}(x) \isdef {\sin(\pi x)\over \pi x} \end{displaymath}]

A simple argument is based on the fact that any analytic function is determined by its zeros and its value at one point. Since [画像:$\mbox{sinc}(x)$] is zero on all the integers except 0, and since [画像:$\mbox{sinc}(0)=1$], it must coincide with the infinite-order Lagrangian basis polynomial for the sample at x=0 which also has its zeros on the nonzero integers and equals 1 at x=0.

The equivalence of sinc interpolation to Lagrange interpolation was apparently first published by the mathematician Borel in 1899, and has been rediscovered many times since [#!Meijering02!#, p. 325].

A direct proof can be based on the equivalance between Lagrange interpolation and windowed-sinc interpolation using a ``scaled binomial window'' [#!KootsookosAndWilliamson95!#,#!VesaT!#]. That is, for a fractional sample delay of D samples, multiply the shifted-by-D, sampled, sinc function

[画像:\begin{displaymath} h_s(n) = \mbox{sinc}(n-D) = \frac{\sin[\pi(n-D)]}{\pi(n-D)} \end{displaymath}]

by a binomial window
[画像:\begin{displaymath} w(n) = \left(\begin{array}{c}N\\ n\end{array}\right), \quad n=0,1,2,\ldots N \end{displaymath}]

and normalize by [#!VesaT!#]
[画像:\begin{displaymath} C(D) = (-1)^N\frac{\pi(N+1)}{\sin(\pi D)}\left(\begin{array}{c}D\\ N+1\end{array}\right), \end{displaymath}]

which scales the interpolating filter to have a unit L2 norm, to obtain the Nth-order Lagrange interpolating filter
\begin{displaymath} h_D(n)=C(D)w(n)h_s(n), \quad n=0,1,2,\ldots,N \end{displaymath}

Since the binomial window converges to the Gaussian window as $N\to\infty,ドル and since the window gets wider and wider, approaching a unit constant in the limit, the convergence of Lagrange to sinc interpolation can be seen.

A more recent alternate proof appears in [#!Yekta09!#].

Next | Prev | Up | Top | JOS Index | JOS Pubs | JOS Home | Search
Download resample.pdf
[How to cite and copy this work] [Comment on this page via email]
``The Digital Audio Resampling Home Page'', by Julius O. Smith III.
Copyright © 2020年09月17日 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA), Stanford University
CCRMA

AltStyle によって変換されたページ (->オリジナル) /