Abstract: It is known that sampling theory lies at the heart of signal processing devices and communication systems. This study presents an account of the current state of sampling theorem after Shannon’s formulation of the sampling theorem. Our emphasis is on some new tends of sampling theory in recent decade. At first, the problem of vector sampling expansion is argued. Secondly, signal reconstruction from local averages is showed. Thirdly, the issue of sampling theorem in the wavelet subspaces is investigated and some results are given. At last, compressed sampling and its two principles are reviewed.
INTRODUCTION
The sampling theorem plays a crucial role in many fields such as signal processing, image processing and digital communications: it tells us how to convert an analog signal into a sequence of numbers, which can be processed digitally on a computer.
For a band-limited signal f(t) without frequencies higher than Ω, the classical Shannon sampling theorem (Shannon, 1949) provides an exact representation by its uniform samples. Reconstruction is obtained by filtering the samples with a interpolation kernel:
where,
and
The classical Shannon sampling theorem is one of the cornerstones of signal processing and communication theory. It is undoubtedly one of the theoretical works that has had the greatest impact on modern electrical engineering.
However, the assumption that a signal is band-limited, although eminently useful and very elegant, is not always realistic. Note that: (1) Band-limited signals are of infinite duration, but real world signals or images are never exactly band-limited and (2) the sinc function, used to reconstruct a band-limited function from its samples, is of infinite support and decays only as 1/x. Therefore, Shannon's reconstruction formula is rarely used in practice (especially with images) because of the slow decay of the sinc function. While the Shannon sampling theorem is based on band-limited signals, it is natural to investigate other signal classes for which a sampling theorem holds.
In 1980’s, the subject of sampling had reached a very mature state. The research in this area had become very mathematically oriented, with less and less immediate relevance to signal processing and communications. In 1990’s, there has been strong revival of the subject, which was motivated by the intense activity taking place around wavelets (Daubechies, 1990). This led researchers to reexamine some of the foundations of Shannon’s theory and develop more general formulations, many of which turn out to be quite practical from the point of view of implementation.
Recently, a new topic about sampling has received growing attention: that is the emerging field of compressed sampling (Donoho, 2006). In the last section, this important area is briefly touched on.
So far, there exist some excellent reviews. For example, Jerri (1977) gave a comprehensive overview of sampling up to the mid-1970’s. Unser (2000) emphasized on regular sampling, where the grid is uniform. In 2009, beyond band-limited sampling (Eldar and Michaeli, 2009) was discussed.
In this survey, the several extensions of the Shannon sampling theorem is presented, that have been developed primarily in the past decades. Our emphasis is on some new tends of sampling theory in recent decade.
VECTOR SAMPLING EXPANSION
In many applications, a signal is measured through a number of channels and then sampled. An obvious question of interest is: for the several channels, what would be the most beneficial sampling policy while maintaining the ability to reconstruct the observed signal? By beneficial, we mean the least possible sampling rates. This is the problem of Vector Sampling Expansion (VSE). VSE systems appear in many applications. For example, in a wireless communication environment or radar environment, there exist N transmitters, emitting N different signals, which are then received by M antennas. A question of great interest is how to sample the received signals at the total minimal rate that will enable unique reconstruction and how to attain the most noise-robust system.
A cornerstone result in this area is the so-called Generalized Sampling Expansion (GSE) due to Papoulis (1977). Papoulis has shown that a band-limited signal f(t) of finite energy, passing through LTI systems and generating M responses gk(t), k = 1,...,M, can be uniquely reconstructed, under some conditions on the M filters, from the samples of the output signals gk(nT), sampled 1/M at the Nyquist rate. Such a sampling scheme might be useful when the original signal is not directly accessible, but some processed versions of it exist and may be used for reconstruction.
More recently, in their study (Seidner et al., 1998; Seidner and Feder, 2000), authors provided a generalization of the GSE. They considered N band-limited signals (or a signal vector) with finite energy f(t)T = [f1(t),f2(t),...,fN(t)], all having the same bandwidth that pass through a Multi-Input Multi-Output (MIMO) LTI system to yield M output signals g(t)T = [g1(t),g2(t),...,gN(t)], where M≥N. The result that the N input signals can be reconstructed from samples of the M output signals was proved. When all the output signals are uniformly sampled at the same rate, reconstruction of f(t) is possible, with some conditions on the MIMO system, if and only if M/N is an integer. Reconstruction is also possible when M/N is not an integer but in this case either the signals are not sampled uniformly, or the sampling rate is not equal for all the output signals.
Furthermore, the study (Feuer et al., 2006) discussed the case of equal uniform sampling of all output channels and found the reconstruction formula and discussed the stochastic signal case. The case that each output signal is sampled non-uniformly was considered. At last, uniform sampling at different sampling rates for different output signals and periodic non-uniform sampling were discussed. And the two possibilities of all output entries sampled at the same rate and at different rates were treated. Through some examples, the value of recognizing the different bandwidths at the input was highlighted.
In the study (Shang et al., 2007; Kim and Kwon, 2008), vector sampling expansions on general finitely generated shift-invariant subspaces was studied. Necessary and sufficient conditions for a vector sampling theorem to hold are given. Several examples to illustrate the main result are presented. In the study, authors (Liu et al., 2008) firstly introduced vector-valued multiresolution analysis and orthogonal vector-valued wavelet. Then, they considered the existence of cardinal compactly supported orthogonal vector-valued wavelet system and described the compactly supported orthogonal cardinal vector-valued scaling function and orthogonal vector-valued wavelet. Thus, vector sampling expansions in the vector-valued wavelet subspace were obtained.
SIGNAL RECONSTRUCTION FROM LOCAL AVERAGES
For physical reasons, e.g., the inertia of the measurement apparatus, it is difficult to measure the value of a signal precisely at time x. In practice, only a local average near x can be measured. Specifically, let {xk} be an increasing real sequence such that xk→±∞ as k→±∞ , then, the sampled values will be ⟨f, μk⟩ for some collection of averaging functions {μk} satisfying that:
It is clear that from local averages one should obtain at least a good approximation of the original signal if δ is small enough. Wiley (1978) studied the approximation error when local averages are used as sampled values. Furthermore, Grochenig (1992) proved that if :
then, every band-limited function f∈BΩ: {f : f∈L2)
and supp
Later, Feichtinger and Grochenig (1994) proved that if:
then, every f∈BΩ is uniquely determined by:
where, yk = (xk+1+xk)/2. Here, the sampling rate is decreased while averaging functions are fixed with respect to sampling points.
Sun and Zhou (2002) showed that if 0<xk+1+xk≤β
for some constant 0<β<π/Ω and the support length of μk
is small enough, then every f∈BΩ is uniquely determined
by its local averages
If μk(x) are taken to be translations of a generating function μk(x) = μ(x-xk) for some averaging function μ(x), then the average sampling procedure can be viewed as prefiltering. Sun and Zhou (2003) studied the reconstruction of functions in shift invariant subspaces from local averages with equally spaced sampling points and symmetric averaging functions, i.e., the averaging function μk(x) is symmetric with respect to x = xk and non-increasing on [xk,xk+δ/2]. They presented an average sampling theorem and gave explicit error bounds for the aliasing error and the truncation error.
SAMPLING THEOREM IN WAVELET SUBSPACE
Wavelet theory (Daubechies, 1992) has been studied extensively in both theory and applications since, 1980's. One of the basic advantages of wavelets is that an even can be simultaneously described in the frequency domain as well as in the time domain. This feature permits a multiresolution analysis of data with different behavior on different scales. The main advantage of wavelets is their time-frequency localization property. Many signals can be efficiently represented by wavelets.
In the classical Shannon sampling theorem, the interpolant is the modulated sinc function. The sinc function also plays a role of a special scaling function from a multiresolution analysis point of view. Therefore, the sampling theorem was naturally extended to wavelet subspaces by Walter (1992). From then on, there exist many surprising results.
Walter (1992) gave a sampling theorem describing the reconstruction of a function f(t) in a scaling space from its samples. He showed that, if a signal f(t) satisfies:
| (1) |
| (2) |
Then, there exists s(t)∈V0 such that, for any function f(t)∈V0, the equality:
holds, where,
This theorem does not require that the scaling function be cardinal, i.e., the interpolant is generally not the same function as the scaling function. Later, Janssen (1993) extended Walter's results to the uniform non-integer sampling which is also called shift sampling by Zak transform.
Xia and Zhang (1993) considered the case in which φ(x)
is an orthogonal scaling function satisfying
holds.
Because of the importance in analyzing and detecting transients and singularities, people are particularly interested in sampling theorems for signals of finite duration and for which the reconstruction function is also of compact support. To this end, note that the sinc function is one of the primary examples of an orthogonal scaling function from the theory of wavelet bases. The sinc function generates a scaling space in the context of multiresolution analysis and serves as the interpolant in the context of the sampling theorem. The question naturally arises: are there orthogonal wavelet bases for which the scaling function both (1) supports a sampling theorem in the same fashion and (2) is of compact support? Unfortunately, the Haar scaling function is the only orthogonal scaling function of compact support for which a Shannon-like sampling property holds (Xia and Zhang, 1993). Thus, people turn to search for the cardinal scaling function which has exponential decay.
Wu et al. (2007) gave some new characterizations about COSF. At first, that there is a relation between the lowpass filter coefficient and wavelet's samples in its integer points was deduced. Secondly, the symmetry property of COSF was discussed. Thirdly, a family of COSF with exponential decay and higher approximation order was constructed. Compared with existing examples, new construction has more freedom and flexibility. The main result is following:
Theorem 2: Let, the scaling function φ(x) and {hk}k∈Z satisfy:
and
Then, a scaling function φ(x) is a COSF if and only if any wavelet function ψ(x) satisfies ψ(k) = g2k, k∈Z
Furthermore, Wu et al. (2009, 2010) generalized above results to the cases of M-band wavelet and higher dimension, respectively. Recently, Li and Guochang (2009) classified the orthogonal interpolating balanced multiwavelets and obtained the sampling theorem in the multiwavelet subspaces.
COMPRESSIVE SAMPLING
Conventional approaches to sampling signals or images follow Shannon’s sampling theorem and its extensions. In fact, this principle underlies nearly all signal acquisition protocols used in consumer audio and visual electronics, medical imaging devices, radio receivers and so on.
In the last several years, an alternative theory of compressive sampling (CS) (Candes and Tao, 2006; Candes et al., 2006a; Tropp and Gilbert, 2007) shows that super-resolved signals and images can be reconstructed from far fewer data than what is usually considered necessary. Further, CS is a very simple and efficient signal acquisition protocol which samples at a low rate and later uses computational power for reconstruction from what appears to be an incomplete set of measurements.
In fact, compressive sampling suggests ways to economically translate analog data into already compressed digital form (Candes and Romberg, 2007; Candes et al., 2006b). Everybody knows that because typical signals have some structure, they can be compressed efficiently without much perceptual loss. This raises a fundamental question: because most signals are compressible, why spend so much effort acquiring all the data when we know that most of it will be discarded? Wouldn’t it be possible to acquire the data in already compressed form so that one does not need to throw away anything? To make this possible, CS relies on two principles: Sparsity, which pertains to the signals of interest and incoherence, which pertains to the sensing modality.
In the following, the notations of sparsity and incoherence are explained in detail.
Sparsity expresses the idea that the information rate of a continuous time signal may be much smaller than suggested by its bandwidth. More precisely, CS exploits the fact that many natural signals are sparse or compressible in the sense that they have concise representations when expressed in the proper basis.
Incoherence extends the duality between time and frequency and expresses the idea that objects having a sparse representation must be spread out in the domain which they are acquired. Put differently, incoherence says that unlike the signal of interest, the sampling/sensing waveforms have an extremely dense representation. The crucial observation is that one can design efficient sensing or sampling protocols that capture the useful information content embedded in a sparse signal and condense it into a small amount of data. What is most remarkable about these sampling protocols is that they allow a sensor to very efficiently capture the information in a sparse signal without trying to comprehend that signal.
ACKNOWLEDGMENT
The authors would like to express their gratitude to editor and the referee for their valuable comments and suggestions that lead to a significant improvement of our manuscript.