Universidade de Aveiro
Paulo J. S. G. Ferreira

Sampling and reconstruction

P. L. Butzer, M. M. Dodson, P. J. S. G. Ferreira, J. R. Higgins, G. Schmeisser and R. L. Stens. Seven pivotal theorems of Fourier analysis, signal analysis, numerical analysis and number theory: their interconnections. Bulletin of Mathematical Sciences, vol. 4, no. 3, pp. 481-525, Dec. 2014.

bms.jpg The present paper deals mainly with seven fundamental theorems of mathematical analysis, numerical analysis, and number theory, namely the generalized Parseval decomposition formula (GPDF), introduced 15 years ago, the well-known approximate sampling theorem (ASF), the new approximate reproducing kernel theorem, the basic Poisson summation formula, already known to Gauss, a newer version of the GPDF having a structure similar to that of the Poisson summation formula, namely, the Parseval decomposition–Poisson summation formula, the functional equation of Riemann's zeta function, as well as the Euler–Maclaurin summation formula. It will in fact be shown that these seven theorems are all equivalent to one another, in the sense that each is a corollary of the others. Since these theorems can all be deduced from each other, one of them has to be proven independently in order to verify all. It is convenient to choose the ASF, introduced in 1963. The epilogue treats possible extensions to the more general contexts of reproducing kernel theory and of abstract harmonic analysis, using locally compact abelian groups. This paper is expository in the sense that it treats a number of mathematical theorems, their interconnections, their equivalence to one another. On the other hand, the proofs of the many intricate interconnections among these theorems are new in their essential steps and conclusions.

Paulo J. S. G. Ferreira and Rowland Higgins. The establishment of sampling as a scientific principle — a striking case of multiple discovery. Notices of the AMS, vol. 58, no. 10, pp. 1446-1450, Nov. 2011.

nams.png During the period 1928-1949, several engineers contributed to the establishment of a sampling principle. They did this virtually independently of each other in the context of communications theory and practice. The question addressed in this paper is the following: Why was the sampling principle the subject of multiple discovery, spread over three continents? The search for an answer led us to investigate the work of Kelvin and Stokes on telegraphy and the emergence of the concept of bandwidth limitation. Kelvin's law of squares and the challenges of communications engineering played a role in the matter, but the full story also involves people like Nyquist, Kotel'nikov, Raabe, Shannon and Someya. Ironically, "the crowding of the ether" that worried Kotel'nikov and others in the 1940s is a problem as pressing today as it was 70 years ago. Telecommunications, as a source of problems of theoretical interest and practical importance, has not yet been exhausted.

Moacir P. Ponti-Jr., Nelson D. A. Mascarenhas, Paulo J. S. G. Ferreira and Claudio A. T. Suazo. Three-dimensional Noisy Image Restoration using Filtered Extrapolation and Deconvolution. Signal, Image and Video Processing, vol. 7, no. 1, pp. 1-10, Jan. 2013.

sivp.jpg The problem of restoration in fluorescence microscopy involves at the same time with blurring and photon noise. Their combined effects corrupt the image by inserting elements that do not belong to the real object and distort the contrast. This hinders the possibility of using the images for visualisation, recognition, and analysis using the three-dimensional data. The algorithms developed to restore the lost frequencies and perform band extrapolation, in general, assume noiseless data or additive noise. This paper presents a restoration approach through band extrapolation and deconvolution that deals more effectively with the noise. It combines a constrained extrapolation algorithm and the Richardson-Lucy iterative algorithm. The results are compared with those obtained using the original Richardson-Lucy algorithm and also regularised by Total Variation. The extrapolation of frequencies is also analysed, for both synthetic and real images. The method improves the results since it yields better signal-to-noise ratio and quality index values, performs band extrapolation, and allows a better visualization of the 3D structures.

P. L. Butzer, P. J. S. G. Ferreira, J. R. Higgins, G. Schmeisser and R. L. Stens. The Summation Formulae of Euler-Maclaurin, Abel-Plana, Poisson, and their Interconnections with the Approximate Sampling Formula of Signal Analysis. Results in Mathematics, vol. 59, no. 3-4, pp. 359-400, May 2011.

