contents

  • interpolation is the process of synthesizing continuous-time world entities from the discrete-time world
  • symbolically, \(x(t) \) is obtained, given \( x[n] \)

continuous-time-conversion

fig: continuous-time world vs. discrete-time world metaphor

polynomial interpolation

  • consider given a discrete sequence of points

disc-time-seq

fig: discrete time sequence

  • to be determined is a continuous function that goes through all the points

disc-time-seq-curve-fit

fig: continuous curve fit through discrete time sequence

  • this transforms \(x(t) \) to \( x[n] \)
  • interpolators are tools to generate curves through points in a localized area
    • these are used to generate band-limited continuous-time functions

interpolation requirements

  • decide on \(T_s\): spacing between the samples
  • make sure \( x(nT_s) = x[n] \)
  • \( x(t) \) has to be smooth
smoothness entailment
  • smoothness means:
    • the interpolation should be infinitely differentiable
  • jumps (1st order discontinuities) requires signals to move faster than light

  • 2nd order discontinuities requires infinite acceleration

  • natural solution: polynomial interpolation

polynomial interpolation

  • this is a naive approach for the interpolation problem
  • for a discrete signal with \(N\) points
    • polynomial of degree \( N-1 \)
  • fit the polynomial
    • \( p(t) = a_0 + a_1 t + a_2 t^2 + \ldots + a_{N-1}t^{N-1} \)
  • here: \[ \begin{align} p(0) & = x[0] \
    p(T_s) & = x[1] \
    p(2T_s) & = x[2] \
    \ldots \
    p( (N-1) T_s ) & = x[N-1] \
    \end{align} \]

