Let @math be a polynomial with at most @math non-zero real coefficients. We give an algorithm for exactly reconstructing f given random examples from the uniform distribution on @math that runs in time polynomial in @math and @math and succeeds if the function satisfies the unique sign property: there is one output value which corresponds to a unique set of values of the participating parities. This sufficient condition is satisfied when every coefficient of f is perturbed by a small random noise, or satisfied with high probability when s parity functions are chosen randomly or when all the coefficients are positive. Learning sparse polynomials over the Boolean domain in time polynomial in @math and @math is considered notoriously hard in the worst-case. Our result shows that the problem is tractable for almost all sparse polynomials. Then, we show an application of this result to hypergraph sketching which is the problem of learning a sparse (both in the number of hyperedges and the size of the hyperedges) hypergraph from uniformly drawn random cuts. We also provide experimental results on a real world dataset.
@cite_7: We present a randomized algorithm that interpolates a sparse polynomial in polynomial time in the bit complexity model. The algorithm can be also applied to approximate polynomials that can be approximated by sparse polynomials (the approximation is in the @math norm).
@cite_6: Can we learn a sparse graph from observing the value of a few random cuts? This and more general problems can be reduced to the challenge of learning set functions known to have sparse Fourier support contained in some collectionP. We prove that if we choose O(k log 4 |P|) sets uniformly at random, then with high probability, observing any k-sparse function on those sets is sucient to recover that function exactly. We further show that other properties, such as symmetry or submodularity imply structure in the Fourier spectrum, which can be exploited to further reduce sample complexity. One interesting special case is that it suces to observe O(|E| log 4 (|V|)) values of a cut function to recover a graph. We demonstrate the eectiveness of our results on two realworld reconstruction problems: graph sketching and obtaining fast approximate surrogates to expensive submodular objective functions.
The recent papers @cite_6 @cite_7 are of particular relevance to us since they establish a connection between learning sparse polynomials and compressed sensing. The authors show that the problem of learning a sparse polynomial is equivalent to recovering the unknown sparse coefficient vector using linear measurements. By applying techniques from compressed sensing theory, namely Restricted Isometry Property (see @cite_6 ) and incoherence (see @cite_7 ), the authors independently established results for reconstructing sparse polynomials using convex optimization. The results have near-optimal sample complexity. However, the running time of these algorithms is exponential in the underlying dimension, @math . This is because the measurement matrix of the equivalent compressed sensing problem requires one column for every possible non-zero monomial.