Optimal trade-off between oversampling and filter length

Question

For some sampling-frequency-preserving operations on Nyquist–Shannon sampled signals, such as:

• a shift a.k.a. translation, and
• differentiation by applying a derivative filter a.k.a. gradient filter,

the ideal filter for each task has an infinite number of taps with weights obtained by sampling the sinc function or its derivative. In practice, finite-impulse-response (FIR) approximations are typically used.

For a given maximum acceptable level of approximation error, the required minimum number of taps in the approximating FIR filter is reduced if there is an overhead $f_B\ldots f_s/2$ between the highest frequency $f_B$ of the signal and half the sampling frequency $f_s$. From filter design perspective, this overhead obtained by oversampling the input signal by a factor $\beta = f_s/(2f_B) > 1$ creates a transition band of non-zero width and relaxes requirements on the filter, as exemplified by the magnitude frequency response of a simple approximative derivative filter decipted in Fig. 1.

Figure 1. Arbitrarily normalized magnitude frequency response of an ideal derivative filter (diagonal red line) and its approximation (black curve) with impulse response $-3/16,$ $31/32,$ $0,$ $-31/32,$ $3/16$. With ideal oversampling, the frequency response above the highest frequency of the signal (vertical blue line) does not contribute to the approximation error.

However, assuming that the output signal is sampled at the same sampling frequency $f_s$ as the input signal, increasing $f_s$ increases the number of output samples, which increases the number of times a dot product between the $N$ filter weights and $N$ signal samples needs to be calculated. In general, for a 1-d signal, $\beta N$ times as many multiply–accumulate operations (MACs) are needed compared to the number of samples in critically sampled (not oversampled) representation of the input and output signals.

For such a task, which oversampling factor $\beta$ minimizes $\beta N$, requiring the least total MACs in FIR filtering without exceeding a given maximum acceptable approximation error measured by a reasonable error metric?

Upsampling to obtain the oversampled input signal shall be considered ideal and not contributing to the MAC count, as if the input signal was obtained perfectly pre-oversampled.

Answer 1

1-d MMSE derivative filter for uniform spectral prior

With some simplifying assumptions about the signal distribution, a filter with least square frequency response error is the Bayesian minimum mean square error (MMSE) filter for a uniform prior of the frequency spectrum. For such 1-d filters, an oversampling factor $\beta \approx 2\ldots2.5$ seems optimal, as it is in the sweet spot of the cost-benefit curves (Fig. 1).

Figure 1. Mean square frequency response error of least square optimal derivative filters as function of computational complexity as measured by $\beta N$ which is proportional to the total number of multiply-accumulates (MACs), for various oversampling factors $\beta$ for which the filters have been optimized. Also shown are traces for different numbers $N$ of non-zero filter coefficients. No advantage was taken from impulse response anti-symmetry or simple coefficients such as $1$.

More data is needed before general conclusions can be drawn.