Paper Info
Title
Fast Fourier Sparsity Testing.
Abstract
A function $f : \mathbb{F}_2^n \to \mathbb{R}$ is $s$-sparse if it has at most $s$ non-zero Fourier coefficients. Motivated by applications to fast sparse Fourier transforms over $\mathbb{F}_2^n$, we study efficient algorithms for the problem of approximating the $\ell_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 $\ell_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 $\mathcal{O}(s)$ for constant accuracy and error parameters, which is only quadratically worse than applicable lower bounds.
Year
DOI
Venue
2020
10.1137/1.9781611976014.10
SOSA@SODA
Field
DocType
Citations 
Discrete mathematics,Computer science,Algorithm,Fast Fourier transform
Conference
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Grigory Yaroslavtsev120917.36
Samson Zhou22516.01