# Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Apr 2015.

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

- [SHAP values via sparse Fourier representation](https://mlsanity.com/paper/2410.06300/) (2024)
- [SHAP values through General Fourier Representations: Theory and Applications](https://mlsanity.com/paper/2511.00185/) (2025)
- [Efficient Algorithm for Sparse Fourier Transform of Generalized q-ary Functions](https://mlsanity.com/paper/2501.12365/) (2025)

## Abstract (arXiv)

For every fixed constant α > 0, we design an algorithm for computing the k-sparse Walsh-Hadamard transform of an N-dimensional vector x ∈ ℝN in time k1+α (log N)O(1). Specifically, the algorithm is given query access to x and computes a k-sparse tildex ∈ ℝN satisfying |tildex - hatx|1 ≤ c |hatx - Hk(hatx)|1, for an absolute constant c > 0, where hatx is the transform of x and Hk(hatx) is its best k-sparse approximation. Our algorithm is fully deterministic and only uses non-adaptive queries to x (i.e., all queries are determined and performed in parallel when the algorithm starts). An important technical tool that we use is a construction of nearly optimal and linear lossless condensers which is a careful instantiation of the GUV condenser (Guruswami, Umans, Vadhan, JACM 2009). Moreover, we design a deterministic and non-adaptive ℓ1/ℓ1 compressed sensing scheme based on general lossless condensers that is equipped with a fast reconstruction algorithm running in time k1+α (log N)O(1) (for the GUV-based condenser) and is of independent interest. Our scheme significantly simplifies and improves an earlier expander-based construction due to Berinde, Gilbert, Indyk, Karloff, Strauss (Allerton 2008). Our methods use linear lossless condensers in a black box fashion; therefore, any future improvement on explicit constructions of such condensers would immediately translate to improved parameters in our framework (potentially leading to k (log N)O(1) reconstruction time with a reduced exponent in the poly-logarithmic factor, and eliminating the extra parameter α). Finally, by allowing the algorithm to use randomness, while still using non-adaptive queries, the running time of the algorithm can be improved to tildeO(k log3 N).