3
$\begingroup$

I'm looking for an algorithm to compute the numeric derivative $\dot x_i$ of a discrete time serie $(x_i, t_i)$.

  • It should runs as the data is generated, hence $\dot x_i$ can only depend on $x_{j<=i}$.

  • The memory resource is scarce, ideally it would only access the passed sample and andother value (either state or a sample), eventually more sample and more states can be used if it proves to be useful

  • The result should be robust to $x_i$ integer aliasing, especially when the derivative is close to zero and the $x_i$ serie has consecutive identical values

For now I'm using and empirical method:

$$ \dot x_i = \begin{cases} \dot x_{-1}=0 & \text{for } i = 0 \\ ( 1 - q )\dot x_{i-1} + q \dfrac{ x_i - x_{i-1}}{t_i - t_{i-1}} & \text{with } q \in [0, 1] \end{cases} $$

This just blends the derivative with its previous value:

  • With $q = 1$ this is the instant derivate.

  • With $q < 1$ it takes into account the past samples by only accessing the previous sample and the previous derivate.

What are the existing methods that could be applied to my problem?

$\endgroup$
5
  • 2
    $\begingroup$ Can you tell us why you're looking for a different method? What are the issues you face with this one? $\endgroup$
    – Jdip
    Commented Jan 31 at 20:03
  • $\begingroup$ Could we assume the sampling is uniform? $\endgroup$
    – Royi
    Commented Feb 1 at 6:58
  • $\begingroup$ I came with this method out of intuition, and I would like to know if there is a better approach. The sampling is not uniform, each sample $x_i$ is measure at time $t_i$, hence it is not uniform. $\endgroup$
    – piwicode
    Commented Feb 2 at 20:35
  • $\begingroup$ A bit more context: I'm computing the velocity of a keystroke on a MIDI instrument. The values $x_i$ comes from a 10 bit analog-to-digital converter samples at ~6 kHz. The samples are not uniform because the process is interrupted by the USB driver, but the jitter is low. $\endgroup$
    – piwicode
    Commented Feb 2 at 20:57
  • $\begingroup$ I heard about backward finite differentiation, but it relies on accessing multiple samples, is there another approach? $\endgroup$
    – piwicode
    Commented Feb 3 at 7:13

1 Answer 1

4
$\begingroup$

There is no "one size fits all" answer.

The main problem is the following. Continuous differentiation is a linear operation and can be interpreted as a filter. Its transfer function is simply

$$\Delta_C(\omega) = j\omega \tag{1}$$

However, this transfer function is NOT bandlimited. In fact it's the exact opposite of bandlimited since it gets bigger and bigger with frequency. Hence you can't sample it without significant amount of aliasing. You can only approximate a differentiator and the best approximation depends on your specific application requirements.

The most common approximation is simply

$$y_1[n] = x[n]-x[n-1] \tag{2}$$

This is a high pass filter with a cutoff frequency at $f_s/4$ where $f_s$ is the sample rate. It's transfer function is $$Y_1(\omega) = e^{-j\omega T_s/2} \cdot 2\sin(j\omega T_s/2) \tag{3}$$

where $T_s=1/f_s$ is the sampling period. At low frequencies the amplitude matches well but it has a constant phase error of a half sample delay since the "center" of the filter is between $n = 0$ and $n= 1$.

This is essentially your method with $q = 1$. Setting $q$ to anything else will cascade a first order lowpass filter. I'm not sure what this is supposed to do, but it certainly increases the error in the frequency domain. Below is an example of the 1st order high pass, the high pass cascaded with a lowpass and the "ideal" transfer function. Note that this only shows the amplitude, there are phase errors as well.

enter image description here

Another option would be to center around $n=0$ , i.e. $$y_2[n] = x[n+1]-x[n-1] \tag{4} $$

That has no phase but is non-causal. The amplitude is also not monotonically rising anymore, so the amplitude error is very large at high frequencies.

Another way is to design a more complicated differentiation FIR filter based on windowing the inverse FFT of the desired transfer function or a least square error fit. However that will also be non-causal and more expensive.

There are few other options and all have a different set of pros and cons, so it really depends on the specific requirements if your application.

$\endgroup$
4
  • $\begingroup$ Thank you for this answer. It uses a lot of concepts that are not clear to me. Proposal $(2)$ corresponds to my method with $q=1$, but it fails at measuring small derivative because of $x$ integer aliasing: it returns 0 when there are consecutive identical values regardless of the trend. I suspect that there is a misunderstanding when you say that for $q=0.5$ my method is the derivate between $n=0$ and $n=1$. Propose (4) does not apply to my problem statement. I stated the requirement of my application, in the question, but I'm happy to get precisions. $\endgroup$
    – piwicode
    Commented Feb 2 at 20:34
  • $\begingroup$ Also, could you please explain why there are $.5$ factors in $(2)$? $\endgroup$
    – piwicode
    Commented Feb 2 at 20:51
  • $\begingroup$ @piwicode: sorry I was sloppy and misread your method. I think I have it mostly fixed now. $\endgroup$
    – Hilmar
    Commented Feb 3 at 15:46
  • $\begingroup$ That makes sense. The integer aliasing is smoothen out by the low pass filter, which is fine I guess. How could I explore other solutions? I'm glad to provide more details about the usecase, my project is documented at github.com/piwicode/… (BTW Should the blue line be $q=1$?) $\endgroup$
    – piwicode
    Commented Feb 4 at 22:25

Your Answer

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

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