lagrange interpolation

  • consider a symmetric interval \(I_N = [-N,\ldots, N] \)
  • set \(T_s = 1 \)

  • then: \[ \begin{align} p(-N) & = x[-N] \
    p(-N + 1) & = x[-N + 1] \
    \ldots \
    p(0) & = x[0] \
    \ldots \
    p(N) & = x[N] \
    \end{align} \]

  • \( P_N \): space of degree-\(2N\) polynomials over \(I_N\)

  • a basis for \( P_N \) is the family of \( 2N + 1 \) lagrange polynomials \[ L_n^{(N)}(t) = \prod_{k=-N, k \neq n}^{N} \frac{t-k}{n-k} \
    n = -N,\ldots,N \]

  • pick N = 1 to get three lagrange polynomials
    • \( L_{-1}^{(1)}, L_{0}^{(1)}, L_{1}^{(1)} \)

  • calculate each polynomial now:

  • \( L_0^{(1)} \):
    • \( \prod_{k = -1}^{1} \frac{t-k}{-k} = \frac{t+1}{1}.\frac{t-1}{-1} = 1 - t^2 \)
    • this is a parabola
      • which is 1 at origin
      • 0 at 1 and -1
  • similarly,
    • \( L_1^{(1)}(t) = \frac{t^2 + t}{2} \)
    • \( L_{-1}^{(1)}(t) = \frac{t^2 - t}{2} \)

  • all lagrangian polynomials generated so are 1 at their index \(N\) and 0 at other integers

  • lagrangian interpolator: \[ p(t) = \sum_{n = -N}^{N} x[n]L_n^{(N)}(t) \]

  • this interpolation is the sough-after polynomial interpolator
  • polynomial of degree \(2N\) through \(2N + 1 \) points in unique
  • the lagrangian interpolator satisfies \[ p(n) = x[n] \
    \text{ for } -N \leq n \leq N \
    \
    \text{ since } \
    L_n^{(N)}(m) = \Bigg \{ \begin{matrix} 1 & \text{ if } n = m \\ 0 & \text{ if } n \neq m \end{matrix} \]
example
  • given sequence

disc-time-seq

fig: discrete time sequence

  • the lagrange interpolation with \( N = 2 \) is as follows
    • this has five lagrange polynomials in all: \( L_{-2}^{(2)}, L_{-1}^{(2)}, L_{0}^{(2)}, L_{1}^{(2)}, L_{2}^{(2)} \)

disc-time-seq

fig: lagrange polynomial [-2]

disc-time-seq

fig: lagrange polynomial [-1]

disc-time-seq

fig: lagrange polynomial [0]

disc-time-seq

fig: lagrange polynomial [1]

disc-time-seq

fig: lagrange polynomial [2]

disc-time-seq

fig: summed lagrange polynomials

disc-time-seq

fig: final interpolation to given discrete signal

lagrange polynomial notes
  • maximally smooth

  • infinitely many continuous derivatives

  • interpolation bricks shape depend on chosen \(N\)
  • each brick looks different

local interpolation

  • other interpolation possibilities essentially have to meet the same requirements
    • decide on \(T_s\)
    • make sure \( x(nT_s) = x[n] \)
    • \( x(t) \) has to be smooth
  • smoothness condition of being infinitely many times differential is too stringent for practical applications

  • signal has to hold smoothness within the limits of the system

  • consider the following sequence in discrete-time

disc-time-seq

fig: discrete time sequence

  • explored in the following are some interpolation strategies

zero-order interpolation

  • piecewise constant function
    • a staircase function
  • matches discrete sequence value at given locations
  • but is not continuous

piecewise-interpolation-function

fig: piecewise interpolation for a discrete time sequence

characteristics
  • \(x(t) = x[ \lfloor t + 0.5 \rfloor ] \)
    • \( -N \leq t \leq N \)

\[ x(t) = \sum_{n = -N}^{N} x[n] rect(t-n) \]

  • interpolation kernel: \( i_0(t) = rect(t) \)
  • \( i_0(t) \): “zero-order hold”
    • interpolator’s support is 1
    • interpolation is not continuous

piecewise-interpolation-function-with-rects

fig: zero-order interpolation - rects for a discrete time sequence

piecewise-interpolation-sum-of-rects

fig: sum of piecewise rect supports

first-order interpolation

  • piece-wise linear function

first-order-functions

fig: first-order interpolation for a discrete time sequence

  • straight lines connect the samples
  • connect the dots strategy
characteristics

\[ x(t) = \sum_{n = -N}^{N} x[n] i_1(t-n) \]

  • interpolation kernel: \[ i_1(t) = \Bigg \{ \begin{matrix} 1 - \vert t \vert & \vert t \vert \leq 1 \\ 0 & \text{ otherwise }\end{matrix} \]
  • interpolator support is 2
  • interpolation is continuous
    • however its derivative is not
  • the interpolation function has inflections at the discrete sample points

first-order-supports

fig: first-order interpolation - support functions through discrete sequence

first-order-sum-of-supports

fig: first-order interpolation - sum of support functions

third-order interpolation

characteristics

\[ x(t) = \sum_{n = -N}^{N} x[n] i_3(t-n) \]

  • interpolation kernel is put together from two cubic polynomials
  • interpolator support is 4
  • interpolation is continuous up to second derivative

third-order-supports

fig: third-order interpolation - support functions through discrete sequence

third-order-sum-of-supports

fig: third-order interpolation - sum of support functions

local interpolations schemes

\[ x(t) = \sum_{n = -N}^{N} x[n] i_c(t-n) \]

  • interpolator’s requirements:
    • \( i_c(0) = 1 \)
    • \( i_c(t) = \) for \(t\) a nonzero integer
  • different interpolator kernels may be used with the interpolator

three kernels

  • box kernel

box-kernel

fig: box interpolator kernel

  • triangle kernel

tri-kernel

fig: triangle interpolator kernel

  • cubic kernel

cubic-kernel

fig: cubic interpolator kernel

properties
  • they become larger and smoother as the order increases
  • same interpolating function independent of \(N\)
    • in contrast with the lagrange interpolation
  • lack of smoothness
    • compared to the lagrange interpolation

sinc interpolation

\[ x(t) = \sum_{n = -\infty}^{\infty} x[n] sinc \bigg( \frac{t - nT_s}{T_s} \bigg) \]

example

  • consider a discrete-time sequence

sinc-interpolation

fig: discrete-time sequence to be interpolated

  • overlaying the interpolator kernels over appropriate sequence points

sinc-interpolation

fig: one kernel, at origin

sinc-interpolation

fig: second kernel added

sinc-interpolation

fig: more kernels added

sinc-interpolation

fig: all discrete samples fitted with corresponding kernels

sinc-interpolation

fig: sum of support kernels

lagrange-sinc interpolation relationship

  • lagrange-sinc interpolation relationship \[ \lim_{N \rightarrow \infty} L_n^{(N)} = sinc(t-n) \]
  • within the system limit, local and global interpolation are the same
    • lagrange interpolation: global
    • sinc interpolation: local
proof
  • proof is too technical (see textbook)
  • intuition: \(sinc(t-n) \) and \( L_n^{(\infty)}(t) \) share infinite number of zeros

\[ \begin{align} sinc(m-n) & = \delta[m-n] \\ & m,n \in \mathbb{Z} \
\
L_n^{(N)}(m) & = \delta[m-n] \
& m,n \in \mathbb{Z}, \\ & -N \leq n,m \leq N \
\end{align} \]

visualization
  • below are comparisons of sinc and higher order lagrange function interpolation

sinc-lagrange

fig: sinc and 100-order lagrange interpolator

sinc-lagrange

fig: sinc and 200-order lagrange interpolator

sinc-lagrange

fig: sinc and 300-order lagrange interpolator

trade-offs

  • lagrange interpolation is maximally smooth
    • but has the drawback that the interpolation kernel depends on N.
  • to avoid lagrange interpolation drawback, another interpolation called local interpolation is used
    • method uses only a neighborhood of 2N+1 points and
    • an interpolation kernel over these 2N+1 points that is equal to 1 at zero and 0 at nonzero integer points

  • the interpolation kernel does not depends on N but some of the smoothness is lost in the process

  • as N goes to infinity, the lagrange interpolation corresponds to a sinc interpolation
    • at the limit, global and local interpolation are equivalent

references