# Efficiently Computing Sparse Fourier Transforms of q-ary Functions

arXiv: https://arxiv.org/abs/2301.06200 · HTML: https://mlsanity.com/paper/2301.06200/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 37 references that are in the map.
- First posted on arXiv 15 Jan 2023.

## Builds on (most cited first, 4 of 4)

- [Adaptive wavelet distillation from neural networks through interpretations](https://mlsanity.com/paper/2107.09145/) (2021)
- [Explaining the physics of transfer learning a data-driven subgrid-scale closure to a different turbulent flow](https://mlsanity.com/paper/2206.03198/) (2022)
- [A Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domain](https://mlsanity.com/paper/1310.1803/) (2013)
- [SPRIGHT: A Fast and Robust Framework for Sparse Walsh-Hadamard Transform](https://mlsanity.com/paper/1508.06336/) (2015)

## Built on by (most cited first, 7 of 7)

- [ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMs](https://mlsanity.com/paper/2505.17495/) (2025)
- [Learning to Understand: Identifying Interactions via the M"obius Transform](https://mlsanity.com/paper/2402.02631/) (2024)
- [SPEX: Scaling Feature Interaction Explanations for LLMs](https://mlsanity.com/paper/2502.13870/) (2025)
- [On Recovering Higher-order Interactions from Protein Language Models](https://mlsanity.com/paper/2405.06645/) (2024)
- [SHAP zero Explains Biological Sequence Models with Near-zero Marginal Cost for Future Queries](https://mlsanity.com/paper/2410.19236/) (2024)
- [Is novelty predictable?](https://mlsanity.com/paper/2306.00872/) (2023)
- [Efficient Algorithm for Sparse Fourier Transform of Generalized q-ary Functions](https://mlsanity.com/paper/2501.12365/) (2025)

## Abstract (arXiv)

Fourier transformations of pseudo-Boolean functions are popular tools for analyzing functions of binary sequences. Real-world functions often have structures that manifest in a sparse Fourier transform, and previous works have shown that under the assumption of sparsity the transform can be computed efficiently. But what if we want to compute the Fourier transform of functions defined over a q-ary alphabet? These types of functions arise naturally in many areas including biology. A typical workaround is to encode the q-ary sequence in binary, however, this approach is computationally inefficient and fundamentally incompatible with the existing sparse Fourier transform techniques. Herein, we develop a sparse Fourier transform algorithm specifically for q-ary functions of length n sequences, dubbed q-SFT, which provably computes an S-sparse transform with vanishing error as qn rightarrow ∞ in O(Sn) function evaluations and O(S n2 log q) computations, where S = qnδ for some δ < 1. Under certain assumptions, we show that for fixed q, a robust version of q-SFT has a sample complexity of O(Sn2) and a computational complexity of O(Sn3) with the same asymptotic guarantees. We present numerical simulations on synthetic and real-world RNA data, demonstrating the scalability of q-SFT to massively high dimensional q-ary functions.