A robust multi-dimensional sparse Fourier transform in the continuous setting
share
Sparse Fourier transform (Sparse FT) is the problem of learning an unknown signal, whose frequency spectrum is dominated by a small amount of k individual frequencies, through fast algorithms that use as few samples as possible in the time domain. The last two decades have seen an extensive study on such problems, either in the one-/multi-dimensional discrete setting [Hassanieh, Indyk, Katabi, and Price STOC'12; Kapralov STOC'16] or in the one-dimensional continuous setting [Price and Song FOCS'15]. Despite this rich literature, the most general multi-dimensional continuous case remains mysterious. This paper initiates the study on the Sparse FT problem in the multi-dimensional continuous setting. Our main result is a randomized non-adaptive algorithm that uses sublinear samples and runs in sublinear time. In particular, the sample duration bound required by our algorithm gives a non-trivial improvement over [Price and Song FOCS'15], which studies the same problem in the one-dimensional continuous setting. The dimensionality in the continuous setting, different from both the discrete cases and the one-dimensional continuous case, turns out to incur many new challenges. To overcome these issues, we develop a number of new techniques for constructing the filter functions, designing the permutation-then-hashing schemes, sampling the Fourier measurements, and locating the frequencies. We believe these techniques can find their applications in the future studies on the Sparse FT problem.
READ FULL TEXT