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.
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.[ 1]
Let the n+1 points to be
z
0
,
z
1
,
.
.
.
,
z
n
{\displaystyle z_{0},z_{1},...,z_{n}}
w
0
,
w
1
,
.
.
.
,
w
n
{\displaystyle w_{0},w_{1},...,w_{n}}
In this way, there exists a unique polynomial
p
n
(
z
)
{\displaystyle p_{n}(z)}
p
n
(
z
i
)
=
w
i
,
where
i
=
0
,
1
,
.
.
.
,
n
.
{\displaystyle p_{n}(z_{i})=w_{i},{\text{where }}i=0,1,...,n.}
[ 2] Furthermore, it is possible to simplify the representation of
p
n
(
z
)
{\displaystyle p_{n}(z)}
interpolating polynomials of Lagrange interpolation:
I
k
(
z
)
=
(
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
)
{\displaystyle 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})}}}
[ 3] From the above equation:
I
k
(
z
j
)
=
δ
k
,
j
=
{
0
,
if
k
≠
j
1
,
if
k
=
j
{\displaystyle 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
)
=
∑
k
=
0
n
w
k
I
k
(
z
)
{\displaystyle p_{n}(z)=\sum _{k=0}^{n}w_{k}I_{k}(z)}
p
n
(
z
j
)
=
w
j
,
j
=
0
,
1
,
.
.
.
,
n
{\displaystyle 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
)
{\displaystyle G_{n}(z)=(z-z_{0})(z-z_{1})...(z-z_{n})}
In that way, the Lagrange Interpolation Formula appears:
p
n
(
z
)
=
∑
k
=
0
n
w
k
G
n
(
z
)
(
z
−
z
k
)
G
n
′
(
z
k
)
{\displaystyle p_{n}(z)=\sum _{k=0}^{n}w_{k}{\frac {G_{n}(z)}{(z-z_{k})G'_{n}(z_{k})}}}
[ 4] Note that if
f
(
z
j
)
=
p
n
(
z
j
)
,
j
=
0
,
1
,
.
.
.
,
n
,
{\displaystyle f(z_{j})=p_{n}(z_{j}),j=0,1,...,n,}
f
(
z
)
=
∑
k
=
0
n
f
(
z
k
)
G
n
(
z
)
(
z
−
z
k
)
G
n
′
(
z
k
)
{\displaystyle f(z)=\sum _{k=0}^{n}f(z_{k}){\frac {G_{n}(z)}{(z-z_{k})G'_{n}(z_{k})}}}
Whittaker tried to extend the Lagrange Interpolation from polynomials to entire functions. He showed that it is possible to construct the entire function[ 5]
C
f
(
z
)
=
∑
n
=
−
∞
∞
f
(
a
+
n
W
)
s
i
n
[
π
(
z
−
a
−
n
W
/
W
)
]
[
π
(
z
−
a
−
n
W
/
W
)
]
{\displaystyle 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
)
{\displaystyle f(z)}
z
n
=
a
+
n
W
{\displaystyle z_{n}=a+nW}
C
f
(
z
)
{\displaystyle C_{f}(z)}
C
f
(
z
)
=
∑
n
=
−
∞
∞
f
(
z
n
)
G
(
z
)
G
′
(
z
n
)
(
z
−
z
n
)
,
where
G
(
z
)
=
s
i
n
[
π
(
z
−
a
)
/
W
]
and
z
n
=
a
+
n
W
{\displaystyle 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}
[ 6]
If a function f can be represented in the form
f
(
t
)
=
∫
−
σ
σ
e
j
x
t
g
(
x
)
d
x
(
t
∈
R
)
,
∀
g
∈
L
2
(
−
σ
,
σ
)
,
{\displaystyle 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
)
=
∑
k
=
−
∞
∞
f
(
k
π
σ
)
s
i
n
(
σ
t
−
k
π
)
σ
t
−
k
π
(
t
∈
R
)
{\displaystyle 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} )}
For a sequence
{
t
k
}
k
∈
Z
{\displaystyle \{t_{k}\}_{k\in \mathbb {Z} }}
[ 7]
D
=
s
u
p
k
∈
Z
|
t
k
−
k
|
<
1
4
,
{\displaystyle D={\underset {k\in \mathbb {Z} }{sup}}|t_{k}-k|<{\frac {1}{4}},}
then
f
(
t
)
=
∑
k
=
−
∞
∞
f
(
t
k
)
G
(
t
)
G
′
(
t
k
)
(
t
−
t
k
)
,
∀
f
∈
B
π
2
,
(
t
∈
R
)
,
{\displaystyle 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} ),}
where
G
(
t
)
=
(
t
−
t
0
)
∏
k
=
1
∞
(
1
−
t
t
k
)
(
1
−
t
t
−
k
)
,
{\displaystyle {\text{ where }}G(t)=(t-t_{0})\prod _{k=1}^{\infty }(1-{\frac {t}{t_{k}}})(1-{\frac {t}{t_{-k}}}),}
B
σ
2
.
{\displaystyle B_{\sigma }^{2}.}
Bernstein space
and
f
(
t
)
{\displaystyle {\text{and }}f(t)}
[ 8] 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
^ Marvasti 2001, p. 124.
^ Marvasti 2001, p. 124-125.
^ Marvasti 2001, p. 126.
^ Marvasti 2001, p. 127.
^ Marvasti 2001, p. 132.
^ Marvasti 2001, p. 134.
^ Marvasti 2001, p. 137.
^ Marvasti 2001, p. 138.
F. Marvasti, Nonuniform sampling: Theory and Practice. Plenum Publishers Co., 2001, pp. 123-140. Category:Digital signal processing
![{\displaystyle C_{f}(z)=\sum _{n=-\infty }^{\infty }f(a+nW){\frac {sin[\pi (z-a-nW/W)]}{[\pi (z-a-nW/W)]}}}](/media/api/rest_v1/media/math/render/svg/1181c6dca5fe8400786b0b24c3094b6c6c0a09b0)
![{\displaystyle 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}](/media/api/rest_v1/media/math/render/svg/b3ce59b03f809ef9158c1a6198e9dc30798c8900)
