Fourier Transform
Decomposes any signal into its frequency components.
The Fourier Transform converts a signal from the time or spatial domain into the frequency domain. Every waveform — audio, image, simulation field — can be expressed as a sum of sine waves at different frequencies. This decomposition makes filtering, compression, and analysis tractable. The Fast Fourier Transform (FFT) computes this in O(n log n) rather than O(n²).
Mathematics
F(ω) = ∫ f(t) e^(−iωt) dt
Discrete form:
X[k] = Σ x[n] e^(−i2πkn/N)
Key Facts
- FFT reduces complexity from O(n²) to O(n log n)
- Convolution in spatial domain = multiplication in frequency domain
- JPEG and MP3 compression both rely on frequency transforms
- Used in MRI reconstruction to recover images from scanner data
Where It Appears
- Audio analysis and compression (MP3, AAC)
- Image compression (JPEG)
- Signal filtering and noise removal
- MRI and CT scan reconstruction
- Fluid simulation spectral methods
- Gravitational wave detection