rm.jpg This paper is concerned with the two summation formulae of Euler-Maclaurin (EMSF) and Abel-Plana (APSF) of numerical analysis, that of Poisson (PSF) of Fourier analysis, and the approximate sampling formula (ASF) of signal analysis. It is shown that these four fundamental propositions are all equivalent, in the sense that each is a corollary of any of the others. For this purpose ten of the twelve possible implications are established. Four of these, namely the implications of the groupings APSF ← ASF → EMSF ↔ PSF are shown here for the first time. The proofs of the others, which are already known and were established by three of the above authors, have been adapted to the present setting. In this unified exposition the use of powerful methods of proof has been avoided as far as possible, in order that the implications may stand in a clear light and not be overwhelmed by external factors. Finally, the four propositions of this paper are brought into connection with four propositions of mathematical analysis for bandlimited functions, including the Whittaker-Kotel’nikov-Shannon sampling theorem. In conclusion, all eight propositions are equivalent to another. Finally, the first three summation formulae are interpreted as quadrature formulae.

P. L. Butzer, P. J. S. G. Ferreira, J. R. Higgins, S. Saitoh, G. Schmeisser and R. L. Stens. Interpolation and sampling: E.T. Whittaker, K. Ogura and their followers. The Journal of Fourier Analysis and Applications, vol. 17, no. 2, pp. 320-354, Apr. 2011.

jfaa.jpg The classical sampling theorem has often been attributed to E.T. Whittaker, but this attribution is not strictly valid. One must carefully distinguish, for example, between the concepts of sampling and of interpolation, and we find that Whittaker worked in interpolation theory, not sampling theory. Again, it has been said that K. Ogura was the first to give a properly rigorous proof of the sampling theorem. We find that he only indicated where the method of proof could be found; we identify what is, in all probability, the proof he had in mind. Ogura states his sampling theorem as a "converse of Whittaker’s theorem", but identifies an error in Whittaker’s work. In order to study these matters in detail we find it necessary to make a complete review of the famous 1915 paper of E.T. Whittaker, and two not so well known papers of Ogura dating from 1920. Since the life and work of Ogura is practically unknown outside Japan, and there he is usually regarded only as an educationalist, we present a detailed overview together with a list of some 70 papers of his which we had to compile. K. Ogura is presented in the setting of mathematics in Japan of the early 20th century. Finally, because many engineering textbooks refer to Whittaker as a source for the sampling theorem, we make a very brief review of some early introductions of sampling methods in the engineering context, mentioning H. Nyquist, K. Küpfmüller, V. Kotel’nikov, H. Raabe, C.E. Shannon and I. Someya.

P. L. Butzer, M. M. Dodson, P. J. S. G. Ferreira, J. R. Higgins, O. Lange, P. Seidler and R. L. Stens. Multiplex signal transmission and the development of sampling techniques: the work of Herbert Raabe in contrast to that of Claude Shannon. Applicable Analysis, vol. 90, no. 3, pp. 643-688, Mar. 2011.

aa.jpg This article discusses the interplay between multiplex signal transmission in telegraphy and telephony, and sampling methods. It emphasizes the works of Herbert Raabe (1909-2004) and Claude Shannon (1916-2001) and the context in which they occurred. Attention is given to the role that the exceptional research atmosphere in Berlin during the 1920s and early 1930s played in the development of some of the ideas underlying these works, first in Germany and then in the USA, as some of the protagonists moved there. Raabe's thesis, published in 1939, describes and analyses a time-division multiplex system for telephony. In order to build his working prototype, Raabe had to develop the theoretical tools he needed and achieved a thorough understanding of sampling, including sampling with pulses of finite duration and sampling of low-pass and band-pass signals. His condition for reconstruction was known as 'Raabe's condition' in the German literature of the time. On the other hand, Shannon's works of 1948 and 1949 contain the classical sampling theorem, but go much further and lay down the abstract theoretical framework that underlies much of the modern digital communications. It is interesting to compare Raabe's very practical approach with Shannon's abstract work: Raabe independently developed his methods to the degree he needed, but his main purpose was to build a working prototype. Shannon, on the other hand, approached sampling independently of practical constraints, as part of information theory - which became tremendously influential.

P. L. Butzer, P. J. S. G. Ferreira, J. R. Higgins, G. Schmeisser and R. Stens. The Sampling Theorem, Poisson's Summation Formula, General Parseval Formula, Reproducing Kernel Formula and the Paley-Wiener Theorem for Bandlimited Signals — Their Interconnections. Applicable Analysis, vol. 90, no. 3, pp. 431-461, Mar. 2011.

