Non-uniform (and uncompressed) sampling from IFIP TC7

A few days ago I’ve been to IFIP TC7 and participated in the minisymposium “Optimization in Banach spaces with sparsity constraints” organized by Kristian Bredies and Christian Clason. My session was very interesting, consisting of talks of Masha Zhariy (Optimization algorithms for sparse reconstruction in inverse problems with adaptive stopping rules), Caroline Vehoeven (On a generalization of the iterative soft-thresholding algorithm for the case of non-separable penalty) and Kristian (Inverse problems in spaces of measures). Unfortunately, I could not take part in the second half of the minisymposium.

Although the minisymposium was interesting, I’d like to talk about the plenary Talk “Signal and systems representation; signal spaces, sampling, and quantization effects” by Holger Boche. The title sounded as I should be able to follow, but I’ve never heard the name before. And indeed, Holger Boche gave a fresh view onto the sampling and reconstruction problem, i.e. the digital-to-analog conversion and its inverse.

It was somehow refreshing to have a talk about sampling which was totally free of the words “compressive” and “compressed”. Holger Boche modelled continuous time signals in the well known Bernstein and Paley-Wiener spaces and started with fairly old but not too well known results on exact reconstruction from non-uniform sampling.

Definition 1 For ${1\leq p\leq \infty}$ and ${\sigma>0}$ , the Paley-Wiener space ${\mathcal{PW}_\sigma^p}$ is
$\displaystyle \mathcal{PW}_\sigma^p = \{\hat g\ :\ g\in L^p([-\sigma,\sigma])\}.$

Definition 2 A function ${\phi}$ is of sine-type if it is of exponential type ${\pi}$ and

its zeros are separated, and
there exist real ${A,B,H}$ such that for all ${|y|\geq H}$ it holds that
$\displaystyle Ae^{\pi|y|}\leq |f(x+iy)| \leq Be^{\pi|y|}.$

Then, one theorem of reconstruction for non-uniform sampling points goes as follows:

Theorem 3 Let ${\phi}$ be a function of sine-type, whose zeros ${(t_k)}$ are all real and define
$\displaystyle \phi_k(t) = \frac{\phi(t)}{\phi'(t_k)(t-t_k)}.$

Then, for every ${f\in\mathcal{PW_\pi^1}}$ and all ${T>0}$ it holds that
$\displaystyle \lim_{N\rightarrow\infty}\|f - \sum_{k=-N}^N f(t_k)\phi_k\|_{L^\infty([-T,T])} \rightarrow 0.$

This theorem is a generalization of a result of J.L. Brown on local uniform convergence of the Shannon-sampling series.

These results are related to a sampling theorem due to Logan which I learned some years ago. First we recall that the Hilbert transform ${\mathcal{H}f}$ of a function ${f}$ can be defined via the Fourier transform ${\mathcal{F}}$ as

$\displaystyle \mathcal{F}(\mathcal{H}(u))(\omega) = (-i\text{sign}(\omega))\mathcal{F}(u)(\omega).$

Then, Logan’s Theorem is as follows:

Theorem 4 (Logan’s Sampling Theorem) Let ${f_1,f_2:\mathbb{R}\rightarrow\mathbb{R}}$ such that the support of both ${\hat f_1}$ and ${\hat f_2}$ is contained in ${[-b,-a]\cup[a,b]}$ for some number ${a}$ and ${b}$ with ${0<a<b<2a}$ . Then, if ${f_1}$ and ${f_2}$ do not have a root in common with their Hilbert transform, it holds that ${\text{sign} f_1 = \text{sign} f_2}$ implies that ${f_2}$ is equal to ${f_1}$ up to a constant factor.

Proof: (Informal) Since modulation shifts the Fourier transform, we can write a function ${f}$ with ${\text{supp}\hat f\subset -b,-a]\cup[a,b]}$ as a modulated sum of functions ${h_1}$ and ${h_2}$ with bandwidth ${(b-a)/2}$ , using ${\mu=(a+b)/2}$ as follows

$\displaystyle f(t) = -i h_1(t)e^{i\mu t} + if_2(t)e^{-i\mu t}.$

Expressing ${\exp}$ in terms of ${\sin}$ and ${\cos}$ gives

$\displaystyle \begin{array}{rcl} f(t) &=& (-if_1(t) + if_2(t))\cos(\mu t) + (f_1(t)+f_2(t))\sin(\mu t)\\ &=& p(t)\cos(\mu t) + q(t)\sin(\mu t). \end{array}$

Note that ${p}$ and ${q}$ are real valued since ${f}$ is assumed to be real valued. Using ${\mathcal{H}(\sin) = \cos}$ and ${\mathcal{H}(\cos) = -\sin}$ we conclude that

$\displaystyle \mathcal{H}(f)(t) = p(t)\sin(\mu t) - q(t)\cos(\mu t).$

With the obvious notation we obtain that

$\displaystyle \mathcal{H}(f_1)(t)f_2(t) - \mathcal{H}(f_2)(t)f_1(t) = p_1(t)q_2(t) - p_2(t)q_1(t) = g(t).$

Now, the zeros of ${g}$ are at least the common zeros of ${f_1}$ and ${f_2}$ . Moreover, the bandwidth of ${g}$ is at most ${b-a}$ (since the bandwidth of ${p_j}$ and ${q_j}$ is at most ${(b-a)/2}$ ). We can conclude that ${g}$ is identically zero by an argument which uses that upper density of the zeros of ${f_1}$ (resp. ${f_2}$ ) is high enough to force ${g}$ to zero. Hence, we know that

$\displaystyle \frac{f_1(t)}{\mathcal{H}(f_1)(t)} = \frac{f_2(t)}{\mathcal{H}(f_2)(t)}$

To finish the proof one needs some argument from complex analysis (using that both sides of the above equations are extendable to meromorphic function of exponetial type) to conclude that ${f_1}$ equals ${f_2}$ up to a constant factor. $\Box$

When I asked about the relation between Logan’s theorem and his results, he replied that Logan’s theorem was the starting point since he was curious why there was no practical implementation of this sampling procedure available. More precisely, he was interested in designing a digital implementation, based on sampling points, which allows to digitize all linear time invariant filters. One of his negative results was the following.

Definition 5 A sequence ${(t_k)}$ is called a complete interpolation sequence for ${\mathcal{PW}_\pi^2}$ and ${\ell^2}$ if for every ${c\in\ell^2}$ there is exactly one ${f\in \mathcal{PW}_\pi^2}$ such that ${f(t_k) = c_k}$ .

Theorem 6 For a complete interpolation sequence ${(t_k)}$ for ${\mathcal{PW}_\pi^2}$ and ${\ell^2}$ , the corresponding reconstruction functions ${\phi_k}$ and a given ${t\in\mathbb{R}}$ there always exists a stable linear time invariant filter ${T}$ and a signal ${f\in \mathcal{PW}_\pi^1}$ such that
$\displaystyle \lim\sup_{N\rightarrow\infty} | (Tf)(t) - \sum_{k=-N}^N f(t_k)(T\phi_k)(t)| = \infty.$

He conjectured (Conjecture 2.1 in his talk), that this phenomenon of point-wise divergence of the approximation of a linear time invariant filter remains, even if oversampling is applied, that there always is a function ${f\in\mathcal{PW}_{\beta\pi}^1}$ ( ${0<\beta<1}$ ) such that point-wise divergence happens. Moreover, he conjectured that (Conjecture 2.2) digitizing stable linear time invariant filter should be possible if one replaced point-sampling by appropriate linear functionals and posed the open problem to both prove this conjecture and to find such linear functionals.

About these ads

regularize