autocorrelation - What is an AMDF?

The wikipedia page for Average Magnitude Difference Function/Formula (AMDF) appears to be empty. What is an AMDF? What are AMDF's properties? What are AMDF's strengths and weaknesses, as compared to other pitch estimation methods such as autocorrelation?

Answer

I've never seen the word "Formula" with "AMDF". My understanding of the definition of AMDF is

$$ Q_x[k,n_0] \triangleq \frac{1}{N} \sum\limits_{n=0}^{N-1} \Big| x[n+n_0] - x[n+n_0+k] \Big| $$

$n_0$ is the neighborhood of interest in $x[n]$. Note that you are summing up only non-negative terms. So $Q_x[k,n_0] \ge 0$. We call "$k$" the "lag". clearly if $k=0$, then $Q_x[0,n_0]=0$. Also, if $x[n]$ is periodic with period $P$ (and let's pretend for the moment that $P$ is an integer) then $Q_x[P,n_0]=0$ and $Q_x[mP,n_0]=0$ for any integer $m$.

Now even if $x[n]$ is not precisely periodic, or if the period is not precisely an integer number of samples (at the particular sampling rate you are using), we would expect $Q_x[k,n_0] \approx 0$ for any lag $k$ that is close to the period or any integer multiple of the period. In fact, if $x[n]$ is nearly periodic, but the period is not at an integer number of samples, we expect to be able to interpolate $Q_x[k,n_0]$ between integer values of $k$ to get an even lower minimum.

My favorite is not the AMDF but the "ASDF" (guess what the "S" stands for?)

$$ Q_x[k,n_0] \triangleq \frac{1}{N} \sum\limits_{n=0}^{N-1} \big( x[n+n_0] - x[n+n_0+k] \big)^2 $$

Turns out you can do calculus with that because the square function has continuous derivatives, but the absolute value function does not.

Here's another reason i like ASDF better than AMDF. If $N$ is very large and we play a little fast-and-loose with the limits of summation:

$$\begin{align} Q_x[k] & = \frac{1}{N} \left( \sum_n \big( x[n] - x[n+k] \big)^2 \right) \\ & = \frac{1}{N} \left( \sum_n (x[n])^2 + \sum_n (x[n+k])^2 - 2 \sum_n x[n] x[n+k] \right) \\ & = \frac{1}{N} \sum_n (x[n])^2 + \frac{1}{N}\sum_n (x[n+k])^2 - \frac{2}{N} \,\sum_n x[n] x[n+k] \\ & = \overline{x^2[n]} + \overline{x^2[n]} - 2\, R_x[k] \\ & = 2 \left( \overline{x^2[n]} - R_x[k] \right) \\ \end{align}$$

where

$$\begin{align} R_x[k] & \triangleq \frac{1}{N} \sum_n x[n] x[n+k] \\ & = \overline{x^2[n]} - \tfrac{1}{2} Q_x[k] \\ & = R_x[0] - \tfrac{1}{2} Q_x[k] \\ \end{align}$$

is normally identified as the "autocorrelation" of $x[n]$.

So we expect the autocorrelation function to be an upside-down (and offset) replica of the ASDF. Wherever the autocorrelation peaks is where the ASDF (and usually also the AMDF) has a minimum.