aa.jpg It is shown that the Whittaker-Kotel’nikov-Shannon sampling theorem of signal analysis, which plays the central role in this article, as well as (a particular case) of Poisson’s summation formula, the general Parseval formula and the reproducing kernel formula, are all equivalent to one another in the case of bandlimited functions. Here equivalent is meant in the sense that each is a corollary of the other. Further, the sampling theorem is equivalent to the Valiron-Tschakaloff sampling formula as well as to the Paley–Wiener theorem of Fourier analysis. An independent proof of the Valiron formula is provided. Many of the equivalences mentioned are new results. Although the above theorems are equivalent amongst themselves, it turns out that not only the sampling theorem but also Poisson's formula are in a certain sense the 'strongest' assertions of the six well-known, basic theorems under discussion.

María Elena Domínguez-Jiménez and Paulo J. S. G. Ferreira. Some extremal properties of Daubechies filters and other orthonormal filters. Signal Processing, vol. 91, no. 1, pp. 85-89, Jan. 2011.

sp.png New extremal properties of Daubechies 4-tap orthonormal filters are given: they maximize a certain functional, have the largest gain in (0,pi), and allow maximum energy compaction in (0,pi/2). These properties do not carry over to Daubechies filters of arbitrary length. They complement what is known about Daubechies filters and highlight the specific role of the 4-tap filter. Moreover, we demonstrate that these properties cannot be fulfilled by any other orthonormal lowpass filter, regardless of its length.

P. L. Butzer, M. M. Dodson, P. J. S. G. Ferreira, J. R. Higgins, O. Lange and P. Seidler. Herbert Raabe's work in multiplex signal transmission and his development of sampling methods. Signal Processing, vol. 90, no. 5, pp. 1436-1455, May 2010.

sp.png This paper discusses the work of Herbert Raabe (1909-2004) and its significance in terms of sampling. Raabe's thesis of 1939 is a milestone in the development of sampling: Raabe built and analysed the first time-division multiplex system for telephony, a task that required of him a thorough understanding of sampling, including sampling with pulses of finite duration and sampling of low-pass and band-pass signals. This paper discusses his approach, its significance from the viewpoint of sampling, the generality of its conclusions, and also the milieu that lead to his remarkable achievements: the exceptional research climate existing in Berlin at the time Raabe worked. The paper also examines the connection between Raabe's condition, the work of Harry Nyquist on telegraphy and the so-called Nyquist rate. An English translation of the sections of Raabe's dissertation more closely related to sampling is included as an appendix.

Manuel J. C. S. Reis, Paulo J. S. G. Ferreira and Salviano F. S. P. Soares. Linear Combinations of B-Splines as Generating Functions for Signal Approximation. Digital Signal Processing, vol. 15, no. 3, pp. 226-236, May 2005.

dsp.png The advantages of B-splines for signal representation are well known. This paper stresses a fact that seems to be less well known, namely, the possibility of using linear combinations of B-splines to obtain representations that are more stable than the usual ones. We give the best possible Riesz bounds for these linear combinations and calculate their duals, in a generalized sampling context.

To put this into perspective, consider an approximation scheme based on a certain kernel function. Often, it would lead to a Riesz sequence or a Riesz basis. Riesz bases are a generalization of orthonormal bases, and can be regarded as the result of applying a bounded invertible operator to the elements of an orthonormal basis. A Riesz sequence, on the other hand is an ``incomplete basis'', as it is merely a Riesz basis for the closed linear span of the set of functions under consideration.

The numerical stability of such representations is important in practice, as it dictates the magnitude of the adverse effects due to noisy data. The stability of Riesz bases and Riesz sequences can be measured by looking at the size of their Riesz bounds. Orthonormal bases are perfect from the viewpoint of numerical stability, and their Riesz bounds are both equal to unity. As the ratio of the upper to the lower bound increases, the numerical stability of the representation decreases. It is well known that the tighter (closer to each other) these bounds are the less any small perturbations in the input data will be felt at the output. This paper points out that the Riesz bounds associated with bases built using certain linear combinations of B-splines are better from the stability point of view than bases directly based on B-splines.

Dorabella M. S. Santos and Paulo J. S. G. Ferreira. Reconstruction from Missing Function and Derivative Samples and Oversampled Filter Banks. In: Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2004, vol. III, Montreal, Canada, pp. 941-944, May 2004. Special session on ``Innovations in Sampling Theory and Applications''.

