The Art of Compression: Fourier Transforms Meets Machine Learning#

1.1 What Is Compression?#

In its simplest form, data compression aims to reduce the amount of data required to represent a piece of information. For example, if you have a 5 MB image file, you can potentially compress it into a 1 MB file without losing noticeable visual quality (lossy compression). Alternatively, you can compress it into a smaller size and later recover the exact original file (lossless compression).

Compression typically involves:

• Removing redundancies.
• Exploiting the structure of the data.
• Sacrificing some aspects of the data (in lossy compression) for the sake of efficiency.

1.2 Lossy vs. Lossless Compression#

There are two main categories of compression:

1. Lossless Compression: This type of compression always allows for perfect reconstruction of the original data. The PNG image format and ZIP file format are examples of lossless methods.
2. Lossy Compression: Most widely adopted for images (JPEG), audio (MP3), and videos, lossy compression discards some information deemed non-critical to human perception or usage scenarios. The trade-off is a smaller file size versus slight degradation in quality.

Both these categories often depend on transforms—like the Fourier, Discrete Cosine Transform (DCT), or wavelet transforms—to represent data in a more compressible form.

1.3 Entropy and Redundancy#

A fundamental concept in compression is entropy, which measures the average amount of information per data point. Data with lower entropy (high redundancy) is easier to compress, while data with higher entropy (low redundancy) is more challenging.

To illustrate, consider text files with valid English sentences. Because English letters and words appear with specific frequencies, it’s possible to compress them effectively. Conversely, a random string of characters is more difficult to compress because it lacks patterns and predictability.

2.1 Overview#

The Fourier transform (FT) is a mathematical technique to decompose a function—or in practice, a signal—into its constituent frequencies. In essence, it maps a signal from the time (or spatial) domain to the frequency domain.

For a continuous variable ( t ), the continuous Fourier transform ( \mathcal{F}{x(t)} ) is given by:

[ X(\omega) = \int_{-\infty}^{\infty} x(t) e^{-j \omega t} , dt. ]

However, in most real-world applications, we use the discrete Fourier transform (DFT) because our data is captured at discrete time intervals and stored in digital form.

2.2 Discrete Fourier Transform (DFT)#

The discrete Fourier transform of a sequence ( x_n ) with length ( N ) is defined by:

[ X_k = \sum_{n=0}^{N-1} x_n , e^{-\frac{2\pi j}{N} kn}, \quad k = 0, 1, \ldots, N-1. ]

The inverse DFT:

[ x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k , e^{\frac{2\pi j}{N} kn}. ]

2.3 Fast Fourier Transform (FFT)#

The FFT is an algorithmic implementation that computes the DFT in a more efficient manner. Without going into the details of butterfly diagrams and divide-and-conquer approaches, it suffices to say that FFT reduces the computational complexity from ( O(N^2) ) to ( O(N \log N) ). This computational advantage makes it feasible to use Fourier transforms in practical contexts like audio and image processing, especially on large datasets.

2.4 Frequency Domain Representation#

One critical reason why Fourier transforms are so popular in compression is the nature of frequency domain representations. Many natural signals—like voice recordings or images—can be represented sparsely in the frequency domain. For instance, if most of the signal’s energy is concentrated in a small set of frequency components, you can store (or transmit) just those significant components and ignore the rest, drastically reducing the data size.

Here is a simple Python snippet to demonstrate how we might compute an FFT on a one-dimensional signal and observe its frequency coefficients.

1
import numpy as np
2
import matplotlib.pyplot as plt
3

4
# Generate a sample signal
5
fs = 1000  # Sampling rate
6
t = np.linspace(0, 1, fs, endpoint=False)
7
# Create a signal with 50 Hz and 120 Hz components
8
freq1, freq2 = 50, 120
9
signal = 0.7 * np.sin(2 * np.pi * freq1 * t) + 0.3 * np.sin(2 * np.pi * freq2 * t)
10

