- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 3(+1)
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies the problem of function reconstruction for functions on the boolean cube which are known to be sparse in the Fourier domain. The authors present an algorithm with asymptotically optimal query count , beating previous results by log factors. However, the main contribution of the paper is to achieve this with rather simple techniques, while previous works relied on complex machinery.
The main technique is sub-space restriction, which is not new in the field of Boolean analysis, and has proved very useful in many scenarios. The authors show that with good enough probability, under the quotient map induced by the restriction, most Fourier frequencies will still be isolated in the new domain. Isolated frequencies can be recovered using a simple condition, which exploits the fact one is working over the boolean cube.
Critical strengths
The paper provides a simplification of other algorithms in the field, which is both theoretically easy to explain and practical to implement. This has great value by itself, as some previous algorithms in the field are merely theoretic and hard to implement in practice. The presentation is generally good and the proofs are rigorous and correct.
Critical weaknesses
- The main weakness of the paper is poor motivation which leads to limited applicability. The applications cited - learning Boolean trees, graph sketching and recovery of set functions - are rather old applications and mostly require more robust setups. Most of the "older" applications are more theoretic and algorithmic in nature, and would not be of interest to a wide audience in the ML community. Moreover, both old and new applications, which include interpretability line of works (for example [1,2,3]), require stronger forms of the problem, namely supporting noise or approximate sparsity. Previous works mostly address that stronger form of the problem, for example by providing guarantees.
- Another weakness I wish to point out is that the main technique does not carry over to the non-boolean case, because reconstruction relies on frequencies being boolean. Moreover, it is unclear if this carries over to other structured transforms, or relies on specific properites of WHT (recent work studied a similar problem via the Mobius transform [2]). Both are major limitations, and it is not properly addressed in the paper. I think the paper would benefit from some discussion pointing out why this technique fails to carry over to the non-boolean case, or to other structured transforms.
- There are a few presentation issues:
- I think the query-access model should be emphasized. The simplest algorithm is random sub-WHT through the RIP, but as the authors mention in passing - it incurs linear cost in . This should be more clearly stated, because the main strength of the paper is the simplicity of the algorithm in the query-access model, not in the linear measurements model where there is a very simple algorithm already.
- In particular, I think it is worth drawing a connection from the sub-WHT algorithm to your algorithm. Your result can be understood as the observation that instead of choosing random frequencies, one can choose random sub-spaces of frequencies, and then the WHT is repetitive so the ambient dimension can be shrinked. I wonder if the sub-matrix generated by this process is RIP with high probability - if yes, this gives a possibly even simpler formulation of your algorithm, which might hold up in robust setups.
- The discussion should be part of the paper, not of the supp material.
[1] SPEX: Scaling Feature Interaction Explanations for LLMs, Kang et al. ICML 25', https://proceedings.mlr.press/v267/kang25a.html [2] Learning to Understand: Identifying Interactions via the Möbius Transform, Kang et al., NIPS 24', https://proceedings.neurips.cc/paper_files/paper/2024/hash/520b379123d16e41f85472e766846486-Abstract-Conference.html [3] SHAP values via sparse Fourier representation, Gorji et al. NIPS 25', https://arxiv.org/abs/2410.06300
Questions for authors
- Does the algorithm extend to the approximate case?
- What are the limitations of the techniques?
- Can the sub-space WHT be interpreted through the Restricted Isometry Property?
4 comments
The subsampled-WHT interpretation
A subsampled-WHT method selects rows of the Hadamard matrix and recovers the sparse Fourier coefficient vector from the resulting linear system. A standard approach uses the Restricted Isometry Property (RIP) to justify recovery through -minimization or related procedures. Such generic recovery procedures may involve computations whose cost depends on the ambient dimension .
Our construction also selects Hadamard rows, but the affine-subspace (of , and not ) structure enables a fundamentally different and efficient decoding procedure. In particular, the query-access model plays an important role in designing the decoder: we exploit the ability to evaluate the function at carefully chosen inputs to construct spectral buckets and identify isolated frequencies through small WHTs and coordinate shifts. Thus, rather than solving a generic sparse-recovery problem, we exploit the structure of the measurements to recover the Fourier support efficiently.
We agree that our hashing perspective suggests interesting connections with RIP-based subsampled-WHT methods. However, the underlying recovery machinery is different, and its efficiency crucially depends on the access model. We appreciate the suggestion to investigate whether our structured subsampled Hadamard operator satisfies RIP. Our current theorem does not establish this property: it guarantees recovery with high probability for each fixed sparse input, whereas RIP requires a single operator to preserve norms simultaneously for all vectors of the relevant sparsity. Establishing RIP would require a separate analysis and could potentially provide a route toward robust recovery guarantees.
Nevertheless, to the best of our understanding, RIP alone would not establish our running-time bound, since the computational efficiency also depends on exploiting the structure of the measurements during decoding.
We would be happy to clarify or revise our discussion further if we have overlooked or misunderstood any aspect of the reviewer's concern.
Dear Reviewer
We would appreciate it if you could let us know whether we have adequately addressed your questions and concerns, or if there are any points that still require clarification. If you feel that we have satisfactorily addressed your concerns, we would kindly request you to reconsider your rating and increase it accordingly.
Thanks for the detailed response.
- I understand your motivation to study the clean setup, and your results are strong and elegant. My main concern is that these techniques won't carry over to the noisy or approximate setting, which are the interesting settings (especially for learning applications). That said, the clean setting is more interesting than I originally thought.
- As for extending to other domains: the aliasing formula (what you refer to as the Poisson sum), extends to any abelian group. However, the isolation lemmas rely on a stronger property: If is the group and is a sub-group containing , the annihilator and it's complement, then the quotient map has kernel . Thus either all elements of are isolated (when ) or all elements aren't isolated. The rest of the lemmas require that for a random sub-group the probability of is bounded by for any . This shows why this algorithm works well for the finite-field vector spaces , potentially with another factor. It also shows why this algorithm won't work well for groups with less factors - as in the cyclic group there is always a non-zero kernel.
- Regarding the RIP condition: I agree that this interpretation isn't very relevant and might be completely false.
Following the discussion I'm updating my score. Thank you for this nice contribution.
We thank the reviewer for carefully reading the manuscript, providing detailed feedback, and recognizing the simplicity of the algorithm and the correctness of the proofs.
Exact sparsity and noiseless access.
Hashing is a cornerstone of sparse Hadamard transform algorithms. A common approach partitions Fourier coefficients into buckets, identifies significant or isolated coefficients, and decodes their frequencies. Our work emphasizes a complementary way to understand this process: Fourier analysis itself supplies the hashing mechanism. Through the restriction identity, a finite-group form of Poisson summation, restricting the input to a random affine subspace automatically aggregates Fourier coefficients into spectral buckets.
Our contribution is to develop this perspective into a simpler recovery algorithm and analysis with improved bounds. In particular, direct coordinate decoding eliminates the nested frequency-recovery procedure and its associated amplification. Given the broad role of Fourier hashing in learning and related algorithmic problems, we believe this formulation may also be useful in other settings. Moreover, our approach admits an efficient software implementation, and our experimental results demonstrate its practical effectiveness.
We do not dispute that noisy settings and approximate recovery are more relevant in many practical applications. Our intention, however, is to use exact recovery as a clean setting in which to demonstrate our approach and establish sharp query-complexity bounds. We believe that obtaining sharp query bounds through a transparent recovery argument is valuable, while recognizing that extensions to noisy and approximately sparse inputs are necessary for broader applicability.
Such extensions require additional analysis. With approximate sparsity, a Fourier tail can contribute to every bucket; with noisy evaluations, even singleton bucket values are perturbed. Isolated coefficients therefore need not be recovered exactly, and residual sparsity alone no longer controls progress. Although coordinate decoding is stable under perturbations sufficiently small relative to the isolated coefficient, a robust theorem would additionally require bounds on tail interference and errors accumulated during subtraction.
Extension to other bases
Our theorem already allows arbitrary real-valued functions; the Boolean assumption concerns the input domain and its characters. Our approach relies on a specific compatibility between Fourier characters and subgroup restriction. For a subspace H≤F2n, the restriction identity gives
$ \widehat{f_{a+H}}(\gamma) = \sum_{\alpha\in\gamma+H^\perp} \widehat f(\alpha)(-1)^{\langle\alpha,a\rangle}. $
This finite-group form of Poisson summation explains why restricting the input to a+H produces exact signed sums over spectral buckets indexed by cosets of H⊥. Coordinate shifts then reveal the bits of an isolated frequency. Beyond F2n, this coordinate-shift sign rule no longer applies directly, so a different frequency decoder is needed.
Orthonormality alone does not provide the restriction identity. Likewise, RIP for a measurement operator does not by itself supply the required implicit hashing structure or an efficient decoder. Our argument therefore does not automatically extend to a general wavelet basis or to the Möbius transform mentioned by the reviewer, and we do not currently establish such extensions.
Within Fourier analysis, finite abelian groups provide a natural direction: restriction to a subgroup gives an exact aggregation identity over cosets of its annihilator. Extending the algorithm would also require suitable subgroups with useful collision properties and an efficient frequency decoder. Where subgroups of useful sizes are unavailable, approximate structures such as Bohr neighborhoods may be relevant, but they would require additional control of leakage and approximation error. We will explain these distinctions in the main paper.
Query access
We will state the chosen-point query-access model prominently near the main theorem and explain this computational advantage and its relationship to subsampled-WHT methods more explicitly.