Adaptive Sparse M”obius Transforms for Learning Polynomials

arXiv:2602.06246v1 Announce Type: new
Abstract: We consider the problem of exactly learning an $s$-sparse real-valued Boolean polynomial of degree $d$ of the form $f:{ 0,1}^n rightarrow mathbb{R}$. 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 mathbb{R}$ 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(sd^2log(n/d))$ queries, trading a factor of $d$ to reduce the number of adaptive rounds to $O(d^2log(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.