11
# Compute FFT
12
fft_values = np.fft.fft(signal)
13
freqs = np.fft.fftfreq(len(signal), 1/fs)
14

15
# Plot
16
plt.figure(figsize=(10, 4))
17
plt.subplot(1, 2, 1)
18
plt.plot(t, signal)
19
plt.title("Time Domain Signal")
20

21
plt.subplot(1, 2, 2)
22
plt.stem(freqs, np.abs(fft_values), use_line_collection=True)
23
plt.title("Frequency Domain Signal")
24
plt.tight_layout()
25
plt.show()

In typical compression workflows, the next step would be to threshold or quantize these frequency coefficients before storage or transmission.

3.1 Step-by-Step#

1. Load or Generate Data: We start with a 1D or 2D dataset (e.g., an audio file or an image).
2. Apply FFT: Compute the FFT (or variations like DCT or wavelet) to get frequency coefficients.
3. Thresholding: Remove or reduce the amplitude of insignificant coefficients.
4. Quantization: Map remaining coefficients to discrete levels for efficient storage.
5. Entropy Coding: Optionally apply a lossless approach (like Huffman or arithmetic coding) to further reduce the size.
6. Decompression: Reverse the process—decode, dequantize, invert transform, and reconstruct the signal/data.

3.2 Simple Compression with Thresholding#

Below is a minimal example demonstrating a very basic compression strategy using thresholding in the Fourier domain:

1
import numpy as np
2

3
def simple_fourier_compress(signal, threshold_ratio=0.1):
4
    """
5
    Compresses the signal by zeroing out small Fourier coefficients.
6
    threshold_ratio is the fraction of largest coefficients to keep.
7
    """
8
    # Compute FFT
9
    fft_values = np.fft.fft(signal)
10

11
    # Determine how many coefficients to keep
12
    n_coeffs = len(fft_values)
13
    num_to_keep = int(n_coeffs * threshold_ratio)
14

15
    # Find the indices of the largest coefficients in magnitude
16
    mag = np.abs(fft_values)
17
    sorted_indices = np.argsort(mag)[::-1]  # descending order
18
    keep_indices = sorted_indices[:num_to_keep]
19

20
    # Zero out all but the kept coefficients
21
    compressed_fft = np.zeros(n_coeffs, dtype=complex)
22
    compressed_fft[keep_indices] = fft_values[keep_indices]
23

24
    return compressed_fft
25

26
def simple_fourier_decompress(compressed_fft):
27
    """
28
    Decompresses the signal by applying the inverse FFT.
29
    """
30
    return np.fft.ifft(compressed_fft)
31

32
# Example usage
33
if __name__ == "__main__":
34
    fs = 1000
35
    t = np.linspace(0, 1, fs, endpoint=False)
36
    signal = 0.7 * np.sin(2*np.pi*50*t) + 0.3 * np.sin(2*np.pi*120*t)
37

38
    compressed = simple_fourier_compress(signal, threshold_ratio=0.1)
39
    reconstructed_signal = simple_fourier_decompress(compressed)
40

41
    # Evaluate error
42
    mse = np.mean((signal - reconstructed_signal.real)**2)
43
    print(f"Mean Squared Error after compression: {mse}")

This simplistic approach demonstrates the core idea: keep only the more significant frequency components. Despite its popularity, real-world applications typically involve additional steps like better quantization strategies, entropy coding, or more advanced transforms (like wavelets).

4.1 Historical Context#

Machine learning has revolutionized many data-driven tasks, including image recognition, natural language processing, and voice assistants. A fascinating extension of ML’s ability to learn compact representations of data looms in the field of compression. Neural networks, in particular, excel at discovering nonlinear patterns and correlations in signals or images.

4.2 Common ML-based Compression Approaches#

