2026-07-25T01:46:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12484 2024-03-06T10:50:15Z ddc:004 open_access

Deterministic Sparse Fourier Transform with an 𝓁_{∞} Guarantee Li, Yi Nakos, Vasileios Fourier sparse recovery derandomization incoherent matrices 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 𝓁_∞/𝓁₁ 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 𝓁_∞/𝓁₁ recovery in time O(nk log² n), and a deterministic collection of O(k² log² n) samples for the 𝓁_∞/𝓁₁ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yi Li and Vasileios Nakos 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.77 urn:nbn:de:0030-drops-124844 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.77 eng https://creativecommons.org/licenses/by/3.0/legalcode