5
$\begingroup$

Given samples of an everywhere non-negative or positive-valued continuous-time signal band-limited to half the sampling frequency, is there some practically applicable way to interpolate it so that there is no danger of producing negative values? The approach should be scalable to arbitrary accuracy so basic linear interpolation won't do. By arbitrary accuracy I mean an arbitrary small difference between the band-limited continuous-time signal and the interpolation.

Perfect sinc interpolation would work because negative contributions would get cancelled by positive contributions. Ideal sinc interpolation is not possible in practice so other filters are used. This could give negative values because usually the filter impulse response has negative values. For example cubic Hermite spline piece-wise polynomial interpolation gives this impulse response:

enter image description here
Figure 1. Cubic Hermite spline impulse response has negative values.

Lagrange polynomials used as splines would also have negative values in the impulse response. B-splines have everywhere non-negative impulse responses, but their pass-band frequency responses deviate increasingly from the brick-wall frequency response of sinc interpolation with increasing B-spline order. The B-spline impulse response tends to a Gaussian function as the order is increased. A Gaussian function in time domain is a Gaussian function in frequency domain, so not a perfect brick-wall filter.

The obvious way to fix the problem would be to 1) take the absolute value of the interpolation output or 2) set all negative output values to zero, but I'm wondering if there is some better (inherently non-negative) method, because both 1) and 2) would create discontinuities in the derivative of the signal. This also creates spectral images.

I don't know how bad the problem stated in this question really is, because if the band-limited signal is non-negative, this also rules out some contradictory discrete signals like $[\dots, 0, 0, 0, 1, 0, 0, 0, \dots].$ The corresponding non-negative continuous signal would then have to be sinc, which is partially negative, which is the contradiction.

Shay Maymon has investigated "bandlimited square-roots" in his 2011 thesis Sampling and Quantization for Optimal Reconstruction. The idea there is to find (not easy) another band-limited signal (complex and at half the bandwidth) the squared magnitude of which equals the wanted band-limited signal. Interpolating that other signal and multiplying the result by its complex conjugate is never negative. That reminds me of this question about interpolation of the magnitude of discrete Fourier transform (DFT).

Improve this question
$\endgroup$
12
  • $\begingroup$ am I taking this correctly, you're willing to break the bandwidth limitation by interpolation? $\endgroup$
    – Marcus Müller
    Apr 12, 2017 at 9:07
  • $\begingroup$ That is not the intention, because the goal is to reconstruct the band-limited continuous-time signal. In practice this cannot be done perfectly so some attenuated remnants of spectral images will appear past the true signal's bandwidth. That's where the interpolation filter's stopband is at. $\endgroup$
    – Olli Niemitalo
    Apr 12, 2017 at 9:13
  • $\begingroup$ ah, ok, so you already know the original signal was non-negative (now I feel a bit stupid because you already said that perfect sinc reconstruction would work, which says exactly that) $\endgroup$
    – Marcus Müller
    Apr 12, 2017 at 9:18
  • 2
    $\begingroup$ OK, I was indeed thinking of splines with non-negative impulse responses such as B-splines. $\endgroup$
    – Matt L.
    Apr 12, 2017 at 10:33
  • 1
    $\begingroup$ I'm a complete noob regarding interpolation; sorry if this is a dumb idea, but: what if you add a constant value to your interpolating filter response, so that it becomes non-negative? If $y(t)=x(t) \ast h(t)$ is acceptable except that it's not always positive, then $x(t) \ast (C+h(t)) = x(t) \ast C + x(t) \ast h(t) = D + x(t) \ast h(t)>0$, with constants $C$ and $D$, $C$ chosen in some appropriate way, and a bit of handwaving in the convolution $x(t) \ast C$. Maybe this idea can be generalized to do what you need. $\endgroup$
    – MBaz
    Apr 12, 2017 at 16:22

2 Answers 2

Reset to default
5
$\begingroup$

If we require the impulse response of the interpolation filter to be non-negative then we can obviously guarantee that the interpolated signal is also non-negative. However, it can be shown that the frequency response of a low pass filter with non-negative impulse response is always far from ideal. More specifically, it can be shown that if $\epsilon$ is the maximum negative pass band deviation of the squared magnitude $|H(\omega)|^2$ of the filter's transfer function from its value at $\omega=0$

$$|H(\omega)|^2\ge |H(0)|^2-\epsilon,\quad |\omega|<\omega_c \tag{1}$$

where $\omega_c$ is the cut-off frequency, then the following inequality holds:

$$|H(\omega)|^2\ge |H(0)|^2-4\epsilon,\quad |\omega|<2\omega_c\tag{2}$$

This inequality imposes a severe restriction on the minimum stop band attenuation if the ripple size $\epsilon$ is chosen sufficiently small (as should be the case for a good low pass filter).

As an example, if $\epsilon$ is chosen such that the pass band ripple is $1$ dB, the attenuation at $\omega=2\omega_c$ cannot be better than $7.5$ dB.

Of course, if $\epsilon\ge |H(0)|^2/4$ then $(2)$ represents no restriction, but in that case the maximum pass band deviation of the magnitude of the transfer function is greater than usually required for a good low pass filter.

Since the inequality $(2)$ is independent of the filter order, an interpolation filter with arbitrary accuracy cannot be realized by a filter with non-negative impulse response.

The proof of $(2)$ can be found in Attenuation Limits for Filters with Monotonic Step Response by A. Papoulis, IRE Transactions on Circuit Theory ( Volume: 9, Issue: 1, March 1962).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I like the reference to ancient short notes $\endgroup$
    – Laurent Duval
    Apr 12, 2017 at 21:45
  • 1
    $\begingroup$ @LaurentDuval: These guys seem to have known it all more than half a century ago ... Whenever I have a system theory question I would consult Papoulis, and more often than not I find an answer or at least a hint. $\endgroup$
    – Matt L.
    Apr 13, 2017 at 7:22
  • $\begingroup$ An observation: For a Gaussian impulse response, in the limit $\epsilon\to0$, Eq. 2 becomes an equality. I think this has to do with the quadratic Taylor approximation of the square of a Gaussian frequency response, and that $(2x)^2/x^2 = 4$. $\endgroup$
    – Olli Niemitalo
    Jul 13, 2019 at 9:02
2
$\begingroup$

If the original signal was perfectly bandlimited and always positive or zero, then an infinite Sinc interpolation should reconstruct that (at the limit).

A realizable (finite length) windowed Sinc will leave a remainder (the difference between a perfect sinc and the window sinc). If an infinite series of evenly spaced grid of samples of that remainder always sums to a negative (or zero) value, then the windowed Sinc should alway err on the positive side during use as a reconstruction function. Not sure how to construct such a window, but it might be possible.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.