Steerable Discrete Fourier Transform

Giulia Fracastoro, Enrico Magli

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, 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.

Introduction

The Discrete Fourier Transform (DFT) is a cornerstone of digital signal processing, essential for applications ranging from image compression to wireless communications. However, the standard DFT is inherently rigid, with fixed basis vectors. Recent advancements in signal analysis have highlighted the utility of "steerable" or directional transforms, which can adapt their geometric parameters to better represent specific signal features. This research introduces the Steerable Discrete Fourier Transform (SDFT), a novel generalization that allows the transform basis to be "rotated" via a continuous parameter.

Methodology: A Graph Signal Processing Perspective

The SDFT is derived by bridging traditional signal processing with Graph Signal Processing (GSP). By treating signals as existing on specific graph structures, the DFT can be re-envisioned as an eigendecomposition of a graph Laplacian.

  • 1D Signals: A 1D signal is modeled on a cycle graph (a ring of nodes). The standard DFT matrix rows correspond to the eigenvectors of this graph's Laplacian.
  • 2D Signals: A 2D signal is modeled on a toroidal grid graph, where a 2D grid wraps around both horizontally and vertically.
A toroidal grid graph used to model 2D signals in the GSP framework.

The core innovation lies in exploiting eigenvalue multiplicity. In these graph structures, many eigenvalues are repeated. Linear algebra dictates that any rotation of eigenvectors within the same eigenspace remains a valid set of eigenvectors. The SDFT introduces a rotation matrix $R(\theta)$ that acts on these pairs of eigenvectors. By adjusting the angle $\theta$, the basis is "steered." When $\theta = 0$, the transform reduces to the standard DFT.

Key Insights and Unified Framework

The SDFT serves as a "parent" transform, unifying several classical signal processing tools. By selecting specific rotation angles, the SDFT becomes equivalent to the Fourier Sine Transform, the Fourier Cosine Transform, or the Hilbert Transform.

The steering mechanism: a rotation in the complex plane allows for continuous adjustment of the transform basis.

Key advantages of this framework include:

  • Symmetry Breaking: Unlike the standard DFT, which maintains strict symmetry for real-valued signals, the SDFT can separate real and imaginary components into distinct coefficients (e.g., at $\theta = \pi/4$).
  • Geometric Adaptation: In 2D, the rotation corresponds to Euclidean space rotations, allowing the transform to align with directional textures in images.
  • Encryption Potential: The continuous parameter $\theta$ can act as a secret key, as the original signal is difficult to reconstruct without the exact rotation value.

Results and Implementation

The SDFT maintains the energy-preservation properties of the original DFT due to its orthonormal rotation, making it suitable for compression. It can be implemented efficiently by applying rotation matrices to the output of a standard Fast Fourier Transform (FFT). Preliminary results demonstrate that the 1D-SDFT can perfectly extract even or odd signal components through simple filtering.

Conclusion and Future Work

While this work establishes the mathematical foundation of the SDFT, future research will focus on extensive benchmarking against other directional transforms like Curvelets. Potential applications include array signal processing, phase retrieval, and medical imaging (MRI), where steerable bases can provide significant performance gains.

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, 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},
}
Figure