Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Authors: Xiaoyu Li, Zhao Song, Shenghao Xie
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we address this gap and introduce the first sublinear-time deterministic sparse Fourier transform algorithm in the continuous setting. Specifically, our algorithm uses e O(k2 polylog(F/η)) samples and e O(k2 polylog(F/η)) time to reconstruct the on-grid signal with arbitrary noise that satisfies a mild condition. This is the optimal recovery guarantee that can be achieved by any deterministic approach. ... In this work, we study the deterministic algorithm for the sparse Fourier transform in the continuous setting, which bridges a significant gap in prior research dominated by randomized approaches. By leveraging innovative techniques such as deterministic hashing, robust noise modeling, and recursive sparse recovery algorithms, the proposed method achieves optimal recovery guarantees in sublinear time. |
| Researcher Affiliation | Academia | 1University of New South Wales 2University of California, Berkeley 3Texas A&M University. Correspondence to: Zhao Song <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 Hash To Bins... Algorithm 2 One Sparse Recovery... Algorithm 3 Sublinear-time Sparse Recovery for bx bz... Algorithm 4 Sublinear-time sparse recovery for bx |
| Open Source Code | No | The paper does not provide any explicit statements about open-sourcing code, nor does it include links to a code repository. |
| Open Datasets | No | The paper introduces theoretical signal models like 'Definition 1.1 (Continuous-time, k-Fourier-sparse signal)' and 'Definition 1.3 (Noisy observation)' but does not mention the use of any specific public or open datasets for experimentation. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments on datasets, thus no dataset splits are discussed. |
| Hardware Specification | No | The paper describes theoretical algorithms and their complexity bounds; it does not report on experimental results or specify any hardware used for computations. |
| Software Dependencies | No | The paper is theoretical and presents algorithms and proofs. It does not mention any specific software dependencies or their versions for implementation or experimental purposes. |
| Experiment Setup | No | The paper is theoretical and describes algorithms and their properties; it does not include details on experimental setup, hyperparameters, or training configurations. |