# Optimal trade-off between oversampling and filter length

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.

• Do you mean "upsampling" (i.e interpolation) rather than "oversampling" (increasing sampling rate)? Also, when you say "ideal filter", I wouldn't be so quick to crown the "bandlimited" as best. For differentiation(s), polynomial interpolations may be better. Differentiation is inherently a local operation. – Cedron Dawg Jul 21 '19 at 13:44
• @CedronDawg "Oversampling" tastes better to me because it gives a desired indication of there being a continuous band-limited signal of which the samples give a representation, and the process of upsampling needs not be considered for this question. See this answer (also linked to in the question) about derivative filtering of Nyquist–Shannon sampled signals. – Olli Niemitalo Jul 21 '19 at 14:12
• I double checked before I asked. Here is one source: audioholics.com/audio-technologies/… With interpolation, the "more points" takes on a different meaning. – Cedron Dawg Jul 21 '19 at 14:20
• @CedronDawg invoking r b-j on "oversampling". I added one "upsamping" to the question. – Olli Niemitalo Jul 21 '19 at 14:39
• I think you and R B-J may be in the minority. Undersampling/Oversampling and Downsampling/Upsampling/Resampling seem to refer to the actual sampling rate for the former and interpolation for the latter in all references I found. Unfortunately I don't have time to work on this right now, but will accept the premise of the question to be about a bandlimited noiseless signal where upsampling and oversampling would be equivalent. I also see you've done considerable work already on the related "Pyhon" question. – Cedron Dawg Jul 21 '19 at 18:36

## 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.