Research map / Learning theory and algorithms / Matrix and tensor methods
Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first deterministic sublinear-time sparse Fourier transform for continuous-time signals with a frequency gap, using de-randomized hashing and a (C, ξ)-noise model.
Problem
Recovering a k-Fourier-sparse continuous-time signal with on-grid frequencies (frequency gap η, band-limit F) from noisy time samples in sublinear time, without randomness; prior continuous SFT algorithms were all randomized.
Approach
Generalizes the discrete deterministic sparse FFT of Li & Nakos (2020) to the continuous setting: a pessimistic-estimator derandomization selects a fixed hashing sequence that avoids bad collisions, combined with a continuous HashToBins procedure and a noise assumption (max of g^2 bounded by its average energy plus ξ).
Key results
- Deterministic algorithm uses O(k^2 log k log^2(F/η)) samples and O(k^2 log k log^3(F/η)) time to recover all heavy frequencies and amplitudes up to O(N) error under (C, ξ)-noise.
- Claimed to be near-optimal given the Ω(k^2) deterministic lower bound from Ganguly (2008) and Foucart et al. (2010).
- Prior randomized continuous SFT achieves eO(k · polylog(F/η)) time, so the deterministic method pays a k factor overhead.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use deterministic hashing and recursive sparse recovery | Continuous sparse Fourier transform · Continuous k-Fourier-sparse signals | samples: at least F/η = Ω(FT) -> O(k2 log k · log2(F/η)) | Helped |
| Use deterministic hashing and recursive sparse recovery | Continuous sparse Fourier transform · Continuous k-Fourier-sparse signals | runtime: O(k2 log k log3(F/η)) | Helped |
| Assume the noise satisfies the (C, ξ)-noise condition | Deterministic Sparse Fourier Transform · Continuous k-Fourier-sparse signals with noise | recovery error: O(N) | Helped |
Limitations
- Deterministic guarantee requires a (C, ξ)-noise assumption on the noise function, which excludes arbitrary noise.
- Sample and time complexity is quadratic in k, worse than the randomized eO(k) bound.
- Assumes on-grid frequencies and signal-to-noise ratio polynomial in F/η; the de-randomization step runs in poly(F/η) time.
Experimental setup
Baselines: Price & Song (2015) Chen et al. (2016) Jin et al. (2023)
Builds on: Li & Nakos (2020) Indyk & Kapralov (2014) Price & Song (2015) Kapralov (2017)
Closest papers by meaning
- Efficient $k$-Sparse Band–Limited Interpolation with Improved Approximation Ratio (NeurIPS 2025 · similarity 0.86)
- Fast Spectrally Sparse Signal Reconstruction via Jacobi-Preconditioned Gradient Descent (ICML 2026 · similarity 0.86)
- The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements (NeurIPS 2025 · similarity 0.85)
- Price of Parsimony: Complexity of Fourier Sparsity Testing (NeurIPS 2025 · similarity 0.85)
- A Fast and Provable Algorithm for Sparse Phase Retrieval (ICLR 2024 · similarity 0.85)
- Exponential Spectral Pursuit: An Effective Initialization Method for Sparse Phase Retrieval (ICML 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.