This repository is the official implementation of Fast Multidimensional Partial Fourier Transform with Automatic Hyperparameter Selection (KDD 2024). The codes for FFTW, MKL, PFT, and Pruned FFT are also included in src/.

Overview

Given a multidimensional array, how can we optimize the computation process for a part of Fourier coefficients? Discrete Fourier transform plays an overarching role in various data mining tasks. Recent interest has focused on efficiently calculating a small part of Fourier coefficients, exploiting the energy compaction property of real-world data. Current methods for partial Fourier transform frequently encounter efficiency issues, yet the adoption of pre-computation techniques within the PFT algorithm has shown promising performance. However, PFT still faces limitations in handling multidimensional data efficiently and requires manual hyperparameter tuning, leading to additional costs. In this paper, we propose Auto-MPFT (Automatic Multidimensional Partial Fourier Transform), which efficiently computes a subset of Fourier coefficients in multidimensional data without the need for manual hyperparameter search. Auto-MPFT leverages multivariate polynomial approximation for trigonometric functions, generalizing its domain to multidimensional Euclidean space. Moreover, we present a convex optimization-based algorithm for automatically selecting the optimal hyperparameter of Auto-MPFT. We provide a rigorous proof for the explicit reformulation of the original optimization problem of Auto-MPFT, demonstrating the process that converts it into a well-established unconstrained convex optimization problem. Extensive experiments show that Auto-MPFT surpasses existing partial Fourier transform methods and optimized FFT libraries, achieving up to 7.6x increase in speed without sacrificing accuracy. In addition, our optimization algorithm accurately finds the optimal hyperparameter for Auto-MPFT, significantly reducing the cost associated with hyperparameter search.

The implementation requires the following libraries.

• mkl.h
• mkl_dfti.h
• ipp.h
• ipps.h
• fftw3.h

We provide the synthetic datasets used in our experiments at here. The real-world datasets are available at Cityscapes, ADE20K, DF2K, RiceLeaf, and Bird.

If you use this code, please cite the following papers.

@inproceedings{park2024fast,
 title={Fast multidimensional partial fourier transform with automatic hyperparameter selection},
 author={Park, Yong-chan and Kim, Jongjin and Kang, U},
 booktitle={Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
 pages={2328--2339},
 year={2024}
}
@inproceedings{park2021fast,
 title={Fast and accurate partial fourier transform for time series data},
 author={Park, Yong-chan and Jang, Jun-Gi and Kang, U},
 booktitle={Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery \& Data Mining},
 pages={1309--1318},
 year={2021}
}