1. Autoencoders: A neural network trained to reconstruct its inputs. The bottleneck layer (latent space) captures a compressed representation.
2. Variational Autoencoders (VAEs): A probabilistic take on autoencoders that learns both a latent space distribution and a reconstruction mechanism.
3. Generative Adversarial Networks (GANs): Employed in compression tasks to generate realistic outputs from compressed representations.
4. Neural Image or Neural Video Codecs: Specialized neural networks optimized for compressing images and videos.

4.3 Why Fourier + ML?#

At first glance, it might seem that either you use transforms (like Fourier or wavelets) or you use end-to-end neural networks. But in practice, combining frequency-domain insights with ML can reap benefits in:

• Feature Extraction: Fourier transforms can serve as a powerful feature extractor for neural nets.
• Dimensionality Reduction: Frequency-domain data can be extremely sparse.
• Efficiency in Training: Less data to feed or fewer parameters to learn.
• Enhanced Reconstruction Quality: ML can fine-tune the approximation around the edges or details lost through transform-based thresholding.

5.1 Hybrid Framework#

A hybrid compression pipeline might look like this:

1. Input: Audio or image data.
2. Fourier Transform: Convert data to frequency domain.
3. Coefficient Selection/Encoding: Keep dominant frequency components or apply advanced thresholding.
4. ML-based Enhancement: Feed the compressed representation into a neural network (e.g., an autoencoder) for further dimensionality reduction or fine detail encoding.
5. Entropy Coding: Optionally apply techniques like arithmetic coding on final compressed output.

5.2 Example with Autoencoder#

Below is a conceptual Python-like pseudo-code snippet illustrating a combined approach:

1
import numpy as np
2
from tensorflow import keras
3
from tensorflow.keras import layers
4

5
# Simple autoencoder architecture
6
def create_autoencoder(input_dim, compressed_dim):
7
    # Encoder
8
    input_layer = keras.Input(shape=(input_dim,))
9
    encoded = layers.Dense(128, activation='relu')(input_layer)
10
    encoded = layers.Dense(compressed_dim, activation='relu')(encoded)
11

12
    # Decoder
13
    decoded = layers.Dense(128, activation='relu')(encoded)
14
    decoded = layers.Dense(input_dim, activation='linear')(decoded)
15

16
    autoencoder = keras.Model(input_layer, decoded)
17
    encoder = keras.Model(input_layer, encoded)
18

19
    encoded_input = keras.Input(shape=(compressed_dim,))
20
    decoder_layer = autoencoder.layers[-1]
21
    for layer in autoencoder.layers[-2::-1]:
22
        if layer == input_layer:
23
            break
24
        decoded_input = layer(decoded_input)  # This is conceptual, actual usage differs
25
    # This snippet is simplified for demonstration
26

27
    return autoencoder, encoder
28

29
def fourier_based_autoencoder_compress(signal, autoencoder, threshold_ratio=0.1):
30
    # Fourier transform
31
    fft_values = np.fft.fft(signal)
32

33
    # Threshold
34
    mag = np.abs(fft_values)
35
    n_coeffs = len(fft_values)
36
    num_to_keep = int(n_coeffs * threshold_ratio)
37
    sorted_indices = np.argsort(mag)[::-1]
38
    keep_indices = sorted_indices[:num_to_keep]
39
    compressed_fft = np.zeros(n_coeffs, dtype=complex)
40
    compressed_fft[keep_indices] = fft_values[keep_indices]
41

42
    # Flatten real and imaginary parts for autoencoder input
43
    real_part = np.real(compressed_fft)
44
    imag_part = np.imag(compressed_fft)
45
    combined = np.concatenate([real_part, imag_part])
46

47
    # Encode with autoencoder
48
    combined = combined.reshape((1, -1))
49
    latents = autoencoder.predict(combined)
50

51
    return latents, keep_indices
52

53
# This snippet is for illustrative purposes and won't run as-is.
54
# Actual usage requires a properly structured encoder and decoder.

