Lagrange Interpolation

• Lagrange interpolation is just polynomial interpolation
• $N$th-order polynomial interpolates $N+1$ points
• First-order case = linear interpolation

Problem Formulation

Given a set of $N+1$ known samples $f(x_k)$, $k=0,1,2,\ldots,N$, find the unique order $N$ polynomial $y(x)$ which interpolates the samples

Solution (Waring, Lagrange):

$$y(x) = \sum_{k=0}^N l_k(x)f(x_k)$$

where

$$l_k(x) \mathrel{\stackrel{\mathrm{\Delta}}{=}}{ (x - x_0) \cdots ... ... \over (x_k - x_0) \cdots (x_k - x_{k-1}) (x_k - x_{k+1}) \cdots (x_k - x_N) }$$

• Numerator gives a zero at all samples but the $k$th
• Denominator simply normalizes $l_k(x)$ to $1$ at $x=x_k$
• As a result,
  $$l_k(x_j) = \delta_{kj} \mathrel{\stackrel{\mathrm{\Delta}}{=}}\left\{\begin{array}{ll} 1, & j=k \\ [5pt] 0, & j\neq k \\ \end{array}\right.$$

• Generalized bandlimited impulse = generalized sinc function:
  Each $l_k(x)$ goes through $1$ at $x=x_k$ and zero at all other sample points
  I.e., $l_k(x)$ is analogous to sinc$(x-x_k)$

• For uniformly spaced samples, Lagrange interpolaton is equivalent to windowed sinc interpolation using a binomial window

• Can be viewed as a linear, spatially varying filter (in analogy with linear, time-varying filters)