Nonuniform sampling

Nonuniform sampling is a branch of Nyquist–Shannon_sampling theorem. Nonuniform sampling is based on Lagrange Interpolation and the relationship between itself and (uniform) sampling theorem. Nonuniform sampling is a generalisation of the Whittaker-Shannon-Kotel (WSK) sampling theorem.

Lagrange (Polynomial) Interpolation

For a given function, it is possible to construct a polynomial of degree n which has the same value with the function at n+1 points.

Let the n+1 points to be $z_{0},z_{1},...,z_{n}$, and the n+1 values to be $w_{0},w_{1},...,w_{n}$.

In this way, there exists a unique polynomial $p_{n}(z)$ such that

$p_{n}(z_{i})=w_{i},{\text{where }}i=0,1,...,n.$

Furthermore, it is possible to simplify the representation of $p_{n}(z)$ using the interpolating polynomials of Lagrange interpolation:

$I_{k}(z)={\frac {(z-z_{0})(z-z_{1})...(z-z_{k-1})(z-z_{k+1})...(z-z_{n})}{(z_{k}-z_{0})(z_{k}-z_{1})...(z_{k}-z_{k-1})(z_{k}-z_{k+1})...(z_{k}-z_{n})}}$

From the above equation:

$I_{k}(z_{j})=\delta _{k,j}={\begin{cases}0,&{\text{if }}k\neq j\\1,&{\text{if }}k=j\end{cases}}$

As a result,

$p_{n}(z)=\sum _{k=0}^{n}w_{k}I_{k}(z)$

$p_{n}(z_{j})=w_{j},j=0,1,...,n$

To make the polynomial form more useful:

$G_{n}(z)=(z-z_{0})(z-z_{1})...(z-z_{n})$

In that way, the Lagrange Interpolation Formula appears:

$p_{n}(z)=\sum _{k=0}^{n}w_{k}{\frac {G_{n}(z)}{(z-z_{k})G'_{n}(z_{k})}}$

Note that if $f(z_{j})=p_{n}(z_{j}),j=0,1,...,n,$, then the above formula becomes:

$f(z)=\sum _{k=0}^{n}f(z_{k}){\frac {G_{n}(z)}{(z-z_{k})G'_{n}(z_{k})}}$

Whittaker-Shannon-Kotel'nikov (WSK) sampling theorem

Whittaker tried to extend the Lagrange Interpolation from polynomials to entire functions. He showed that it is possible to construct the entire function

$C_{f}(z)=\sum _{n=-\infty }^{\infty }f(a+nW){\frac {sin[\pi (z-a-nW/W)]}{[\pi (z-a-nW/W)]}}$

which has the same value with $f(z)$ at the points $z_{n}=a+nW$

Moreover, $C_{f}(z)$ can be written in a similar form of the last equation in previous section:

$C_{f}(z)=\sum _{n=-\infty }^{\infty }f(z_{n}){\frac {G(z)}{G'(z_{n})(z-z_{n})}},{\text{ where }}G(z)=sin[\pi (z-a)/W]{\text{ and }}z_{n}=a+nW$

When a=0 and W=1, then the above equation becomes almost the same as WSK theorem:

If a function f can be represented in the form

$f(t)=\int _{-\sigma }^{\sigma }e^{jxt}g(x)\,dx\qquad (t\in \mathbb {R} ),\qquad \forall g\in L^{2}(-\sigma ,\sigma ),$

then f can be reconstructed from its samples as following:

$f(t)=\sum _{k=-\infty }^{\infty }f({\frac {k\pi }{\sigma }}){\frac {sin(\sigma t-k\pi )}{\sigma t-k\pi }}\qquad (t\in \mathbb {R} )$

Nonuniform Sampling

For a sequence $\{t_{k}\}_{k\in \mathbb {Z} }$ satisfying

$D={\underset {k\in \mathbb {Z} }{sup}}|t_{k}-k|<{\frac {1}{4}},$

then

$f(t)=\sum _{k=-\infty }^{\infty }f(t_{k}){\frac {G(t)}{G'(t_{k})(t-t_{k})}},\qquad \forall f\in B_{\pi }^{2},\qquad (t\in \mathbb {R} ),$

${\text{ where }}G(t)=(t-t_{0})\prod _{k=1}^{\infty }(1-{\frac {t}{t_{k}}})(1-{\frac {t}{t_{-k}}}),$ and $B_{\sigma }^{2}.$ is Bernstein space

${\text{and }}f(t)$ is uniformly convergent on compact sets.

The above is called Paley-Wiener-Levinson Theorem which generalize WSK sampling theorem from uniform samples to non uniform samples. Both of them can reconstruct a band-limited signal from those samples, respectively.

References

• F. Marvasti, Nonuniform sampling: Theory and Practice. Plenum Publishers Co., 2001, pp. 123-140.

Category:Digital signal processing