CS Paper Radar

On the Real Part of Butterfly Factorizations, with Application to Fast Transforms

Ma{ë}l Chaumette, R{é}mi Gribonval, Elisa Riccietti

eess.SP ·submitted 2026-10-05 16:00 UTC · v1

Abstract

Fast transforms such as the Discrete Cosine Transform can be expressed as the real part of a product of complex-valued structured sparse matrices known as Kronecker-sparse factors. More generally, products of such structured sparse matrices appear in square dyadic butterfly and monarch matrices, which are known to represent many fast transforms efficiently. Yet, it has remained unclear whether taking the real or the imaginary part of such products preserves this structure. In this letter, we give a condition on the factors to ensure that the structure is preserved. This condition is satisfied in the case of the Discrete Cosine Transform, the Discrete Sine Transform and the Discrete Hartley Transform, allowing us to provide a new representation of these transforms as products of real-valued Kronecker-sparse factors, which opens new avenues for efficient GPU implementations using low-precision numerical format.

Closest papers

Nearest neighbours by meaning across the whole index.

Sparse Integer Fourier Transform and Its Application In Machine Learning

cs.MS cs.LG ·2026-11-16 ·Jinyang Li, Jie Chen
similarity 0.64
Abstract

The Discrete Fourier transform, mainly implemented by Fast Fourier Transform (FFT), has been essential for numerous domains, such as digital signal processing and feature extraction in materials design. However, current FFT methods suffer from extensive non-trivial multiplications and twiddle-factor operations in the big data era. To improve the computational efficiency of FFT, this study proposes Sparse Integer Fourier Transform (SIFT), a method that leverages the fast computing of sparsity and small integers, and applies the Radix-n method to derive an FFT. The 2N-point DFT matrix in Radix-n FFT is decomposed into four sparse integer matrices. A diagonal matrix containing complex twiddle factors is efficiently approximated using an optimization strategy while the remaining matrices retain sparsity and integer entries. For radix-32 FFT, SIFT reduces the estimated arithmetic cost by 75%, with RMSE below $2.3765\times10^{-8}$ and MAPE below 0.01089%. We evaluate frequency extraction in a numerical test and an engineering case. In the numerical test, MAPE and RMSE are below 2.016% and $2.536\times10^{-6}$, respectively. For wind turbine fault diagnosis, SIFT extracts compact spectral features that retain fault information while reducing the classifier's input dimensionality relative to the full time series.

0.23

32-point DFT Approximations Based on Minimal Frobenius Error and DFT Symmetries

eess.SP math.NA ·2026-09-01 ·L. Andrade-Silva, W. A. S. Aleixo, R. J. Cintra
similarity 0.61
Abstract · 10 pages, 2 figures, 5 tables

This work introduces low-complexity, multiplierless approximations for the 32-point discrete Fourier transform. The proposed methods are obtained by minimizing the Frobenius error compared against the DFT matrix over a set of trivial multipliers. A row-wise, symmetry-constrained parameterization is employed to reduce the search space size, rendering the task computationally tractable. The resulting approximations could outperform the reference method in the literature according to energy-based error measurements. A sparse matrix factorization is provided for efficient computation; the arithmetic costs are 152 real additions and 34 bit-shifts only.

0.23

Discrete cosine-sine transform and fast 16-point integer cosine-sine transform low-complexity for video coding

eess.IV ·2026-09-15 ·Lev Hnativ, Yaroslav Luts
publishedunusual similarity 0.58
Abstract · Presented at SPIE Optics + Photonics, Proc. SPIE 13137, Applications of Digital Image Processing XLVII, 1313715 (30 Sept 2024), 13 p.,3 fig

A matrix method for constructing a discrete cosine-sine transform of order N is proposed, upon which discrete and integer cosine-sine transforms of order 16 are constructed. A fast algorithm for computing an integer cosine-sine transform of order-16 with low multiplicative complexity, which is 8.25 times smaller and requires 115% more addition operations compared to the fast discrete cosine-sine transform algorithm, is presented.

0.45

Exact Factorisation and Fast Computation of Invertible Constant-Q Transforms

eess.SP cs.SDeess.ASmath.NA ·2026-09-24 ·Facundo Franchino, Eloi Moliner, Vesa Välimäki
similarity 0.54
Abstract · 5 pages, 2 figures, 2 tables. Submitted to ICASSP 2027

The constant-Q transform (CQT) represents audio on a logarithmic frequency axis. Its nonstationary Gabor formulation is exactly invertible, but the unequal numbers of time coefficients in its bands complicate GPU computation. An exact factorisation combines spectral selection, conjugation, windowing, and reordering into a fixed map between one packed Fourier transform and the shorter band inverse transforms. The factors give waveform reconstruction, real adjoints for backpropagation, and bounds on arithmetic depth and block width; overlapping slices permit streaming with bounded memory. Tests on two GPU models show that Flash-CQT reduces analysis-synthesis round-trip time by factors of two to eight relative to a baseline computing the same CQT. The proposed implementation also uses over 30% less peak temporary workspace and reaches a negligible reconstruction error, with a signal-to-noise ratio of about 130 dB, in single-precision floating-point arithmetic. These advances make Flash-CQT a practical, computationally efficient front end for spectral analysis and modern audio machine-learning systems.

