Nonuniform sampling is a branch of sampling theory involving results related to the
Nyquist–Shannon sampling theorem
The Nyquist–Shannon sampling theorem is a theorem in the field of signal processing which serves as a fundamental bridge between continuous-time signals and discrete-time signals. It establishes a sufficient condition for a sample rate that per ...
. Nonuniform sampling is based on
Lagrange interpolation
In numerical analysis, the Lagrange interpolating polynomial is the unique polynomial of lowest degree that interpolates a given set of data.
Given a data set of coordinate pairs (x_j, y_j) with 0 \leq j \leq k, the x_j are called ''nodes'' an ...
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. 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. 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. In the 2000s, a complete theory was developed
(see the section
Beyond Nyquist below) using
compressed sensing
Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) is a signal processing technique for efficiently acquiring and reconstructing a signal, by finding solutions to underdetermined linear systems. This ...
. In particular, the theory, using signal processing language, is described in this 2009 paper. 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
A spectrum (plural ''spectra'' or ''spectrums'') is a condition that is not limited to a specific set of values but can vary, without gaps, across a continuum. The word was first used scientifically in optics to describe the rainbow of colors ...
. Note that minimum sampling requirements do not necessarily guarantee
numerical stability.
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
, and the ''n'' + 1 values to be
.
In this way, there exists a unique polynomial
such that
:
Furthermore, it is possible to simplify the representation of
using the interpolating polynomials of Lagrange interpolation:
:
From the above equation:
:
As a result,
:
:
To make the polynomial form more useful:
:
In that way, the Lagrange Interpolation Formula appears:
:
Note that if
, then the above formula becomes:
:
Whittaker–Shannon–Kotelnikov (WSK) sampling theorem
Whittaker tried to extend the Lagrange Interpolation from polynomials to
entire functions
In complex analysis, an entire function, also called an integral function, is a complex-valued Function (mathematics), function that is holomorphic function, holomorphic on the whole complex plane. Typical examples of entire functions are polynomia ...
. He showed that it is possible to construct the entire function
:
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:
If a function f can be represented in the form
:
then ''f'' can be reconstructed from its samples as following:
:
Nonuniform sampling
For a sequence
satisfying
:
then
:
where
*
*
is
Bernstein space, and
*
is uniformly convergent on compact sets.
[Marvasti 2001, p. 138.]
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
{{Reflist
*F. Marvasti, Nonuniform sampling: Theory and Practice. Plenum Publishers Co., 2001, pp. 123–140.
Digital signal processing