acceptodds
Under review as a conference paper at ICLR 2027

Exact Fourier-Sparse Recovery over Hypercube : Simpler and Stronger

Abstract

We study the problem of exact recovery of Fourier-sparse functions over the Boolean hypercube , a fundamental problem at the intersection of learning theory, signal processing, and inverse problems. Given oracle access to such a function whose Fourier spectrum is supported on at most \(k\) coefficients, the goal is to identify all nonzero Fourier coefficients exactly using as few queries as possible. An \(\Omega(nk)\) query lower bound is known for this problem, which also implies an \(\Omega(nk)\) lower bound on the running time. Recent works have made significant progress, developing algorithms whose query and time complexities are within polylogarithmic factors of these lower bounds. However, these algorithms often rely on relatively sophisticated machinery, making the underlying recovery process less transparent. In this work, we present a randomized algorithm that achieves polylogarithmic improvements over the best known results, while being substantially simpler in its design. Our algorithm uses \(O(nk)\) queries and \(O(nk\log k)\) time, making it sample-optimal up to constant factors, with running time within an \(O(\log k)\) factor of the corresponding lower bound. Beyond these quantitative improvements, we believe our approach enables a substantially simpler and more transparent recovery framework, which may prove useful in broader sparse-recovery settings.

Primary area:
learning theory
Keywords:
Learning Theory, Boolean Functions, Fourier Analysis, Exact Reconstruction, Sparsity

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_JtpjOpenReview ↗
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 O(nk)O(nk), 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
  1. 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 ℓ2/ℓ∞\ell_2/\ell_{\infty} guarantees.
  2. 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.
  3. 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 2n2^n. 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
  1. Does the algorithm extend to the approximate case?
  2. What are the limitations of the techniques?
  3. Can the sub-space WHT be interpreted through the Restricted Isometry Property?
4 comments

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≤F2nH\leq\mathbb{F}_2^n, 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+Ha+H produces exact signed sums over spectral buckets indexed by cosets of H⊥H^\perp. Coordinate shifts then reveal the bits of an isolated frequency. Beyond F2n\mathbb{F}_2^n, 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.

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 ℓ1\ell_1-minimization or related procedures. Such generic recovery procedures may involve computations whose cost depends on the ambient dimension 2n2^n.

Our construction also selects Hadamard rows, but the affine-subspace (of F2n\mathbb{F}^{n}_{2}, and not Rn\mathbb{R}^{n}) 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 GG is the group and S≤G^S\le \hat{G} is a sub-group containing supp(f^)supp(\hat{f}), H⊥⊕W=G^H^\bot\oplus W=\hat{G} the annihilator and it's complement, then the quotient map S→G^/H⊥S\to \hat{G}/H^\bot has kernel S∩H⊥S\cap H^\bot. Thus either all elements of SS are isolated (when S∩H⊥={0}S\cap H^\bot=\{0\}) or all elements aren't isolated. The rest of the lemmas require that for a random sub-group HH the probability of v∈H⊥v\in H^\bot is bounded by C/∣H∣C/|H| for any v≠0v\ne0. This shows why this algorithm works well for the finite-field vector spaces Fpd\mathbb{F}_p^d, potentially with another pp factor. It also shows why this algorithm won't work well for groups with less factors - as in the cyclic group ZN\mathbb{Z}_N 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.

Reviewer_nJN7OpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies exact recovery of Fourier-sparse functions over the Boolean hypercube. It claims to give an algorithm that uses O(nk)O(nk) queries with O(nklog⁡k)O(nk\log k) running time. In a broad scaling regime, this is sample-optimal, with running time within a logarithmic factor of optimal. It also claims that the algorithm and analysis are simpler than prior work.

Critical strengths
  • The algorithm uses O(nk)O(nk) queries and O(nklog⁡k)O(nk\log k) time, making it sample-optimal up to constant factors whenever n−log⁡2k=Ω(n)n-\log_2 k=\Omega(n), with running time within an O(log⁡k)O(\log k) factor of the lower bound.
  • The algorithm and analysis are both simple, and the underlying ideas are quite accessible
Critical weaknesses

None

Questions for authors

None.

Optional feedback, these comments do not affect my acceptance recommendation, and no response is required for my assessment.

  • The comparison with Amrollahi et al. (2019) is helpful. Since their Definition 7 and Claim 8 also use affine restrictions to implement hashing, the discussion on page 3 could more precisely identify where the simplification lies.
  • Out of curiosity, do you have any intuition on whether the remaining O(log⁡k)O(\log k) gap in running time can be closed?
2 comments

We thank the reviewer for carefully reading the manuscript and for their encouraging feedback, especially for recognizing the improved bounds and the simplicity of our algorithm and analysis.

Comparison with Amrollahi et al. (2019).