0.28

Greedy Vector Approximation Based on Rotation for Multiplierless Complex Products

eess.SP ·2026-11-18 ·Luiz F. da S. Coelho, Paulo S. R. Diniz, Didier Le Ruyet
similarity 0.53
Abstract · This paper is submitted to ICASSP 2027

This paper proposes a greedy approximation algorithm for performing complex-valued inner products in multiplierless hardware. The matching pursuits for accurate rotation approximation (MPARA) algorithm approximates the tangent of the phase of complex elements as a sum of signed powers of two (SOPOT) representation, enabling multiplierless hardware for complex-valued multiplication. The proposed algorithm outperforms other state-of-the-art approximation methods for approximating the twiddle factors of a fast Fourier transform (FFT).

0.35

Scaling Fourier-Based Sparse Matrix Analysis on GPUs

cs.PF ·2026-09-17 ·Ruifeng Zhang, Sai Krishna Teja Varma Manthena, Jiajia Li, Xipeng Shen
similarity 0.52
Abstract · 13 pages, 7 figures

Sparse computations are important workloads in applications such as scientific computing, graph neural networks (GNNs), and machine learning. While many sparse operations can benefit from modern GPUs, the sparsity pattern remains important to performance because it affects memory coalescing, block organization, and load balancing. Previous studies show that spectral signatures can help analyze the global structure of sparse matrices. The fast Fourier transform (FFT) is commonly used to extract spectral signatures, and efficient GPU FFT libraries are available. However, sparse matrices, especially adjacency matrices for large graphs, tend to be very large and sparse. Existing dense-matrix-based FFT implementations are difficult to scale up, making the spectral patterns of these matrices difficult to obtain. We therefore propose a three-fold research approach comprising a lossless Binary-Sparse FFT (BS-FFT) and two compression methods: Elastic BS-FFT, which reuses the BS-FFT pipeline on a sampled frequency grid, and density-map-based spatial compression. Experiments show that BS-FFT reduces GPU memory use by 2.9--11.6 times relative to dense cuFFT and completes all 15 GNN adjacency matrices where dense cuFFT completes 6 on a 40 GB A100. Elastic BS-FFT and Density Map compression reduce GPU computation time by 2.0--1466.4 times relative to BS-FFT with spectral feature error of only 0.16% to 11.56% across the sampling rates from 6.25% to 0.0061%.

0.19

A Numerical Refinement of an Exact Discrete Fourier Transform Bound

cs.CC cs.DS ·2026-10-31 ·Zhihao Yao, Sichao Liu
theory similarity 0.52
Abstract

We refine the numerical bounds in Kartal's instantiation of Sussman's exact discrete Fourier transform construction. For every integer n >= 1, the resulting algorithm computes the length-n transform with work O(n (log n)^(1 - delta)), where delta = 0.0030201659. The bound holds in an exact complex-arithmetic RAM model with a supplied canonical root of unity. This final exponent saving exceeds the earlier certified parameter C_0 = 0.00302016 by 5.9 x 10^(-9). We retain the underlying circuit, tighten rational bounds for sums of powers of its block and target ranks, and increase the fixed tensor power from 7760 to 11640. These bounds establish the inequalities for Sussman's recursion at the intermediate certificate parameter C = 0.00302016595. The gap C - delta absorbs the overhead of recursion and Fourier reduction. The resulting transform theorem is proved in Lean and checked against the reference problem statement.

0.25

KBBQ: A Predictive Noise Law and the Limits of Spectrum Flattening in FP4 Quantization

cs.LG cs.AI ·2026-09-08 ·Lexington Whalen, Yuki Ito, Ryo Sakamoto
theory similarity 0.52
Abstract · 18 pages, 8 pages main text, 2 figures

We develop a second-order theory of quantization noise in matrix multiplication in which the quantization format is characterized by the variance it assigns to each element. The constant variance profile of integer quantization recovers existing integer-noise theory, while the multiplicative profile of floating-point rounding reduces the data dependence to a scalar, the participation factor $κ$, yielding a closed-form signal-to-noise-ratio law. The resulting functional also admits a closed-form upper bound $κ^{*}$ that no function-preserving linear transform can exceed and that is attained by a recent state-of-the-art method. Building on this analysis, we introduce KBBQ (\textbf{K}appa-\textbf{B}raked \textbf{B}lockwise \textbf{Q}uantization), which parameterizes the extent to which a transform approaches this ceiling. At W4A4, across four base models and two FP4 formats, KBBQ outperforms the prior state of the art without additional deployment-time computation.

0.29