icassp2004.png This paper deals with two-channel sampling using an oversampled filter bank. It emphasizes sampling of one function and its derivative, at a rate higher than the critical minimum rate (oversampling), and the problem of reconstructing the function even when a finite number of samples (of the function or of its derivative) are unknown. The motivation for considering this problem is the need to add redundancy to data, as in conventional channel coding, and the convenience of doing it in a domain suited to the data, as in joint source-channel coding.

J. J. Benedetto and P. J. S. G. Ferreira (Eds.). Modern Sampling Theory: Mathematics and Applications. Birkhäuser, Boston, 2001.

mstma.jpg This book focuses on recent mathematical methods and theoretical developments, as well as some current central applications of Shannon sampling. The sampling theorem, originated in the 19th century, is often associated with the names of Shannon, Kotel'nikov, and Whittaker; and one of the features of this book is an English translation of the pioneering work in the 1930s by Kotel'nikov, a Russian engineer. Includes a wide and coherent range of mathematical ideas essential for modern sampling techniques. These ideas involve wavelets and frames, complex and abstract harmonic analysis, the Fast Fourier Transform (FFT), and special functions and eigenfunction expansions. Some of the applications addressed are tomography and medical imaging.

P. J. S. G. Ferreira. Sampling and Generalized Almost Periodic Extension of Functions. IEEE Transactions on Circuits and Systems—II: Analog and Digital Signal Processing, vol. 46, no. 4, pp. 475-478, Apr. 1999.

ieee-tcas2.jpg This paper explores the connections between nonuniform sampling of a certain function and the almost periodic extension of its Fourier transform. It shows that the Fourier transform of a band-limited function can be extended (as a weighted sum of translates) as a Stepanoff almost periodic function to the whole frequency axis. This result leads to a generalized nonuniform sampling theorem which, unlike previous results, does not require the continuity of the Fourier transform of the sampled function, and is valid for finite-energy band-limited functions.

P. J. S. G. Ferreira (Ed.). Proceedings of the 1997 Workshop on Sampling Theory and Applications, SampTA'97. Universidade de Aveiro, Portugal, June 1997.

sampta97.png The SampTA'97 Workshop took place in Aveiro, in 1997, and the Proceedings volume contains 84 papers (the complete list of papers is available). To obtain the volume contact the editor. For other related publications, see the section on Frames, codes and reconstruction, the section on Missing samples, and the section on Shannon sampling.

P. J. S. G. Ferreira. Nonuniform sampling of nonbandlimited signals. IEEE Signal Processing Letters, vol. 2, no. 5, pp. 89-91, May 1995.

ieee-spl.png This paper shows that the approximation error computed between a smoothed version of the signal (with an ideal low-pass filter of band-width 2w) and a nonuniform sampling approximation of the signal based on the sinc kernel is O(w log w / N) in the sup norm. See also the section Approximation and coding.

P. J. S. G. Ferreira. The stability of a procedure for the recovery of lost samples in band-limited signals. Signal Processing, vol. 40, no. 3, pp. 195-205, Dec. 1994.

sp.png This paper studies the eigenvalues of a matrix that arises in the recovery of lost samples from oversampled band-limited signals. Emphasis is placed on the variation of the eigenvalues as a function of the distribution of the missing samples and as a function of the oversampling parameter. The paper presents a number of results which help to understand the numerical difficulties that may occur in this class of problems, and ways to circumvent them. If you are interested in the discrete, finite-dimensional version of this problem, in which the Fourier transform is replaced by the DFT, see the paper The eigenvalues of matrices that occur in certain interpolation problems.

P. J. S. G. Ferreira. Incomplete sampling series and the recovery of missing samples from oversampled band-limited signals. IEEE Transactions on Signal Processing, vol. 40, no. 1, pp. 225-227, Jan. 1992.

ieee-tsp.jpg It is well known that a bandlimited oversampled signal is completely determined even if an arbitrary finite number of samples is lost. This paper gives (i) an alternative simple proof of this fact (ii) shows that it carries over to generalized sampling expansions. More precisely, it is shown that any finite number of missing samples can be recovered from the remaining ones, in the case of generalized Kramer sampling expansions, if an appropriate oversampling constraint is satisfied. The recovery can be accomplished either iteratively or noniteratively.