Fourier Transform Distance¶

Introduction¶

Fourier Transform Distance (FTD) is a frequency-domain approach to measuring similarity between time series by comparing their spectral components. This distance metric transforms time series data into the frequency domain using the Discrete Fourier Transform (DFT), allowing comparison of sequences based on their frequency characteristics rather than their time-domain representations. This approach is particularly effective for detecting similarities in periodic patterns and is robust to phase shifts and noise.

Mathematical Definition¶

For two time series X = (x₁, …, xₙ) and Y = (y₁, …, yₙ), the Fourier Transform Distance is defined as:

\[FTD(X,Y) = \sqrt{\sum_{k=0}^{N-1} |F_X(k) - F_Y(k)|^2}\]

where: - \(F_X(k)\) and \(F_Y(k)\) are the Discrete Fourier Transforms of X and Y respectively - \(N\) is the number of frequency components considered - \(F_X(k) = \sum_{n=0}^{N-1} x_n e^{-2\pi i kn/N}\)

The DFT components are complex numbers representing: - Magnitude: \(|F(k)| = \sqrt{Re(F(k))^2 + Im(F(k))^2}\) - Phase: \(\phi(k) = \arctan(Im(F(k))/Re(F(k)))\)

Properties¶

FTD exhibits several important characteristics:

Key Properties: - Frequency domain comparison - Phase shift invariant (when using magnitude spectrum) - Linear time complexity using FFT - Preserves Parseval’s theorem - Handles periodic patterns effectively
Advantages: - Robust to noise - Effective for periodic data - Computationally efficient - Captures frequency components - Allows dimension reduction
Considerations: - Requires equal-length sequences - May need padding or truncation - Sensitive to sampling rate - Best suited for periodic patterns

Academic References¶

Agrawal, R., Faloutsos, C., & Swami, A. (1993). “Efficient Similarity Search in Sequence Databases.” Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, 69-84.
Oppenheim, A. V., & Schafer, R. W. (2009). “Discrete-Time Signal Processing.” Prentice Hall.
Rafiei, D., & Mendelzon, A. (2000). “Similarity-Based Queries for Time Series Data.” Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, 13-25.

Use Cases¶

FTD is particularly effective in:

Periodic pattern detection
Signal processing applications
Audio similarity analysis
Vibration analysis
Scientific data comparison
Seasonal pattern detection
Anomaly detection in periodic signals

Implementation Details¶

In the distancia package, FTD is implemented with the following features:

Fast Fourier Transform (FFT) algorithm
Configurable frequency range
Optional preprocessing steps
Support for different distance metrics in frequency domain

Example Usage¶

from distancia import FourierDistance

# Initialize Fourier Distance
ftd = FourierDistance(num_components=None)  # Use all components

# Calculate distance between two time series
distance = ftd.calculate(series1, series2)

# With specific number of components
ftd_reduced = FourierDistance(num_components=10)
distance_reduced = ftd_reduced.calculate(series1, series2)

Complexity Analysis¶

Time Complexity: O(n log n) using FFT
Space Complexity: O(n)

where n is the length of the input sequences.

Parameter Selection¶

Number of Components: - Controls dimensionality reduction - Trade-off between accuracy and computation - Typically 10-20% of sequence length - Can be selected based on energy retention
Preprocessing Options: - Detrending - Normalization - Zero-padding - Window functions (Hamming, Hanning, etc.)

Conclusion¶

Fourier Transform Distance provides a powerful approach to time series comparison by operating in the frequency domain. Its ability to capture periodic patterns and frequency components makes it particularly valuable for applications involving cyclic or periodic data. The use of FFT ensures computational efficiency, while the option to reduce dimensions by selecting fewer frequency components provides flexibility in handling large datasets.

The method’s robustness to noise and phase shifts, combined with its efficient implementation, makes it an excellent choice for applications where frequency content is more relevant than time-domain features. However, users should consider their data’s characteristics, particularly periodicity and sampling rate, when choosing this distance measure.

Note

The selection of appropriate preprocessing steps and the number of frequency components is crucial for optimal performance. Consider the nature of your data and computational requirements when configuring these parameters.