Effective support, Dirac combs, and signal recovery

Abstract

Let $f:{\mathbb{Z}}_N^d\to \mathbb{C}$ be a signal with the Fourier transform $\hat{f}:{\mathbb{Z}}_N^d\to \mathbb{C}$. A classical result due to Matolcsi and Szucs (\cite{MS73}), and, independently, to Donoho and Stark (\cite{DS89}) states if a subset of frequencies ${\{\hat{f}(m)\}}_{m\in S}$ of $f$ are unobserved due to noise or other interference, then $f$ can be recovered exactly and uniquely provided that $$|E|\cdot |S|<\frac{N^d}{2},$$ where $E$ is the support of $f$, i.e., $E=\{x\in {\mathbb{Z}}_N^d:f(x)\ne 0\}$. In this paper, we consider signals that are Dirac combs of complexity ${\hat{I}}^3$, meaning they have the form $f(x)={\sum }_{i=1}^3{a}_i{1}_{A_i}(x)$, where the sets $A_i\subset {\mathbb{Z}}_N^d$ are disjoint, $a_i$ are complex numbers, and ${\hat{I}}^3\le N^d$. We will define the concept of effective support of these signals and show that if ${\hat{I}}^3$ is not too large, a good recovery condition can be obtained by pigeonholing under additional reasonable assumptions on the distribution of values. Our approach produces a non-trivial uncertainty principle and a signal recovery condition in many situations when the support of the function is too large to apply the classical theory.