A sampling theorem for periodic piecewise polynomial signals

Thierry Blu, Pina Marziliano, Martin Vetterli
2001
Conference paper

Abstract

We consider the problem of sampling signals which are not bandlimited, but still have a finite number of degrees of freedom per unit of time, such as, for example, piecewise polynomials. We demonstrate that by using an adequate sampling kernel and a sampling rate greater or equal to the number of degrees of freedom per unit of time, one can uniquely reconstruct such signals. This proves a sampling theorem for a wide class of signals beyond bandlimited signals. Applications of this sampling theorem can be found in signal processing, communication systems and biological systems.

Official source

https://infoscience.epfl.ch/record/34050?ln=en

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Related publications

Sampling signals with finite rate of innovation

Thierry Blu, Pina Marziliano, Martin Vetterli

Consider classes of signals that have a finite number of degrees of freedom per unit of time and call this number the rate of innovation. Examples of signals with a finite rate of innovation include streams of Diracs (e.g., the Poisson process), nonuniform splines, and piecewise polynomials. Even though these signals are not bandlimited, we showthat they can be sampled uniformly at (or above) the rate of innovation using an appropriate kernel and then be perfectly reconstructed. Thus, we prove sampling theorems for classes of signals and kernels that generalize the classic "bandlimited and sinc kernel" case. In particular, we show how to sample and reconstruct periodic and finite-length streams of Diracs, nonuniform splines, and piecewise polynomials using sinc and Gaussian kernels. For infinite-length signals with finite local rate of innovation, we show local sampling and reconstruction based on spline kernels. The key in all constructions is to identify the innovative part of a signal (e.g., time instants and weights of Diracs) using an annihilating or locator filter: a device well known in spectral analysis and error-correction coding. This leads to standard computational procedures for solving the sampling problem, which we show through experimental results. Applications of these new sampling results can be found in signal processing, communications systems, and biological systems.

Institute of Electrical and Electronics Engineers2002

Sampling of communications systems with bandwidth expansion

Andrea Ridolfi, Martin Vetterli

Many communication systems are {\em bandwidth-expanding}: the transmitted signal occupies a bandwidth larger than the {\em symbol rate}. The sampling theorems of Kotelnikov, Shannon, Nyquist et al. shows that in order to represent a bandlimited signal, it is necessary to sample at what is popularly referred to as the Shannon or Nyquist rate. However, in many systems, the required sampling rate is very high and expensive to implement. In this work we show that it is possible to get suboptimal performance by sampling close to the {\em symbol rate} of the signal, using well-studied algorithmic components. This work is based on recent results on sampling for some classes of non-bandlimited signals. In the present paper, we extend these sampling results to the case when there is noise. In our exposition, we use Ultra Wideband (UWB) signals as an example of how our framework can be applied.

2002

Over the past decade researches in applied mathematics, signal processing and communications have introduced compressive sampling (CS) as an alternative to the Shannon sampling theorem. The two key observations making CS theory widely applicable to numerous areas of signal processing are: i) due to their structural properties, natural signals typically have sparse representations in properly chosen orthogonal bases, ii) the number of linear non-adaptive measurements required to acquire high-dimensional data with CS is proportional to the signal’s sparsity level in the chosen basis. In multichannel signal applications the data of different channels is often highly correlated and therefore the unstructured sparsity hypothesis deployed by the classical CS theory results in suboptimal measurement rates. Meanwhile, the wide range of applications of multichannel signals and the extremely large and increasing flow of data in those applications motivates the development of more comprehensive models incorporating both inter and intra-channel data structures in order to achieve more efficient dimensionality reduction. The main focus of this thesis is on studying two new models for efficient multichannel signal compressed sensing. Our first approach proposes a simultaneous low-rank and joint-sparse matrix model for multichannel signals. As a result, we introduce a novel CS recovery scheme based on Nuclear-l2/l1 norm convex minimization for low-rank and joint-sparse matrix approximation. Our theoretical analysis indicates that using this approach can achieve significantly lower sampling rates for a robust multichannel data CS acquisition than state-of-the-art methods. More remarkably, our analysis confirms the near-optimality of this approach: the number of CS measurements are nearly proportional to the few degrees of freedom of such structured data. Our second approach introduces a stronger model for multichannel data synthesized by a linear mixture model. Here we assume that the mixture parameters are given as side information. As a result, multichannel data CS recovery turns into a compressive source separation problem, where we propose a novel decorrelating scheme to exploit the knowledge of mixture parameters for a robust and numerically efficient source identification. Our theoretical guarantees explain the fundamental limits of this approach in terms of the number of CS measurements, the sparsity level of sources, the sampling noise, and the conditioning of the mixture parameters. We apply these two approaches to compressive hyperspectral image recovery and source separation, and compare the efficiency of our methods to state-of-the-art approaches for several challenging real-world hyperspectral datasets. Note that applications of these methods are not limited to hyperspectral imagery and it can have a broad impact on numerous multichannel signal applications. As an example, for sensor network applications deploying compressive sampling schemes, our results indicate a tight tradeoff between the number of available sensors (channels) and the complexity/cost of each sensor. Finally, in a different multichannel signal application, we deal with a simple but very important problem in computer vision namely the detection and localization of people given their multi-view silhouettes captured by networks of cameras. The main challenge in many existing solutions is the tradeoff between robustness and numerical efficiency. We model this problem by a boolean (non-linear) inverse problem where, by penalizing the sparsity of the solution, we achieve accurate results comparable to state-of-the-art methods. More remarkably, using boolean arithmetics enables us to propose a real-time and memory efficient approximation algorithm that is mainly rooted in the classical literature of group testing and set cover.

EPFL2012