Their Definition 7 and Claim 8 already implement spectral hashing through affine restrictions, albeit in the dual space. Their algorithm exploits the assumption that every frequency has Hamming weight at most dd. Once a Fourier coefficient is isolated, the corresponding frequency is recovered using a second sparse-recovery procedure: the coordinates are hashed, isolated nonzero coordinates are identified through binary index measurements, and the process is repeated on the remaining coordinates. Since this inner procedure is randomized, SHTINNER (their subroutine) repeats it and uses majority voting to obtain a reliable estimate.

For unrestricted-degree frequencies, we replace this entire inner recovery procedure with the coordinate shifts e1,…,ene_1,\ldots,e_n. If an isolated coefficient has value c≠0c\neq 0, the corresponding bucket values are

$ b_0=c$, and $ b_i=c(-1)^{\alpha_i}. $

Thus, each coordinate can be recovered directly as

$ \alpha_i=\mathbf{1}[b_i b_0<0]. $

Consequently, decoding is deterministic, conditional on isolation. This eliminates the need for inner coordinate hashing, iterative coordinate recovery, and majority amplification.

Our analysis also provides a direct and simple bound on the Fourier residual: if XrX_r coefficients collide in round rr, the support size of the residual after that round is at most 3Xr/23X_r/2. Combined with our choice of schedule, this yields an O(nk)O(nk) query bound.

Thus, the main algorithmic contribution is the elimination of the nested frequency-recovery procedure, allowing us to handle unrestricted-degree frequencies. In particular, when d=Θ(n)d=\Theta(n), our O(nk)O(nk) query complexity improves upon the O(kdlog⁡n)O(kd\log n) bound of Amrollahi et al. Their approach, however, retains the advantage of exploiting low-degree structure, which our algorithm does not seek to leverage.

The remaining logarithmic running-time gap.

We do not currently know whether this logarithmic gap can be closed. Our implementation incurs O(nklog⁡k)O(nk\log k) running time, primarily due to the restricted Walsh–Hadamard transforms and residual maintenance across rounds. Eliminating the logarithmic factor would require improving these operations, potentially through the reuse of intermediate computations or a fundamentally different recovery procedure.

Thank you for the detailed response. The explanation of how coordinate shifts replace the nested frequency-recovery procedure helpfully clarifies the simplification relative to Amrollahi et al. In my opinion, a concise version of this comparison would be useful in the manuscript.

Thank you also for discussing the remaining logarithmic running-time gap.

I have no further questions and maintain my recommendation.

Reviewer_7EqgOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors propose a randomized algorithm for exact recovery of Fourier-sparse functions over the Boolean hypercube. Their algorithm, based on random subspace restrictions and iterative recovery, provides a simpler approach than previous algorithms and achieves O(nk) queries and O(nk log(k)) runtime.

Critical strengths
  • The paper addresses an important problem in sparse recovery and provides a relatively simple analysis
  • The proposed algorithm improves both query and runtime complexities over previous results, and the underlying approach seems potentially applicable beyond Fourier-sparse recovery
Critical weaknesses

The paper assumes a noiseless, exactly-sparse model. Although the authors clearly acknowledge this limitation (l. 694 in the appendix), it remains unclear whether the analysis could be extended to broader settings. I believe this limitation acknowledgement should be moved to the main part of the paper.

Questions for authors

Could the authors clarify the conditions under which the O(nk) query complexity is optimal?

3 comments

We thank the reviewer for carefully reading the manuscript and for their encouraging feedback, particularly for recognizing the importance of the problem, the simplicity of the analysis, and the improvements in query and running-time complexity.

Exact sparsity and noiseless access.

We agree that these assumptions and their implications should be stated more prominently in the main paper. Accordingly, we will move the relevant discussion from Appendix B.2 to the main text.

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. Moreover, our approach admits an efficient software implementation, as evidenced by our experimention results.

Approximate recovery is an important extension, but it requires additional technical developments. In the presence of a Fourier tail or observation noise, bucket values become perturbed, so isolated coefficients can no longer be recovered exactly, and the residual support size alone is no longer a sufficient measure of progress. An extension would therefore require carefully controlling interference within buckets, as well as the errors accumulated during decoding and subsequent subtraction. We will clarify the distinction between our exact-recovery guarantees and these important directions for future work.

Conditions for query optimality.

The relevant lower bound is $ \Omega\left(k(n-\log_2 k)\right). $ Haviv and Regev (2015, Theorem 3.7) establish this bound for uniformly and independently drawn samples. Their fixed-query counting argument also applies to non-adaptive membership queries. We will explain this connection in greater detail in the revised manuscript.

Consequently, our O(nk)O(nk) query bound is optimal up to constant factors among non-adaptive algorithms whenever k≤2(1−δ)nk \leq 2^{(1-\delta)n}, for any fixed constant δ>0\delta>0.

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.

We thank the authors for their clarifications. All my questions and concerns were addressed. My overall rating and confidence remain unchanged.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.