Exact sampling results for 1-D and 2-D signals with finite rate of innovation using Strang-Fix conditions and local reconstruction algorithms

Pier Luigi DragottiProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 2005 · DOI

TL;DR

This paper introduces a novel approach to sampling and reconstructing signals with a "finite rate of innovation" (FRI). Unlike previous methods requiring complex, infinite-support kernels, this work demonstrates how to use simpler, compact-support kernels and local reconstruction algorithms, making the process more practical and stable for both 1D and 2D signals.

What Problem Does This Paper Address?

Traditional signal sampling, like the Shannon-Nyquist theorem, assumes signals are bandlimited. However, many real-world signals, such as those containing sharp transitions (like piecewise polynomials or streams of Dirac impulses), are not bandlimited but can be described by a finite number of parameters over time. These are known as signals with a "finite rate of innovation" (FRI). Previous methods for sampling FRI signals often relied on kernels with infinite support (like sinc functions), which are physically unrealizable and lead to computationally complex and unstable reconstruction algorithms. This paper tackles the challenge of developing practical and stable sampling and reconstruction schemes for FRI signals using more manageable, compact-support kernels.

Methods

The core of this paper lies in identifying a specific class of sampling kernels that enable exact reconstruction of FRI signals. These kernels must satisfy certain conditions, allowing them to "reproduce" polynomials or exponentials.

  • Strang-Fix Conditions: For polynomial reproduction, the kernels must satisfy the Strang-Fix conditions. This means that a linear combination of shifted versions of the kernel can exactly represent polynomials up to a certain degree.
  • Exponential Splines (E-Splines): For exponential reproduction, the paper leverages E-Splines, which are generalizations of B-Splines. These kernels, when combined with appropriate filtering, can effectively reproduce exponential functions.
  • Rational Fourier Transforms: Kernels with rational Fourier transforms are also considered, as they can be converted into kernels that reproduce exponentials through filtering.
  • Annihilating Filter Method: The reconstruction process for FRI signals relies on the "annihilating filter" method. This technique uses a filter whose roots correspond to the unknown parameters of the FRI signal (e.g., locations of Diracs). The paper shows how to adapt this method to work with samples obtained using the new, compact-support kernels.
  • Local Reconstruction: A key innovation is the use of "local" reconstruction algorithms. Instead of relying on global properties of the signal, these algorithms process information in a localized manner, contributing to stability and efficiency.
  • Extension to 2D: The methods are extended to two-dimensional signals by using tensor products of 1D kernels and employing complex moments for reconstruction.

Datasets

Not discussed in the paper. The paper focuses on theoretical results and demonstrates its methods with synthetic examples (e.g., streams of Diracs, piecewise constant signals, bilevel polygons).

Key Insights and Ideas

  • Compact Kernels for FRI: The most significant insight is that FRI signals can be sampled and reconstructed exactly using kernels with compact support, contrary to prior assumptions that infinite support was necessary for complex FRI signals.
  • Reproducing Properties are Key: The crucial property of a sampling kernel for FRI signals is its ability to reproduce polynomials or exponentials, not necessarily its bandlimiting properties.
  • Practicality and Stability: By using compact-support kernels and local reconstruction, the proposed methods offer a more practical and stable alternative to existing FRI sampling schemes.
  • Unified Framework: The paper presents a unified framework that can handle various FRI signal types (Diracs, differentiated Diracs, piecewise polynomials, exponentials) by leveraging the properties of the sampling kernel and the annihilating filter method.
  • Electrical Circuits as Kernels: The work highlights the potential of using electrical circuits with rational transfer functions (like RC circuits) as practical sampling kernels, as they can be transformed into kernels that reproduce exponentials.

Key Results

The paper establishes theoretical results (theorems) demonstrating the exact reconstructibility of FRI signals under specific conditions:

  • Theorem 1 (Polynomials): A sampling kernel with compact support that can reproduce polynomials up to degree $N > 2K-1$ can uniquely determine a stream of $K$ Diracs if there are at most $K$ Diracs in an interval of length $KLT$.
  • Theorem 2 (Differentiated Diracs): Similar conditions apply for streams of differentiated Diracs.
  • Theorem 3 (Piecewise Polynomials): For piecewise polynomial signals with pieces of degree $M-1$, the conditions are extended to ensure unique reconstruction.
  • Theorem 4 (Exponentials): A kernel that can reproduce exponentials $e^{a_m t}$ (where $a_m = a_0 + m\lambda$) up to degree $N > 2K-1$ can uniquely determine a stream of $K$ Diracs if there are at most $K$ Diracs in an interval of length $KLT$.
  • 2D Extension: The paper shows that similar principles apply to 2D signals, enabling the reconstruction of bilevel polygons and sets of 2D Diracs using complex moments.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical, establishing the conditions for exact reconstruction. While it uses illustrative examples (like the RC circuit), it doesn't present extensive experimental validation on real-world datasets.
  • "At Most K Diracs" Condition: The theorems rely on conditions like having "at most K Diracs" in a certain interval. In practice, determining this local rate of innovation precisely can be challenging.
  • Noise Sensitivity: The paper focuses on exact reconstruction from noiseless samples. The robustness of these methods to noise is not explicitly addressed.
  • Future Work: The authors suggest that applications could be found in image super-resolution, communication systems, and biological systems. Further research could explore the practical implementation of these schemes, their performance in the presence of noise, and their application to more complex FRI signal models. The paper also hints at using more complex electrical circuits (e.g., cascades of RC circuits) for higher rates of innovation.

Summary updated

Abstract

Recently, it was shown that it is possible to sample classes of signals with finite rate of innovation. These sampling schemes, however, use kernels with infinite support and this leads to complex and instable reconstruction algorithms. In this paper, we show that many signals with finite rate of innovation can be sampled and perfectly reconstructed using kernels of compact support and a local reconstruction algorithm. The class of kernels that we can use is very rich and includes any function satisfying Strang-Fix conditions, Exponential Splines and functions with rational Fourier transforms. Our sampling schemes can be used for either 1-D or 2-D signals with finite rate of innovation.
BibTeX
@inproceedings{dragotti2005exact,
  author = {Pier Luigi Dragotti},
  title = {{Exact sampling results for 1-D and 2-D signals with finite rate of innovation using Strang-Fix conditions and local reconstruction algorithms}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {2005},
  doi = {10.1117/12.616903},
}
Figure