Page MenuHomec4science
Files F104878058

2_interpolation.tex
No OneTemporary
Actions

File Metadata

Created
Thu, Mar 13, 02:10

2_interpolation.tex
View Options

\documentclass[aspectratio=169]{beamer}
\def\stylepath{../styles}
\usepackage{\stylepath/com303}
\begin{document}
\begin{frame} \frametitle{Overview:}
\begin{itemize}
\item Polynomial interpolation
\item Local interpolation
\item Sinc interpolation
\end{itemize}
\end{frame}
\begin{frame} \frametitle{Interpolation}
\centering
$x[n] \longrightarrow x(t)$
\vspace{2em}
``fill the gaps'' between samples
\end{frame}
%% finite-length signal, 5 taps
\def\ta{1 } \def\tb{2 } \def\tc{0.7 } \def\td{2.4 } \def\te{-1.5 }
%% the tap plotting string
\def\taps{-2 \ta -1 \tb 0 \tc 1 \td 2 \te}
\def\plotTaps{\dspTaps[linecolor=blue!70]{\taps}}
%% Lagrange polynomials
\def\lpa{%
dup 1 add -1 div exch %
dup -2 div exch %
dup -1 add -3 div exch %
-2 add -4 div %
mul mul mul }
\def\lpb{%
dup 2 add exch %
dup -1 div exch %
dup -1 add -2 div exch %
-2 add -3 div %
mul mul mul }
\def\lpc{%
dup 2 add 2 div exch %
dup 1 add 1 div exch %
dup -1 add -1 div exch %
-2 add -2 div %
mul mul mul }
\def\lpd{%
dup 2 add 3 div exch %
dup 1 add 2 div exch %
dup 1 div exch %
-2 add -1 div %
mul mul mul }
\def\lpe{%
dup 2 add 4 div exch %
dup 1 add 3 div exch %
dup 2 div exch %
-1 add 1 div %
mul mul mul }
\def\lagInterp{%
x \lpa \ta mul %
x \lpb \tb mul %
x \lpc \tc mul %
x \lpd \td mul %
x \lpe \te mul %
add add add add}
%% cubic interpolator
\def\cubFunA{abs dup 2 exp -2.25 mul exch 3 exp 1.25 mul 1 add add }
\def\cubFunB{abs dup dup 8 mul exch 2 exp -5 mul add exch 3 exp -4 add add -0.75 mul }
\def\cubFun#1{
#1 sub
dup dup dup dup %
-2 lt {pop pop pop pop 0} {
2 gt {pop pop pop 0 } {
-1 lt {pop \cubFunB } {
1 gt {\cubFunB }
{\cubFunA}
ifelse }%
ifelse }%
ifelse }%
ifelse }
\def\triInterp{%
x \cubFun{-2} \ta mul %
x \cubFun{-1} \tb mul %
x \cubFun{0} \tc mul %
x \cubFun{1} \td mul %
x \cubFun{2} \te mul %
add add add add}
\def\t#1{\csname t#1\endcsname}
\begin{frame} \frametitle{Example}
\begin{figure}
\begin{dspPlot}[sidegap=0,yticks=1,xticks=none]{-2.5,2.5}{-2,3}
\moocStyle
\plotTaps
\end{dspPlot}
\end{figure}
\end{frame}
\begin{frame} \frametitle{Example}
\begin{figure}
\begin{dspPlot}[sidegap=0,yticks=1,xticks=none]{-2.5,2.5}{-2,3}
\moocStyle
\plotTaps
\pscurve(-2, \ta)(0,0)(2, \te)
\end{dspPlot}
\end{figure}
\end{frame}
\begin{frame} \frametitle{Example}
\begin{figure}
\begin{dspPlot}[sidegap=0,yticks=1,xticks=none]{-2.5,2.5}{-2,3}
\moocStyle
\plotTaps
\pscurve(-2, \ta)(-1.75, 2)(-1.5, -1.5)(-1.25, 1.5)%
(-1, \tb)(-0.75, 0.5)(-0.5, .6)(-0.25, .5)%
(0, \tc)(0.25, -1)(0.5, 1)(0.75, -1)%
(1, \td)(1.25, 1.5)(1.5, 2.5)(1.75, 1.8)(2, \te)
\end{dspPlot}
\end{figure}
\end{frame}
\begin{frame} \frametitle{Example}
\begin{figure}
\begin{dspPlot}[sidegap=0,yticks=1,xticks=none]{-2.5,2.5}{-2,3}
\moocStyle
\plotTaps
\only<2->{%
\dspFunc[xmin=-2,xmax=2]{\triInterp}
\dspFunc[linestyle=dashed,xmax=-2]{\triInterp}
\dspFunc[linestyle=dashed,xmin=2]{\triInterp}}
\end{dspPlot}
\end{figure}
\end{frame}
\begin{frame} \frametitle{Interpolation requirements}
\begin{itemize}
\item decide on $T_s$
\item make sure $x(nT_s) = x[n]$
\item make sure $x(t)$ is {\em smooth}
\end{itemize}
\end{frame}
\begin{frame} \frametitle{Why smoothness?}
\begin{itemize}
\item jumps (1st order discontinuities) would require the signal to move ``faster than light''...
\item 2nd order discontinuities would require infinite acceleration
\item ...
\vspace{1em}
\item the interpolation should be infinitely differentiable
\vspace{1em}
\item ``natural'' solution: {\color{red} polynomial interpolation}
\end{itemize}
\end{frame}
\begin{frame} \frametitle{Polynomial interpolation}
\begin{itemize}
\item $N+1$ points $\rightarrow$ polynomial of degree $N$
\item $x_p(t) = a_0 + a_1 t + a_2 t^2 + \ldots + a_N t^{N}$
\item straightforward approach:
\vspace{1em}
\[
\left\{
\begin{aligned}
x_p(0) &= x[0] \\
x_p(T_s) &= x[1] \\
x_p(2T_s) &= x[2] \\
& \ldots \\
x_p(NT_s) &= x[N] \\
\end{aligned}
\right.
\]
\end{itemize}
\end{frame}
\begin{frame} \frametitle{Polynomial interpolation}
Without loss of generality:
\begin{itemize}
\item even polynomial degree $2N$
\item fit polynomial over $2N+1$ data points symmetrically distributed around zero
\vspace{1em}
\[
\left\{
\begin{aligned}
x_p(-NT_s) &= x[-N] \\
x_p((-N+1)T_s) &= x[-N+1] \\
& \ldots \\
x_p(0) &= x[0] \\
& \ldots \\
x_p((N-1)T_s) &= x[N-1] \\
x_p(NT_s) &= x[N] \\
\end{aligned}
\right.
\]
\end{itemize}
\end{frame}
\begin{frame} \frametitle{Polynomial interpolation}
Without loss of generality:
\begin{itemize}
\item set $T_s=1$
\item find the $2N+1$ coefficients $a_0, \ldots, a_{2N}$ by solving:
\[
\sum_{k = 0}^{2N} a_k n^k = x[n] \qquad n = -N, -N+1, \ldots, 0, \ldots, N-1, N
\]
% \vspace{1em}
% \[
% \left\{
% \begin{aligned}
% x_p(-N) &= x[-N] \\
% x_p(-N+1) &= x[-N+1] \\
% & \ldots \\
% x_p(0) &= x[0] \\
% & \ldots \\
% x_p(N-1) &= x[N-1] \\
% x_p(N) &= x[N] \\
% \end{aligned}
% \right.
% \]
\end{itemize}
\end{frame}
\begin{frame} \frametitle{Lagrange interpolation}
Let's use the power of vector spaces:
\begin{itemize}
\item $P_N$: space of degree-$2N$ polynomials over $I_N = [-N, N]$
\item interpolation will be a linear combination of basis vectors for $P_N$
\item what is a good basis for \textit{interpolation?}
% \item a basis for $P_N$ is the family of $2N+1$ Lagrange polynomials
% \[
% L^{(N)}_n(t) = \mathop{\prod_{k = -N}}_{k\neq n}^{N}\frac{t - k}{n - k} \qquad\qquad n = -N, \ldots, N
% \]
\end{itemize}
\end{frame}
\begin{frame} \frametitle{Aside: $N$-degree polynomial bases on the interval}
Given a set of $N+1$ points, the degree-$N$ polynomial interpolation is unique; however, when numerical issues come into play:
\vspace{1em}
\begin{itemize}
\item naive basis: $1, t, t^2, \ldots, t^{N}$; most general but very ill-conditioned
\item Lagrange polynomials: equal degree, equally-spaced points but potential oscillation at edges
\item Legendre polynomials: orthonormal, increasing degree, points denser at edges, better conditioning
\item Chebyshev polynomials: orthonormal, increasing degree, optimal point placement (minimax criterion)
\end{itemize}
\end{frame}
\begin{frame} \frametitle{Lagrange interpolation}
\begin{itemize}
\item $P_N$: space of degree-$2N$ polynomials over $I_N = [-N, N]$
\item a basis for $P_N$ is the family of $2N+1$ Lagrange polynomials
\[
L^{(N)}_n(t) = \mathop{\prod_{k = -N}}_{k\neq n}^{N}\frac{t - k}{n - k} \qquad\qquad n = -N, \ldots, N
\]
\end{itemize}
\end{frame}
\begin{frame} \frametitle{Lagrange polynomials for $I_2$}
\begin{align*}
L^{(2)}_{-2}(t) &= \left(\frac{t + 1}{-2 + 1}\right) \, \left(\frac{t}{-2}\right) \, \left(\frac{t - 1}{-2 - 1}\right) \, \left(\frac{t -2}{-2 - 2}\right) = \frac{(t+1)t(t-1)(t-2)}{24}\\
L^{(2)}_{-1}(t) &= \left(\frac{t + 2}{-1 + 2}\right) \, \left(\frac{t}{-1}\right) \, \left(\frac{t - 1}{-1 - 1}\right) \, \left(\frac{t -2}{-1 - 2}\right) = \frac{(t+2)t(t-1)(t-2)}{-6}\\
L^{(2)}_{0}(t) &= \left(\frac{t + 2}{2}\right) \, \left(\frac{t+1}{1}\right) \, \left(\frac{t - 1}{- 1}\right) \, \left(\frac{t -2}{-2}\right) = \frac{(t+2)(t+1)(t-1)(t-2)}{-4}\\
L^{(2)}_{1}(t) &= L^{(2)}_{-1}(-t)\\
L^{(2)}_{2}(t) &= L^{(2)}_{-2}(-t)\\
\end{align*}
\end{frame}
\def\LagPoly#1#2#3#4{\only<#1->{%
\dspFunc[linecolor=#2]{x \csname lp#3\endcsname}%
\only<#1|handout:0>{\dspText(0,1.3){\color{#2} $L_{#4}^{(2)}(t)$}}}}
\begin{frame}
\frametitle{Lagrange interpolation polynomials}
\center
\begin{figure}
\begin{dspPlot}[sidegap=0,yticks=0.5,height=5cm]{-2.5,2.5}{-0.8,1.6}
\moocStyle
\begin{dspClip}%
\LagPoly{1}{green}{a}{-2}%
\LagPoly{2}{blue}{b}{-1}%
\LagPoly{3}{orange}{c}{0}%
\LagPoly{4}{black}{d}{1}%
\LagPoly{5}{cyan}{e}{2}%
\end{dspClip}
\end{dspPlot}
\end{figure}
\end{frame}
\begin{frame} \frametitle{Interpolation property of Lagrange polynomials}
\[
m \in \mathbb{N} \quad\Rightarrow\quad L^{(N)}_n(m) = \left\{
\begin{array}{ll}
1 & \mbox{if $n=m$}\\
0 & \mbox{if $n \neq m$}
\end{array}\right. \qquad\qquad -N \leq n,m \leq N
\]
\end{frame}
\begin{frame} \frametitle{Lagrange interpolator for the data set}
\[
x_p(t) = \sum_{n = -N}^{N} x[n]L^{(N)}_n(t)
\]
\end{frame}
\begin{frame} \frametitle{Lagrange interpolation}
The Lagrange interpolator {\em is} the unique polynomial interpolation for the data set:
\begin{itemize}
\item a polynomial of degree $2N$ through $2N+1$ points is uniquely defined
\item the Lagrangian interpolator satisfies
\[
x_p(n) = x[n] \qquad \mbox{for $-N \le n \le N$}
\]
since
\[
L^{(N)}_n(m) = \left\{
\begin{array}{ll}
1 & \mbox{if $n=m$}\\
0 & \mbox{if $n \neq m$}
\end{array}\right. \qquad\qquad -N \leq n,m \leq N
\]
\end{itemize}
\end{frame}
% slide showing current interpolator in red and past interpolators in blue
\def\interpolant#1#2#3#4{%
\FPupn\n{#1 1 + 0 trunc}%
\only<#1|handout:#1>{%
\dspTaps{#3 \csname t#4\endcsname}%
\dspFunc[linewidth=0.5pt]{x \csname lp#4\endcsname \csname t#4\endcsname mul}}%
\only<\n-#2|handout:\n-#2>{\dspFunc[linewidth=0.5pt,linecolor=blue!50]{x \csname lp#4\endcsname \csname t#4\endcsname mul}}}%
\def\polyName#1#2{\only<#1|handout:#1>{$x[#2]L^{(2)}_{#2}(t)$}}
\begin{frame}
\frametitle{Lagrange interpolation}
\begin{center}
\begin{figure}
$\vphantom{x[0]L^{(N)}_{0}(t)}$%
\polyName{2}{-2}\polyName{3}{-1}\polyName{4}{0}\polyName{5}{1}\polyName{6}{2}\\
\begin{dspPlot}[sidegap=0]{-2.5,2.5}{-2,3}
\moocStyle
\plotTaps
\begin{dspClip}
\interpolant{2}{7}{-2}{a}%
\interpolant{3}{7}{-1}{b}%
\interpolant{4}{7}{0}{c}%
\interpolant{5}{7}{1}{d}%
\interpolant{6}{7}{2}{e}%
\only<7-8|handout:7-8>{\dspFunc[linewidth=2pt,xmin=-2,xmax=2]{\lagInterp}}%
\end{dspClip}
\end{dspPlot}
\end{figure}
\end{center}
\end{frame}
\begin{frame}
\frametitle{Polynomial interpolation}
key property:
\begin{itemize}
\item maximally smooth (infinitely many continuous derivatives)
\end{itemize}
\vspace{2em}
drawback:
\begin{itemize}
\item interpolation ``machine'' depend on $N$: we need to use a different set of polynomials if the length of the dataset changes
\end{itemize}
\centering
\vspace{2em}
can we find a ``universal'' interpolation machine?
\end{frame}
\begin{frame}
\frametitle{Relaxing the interpolation requirements}
\setbeamercovered{transparent}
\begin{itemize}[<+->]
\item<1-2> decide on $T_s$
\item<1-2> make sure $x(nT_s) = x[n]$
\item<1|handout:0> make sure $x(t)$ is {\em smooth}
\end{itemize}
\end{frame}
\begin{frame} \frametitle{Zero-order interpolation}
\center
\begin{figure}
\begin{dspPlot}[sidegap=0]{-2.5,2.5}{-2,3}
\moocStyle
\plotTaps
\only<2->{%
\psline(-2,\ta)(-1.5,\ta)(-1.5,\tb)(-.5,\tb)(-.5,\tc)(0.5,\tc)(0.5,\td)(1.5,\td)(1.5,\te)(2,\te)}
\end{dspPlot}
\end{figure}
\end{frame}
\begin{frame} \frametitle{Zero-order interpolation}
\begin{itemize}
\item $x_0(t) = x[\, \lfloor t + 0.5 \rfloor \,], \qquad -N \leq t \leq N$
\vspace{1em}
\item $\displaystyle x_0(t) = \sum_{n = -N}^{N}x[n]\rect(t - n)$
\item interpolation kernel: $i_0(t) = \rect(t)$
\item $i_0(t)$: ``zero-order hold''
\item interpolator's support is 1
\item interpolation is not even continuous
\end{itemize}
\end{frame}
\def\interpolant#1#2#3#4{%
\FPupn\n{#1 1 + 0 trunc}%
\only<#1>{%
\dspTaps{#3 \csname t#4\endcsname}%
\dspFunc[linewidth=0.5pt]{x \dspRect{#3}{1} \csname t#4\endcsname mul}}%
\only<\n-#2>{\dspFunc[linewidth=0.5pt,linecolor=blue!50]{x \dspRect{#3}{1} \csname t#4\endcsname mul}}}%
\begin{frame} \frametitle{Zero-order interpolation}
\center
\begin{figure}
\begin{dspPlot}[sidegap=0,height=5cm,width=10cm]{-2.5,2.5}{-2,3}
\moocStyle
\plotTaps
\interpolant{2}{7}{-2}{a}%
\interpolant{3}{7}{-1}{b}%
\interpolant{4}{7}{0}{c}%
\interpolant{5}{7}{1}{d}%
\interpolant{6}{7}{2}{e}%
\only<7->{%
\psline(-2,\ta)(-1.5,\ta)(-1.5,\tb)(-.5,\tb)(-.5,\tc)(0.5,\tc)(0.5,\td)(1.5,\td)(1.5,\te)(2,\te)}
\end{dspPlot}
\end{figure}
\end{frame}
\begin{frame} \frametitle{First-order interpolation}
\center
\begin{figure}
\begin{dspPlot}[sidegap=0,height=5cm,width=10cm]{-2.5,2.5}{-2,3}
\moocStyle
\plotTaps
\psline(-2,\ta)(-1,\tb)(0,\tc)(1,\td)(2,\te)
\end{dspPlot}
\end{figure}
\end{frame}
\begin{frame} \frametitle{First-order interpolation}
\begin{itemize}
\item ``connect the dots'' strategy
\vspace{1em}
\item $\displaystyle x_1(t) = \sum_{n = -N}^{N}x[n]\,i_1(t - n)$
\item interpolation kernel:
\[
i_1(t) = \begin{cases} 1-|t| & |t|\le 1 \\ 0 & \mbox{otherwise} \end{cases}
\]
\item interpolator's support is 2
\item interpolation is continuous but derivative is not
\end{itemize}
\end{frame}
\def\interpolant#1#2#3#4{%
\FPupn\n{#1 1 + 0 trunc}%
\only<#1|handout:#1>{%
\dspTaps{#3 \csname t#4\endcsname}%
\dspFunc[linewidth=0.5pt]{x \dspTri{#3}{1} \csname t#4\endcsname mul}}%
\only<\n-#2|handout:\n-#2>{\dspFunc[linewidth=0.5pt,linecolor=blue!50]{x \dspTri{#3}{1} \csname t#4\endcsname mul}}}%
\begin{frame} \frametitle{First-order interpolation}
\center
\begin{figure}
\begin{dspPlot}[sidegap=0,height=5cm,width=10cm]{-2.5,2.5}{-2,3}
\moocStyle
\plotTaps
\interpolant{2}{7}{-2}{a}%
\interpolant{3}{7}{-1}{b}%
\interpolant{4}{7}{0}{c}%
\interpolant{5}{7}{1}{d}%
\interpolant{6}{7}{2}{e}%
\only<7|handout:7>{\psline(-2,\ta)(-1,\tb)(0,\tc)(1,\td)(2,\te)}
\end{dspPlot}
\end{figure}
\end{frame}
\begin{frame} \frametitle{Third-order interpolation}
\begin{itemize}
\item $\displaystyle x_3(t) = \sum_{n = -N}^{N}x[n]\,i_3(t - n)$
\item interpolation kernel obtained by splicing two cubic polynomials
\item interpolator's support is 4
\item interpolation is continuous up to second derivative
\end{itemize}
\end{frame}
\def\interpolant#1#2#3#4{%
\FPupn\n{#1 1 + 0 trunc}%
\only<#1|handout:#1>{%
\dspTaps{#3 \csname t#4\endcsname}%
\dspFunc[linewidth=0.5pt]{x \cubFun{#3} \csname t#4\endcsname mul}}%
\only<\n-#2|handout:\n-#2>{\dspFunc[linewidth=0.5pt,linecolor=blue!50]{x \cubFun{#3} \csname t#4\endcsname mul}}}%
\begin{frame} \frametitle{Third-order interpolation}
\center
\begin{figure}
\begin{dspPlot}[sidegap=0,height=5cm,width=10cm]{-2.5,2.5}{-2,3}
\moocStyle
\plotTaps
\interpolant{2}{7}{-2}{a}%
\interpolant{3}{7}{-1}{b}%
\interpolant{4}{7}{0}{c}%
\interpolant{5}{7}{1}{d}%
\interpolant{6}{7}{2}{e}%
\only<7|handout:7>{\dspFunc[xmin=-2,xmax=2]{\triInterp}}
\end{dspPlot}
\end{figure}
\end{frame}
\begin{frame} \frametitle{Local interpolation schemes}
\[
\displaystyle x(t) = \sum_{n = -N}^{N}x[n]\,i_c(t - n)
\]
\vspace{1em}
Kernel must satisfy the interpolation property:
\begin{itemize}
\item $i_c(0) = 1$
\item $i_c(m) = 0$ for $m$ a nonzero integer.
\end{itemize}
\end{frame}
\begin{frame} \frametitle{Local interpolators}
\center
\begin{figure}
\begin{dspPlot}[sidegap=0]{-2.8,2.8}{-.5,1.3}
\moocStyle
\only<1|handout:1>{\dspFunc{x \dspRect{0}{1}} \dspText(0,1.5){$i_0(t)$}}
\only<2-|handout:2->{\dspFunc[linecolor=lightgray]{x \dspRect{0}{1}} \dspText(0,1.5){$i_0(t)$}}
\only<2|handout:2>{\dspFunc{x \dspTri{0}{1}} \dspText(0,1.5){$i_1(t)$}}
\only<3-|handout:3->{\dspFunc[linecolor=lightgray]{x \dspTri{0}{1}} \dspText(0,1.5){$i_1(t)$}}
\only<3|handout:3>{\dspFunc{x \cubFun{0}} \dspText(0,1.5){$i_3(t)$}}
\end{dspPlot}
\end{figure}
\end{frame}
%\begin{frame}
% \frametitle{Comparison}
% \center
% \begin{figure}
% \begin{dspPlot}[sidegap=0]{-2.5,2.5}{-2,3}
% \moocStyle
% \plotTaps
% \dspFunc[xmin=-2,xmax=2]{\lagInterp}
% \only<2->{\psline[linecolor=cyan](-2, 1)(-1.5, 1)(-1.5, 2)(-.5,2)(-.5,0.7)%
% (0.5,0.7)(0.5,2.4)(1.5,2.4)(1.5,-1.5)(2,-1.5)}
% \only<3->{\psline[linecolor=orange](-2, 1)(-1, 2)(0,0.7)(1,2.4)(2,-1.5)}
% \only<4->{\dspFunc[linecolor=green,xmin=-2,xmax=2]{\triInterp}}
% \end{dspPlot}
% \end{figure}
%\end{frame}
\begin{frame}
\frametitle{Local interpolation}
key property:
\begin{itemize}
\item same interpolating function independently of $N$
\end{itemize}
\vspace{2em}
drawback:
\begin{itemize}
\item lack of smoothness
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Polynomial interpolation}
key property:
\begin{itemize}
\item maximally smooth (infinitely many continuous derivatives)
\end{itemize}
\vspace{2em}
drawback:
\begin{itemize}
\item interpolation kernels depend on $N$
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{A remarkable result:}
{\Large
\[
\lim_{N\rightarrow\infty} L^{(N)}_n(t) = \sinc\left(t - n\right)
\]
}
\vspace{2em}
\begin{itemize}
\item in other words: $\lim_{N\rightarrow\infty} L^{(N)}_n(t) = L^{(\infty)}_0(t-n)$
\item in the limit, local and global interpolation are the same!
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Sinc interpolation formula}
{\Large
\[
x(t) = \sum_{n = -\infty}^{\infty}x[n]\,\sinc\left(t - n\right)
\]}
\end{frame}
\def\smooth{ 10 div 360 mul dup sin exch dup 2 mul sin exch dup mul 360 div sin add add 2.2 div 0.2 add }
\def\interpolant#1{ \dspSinc{#1}{1} #1 \smooth mul }
\def\interpolant#1#2#3{%
\FPupn\n{#1 1 + 0 trunc}%
\only<#1>{%
\listplot[plotstyle=LineToXAxis, linestyle=solid,%
showpoints=true, dotstyle=*, linewidth=\dspStemWidth,%
dotsize=\dspDotSize]{#3 #3 \smooth #3 #3 \smooth}
\dspFunc[linewidth=0.5pt]{x \dspSinc{#3}{1} #3 \smooth mul}}%
\only<\n-#2>{\dspFunc[linewidth=0.5pt,linecolor=blue!50]{x \dspSinc{#3}{1} #3 \smooth mul}}}%
\begin{frame}
\frametitle{Sinc interpolation}
\begin{center}
\begin{figure}
\begin{dspPlot}[yticks=1,xticks=100,sidegap=0]{-4.5,7.5}{-0.8,1.2}
\moocStyle \SpecialCoor
\dspSignal[linecolor=blue!70]{x \smooth}
\interpolant{2}{6}{0}
\interpolant{3}{6}{1}
\interpolant{4}{6}{2}
\interpolant{5}{6}{3}
\interpolant{6}{6}{4}
\only<7-8>{
\multido{\n=-4+1}{12}{%
\dspFunc[linewidth=0.5pt,linecolor=blue!50]{x \dspSinc{\n}{1} \n \smooth mul}}}
\only<8-9>{\dspFunc{x \smooth}}
\end{dspPlot}
\end{figure}
\end{center}
\end{frame}
% L_0^N(t) = \prod_{k=1}^{N} [t^2/k^2 - 1]
\def\sincApp#1{%
1
1 1 #1 {%
dup mul
x dup mul
exch div
1 exch sub
mul
} for}
\def\plotApp#1#2{%
\only<#1|handout:#1>{\dspFunc{\sincApp{#2}}\dspLegend(-14,1.2){green {$\sinc(t)$} darkred {$L_0^{(#2)}(t)$}}}}
\begin{frame} \frametitle{Convergence: graphical ``proof''}
\begin{align*}
L^{(N)}_n(t) &= \mathop{\prod_{k = -N}}_{k\neq n}^{N}\frac{t - k}{n - k} \\ \\
L_0^{N}(t) &= \mathop{\prod_{k = -N}}_{k\neq 0}^{N}\frac{t - k}{-k} = \mathop{\prod_{k = -N}}^{-1}\frac{t - k}{-k} \mathop{\prod_{k = 1}}^{N}\frac{t - k}{-k} \\
&= \mathop{\prod_{k = 1}}^{N}\frac{t + k}{k} \mathop{\prod_{k = 1}}^{N}\frac{t - k}{-k} \\
& = \mathop{\prod_{k = 1}}^{N}\left(1 - \frac{t^2}{k^2}\right)
\end{align*}
\end{frame}
\begin{frame} \frametitle{Convergence: graphical ``proof''}
\center
\begin{figure}
\begin{dspPlot}[sidegap=0,xout=true]{-15,15}{-.5,1.3}
\moocStyle
\dspFunc[linecolor=green]{x \dspSinc{0}{1}}
\plotApp{2}{100}
\plotApp{3}{200}
\plotApp{4}{300}
\end{dspPlot}
\end{figure}
\end{frame}
\begin{frame} \frametitle{Convergence: mathematical intuition}
\begin{itemize}[<+->]
\item $\sinc(t-n)$ and $L^{(\infty)}_n(t)$ share an infinite number of zeros:
\vspace{1em}
\begin{align*}
\sinc(m-n) &= \delta[m-n] \qquad m,n \in \mathbb{Z} \\
L^{(N)}_n(m) &= \delta[m-n] \qquad m,n \in \mathbb{Z}, \quad -N \le n,m \le N
\end{align*}
\end{itemize}
\end{frame}
%\begin{frame}
% \frametitle{Convergence: Euler's ``proof'' (1748)}
% consider the $N$ roots of unity for $N$ odd:
% \begin{itemize}
% \item $z = 1$
% \item $z = e^{\pm j\frac{2\pi}{N} k}$ for $k = 1, \ldots, (N-1)/2$
% \item (set $\omega_N = 2\pi/N$)
% \end{itemize}
%\end{frame}
%
%\begin{frame}
% \frametitle{Convergence: Euler's ``proof'' (1748)}
% group the complex conjugate roots pairwise in the factors the polynomial $z^N-1$:
% \[
% z^N-1 = (z-1)\prod_{k=1}^{(N-1)/2} (z^2 - 2z\cos(\omega_N k) + 1)
% \]
% \vspace{2em}
% in general:
% \[
% z^N-a^N = (z-a)\prod_{k=1}^{(N-1)/2} (z^2 - 2az\cos(\omega_N k) + a^2).
% \]
%\end{frame}
%
%\begin{frame}
% \frametitle{Convergence: Euler's ``proof'' (1748)}
%first trick: replace $z$ and $a$ by $z = (1+x/N)$ and $a = (1-x/N)$:
%\begin{eqnarray*}
% \lefteqn{\left(1+\frac{x}{N}\right)^N - \left(1-\frac{x}{N}\right)^N =} \nonumber \\
%&=& \frac{4x}{N}\prod_{k=1}^{(N-1)/2} \left(1-\cos(\omega_N k) + \frac{x^2}{N^2}(1+\cos(\omega_N k))\right) \\
%& = & \frac{4x}{N}\prod_{k=1}^{(N-1)/2} (1-\cos(\omega_N k)) \left(1 + \frac{x^2}{N^2}\cdot\frac{1+\cos(\omega_N k)}{1-\cos(\omega_N k)}\right) \\
%& = & Ax\,\prod_{k=1}^{(N-1)/2}\left(1 + \frac{x^2\,(1+\cos(\omega_N k))}{N^2\,(1-\cos(\omega_N k))}\right)
%\end{eqnarray*}
%\end{frame}
\begin{frame}
\frametitle{Convergence: Euler's ``proof'' (1748)}
\centering
very cute (if non-rigorous) proof -- see handout or book for details
\end{frame}
\begin{frame}
\frametitle{Convergence: rigorous proof}
\centering
uses the properties of Fourier series expansions -- see handout or book for details
\end{frame}
\begin{frame}
\frametitle{Sinc interpolation formula for any $T_s$}
{\Large
\[
x(t) = \sum_{n = -\infty}^{\infty}x[n]\,\mbox{sinc}\left(\frac{t - nT_s}{T_s}\right)
\]}
\end{frame}
\end{document}

Event Timeline

c4science · Help