2022/05/02 by Gao, Yeqi, Song, Zhao, Sun, Baocheng +2
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2205.00658
We revisit the classical problem of Fourier-sparse signal reconstruction -- a variant of the Set Query problem -- which asks to efficiently reconstruct (a subset of) a d-dimensional Fourier-sparse signal (‖x(t)‖0 ≤ k), from minimum noisy samples of x(t) in the time domain. We present a unified framework for this problem by developing a theory of sparse Fourier transforms (SFT) for frequencies lying on a lattice, which can be viewed as a ``semi-continuous'' version of SFT in between discrete and continuous domains. Using this framework, we obtain the following results: \bullet **Dimension-free Fourier sparse recovery** We present a sample-optimal discrete Fourier Set-Query algorithm with O(kω+1) reconstruction time in one dimension, independent of the signal's length (n) and ℓ_∞-norm. This complements the state-of-art algorithm of [Kapralov, STOC 2017], whose reconstruction time is O(k log2 n log R^*), where R^* ≈ ‖x‖_∞ is a signal-dependent parameter, and the algorithm is limited to low dimensions. By contrast, our algorithm works for arbitrary d dimensions, mitigating the exp(d) blowup in decoding time to merely linear in d. A key component in our algorithm is fast spectral sparsification of the Fourier basis. \bullet **High-accuracy Fourier interpolation** In one dimension, we design a poly-time (3+ √(2) +ε)-approximation algorithm for continuous Fourier interpolation. This bypasses a barrier of all previous algorithms [Price and Song, FOCS 2015, Chen, Kane, Price and Song, FOCS 2016], which only achieve c>100 approximation for this basic problem. Our main contribution is a new analytic tool for hierarchical frequency decomposition based on noise cancellation.