“Sparce Sampling: Variations on a Theme by Shannon”

Abstract

Sampling is not only a beautiful topic in harmonic analysis, with an interesting history, but also a subject with high practical impact, at the heart of signal processing and communications and their applications. The question is very simple: when is there a one-to-one relationship between a continuous-time function and adequately acquired samples of this function? A cornerstone result is of course Shannon's sampling theorem, which gives a sufficient condition for reconstructing the projection of a signal onto the subspace of bandlimited functions, and this by taking inner products with a sinc function and its shifts. Many variations of this basic framework exist, and they are all related to a subspace structure of the classes of objects that can be sampled. Recently, this framework has been extended to classes of non-bandlimited sparse signals, which do not have a subspace structure. Perfect reconstruction is possible based on a suitable projection measurement. This gives a sharp result on the sampling and reconstruction of sparse continuous-time signals, namely that 2K measurements are necessary and sufficient to perfectly reconstruct a K-sparse continuous-time signal. In accordance with the principle of parsimony, we call this sampling at Occam's rate. We first review this result and show that it relies on structured Vandermonde measurement matrices, of which the Fourier matrix is a particular case. It also uses a separation into location and value estimation, the first being non-linear, while the second is linear. Because of this structure, fast, O(K^3) methods exist, and are related to classic algorithms used in spectral estimation and error correction coding. We then generalize these results to a number of cases where sparsity is present, including piecewise polynomial signals, as well as to broad classes of sampling or measurement kernels, including Gaussians and splines. Of course, real cases always involve noise, and thus, retrieval of sparse signals in noise is considered. That is, is there a stable recovery mechanism, and robust practical algorithms to achieve it. Lower bounds by Cramer-Rao are given, which can also be used to derive uncertainty relations with respect to position and value of sparse signal estimation. Then, a concrete estimation method is given using an iterative algorithm due to Cadzow, and is shown to perform close to optimal over a wide range of signal to noise ratios. This indicates the robustness of such methods, as well as their practicality. Next, we consider the connection to compressed sensing and compressive sampling, a recent approach involving random measurement matrices, a discrete set up, and retrieval based on convex optimization. These methods have the advantage of unstructured measurement matrices (actually, typically random ones) and therefore a certain universality, at the cost of some redundancy. We compare the two approaches, highlighting differences, similarities, and respective advantages. Finally, we move to applications of these results, which cover wideband communications, noise removal, and superresolution imaging, to name a few. We conclude by indicating that sampling is alive and well, with new perspectives and many interesting recent results and developments.

Bio

Martin Vetterli got his Engineering degree from Eidgenoessische Technische Hochschule Zuerich (ETHZ), his MS from Stanford University and his Doctorate from Ecole Polytechnique Federale de Lausanne (EPFL). He was on the faculty of Columbia University in New York, and the University of California at Berkeley before joining the Communication Systems Dept. of EPFL, where he is also vice-president of the university. He works on signal processing and communications, in particular, wavelet and sampling theory with applications, source compression, joint source-channel coding, self-organized communication systems, sensor networks and their application to environmental monitoring.  Author or co-author of about 120 journal papers, he is an ISI highly cited scientist in engineering. His work won him several prizes (best paper awards from EURASIP in 1984 and of the IEEE Signal Processing Society in 1991,1996 and 2006). He is the co-author, with J.Kovacevic, of the graduate book "Wavelets and Subband Coding" (Prentice-Hall, 1995 and online), with P.Prandoni of the textbook "Signal Processing for Communications" (EPFL Press, 2008 and online) and a forthcoming book, with J.Kovacevic and V.Goyal "Fourier and Wavelets: Theory, Algorithms and Applications".