# Adaptive Sparse M"obius Transforms for Learning Polynomials

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 36 references that are in the map.
- First posted on arXiv 5 Feb 2026.

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

- [Learning to Understand: Identifying Interactions via the M"obius Transform](https://mlsanity.com/paper/2402.02631/) (2024)
- [A Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domain](https://mlsanity.com/paper/1310.1803/) (2013)
- [Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases](https://mlsanity.com/paper/2010.00439/) (2020)
- [On Exact Learning Monotone DNF from Membership Queries](https://mlsanity.com/paper/1405.0792/) (2014)
- [Computing a k-sparse n-length Discrete Fourier Transform using at most 4k samples and O(k log k) complexity](https://mlsanity.com/paper/1305.0870/) (2013)
- [Learning Low Degree Hypergraphs](https://mlsanity.com/paper/2202.09989/) (2022)
- [Adaptive Learning a Hidden Hypergraph](https://mlsanity.com/paper/1607.00507/) (2016)

## Abstract (arXiv)

We consider the problem of exactly learning an s-sparse real-valued Boolean polynomial of degree d of the form f: 0,1n rightarrow ℝ. This problem corresponds to decomposing functions in the AND basis and is known as taking a M"obius transform. While the analogous problem for the parity basis (Fourier transform) f: -1,1 n rightarrow ℝ is well-understood, the AND basis presents a unique challenge: the basis vectors are coherent, precluding standard compressed sensing methods. We overcome this challenge by identifying that we can exploit adaptive group testing to provide a constructive, query-efficient implementation of the M"obius transform (also known as M"obius inversion) for sparse functions. We present two algorithms based on this insight. The Fully-Adaptive Sparse M"obius Transform (FASMT) uses O(sd log(n/d)) adaptive queries in O((sd + n) sd log(n/d)) time, which we show is near-optimal in query complexity. Furthermore, we also present the Partially-Adaptive Sparse M"obius Transform (PASMT), which uses O(sd2log(n/d)) queries, trading a factor of d to reduce the number of adaptive rounds to O(d2log(n/d)), with no dependence on s. When applied to hypergraph reconstruction from edge-count queries, our results improve upon baselines by avoiding the combinatorial explosion in the rank d. We demonstrate the practical utility of our method for hypergraph reconstruction by applying it to learning real hypergraphs in simulations.