Fast Fourier Sparsity Testing
share
A function f : F_2^n →R is s-sparse if it has at most s non-zero Fourier coefficients. Motivated by applications to fast sparse Fourier transforms over F_2^n, we study efficient algorithms for the problem of approximating the ℓ_2-distance from a given function to the closest s-sparse function. While previous works (e.g., Gopalan et al. SICOMP 2011) study the problem of distinguishing s-sparse functions from those that are far from s-sparse under Hamming distance, to the best of our knowledge no prior work has explicitly focused on the more general problem of distance estimation in the ℓ_2 setting, which is particularly well-motivated for noisy Fourier spectra. Given the focus on efficiency, our main result is an algorithm that solves this problem with query complexity O(s) for constant accuracy and error parameters, which is only quadratically worse than applicable lower bounds.
READ FULL TEXT