Efficient Non-Adaptive Sparse Fourier Learning on the Boolean Cube and Finite Abelian GroupsResearch Paper
Learning a real function on the Boolean cube from a few of its values is a basic task in computational learning theory, property testing and signal processing on . Many functions in these areas are close to a combination of a few parities. When such a function is sampled only at chosen points, the natural goal is to find a short Fourier expansion…