Signal theory 101 : You have some signal that you observe : v ∈ Rⁿ. You have a database of k reference signals you know about vrefₖ ∈ Rⁿ. What you want is to

Signal theory 101 : You have some signal that you observe : v ∈ Rⁿ. You have a database of k reference signals you know about vrefₖ ∈ Rⁿ. What you want is to match the signal you observe to one of the reference signal. This is called template matching : you pick the closest reference signal to the observation : You compute argminₖ distance( v, vrefₖ) This is great but it scales badly with respect to the number of reference signals. So instead of trying to find the closest signal, you try to decompose the signal as a sum of reference signals : You compute argmin over λₖ distance( v, Σₖ λₖvrefₖ) This decomposition is not unique, so you regularize it (if your distance and norm are well picked the following is convex so you can get uniqueness guarantees): You compute argmin over λₖ ( distance( v, Σₖ λₖvrefₖ) + Σₖnorm(λₖ) ) This is called sparse coding. The rest (fft, stft,wavelet transform,...) are mathematical tricks (called transforms) to compute this more efficiently by choosing certain special reference signals (picking a basis). The first math trick to be aware is (a-b)²= a²+b²-2ab : This is the bridge that relate what is called correlation to the distance : for vector a,b ∈ Rⁿ : Σₖ(aₖ-bₖ)² = Σₖaₖ²+ Σₖbₖ²- 2* Σₖ(aₖbₖ) With judicious pick the first two sums Σₖaₖ² and Σₖbₖ² can be made irrelevant to the minimization problem because they are either constant by construction (normalized to 1) or don't depend on the variable that we minimized over. This trick applies both to template matching and sparse coding (even though there is more terms they all simplify). If the two first terms can be made to disappear then minimizing the distance has the same result as maximizing the correlation. Then you have a bunch of sliding sums and recursive summation tricks which all depend on the specific shape of your data. Notably with fft there is the well known butterfly algorithm. A century of techniques and theory since Hilbert have been devoted to finding various smart variants. And they allow you to compute this decomposition fast usually in O(n) or O(nlog(n)). The alternative to hand-crafted techniques, is learning the reference signals from the data (Sparse dictionary learning). You can also brute-force your way through with deep-learned filter banks. It works better but require more compute, and have less guarantees. It also let you deal with nitty gritty details like missing data and masks.