Source-linked AI summary
Exact Factorisation and Fast Computation of Invertible Constant-Q Transforms
Facundo Franchino, Eloi Moliner, Vesa Välimäki
TL;DR
The invertible CQT’s unequal band lengths complicate GPU computation. Flash-CQT combines the operations between Fourier stages in a fixed map, and is 2.1 to nearly 8 times faster than the CQT baseline on A100 across batch sizes.
Problem
Separate GPU stages for an invertible CQT add kernel launches, temporary buffers, and data movement, while padding bands to a common length wastes arithmetic and storage.
Source: §1 · p. 1Method
Flash-CQT uses a fixed map to combine operations between Fourier stages, routing weighted band bins into each band’s short inverse FFT while retaining native band lengths.
Source: §1 · p. 1Results
Flash-CQT is 2.1 to nearly 8 times faster than the CQT baseline across batch sizes on A100, with 129.8 dB reconstruction SNR.
Source: §5.1 · p. 4Takeaways & Limitations
The construction also applies to painless NSGTs beyond the evaluated CQT configuration, such as auditory filterbanks.
Source: §6 · p. 4
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
Flash-CQT addresses the GPU cost of an exactly invertible, differentiable CQT by combining operations between Fourier stages in a fixed map. The factorisation keeps each band’s native length while enabling reconstruction and real adjoints for backpropagation.
1. INTRODUCTION
- The CQT uses geometrically spaced bands and windows inversely scaled with centre frequency, giving constant Q and resolution suited to pitch and music analysis.Its long low-frequency windows distinguish nearby components, while short high-frequency windows resolve rapid changes.Source: §1 · p. 1
- An exactly invertible CQT maps analysed, edited, or generated coefficients back to a waveform, and its linear analysis and synthesis operations are differentiable.The NSGT provides a construction for invertible transforms with frequency-dependent windows.Source: §1 · p. 1
- Existing differentiable CQT implementations make computational cost important because they are used repeatedly in training and inference.The passage contrasts nnAudio’s differentiable analysis without an exact inverse with implementations that provide both invertibility and differentiation.Source: §1 · p. 1
- Separate GPU calls for the invertible CQT’s Fourier, selection, windowing, and band inverse-FFT stages add launches, temporary buffers, and data movement.Padding bands to a common length also wastes arithmetic and storage.Source: §1 · p. 1
- The fixed-map factorisation combines spectral selection, conjugation, windowing, and reordering so routing and each band’s short inverse FFT run in one GPU kernel.Theorem 1 bounds the map’s depth and width; the factors also give reconstruction and real adjoints for backpropagation.Source: §1 · p. 1
2. THE INVERTIBLE TRANSFORM
The transform analyzes a real signal into overlapping frequency bands with their own coefficient lengths, then synthesizes a waveform using dual windows. In the painless case, coverage and diagonal weighting yield exact reconstruction in exact arithmetic.
2. THE INVERTIBLE TRANSFORM
- Each CQT band has its own coefficient vector length Mλ, producing ragged arrays because bandwidth grows with frequency.Higher-frequency bands require more time coefficients over a fixed duration.Source: §2 · p. 2
- Analysis computes one length-N spectrum, applies each band’s real spectral window and bin selection, then uses a short inverse DFT to produce its coefficients.The CQT has overlapping bands with distinct lengths Mλ; it also retains DC and Nyquist sidebands, while negative-frequency bands follow by conjugate symmetry.Source: §2 · p. 2
- In the painless case, band supports fit their local spectra without collisions and together cover every Fourier bin, allowing synthesis with diagonal weighting.The windows must cover every bin, and the dual weights normalize overlapping contributions.Source: §2 · p. 2
- Synthesis applies each band’s short DFT, returns bins to their original positions, weights them with the dual window, and takes an inverse DFT of their sum.For analysed coefficients, ST = I on real signals in exact arithmetic.Source: §2 · p. 2
3. PACKED ROUTING AND ARITHMETIC STRUCTURE
The section factors CQT analysis around packed-spectrum routing, then develops layer and block-width bounds and reverse-order adjoints for synthesis and backpropagation.
3. PACKED ROUTING AND ARITHMETIC STRUCTURE
- Pairing consecutive real samples halves the FFT length while preserving all signal information; each required signal-spectrum bin follows from two packed-spectrum bins.The packed spectrum contains exactly N real numbers, matching the signal.Source: §3 · p. 2
- The router maps the packed spectrum directly to each band spectrum, combining bin recovery, windowing, and selection in one table without forming the full spectrum.It is real-linear because it includes conjugation, though generally not complex-linear.Source: §3 · p. 2
- Synthesis reverses the analysis factors, adds band contributions in the packed domain, and uses one inverse FFT for all bands.The conjugate term accounts for negative frequencies; DC and Nyquist are made real.Source: §3 · p. 2
3.1. Depth and block width
- The factorisation describes analysis and synthesis as layers of independent small blocks, with router blocks bounded by four real inputs and 2D real outputs.D is the maximum fan-out across packed-bin pairs; the theorem bounds depth and block width when transform lengths factor into integers no larger than r.Source: §3.1 · pp. 2–3
3.2. Adjoints for training
- Backpropagation reverses the factor order and takes real adjoints; the router’s conjugate term makes its adjoint a real, rather than ordinary complex, adjoint.The fixed maps reuse the same index tables and Fourier routines, and require no saved transform activations.Source: §3.2 · p. 3
4. IMPLEMENTATION
The CUDA implementation uses a fixed-length, multi-resolution CQT layout and specialized kernels; its short-signal handling trades frequency selectivity or low-band coverage for fitting the slice length.
4. IMPLEMENTATION
- For a slice of N = 65,536 at 44.1 kHz, the configuration combines three CQT resolutions covering 3, 4, and 2 octaves at 8, 16, and 32 bands per octave, yielding 152 positive-frequency bands.The bands share one coefficient length per octave.Source: §4 · p. 3
- The fast kernels specialize to N = 65,536 and packed length 32,768, using three radix-32 layers and routing tables indexed in FFT output order.Band kernels read the routing tables and radix plans at run time while assuming this packed length.Source: §4 · p. 3
- Each 256-thread block handles one band and batch element; synthesis uses atomic FP32 additions to accumulate dual-routed contributions before the packed inverse FFT.The kernels use at most 16.25 KiB of shared memory, and index maps permit stages to overwrite inputs within one buffer.Source: §4 · p. 3
- At fan-out D = 7, Theorem 1 gives depth 7 and real block width 64 for r = 32; this bound concerns arithmetic structure, not runtime or kernel launches.The maximum fan-out occurs at packed pairs 59 through 63.Source: §4 · p. 3
- For signals shorter than 65,536 samples, omitting the lowest bands or lowering Q accommodates the slice, while lowering Q shortens windows at the cost of frequency selectivity.Shorter signals would require new specialized kernels; longer signals use 50%-overlapping slices and a Tukey transition window.Source: §4 · p. 3
5. EVALUATION
Flash-CQT accelerates invertible CQT round trips against a baseline computing the same operator, while retaining high reconstruction fidelity and reducing temporary workspace. A differentiable round-trip test also finds faster execution than the baseline and close agreement with autograd gradients.
5.1. Analysis and reconstruction
- 5.2× faster at B = 1; round-trip speedups range from 2.1 to nearly 8 on A100 and 2.0 to 6.0 on V100 versus the CQT baseline.Fig. 2(a) shows round-trip time against batch size under CUDA graph replay.Source: §5.1 · p. 4, Figure 2 · p. 4
- At B = 1, Flash-CQT takes 2.3 times the STFT time under graph replay and reaches parity near B = 16; at B = 128, eager STFT takes 1.39 ms versus 1.66 ms for Flash-CQT.The graph STFT takes 2.32 ms at B = 128.Source: §5.1 · p. 4
- 129.8 dB reconstruction SNR, varying by at most 0.1 dB, corresponds to about 3 × 10^-7 relative Euclidean error and is consistent with FP32 round-off.The measured error is a few times the FP32 machine epsilon of 1.2×10^-7.Source: §5.1 · p. 4
- 36–38% less transient workspace per signal across batches comes from keeping the spectrum packed and overwriting buffers in place.Transient workspace excludes inputs and persistent tables.Source: §5.1 · p. 4
5.2. Differentiable round trip
- Eager differentiable round trips are 2.2–5.3× faster on A100 and 1.7–3.0× faster on V100 than the CQT baseline; analysis and synthesis gradients agree with autograd at 130.05 and 129.48 dB.This experiment includes squared error and backpropagation through both transforms, but not a neural network; effects on complete model training remain open.Source: §5.2 · p. 4
6. CONCLUSION
Flash-CQT combines the operations between Fourier stages in an exact factorisation of the invertible CQT, reducing round-trip time and workspace while retaining reconstruction accuracy. The approach also supports applications using invertible CQT coefficients and extends to other painless NSGTs, though their performance remains unestablished.
6. CONCLUSION
- On the tested GPUs, Flash-CQT reduces round-trip time by factors of two to eight against the CQT baseline.The implementation uses over a third less temporary workspace and retains about 130 dB reconstruction SNR.Source: §6 · p. 4
- The construction supports invertible-CQT applications including diffusion-based audio generation, source separation, bandwidth extension, and timbre transfer, and sliced operation extends it to long recordings and streaming.These applications retain logarithmic frequency resolution; CQT losses and discriminators can also use fused analysis kernels and exact adjoints.Source: §6 · p. 4
- The factorisation also applies to other painless NSGTs, such as auditory filterbanks, although their fan-out and performance remain to be established.Source: §6 · p. 4