Sparse Sampling: Variations on a Theme by Shannon
published: Dec. 5, 2008, recorded: November 2008, views: 12655
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
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.
Joint work with Thierry Blu (CUHK), Lionel Coulot, Ali Hormati (EPFL), Pier-Luigi Dragotti (ICL) and Pina Marziliano (NTU).
Download slides: etvc08_vetterli_ssvoat_01.ppt (5.7 MB)
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !
Write your own review or comment: