Steerable Discrete Fourier Transform

Giulia Fracastoro, Enrico Magli

TL;DR

The Steerable Discrete Fourier Transform (SDFT) is a novel generalization of the standard DFT that allows the transform basis to be "rotated" via a continuous parameter. By leveraging Graph Signal Processing, the authors show that the DFT is just one specific instance of a broader family of transforms that includes the Hilbert, Sine, and Cosine transforms.

What Problem Does This Paper Address?

The Discrete Fourier Transform (DFT) is the "Swiss Army knife" of digital signal processing, used in everything from JPEG compression to wireless communications. However, the standard DFT is rigid—its basis vectors are fixed. In recent years, researchers have found great success with "steerable" or directional transforms (like the steerable Discrete Cosine Transform), which can adapt their geometric parameters to better match the features of a specific signal or image.

The challenge addressed here is: Can we make the DFT steerable? While generalizations like the Fractional Fourier Transform exist, they often represent rotations in the time-frequency plane. This paper seeks a way to steer the DFT basis itself by looking at it through the lens of Graph Signal Processing (GSP).

Methods

The authors bridge the gap between traditional signal processing and GSP by treating signals as existing on specific graph structures:

  • 1D Case: A 1D signal is viewed as a signal on a cycle graph (a ring of nodes). The rows of a standard DFT matrix are actually the eigenvectors of the Laplacian matrix of this cycle graph.
  • 2D Case: A 2D signal is viewed as a signal on a toroidal grid graph (a 2D grid that wraps around like a donut).

The "secret sauce" of this paper lies in eigenvalue multiplicity. In these specific graphs, many eigenvalues are repeated (they have a multiplicity of 2, 4, or even 8). In linear algebra, if an eigenvalue is repeated, any rotation of its corresponding eigenvectors is also a valid eigenvector.

The authors define the SDFT by introducing a rotation matrix $R(\theta)$ that acts on these pairs of eigenvectors. By changing the angle $\theta$, you "steer" the basis. When $\theta = 0$, you get the standard DFT. When you change $\theta$, you get a new, valid graph transform that maintains the energy-preservation properties of the original DFT but changes how the signal's information is distributed across the coefficients.

Datasets

As a theoretical paper focused on transform design, it does not use large-scale external datasets like ImageNet. Instead, the authors use:

  • Synthetic 1D signals: To demonstrate how the SDFT can separate even and odd components.
  • Mathematical Proofs: To establish the relationship between the SDFT and other classical transforms.

Key Insights and Ideas

  • Symmetry Breaking: For real-valued signals, the standard DFT has a strict symmetry ($x_k = x^*_{N-k}$). The SDFT can "break" this symmetry. For example, at a rotation of $\pi/4$, the real and imaginary parts of the signal are completely separated into different coefficients.
  • A Unified Framework: The authors prove that the SDFT is a "parent" transform. By choosing specific angles, the SDFT becomes equivalent to the Fourier Sine Transform, the Fourier Cosine Transform, or the Hilbert Transform.
  • Geometric Steering in 2D: In the 2D case, the rotation corresponds to a rotation in the two-dimensional Euclidean space, allowing the transform to adapt to the directional textures of an image.
  • Encryption Potential: Because the rotation angle $\theta$ can be any real number, it can serve as a continuous "secret key." A signal transformed with a specific $\theta$ is difficult to reconstruct without knowing that exact parameter.

Key Results

  • Component Separation: The paper demonstrates that a 1D-SDFT with $\theta = \pi/4$ can perfectly extract the even or odd components of a signal using a simple filtering operation.
  • Energy Preservation: Because the rotation is orthonormal, the SDFT preserves the total energy of the signal, making it suitable for compression and reconstruction tasks.
  • Computational Efficiency: The authors note that since the SDFT is a rotation applied to the output of a standard DFT, it can be implemented efficiently by first using a Fast Fourier Transform (FFT) and then applying the rotation matrices.

Limitations and Future Work

The paper is primarily a mathematical foundation. While it suggests many applications, it does not provide:

  • Extensive Benchmarking: There are no head-to-head comparisons against other directional transforms (like Curvelets or Contourlets) in terms of compression ratios or denoising performance.
  • High-Dimensional Rotations: In the 2D case, eigenvalues can have a multiplicity of 8, implying a rotation in an 8-dimensional space. The authors restricted their study to 2D rotations for "geometrical meaning," leaving the potential of higher-dimensional steering unexplored.

The authors suggest that future work could apply the SDFT to array signal processing, phase retrieval, and Magnetic Resonance Imaging (MRI), where the ability to steer the Fourier basis could offer significant advantages.

Summary updated

Abstract

Directional transforms have recently raised a lot of interest thanks to their numerous applications in signal compression and analysis. In this letter, we introduce a generalization of the discrete Fourier transform (DFT), called steerable DFT (SDFT). Since the DFT is used in numerous fields, it may be of interest in a wide range of applications. Moreover, we also show that the SDFT is highly related to other well-known transforms, such as the Fourier sine and cosine transforms and the Hilbert transforms.
BibTeX
@article{fracastoro2017steerable,
  author = {Giulia Fracastoro and Enrico Magli},
  title = {{Steerable Discrete Fourier Transform}},
  journal = {IEEE Signal Processing Letters},
  year = {2017},
  url = {https://openreview.net/forum?id=C9Hz0EfLBh},
}

Loading related content...

Figure