Jump to content

Nonuniform sampling: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
AnomieBOT (talk | contribs)
m Dating maintenance tags: {{Cleanup}}
Cewbot (talk | contribs)
 
(18 intermediate revisions by 11 users not shown)
Line 1: Line 1:
{{Short description|Generalizations of Nyquist-Shannon sampling theorem for reconstructing signals}}
{{overly detailed|date=July 2012}}
'''Nonuniform sampling''' is a branch of sampling theory involving results related to the [[Nyquist–Shannon sampling theorem]]. Nonuniform sampling is based on [[Lagrange interpolation]] and the relationship between itself and the (uniform) sampling theorem. Nonuniform sampling is a generalisation of the Whittaker–Shannon–Kotelnikov (WSK) sampling theorem.
{{cleanup|reason=too mathematical, lacks a 'so what'|date=July 2012}}
'''Nonuniform sampling''' is a branch of [[Nyquist–Shannon_sampling_theorem|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.


The sampling theory of Shannon can be generalized for the case of nonuniform samples, that is, samples not taken equally spaced in time. The Shannon sampling theory for non-uniform sampling states that a band-limited signal can be perfectly reconstructed from its samples if the average sampling rate satisfies the Nyquist condition.<ref>Nonuniform Sampling, Theory and Practice (ed. F. Marvasti), Kluwer Academic/Plenum Publishers, New York, 2000</ref> Therefore, although uniformly spaced samples may result in easier reconstruction algorithms, it is not a necessary condition for perfect reconstruction.
The sampling theory of Shannon can be generalized for the case of nonuniform samples, that is, samples not taken equally spaced in time. The Shannon sampling theory for non-uniform sampling states that a band-limited signal can be perfectly reconstructed from its samples if the average sampling rate satisfies the Nyquist condition.<ref>Nonuniform Sampling, Theory and Practice (ed. F. Marvasti), Kluwer Academic/Plenum Publishers, New York, 2000</ref> Therefore, although uniformly spaced samples may result in easier reconstruction algorithms, it is not a necessary condition for perfect reconstruction.


The general theory for non-baseband and nonuniform samples was developed in 1967 by [[Henry Landau|Landau]].<ref>H. J. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions,” Acta Math., vol. 117, pp.37–52, Feb. 1967.</ref> He proved that, to paraphrase roughly, the average sampling rate (uniform or otherwise) must be twice the ''occupied'' bandwidth of the signal, assuming it is ''a priori'' known what portion of the spectrum was occupied.
The general theory for non-baseband and nonuniform samples was developed in 1967 by [[Henry Landau]].<ref>H. J. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions,” Acta Math., vol. 117, pp. 37–52, Feb. 1967.</ref> He proved that the average sampling rate (uniform or otherwise) must be twice the ''occupied'' bandwidth of the signal, assuming it is ''a priori'' known what portion of the spectrum was occupied.
In the late 1990s, this work was partially extended to cover signals of when the amount of occupied bandwidth was known, but the actual occupied portion of the spectrum was unknown.<ref>see, e.g., P. Feng, “Universal minimum-rate sampling and spectrum-blind reconstruction for multiband signals,” Ph.D. dissertation, University
In the late 1990s, this work was partially extended to cover signals for which the amount of occupied bandwidth was known, but the actual occupied portion of the spectrum was unknown.<ref>see, e.g., P. Feng, “Universal minimum-rate sampling and spectrum-blind reconstruction for multiband signals,” Ph.D. dissertation, University
of Illinois at Urbana-Champaign, 1997.</ref> In the 2000s, a complete theory was developed
of Illinois at Urbana-Champaign, 1997.</ref> In the 2000s, a complete theory was developed
(see the section [[Nyquist–Shannon_sampling_theorem#Beyond_Nyquist|Beyond Nyquist]] below) using [[compressed sensing]]. In particular, the theory, using signal processing language, is described in this 2009 paper.<ref>[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.154.4255 Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals], Moshe Mishali and Yonina C. Eldar, in '''IEEE Trans. Signal Processing''', March 2009, Vol 57 Issue 3</ref> They show, among other things, that if the frequency locations are unknown, then it is necessary to sample at least at twice the Nyquist criteria; in other words, you must pay at least a factor of 2 for not knowing the location of the [[spectrum]]. Note that minimum sampling requirements do not necessarily guarantee [[Numerical stability|stability]].
(see the section [[Nyquist–Shannon sampling theorem#Sampling below the Nyquist rate under additional restrictions|Beyond Nyquist]] below) using [[compressed sensing]]. In particular, the theory, using signal processing language, is described in this 2009 paper.<ref>[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.154.4255 Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals], Moshe Mishali and Yonina C. Eldar, in '''IEEE Trans. Signal Process.''', March 2009, Vol 57 Issue 3</ref> They show, among other things, that if the frequency locations are unknown, then it is necessary to sample at least at twice the Nyquist criteria; in other words, you must pay at least a factor of 2 for not knowing the location of the [[spectrum]]. Note that minimum sampling requirements do not necessarily guarantee [[numerical stability]].


==Lagrange (Polynomial) Interpolation==
==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.<ref>Marvasti 2001, p. 124.</ref>
For a given function, it is possible to construct a polynomial of degree ''n'' which has the same value with the function at ''n''&nbsp;+&nbsp;1 points.<ref>Marvasti 2001, p. 124.</ref>


Let the n+1 points to be <math>z_0, z_1, ..., z_n</math>, and the n+1 values to be <math>w_0, w_1, ..., w_n</math>.
Let the ''n''&nbsp;+&nbsp;1 points to be <math>z_0, z_1, \ldots , z_n</math>, and the ''n''&nbsp;+&nbsp;1 values to be <math>w_0, w_1, \ldots, w_n</math>.


In this way, there exists a unique polynomial <math>p_n(z)</math> such that
In this way, there exists a unique polynomial <math>p_n(z)</math> such that


:<math>p_n(z_i) = w_i, \text{where }i = 0, 1, ..., n.</math><ref>Marvasti 2001, p. 124-125.</ref>
:<math>p_n(z_i) = w_i, \text{ where }i = 0, 1, \ldots, n.</math><ref>Marvasti 2001, pp. 124–125.</ref>


Furthermore, it is possible to simplify the representation of <math>p_n(z)</math> using the '''interpolating polynomials''' of Lagrange interpolation:
Furthermore, it is possible to simplify the representation of <math>p_n(z)</math> using the '''interpolating polynomials''' of Lagrange interpolation:


:<math>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)}</math><ref>Marvasti 2001, p. 126.</ref>
:<math>I_k(z) = \frac{(z-z_0)(z-z_1)\cdots(z-z_{k-1})(z-z_{k+1})\cdots(z-z_n)}{(z_k-z_0)(z_k-z_1)\cdots(z_k-z_{k-1})(z_k-z_{k+1})\cdots(z_k-z_n)}</math><ref>Marvasti 2001, p. 126.</ref>


From the above equation:
From the above equation:
Line 36: Line 35:
As a result,
As a result,


:<math>p_n(z) = \sum_{k=0}^{n}w_kI_k(z)</math>
:<math>p_n(z) = \sum_{k=0}^n w_kI_k(z)</math>


:<math>p_n(z_j) = w_j, j = 0, 1, ..., n</math>
:<math>p_n(z_j) = w_j, j = 0, 1, \ldots, n</math>


To make the polynomial form more useful:
To make the polynomial form more useful:


:<math>G_n(z) = (z-z_0)(z-z_1)...(z-z_n)</math>
:<math>G_n(z) = (z-z_0)(z-z_1)\cdots(z-z_n)</math>


In that way, the '''Lagrange Interpolation Formula''' appears:
In that way, the '''Lagrange Interpolation Formula''' appears:


:<math>p_n(z) = \sum_{k=0}^{n}w_k\frac{G_n(z)}{(z-z_k)G'_n(z_k)}</math><ref>Marvasti 2001, p. 127.</ref>
:<math>p_n(z) = \sum_{k=0}^n w_k\frac{G_n(z)}{(z-z_k)G'_n(z_k)}</math><ref>Marvasti 2001, p. 127.</ref>


Note that if <math>f(z_j)=p_n(z_j), j=0, 1, ..., n,</math>, then the above formula becomes:
Note that if <math>f(z_j)=p_n(z_j), j=0, 1, \ldots, n,</math>, then the above formula becomes:


:<math>f(z) = \sum_{k=0}^{n}f(z_k)\frac{G_n(z)}{(z-z_k)G'_n(z_k)}</math>
:<math>f(z) = \sum_{k=0}^n f(z_k)\frac{G_n(z)}{(z-z_k)G'_n(z_k)}</math>


==Whittaker-Shannon-Kotel'nikov (WSK) sampling theorem==
==Whittaker–Shannon–Kotelnikov (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<ref>Marvasti 2001, p. 132.</ref>
'''Whittaker''' tried to extend the Lagrange Interpolation from polynomials to [[entire functions]]. He showed that it is possible to construct the entire function<ref>Marvasti 2001, p. 132.</ref>


:<math>C_f(z) = \sum_{n=-\infty}^{\infty}f(a+nW)\frac{sin[\pi(z-a-nW/W)]}{[\pi(z-a-nW/W)]}</math>
:<math>C_f(z) = \sum_{n=-\infty}^\infty f(a+nW)\frac{\sin[\pi(z-a-nW)/W]}{[\pi(z-a-nW)/W]}</math>


which has the same value with <math>f(z)</math> at the points <math>z_n = a + nW</math>
which has the same value with <math>f(z)</math> at the points <math>z_n = a + nW</math>



Moreover, <math>C_f(z)</math> can be written in a similar form of the last equation in previous section:
Moreover, <math>C_f(z)</math> can be written in a similar form of the last equation in previous section:


:<math>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</math>
:<math>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-z_n)/W]\text{ and }z_n=a+nW</math>


When ''a''&nbsp;=&nbsp;0 and ''W''&nbsp;=&nbsp;1, then the above equation becomes almost the same as WSK theorem:<ref>Marvasti 2001, p. 134.</ref>

When a=0 and W=1, then the above equation becomes almost the same as WSK theorem:<ref>Marvasti 2001, p. 134.</ref>


If a function f can be represented in the form
If a function f can be represented in the form
:<math>f(t) = \int_{-\sigma}^{\sigma}e^{jxt}g(x)\, dx \qquad (t\in \mathbb{R}), \qquad \forall g\in L^2(-\sigma,\sigma),</math>
:<math>f(t) = \int_{-\sigma}^\sigma e^{jxt}g(x)\, dx \qquad (t\in \mathbb{R}), \qquad \forall g\in L^2(-\sigma,\sigma),</math>


then f can be reconstructed from its samples as following:
then ''f'' can be reconstructed from its samples as following:


:<math>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})</math>
:<math>f(t) = \sum_{k=-\infty}^\infty f\left(\frac{k\pi}{\sigma}\right)\frac{\sin(\sigma t-k\pi)}{\sigma t-k\pi} \qquad (t\in \mathbb{R})</math>


==Nonuniform Sampling==
==Nonuniform sampling==
For a sequence <math>\{t_k\}_{k\in \mathbb{Z}}</math> satisfying<ref>Marvasti 2001, p. 137.</ref>
For a sequence <math>\{t_k\}_{k\in \mathbb{Z}}</math> satisfying<ref>Marvasti 2001, p. 137.</ref>
:<math>D=\underset{k\in\mathbb{Z}}{sup}|t_k-k|<\frac{1}{4},</math>
:<math>D=\sup_{k\in\mathbb{Z}}|t_k-k|<\frac{1}{4},</math>


then
then
:<math>f(t) = \sum_{k=-\infty}^{\infty}f(t_k)\frac{G(t)}{G'(t_k)(t-t_k)},\qquad \forall f\in B^2_\pi,\qquad (t\in \mathbb{R}),</math>
:<math>f(t) = \sum_{k=-\infty}^\infty f(t_k)\frac{G(t)}{G'(t_k)(t-t_k)},\qquad \forall{}f\in B^2_\pi,\qquad (t\in \mathbb{R}),</math>
where
*<math>\textstyle G(t)=(t-t_0)\prod_{k=1}^\infty \left(1-\frac{t}{t_k}\right)\left(1-\frac{t}{t_{-k}}\right),</math>
*<math>B^2_\sigma</math> is [[Bernstein space]], and
*<math>f(t)</math> is uniformly convergent on compact sets.<ref>Marvasti 2001, p. 138.</ref>


The above is called the 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.
:<math>\text{ where }G(t)=(t-t_0)\prod_{k=1}^{\infty}(1-\frac{t}{t_k})(1-\frac{t}{t_{-k}}),</math> and <math>B^2_\sigma.</math> is '''Bernstein space'''

:<math>\text{and }f(t)</math> is uniformly convergent on compact sets.<ref>Marvasti 2001, p. 138.</ref>

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==
==References==
{{Reflist}}
{{Reflist}}
*F. Marvasti, Nonuniform sampling: Theory and Practice. Plenum Publishers Co., 2001, pp. 123-140.
*F. Marvasti, Nonuniform sampling: Theory and Practice. Plenum Publishers Co., 2001, pp.&nbsp;123–140.


[[Category:Digital signal processing]]
[[Category:Digital signal processing]]

{{maths-stub}}

Latest revision as of 02:04, 7 August 2023

Nonuniform sampling is a branch of sampling theory involving results related to the Nyquist–Shannon sampling theorem. Nonuniform sampling is based on Lagrange interpolation and the relationship between itself and the (uniform) sampling theorem. Nonuniform sampling is a generalisation of the Whittaker–Shannon–Kotelnikov (WSK) sampling theorem.

The sampling theory of Shannon can be generalized for the case of nonuniform samples, that is, samples not taken equally spaced in time. The Shannon sampling theory for non-uniform sampling states that a band-limited signal can be perfectly reconstructed from its samples if the average sampling rate satisfies the Nyquist condition.[1] Therefore, although uniformly spaced samples may result in easier reconstruction algorithms, it is not a necessary condition for perfect reconstruction.

The general theory for non-baseband and nonuniform samples was developed in 1967 by Henry Landau.[2] He proved that the average sampling rate (uniform or otherwise) must be twice the occupied bandwidth of the signal, assuming it is a priori known what portion of the spectrum was occupied. In the late 1990s, this work was partially extended to cover signals for which the amount of occupied bandwidth was known, but the actual occupied portion of the spectrum was unknown.[3] In the 2000s, a complete theory was developed (see the section Beyond Nyquist below) using compressed sensing. In particular, the theory, using signal processing language, is described in this 2009 paper.[4] They show, among other things, that if the frequency locations are unknown, then it is necessary to sample at least at twice the Nyquist criteria; in other words, you must pay at least a factor of 2 for not knowing the location of the spectrum. Note that minimum sampling requirements do not necessarily guarantee numerical stability.

Lagrange (polynomial) interpolation

[edit]

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.[5]

Let the n + 1 points to be , and the n + 1 values to be .

In this way, there exists a unique polynomial such that

[6]

Furthermore, it is possible to simplify the representation of using the interpolating polynomials of Lagrange interpolation:

[7]

From the above equation:

As a result,

To make the polynomial form more useful:

In that way, the Lagrange Interpolation Formula appears:

[8]

Note that if , then the above formula becomes:

Whittaker–Shannon–Kotelnikov (WSK) sampling theorem

[edit]

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

which has the same value with at the points

Moreover, can be written in a similar form of the last equation in previous section:

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

If a function f can be represented in the form

then f can be reconstructed from its samples as following:

Nonuniform sampling

[edit]

For a sequence satisfying[11]

then

where

  • is Bernstein space, and
  • is uniformly convergent on compact sets.[12]

The above is called the 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

[edit]
  1. ^ Nonuniform Sampling, Theory and Practice (ed. F. Marvasti), Kluwer Academic/Plenum Publishers, New York, 2000
  2. ^ H. J. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions,” Acta Math., vol. 117, pp. 37–52, Feb. 1967.
  3. ^ see, e.g., P. Feng, “Universal minimum-rate sampling and spectrum-blind reconstruction for multiband signals,” Ph.D. dissertation, University of Illinois at Urbana-Champaign, 1997.
  4. ^ Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals, Moshe Mishali and Yonina C. Eldar, in IEEE Trans. Signal Process., March 2009, Vol 57 Issue 3
  5. ^ Marvasti 2001, p. 124.
  6. ^ Marvasti 2001, pp. 124–125.
  7. ^ Marvasti 2001, p. 126.
  8. ^ Marvasti 2001, p. 127.
  9. ^ Marvasti 2001, p. 132.
  10. ^ Marvasti 2001, p. 134.
  11. ^ Marvasti 2001, p. 137.
  12. ^ Marvasti 2001, p. 138.
  • F. Marvasti, Nonuniform sampling: Theory and Practice. Plenum Publishers Co., 2001, pp. 123–140.