Note that this example is heavily simplified. In real implementations:

• We carefully handle the dimensionalities.
• We might use 2D transforms for images.
• The neural network architecture must be tailored to match the data format.
• We need a corresponding decoder path that reconstructs from the latent space.

5.3 Summary Table of the Process#

6.1 Audio Compression#

Traditional audio codecs perform transform-based compression (e.g., MP3 using MDCT). Neural networks can either act as an additional layer for more refined compression or replace parts of the pipeline altogether. Advanced ML-based codecs can yield better perceptual quality at comparable or lower bitrates.

6.2 Image Compression#

JPEG relies on the DCT to transform 8×8 pixel blocks into frequency coefficients, which then get quantized. Neural networks, especially autoencoders, are capable of learning more specialized transforms that adapt to the statistical regularities of natural images. Combining them with classical transforms can further leverage the broad coverage of frequency components.

6.3 Video Compression#

Because of motion and temporal redundancies, video compression is more complex, typically handled by complex standards like H.264 or H.265. Neural networks have shown promise in capturing motion vectors more effectively, and Fourier transforms provide potential for additional spatio-temporal filtering.

6.4 Medical Imaging#

Fourier transforms are integral to MRI (Magnetic Resonance Imaging), which acquires data in the frequency domain. Machine learning can be applied to partially sampled k-space data (the MRI frequency domain representation) to reconstruct high-quality images with fewer samples, effectively compressing the acquisition process—this relates to the concept of compressive sensing.

7.1 Compressive Sensing#

Compressive sensing takes advantage of the fact that many signals have sparse representations in certain domains (like Fourier or wavelet). Instead of fully sampling the entire signal and then compressing, compressive sensing designs the acquisition process to capture fewer samples from the start. Reconstruction is done through optimization or ML-based algorithms that exploit sparsity or learned priors.

A typical compressive sensing workflow:

1. Undersampled Acquisition: Fewer samples than Nyquist-Shannon would dictate.
2. Sparse Prior: Knowledge that the signal has a sparse representation in some domain.
3. Reconstruction Algorithm: Solve an optimization problem (e.g., L1 minimization) or use a deep network to guess the missing elements subject to sparsity.

7.2 Dictionary Learning#

Instead of using fixed transforms like FFT or DCT, you can learn an optimal transform—often called a dictionary—that best represents your dataset. Machine learning algorithms like K-SVD or dictionary-based autoencoders can adapt the transform to match the data’s specific structure, achieving higher compression ratios or better reconstruction quality than off-the-shelf transforms.

7.3 Wavelet Transforms#

Fourier transforms capture global frequency information, which can sometimes be less ideal for localized features. Wavelets address this by offering time-frequency localization. Many modern image compression standards (like JPEG2000) use wavelets. Wavelet transforms can also be integrated into ML architectures—similar to how Fourier-based approaches are used.

7.4 Discrete Cosine Transform (DCT)#

The DCT is closely related to the discrete Fourier transform but focuses on real values and specific boundary conditions, making many signals (especially images) more compact. JPEG uses DCT extensively, and many ML-based image compression pipelines still incorporate DCT blocks as a building mechanism.

8.1 Workflow#

1. Acquire an image (e.g., a grayscale 256×256 image).
2. Apply 2D DFT: Convert the entire image to the frequency domain.
3. Threshold or Quantize: Keep the top X% of coefficients based on magnitude.
4. Construct a 2D array that holds these coefficients�?magnitudes and phases.
5. Process the array with a convolutional autoencoder to further compress the data.
6. Use a learned decoder to reconstruct the frequency-domain representation.
7. Apply the inverse DFT to reconstruct the final image.

8.2 Sample Code (Conceptual)#

1
import numpy as np
2
import cv2
3
from tensorflow import keras
4
from tensorflow.keras import layers
5

