文章基本信息
- 标题：Deterministic Sparse Fourier Transform with an ð"_{â^Z} Guarantee
- 本地全文：下载
- 作者：Yi Li ; Vasileios Nakos
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：168
- 页码：77:1-77:14
- DOI：10.4230/LIPIcs.ICALP.2020.77
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：In this paper we revisit the deterministic version of the Sparse Fourier Transform problem, which asks to read only a few entries of x â^^ â",â¿ and design a recovery algorithm such that the output of the algorithm approximates xÌ,, the Discrete Fourier Transform (DFT) of x. The randomized case has been well-understood, while the main work in the deterministic case is that of Merhi et al. (J Fourier Anal Appl 2018), which obtains O(k² log^(-1) k â<. log^5.5 n) samples and a similar runtime with the ð"â,,/ð"â, guarantee. We focus on the stronger ð"_â^Z/ð"â, guarantee and the closely related problem of incoherent matrices. We list our contributions as follows. 1) We find a deterministic collection of O(k² log n) samples for the ð"_â^Z/ð"â, recovery in time O(nk log² n), and a deterministic collection of O(k² log² n) samples for the ð"_â^Z/ð"â, sparse recovery in time O(k² log³n). 2) We give new deterministic constructions of incoherent matrices that are row-sampled submatrices of the DFT matrix, via a derandomization of Bernsteinâs inequality and bounds on exponential sums considered in analytic number theory. Our first construction matches a previous randomized construction of Nelson, Nguyen and Woodruff (RANDOM'12), where there was no constraint on the form of the incoherent matrix. Our algorithms are nearly sample-optimal, since a lower bound of Ω(k² + k log n) is known, even for the case where the sensing matrix can be arbitrarily designed. A similar lower bound of Ω(k² log n/ log k) is known for incoherent matrices.
- 关键词：Fourier sparse recovery; derandomization; incoherent matrices
