5.1. Similarity

In this chapter, we’ll develop the concepts of the frequency domain and the Discrete Fourier Transform from first principles. The underlying idea throughout is that one can equivalently represent a signal by its sequence of sample values, or as a combination of sinusoids. The sequence of sample values, which we’ve been calling \(x[n]\) is known as the time-domain representation because the variable \(n\) that we change to view the entire signal corresponds to time (sample index). The alternate representation that we’ll develop in this chapter will instead vary the frequency of different sinusoids, and not depend explicitly on time.

To make this all work, we’ll need to develop a way to convert from the time domain to the frequency domain. Our basic strategy will be to compare the input signal \(x[n]\) to a collection of fixed reference signals. The result of these comparisons will be a collection of similarity measurements, which (loosely speaking) measure “how much” of each reference signal is in \(x[n]\).

5.1.1. Measuring similarity

One could imagine many different ways to compare two signals \(\blue{x[n]}\) and \(\red{y[n]}\).

The definition of similarity that we’ll use is to go sample-by-sample, multiplying \(\blue{x[n]} \cdot \red{y[n]}\), and summing up the results to produce a single number \(\purple{S}\). In equations, this looks as follows:

(5.1)\[\purple{S(x, y)} = \sum_{n=0}^{N-1} \blue{x[n]} \cdot \red{y[n]}\]

or equivalently in code:

def similarity(x, y):
    '''Compute similarity between two signals x and y 
    
    Parameters
    ----------
    x, y : np.ndarrays of equal length
    
    Returns
    -------
    S : real number
        The similarity between x and y
    '''
    
    # Initialize similarity to 0
    S = 0
    
    # Accumulate the sample-wise products
    N = len(x)
    for n in range(N):
        S = S + x[n] * y[n]
        
    return S

Fig. 5.1 provides a demonstration of this similarity calculation. Two signals \(\blue{x[n]}\) (a triangle wave, top plot) and \(\red{y[n]}\) (a cosine wave, center plot) with \(N=32\) samples are compared by summing the sample-by-sample product (\(\blue{x[n]} \cdot \red{y[n]}\), bottom plot).

Each step of the loop (equivalently, term of the summation) is calculated independently, and the height of the bar on the right plot shows the running total. When the loop is finished (we’ve summed all samples \(n=0,1,\dots,31\)), we’ll have computed the total similarity \(\purple{S}\).

Once Loop Reflect

Fig. 5.1 Similarity \(\purple{S}\) between signals \(\blue{x}\) and \(\red{y}\) is computed by summing the element-wise product of their samples \(\blue{x[n]} \cdot \red{y[n]}\).

This process might feel a bit like convolution, and the equations do look similar and involve many of the same ingredients. However, there are some key differences:

1. Convolution can be computed between any two signals. Similarity is only defined for two signals of exactly the same length.

2. Convolution involves shifting (delaying) one signal several times to produce the output. Similarity does not use shifting.

3. Convolution produces an output signal of multiple samples. Similarity produces a single number.

5.1.2. Interpreting similarity

Note that the values of \(\blue{x[n]}\) and \(\red{y[n]}\) can be either positive or negative, and as a result, so can the similarity value \(\purple{S(x, y)}\). To build some intuition for how this similarity behaves, it can be helpful to imagine situations which could lead to different values of \(\purple{S}\): large positive, large negative, or near zero.

Whenever the signs of \(\blue{x[n]}\) and \(\red{y[n]}\) agree, the contribution to the total sum \(\purple{S}\) is positive. If this happens often (over many sample indices \(n\)), then \(\purple{S}\) will consist primarily of positive contributions, and therefore be a large positive number. This is the case in the example above, where the signs of the two signals are generally in agreement, leading to the high similarity score.

Likewise, when the signs disagree (e.g., \(\blue{x[n]} > 0 > \red{y[n]}\)), the contribution to the sum is negative. Again, if this happens often, then \(\purple{S}\) will consist primarily of negative contributions, and be a large negative number.

If neither of these situations occur, then the signs of \(\blue{x[n]}\) and \(\red{y[n]}\) agree and disagree comparably often. The positive and negative contributions will be (approximately) balanced, so the total \(\purple{S}\) will be near zero.

An example of each of these three cases is demonstrated in the figure below. It’s important to remember that these cases are meant as qualitative examples, and the behavior of \(\purple{S}\) will depend also on the magnitude of the sample values, not just their signs.

Fig. 5.2 Top: two waves of the same frequency and small phase difference produce a high similarity score \(\purple{S=21.7}\). Middle: two waves with maximal phase difference (\(pi\)) produce a minimal similarity score \(\purple{S=-25.0}\). Bottom: two waves of different frequencies can produce a similarity score of \(\purple{S=0}\).

5.1.3. Summary

The definition of similarity that we’ve seen here can be applied to any pair of signals \(x\) and \(y\), as long as they have the same length.

In the context of the Fourier transform, we’re given a signal \(x\), and the transform will be defined by the similarity scores produced by comparing \(x\) to a collection of signals. Our next step is to determine what that collection will be.