6
# Assume 'input_image' is a 2D numpy array (grayscale)
7
def apply_2d_dft(image):
8
    return np.fft.fft2(image)
9

10
def threshold_dft(dft_image, threshold_ratio=0.1):
11
    # Flatten
12
    flat_dft = dft_image.flatten()
13
    mags = np.abs(flat_dft)
14
    sorted_indices = np.argsort(mags)[::-1]
15
    num_to_keep = int(len(flat_dft) * threshold_ratio)
16
    keep_indices = sorted_indices[:num_to_keep]
17

18
    thresholded_dft = np.zeros_like(flat_dft, dtype=complex)
19
    thresholded_dft[keep_indices] = flat_dft[keep_indices]
20
    return thresholded_dft.reshape(dft_image.shape)
21

22
def inverse_2d_dft(dft_image):
23
    return np.fft.ifft2(dft_image).real
24

25
# Simple conv autoencoder structure (very conceptual)
26
def create_conv_autoencoder(input_shape):
27
    encoder_input = keras.Input(shape=input_shape)
28

29
    # Encoder
30
    x = layers.Conv2D(16, (3, 3), activation='relu', padding='same')(encoder_input)
31
    x = layers.MaxPooling2D((2, 2), padding='same')(x)
32
    x = layers.Conv2D(8, (3, 3), activation='relu', padding='same')(x)
33
    encoded = layers.MaxPooling2D((2, 2), padding='same')(x)
34

35
    # Decoder
36
    x = layers.Conv2D(8, (3, 3), activation='relu', padding='same')(encoded)
37
    x = layers.UpSampling2D((2, 2))(x)
38
    x = layers.Conv2D(16, (3, 3), activation='relu', padding='same')(x)
39
    x = layers.UpSampling2D((2, 2))(x)
40
    decoded = layers.Conv2D(1, (3, 3), activation='sigmoid', padding='same')(x)
41

42
    autoencoder = keras.Model(encoder_input, decoded)
43
    return autoencoder
44

45
# Example usage
46
def hybrid_compress_image(input_image, threshold_ratio=0.1):
47
    # 1. Apply DFT
48
    dft_image = apply_2d_dft(input_image)
49
    # 2. Threshold
50
    thresholded = threshold_dft(dft_image, threshold_ratio=threshold_ratio)
51
    # 3. Prepare for autoencoder - separate magnitude/phase or real/imag
52
    # For simplicity, let's just take magnitude
53
    mag = np.abs(thresholded)
54
    mag = mag / np.max(mag)  # Normalize
55

56
    # Reshape to a suitable input for the autoencoder
57
    mag_input = mag.reshape(mag.shape[0], mag.shape[1], 1)
58
    mag_input = np.expand_dims(mag_input, axis=0)  # batch dimension
59

60
    autoencoder = create_conv_autoencoder((mag.shape[0], mag.shape[1], 1))
61
    autoencoder.compile(optimizer='adam', loss='mse')
62

63
    # In practice: train autoencoder offline on many images
64
    # Here: a single pass demonstration
65
    autoencoder.fit(mag_input, mag_input, epochs=1, verbose=0)
66

67
    compressed_mag = autoencoder.predict(mag_input)
68

69
    # 4. Reverse steps (conceptual)
70
    compressed_mag = compressed_mag[0, :, :, 0]
71
    compressed_mag = compressed_mag * np.max(np.abs(thresholded))  # denormalize
72
    # We might combine phase info here in real use cases
73

74
    # 5. Inverse DFT
75
    # This part is incomplete since we only used magnitude in the example
76
    # A more realistic example must store phase or real/imag parts
77
    reconstructed_dft = compressed_mag * np.exp(1j * np.angle(thresholded))
78
    final_image = inverse_2d_dft(reconstructed_dft)
79

80
    return final_image

This code is primarily conceptual and should not be considered production-ready. However, it illustrates the potential synergy between a transform-based approach and a neural model.