# A Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domain

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2013.

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

- [ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMs](https://mlsanity.com/paper/2505.17495/) (2025)
- [A Scalable Walsh-Hadamard Regularizer to Overcome the Low-degree Spectral Bias of Neural Networks](https://mlsanity.com/paper/2305.09779/) (2023)
- [SHAP values via sparse Fourier representation](https://mlsanity.com/paper/2410.06300/) (2024)
- [Learning k-body Hamiltonians via compressed sensing](https://mlsanity.com/paper/2410.18928/) (2024)
- [Efficiently Computing Sparse Fourier Transforms of q-ary Functions](https://mlsanity.com/paper/2301.06200/) (2023)
- [Advances in Set Function Learning: A Survey of Techniques and Applications](https://mlsanity.com/paper/2501.14991/) (2025)
- [Efficient Algorithm for Sparse Fourier Transform of Generalized q-ary Functions](https://mlsanity.com/paper/2501.12365/) (2025)
- [Adaptive Sparse M"obius Transforms for Learning Polynomials](https://mlsanity.com/paper/2602.06246/) (2026)
- [Spectral Feedback for Test-Time Alignment of Protein Diffusion Models](https://mlsanity.com/paper/2609.30456/) (2026)

## Abstract (arXiv)

A new iterative low complexity algorithm has been presented for computing the Walsh-Hadamard transform (WHT) of an N dimensional signal with a K-sparse WHT, where N is a power of two and K = O(Nα), scales sub-linearly in N for some 0 < α < 1. Assuming a random support model for the non-zero transform domain components, the algorithm reconstructs the WHT of the signal with a sample complexity O(K log2(fracNK)), a computational complexity O(Klog2(K)log2(fracNK)) and with a very high probability asymptotically tending to 1. The approach is based on the subsampling (aliasing) property of the WHT, where by a carefully designed subsampling of the time domain signal, one can induce a suitable aliasing pattern in the transform domain. By treating the aliasing patterns as parity-check constraints and borrowing ideas from erasure correcting sparse-graph codes, the recovery of the non-zero spectral values has been formulated as a belief propagation (BP) algorithm (peeling decoding) over a sparse-graph code for the binary erasure channel (BEC). Tools from coding theory are used to analyze the asymptotic performance of the algorithm in the very sparse (α∈(0,frac13]) and the less sparse (α∈(frac13,1)) regime.