Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Authors: Xiaoyu Li
Zhao Song
Shenghao Xie
Venue: ICML 2025 poster (2025)
Keywords: Fourier transform
sparse recovery
derandomization
sublinear time
Primary area: general_machine_learning->representation_learning

Abstract: The Fourier transform is a fundamental tool in computer science and signal processing. In particular, when the signal is sparse in the frequency domain---having only $k$ distinct frequencies---sparse Fourier transform (SFT) algorithms can recover the signal in a sublinear time (proportional to the sparsity $k$). Most prior research focused on SFT for discrete signals, designing both randomized and deterministic algorithms for one-dimensional and high-dimensional discrete signals. However, SFT for continuous signals (i.e., $x^*(t)=\sum_{j=1}^k v_j e^{2\pi \mathbf{i} f_j t}$ for $t\in [0,T]$) is a more challenging task. The discrete SFT algorithms are not directly applicable to continuous signals due to the sparsity blow-up from the discretization. Prior to this work, there is a randomized algorithm that achieves an $\ell_2$ recovery guarantee in $\widetilde{O}(k\cdot \mathrm{polylog}(F/\eta))$ time, where $F$ is the band-limit of the frequencies and $\eta$ is the frequency gap.
Nevertheless, whether we can solve this problem without using randomness remains open.  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 $\widetilde{O}(k^2 \cdot \mathrm{polylog}(F/\eta))$ samples and $\widetilde{O}(k^2 \cdot \mathrm{polylog}(F/\eta))$ 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.

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Xiaoyu Li!
Zhao Song?
Shenghao Xie
Abstract
computer science and applied mathematics. Its applications include integer multiplication (Fürer, 2009), SUBSET SUM and 3SUM (Cormen et al., 2009; Bringmann, 2017; Koil- iaris & Xu, 2017), linear programming (Lee et al., 2019; Jiang et al., 2021), distributional learning (Diakonikolas et al., 201 6atb;c), learning a mixture of regressions (Chen et al., 2020), fast Johnsoo--Lindenstrauu transform (Lu et al., 2013), and TensorSRHT (Ahle et al., 2020; Song al., 2021) with its applications to optimization (Song et al., 2024). In applied math, the Fourier transform is a key math- ematical tool in solving partial differential equations and performing function approximation (Evans, 2022; Smets et al., 2023; Helwig et al., 2023).
The Fourier transform is fundamental tool in computer science and signal processing. In par- ticular, when the signal is sparse in the frequency davain-baving only k distinct frequencies- sparse Fourier transform (SFT) algorithms can recover the signal in a sublinear time (propor- tional to the sparsity k). Most prior research fo- cused on SFT for discrete signals, designing both randomized and deterministic algorithms for one- dimensional and high-dimensional diserete sig- nals. However, SFT for continuous signals (i.e., x² (t) = Σド= U,e2misit for E [0, T') is more challenging task. The discrete SFT algorithms are not directly applicable to continuous signals due to the sparsity blow-up from the discretization. Prior to this work, there is a randomized algo- rithm that achieves an l recovery guarantee in Ókk polylog( (F/n) time, where F is the band- limit of the frequencies and 17 is the frequency gap. Nevertheless, whether we can solve this problem without using randomness remains open. In this work, we address this gap and introduce the first sublinear-time deterministic sparse Fourier trans- form algorithm in the continuous setting. Specif- ically, our algorithm uses Ō(k². polylog( (F/1)) samples and Ō volylog(P/n)) time to recon- struct the on- grid signal with arbitrary noise that satisfies mild condition. This is the optimal recovery guarantee that can be achieved by any deterministic approach.
The Fourier transform also has wide range of world ap- plications, including signal processing, electrical engineer- ing, pattern recognition, image/audio/video compression, etc. The famous random Fourier feature methods (Rahimi & Recht, 2007; 2008; Le et al., 2013; Yang et al., 2014; Yu al., 2016; Tancik al., 2020; Li al., 2020; Cheng et al., 2023) bridge the classical Fourier analysis and mod- ern kernel methods. In recent years, Fourier transform has also emerged powerful tool within machine learning research, inspiring diverse models and algorithms (Lee et al., 2020; Choromanski et al., 2021; Li et al., 2021; Song & Yu, 2021; Song et al., 2023b; Yu et al., 2023; Yi et al., 2023; Tran et al., 2023; Bonev et al., 2023; Zeng et al., 2024; Tan et al., 2024; Xiao al., 2024; Chen al., 2024; Liang et al., 2024; Zhou al., 2024; 2025; Alman & Song, 2025; Li et al., 2025; Yu et al., 2025). Due to its significance in both theory and practice, finding an efficient algorithm to compute the Fourier transform is of utmost importance.
Since the seminal fast Fourier transform (FFT) algorithm given by Cooley & Tukey (1965), the community has been looking for a faster o(N log N) time algorithm, but has not yet had success. In contrast, as quoted from Indyk & Kapralov (2014):
1. Introduction
The Fourier transform (FT) was introduced by Joseph Fourier in 1822 (Fourier, 1822). Today, it is widely used in
'University of New South Wales University of California, Berkeley "Texas A&M University. Correspondence to: Zhao Song <magic.linuxkdee @ gomi.
"Many of these upplications rely on the fact that most of the Fourier coefficients of the signals are small or equal to zero, i.e., the signals are (ap- proximately) sparse."
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
That is, when the Fourier spectrum approximately k-

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
sparse for a sublinear parameter l: = o(N), we can expect better sublinear-sampletine algorithms. This motivates the studies on the sparse Fourier transform problem (Sparse FT).
Definition 1.2 (Possible range of active frequency). For given frequency gap y and bounded range [-F, F), we define the possible range of active frequency the set
F {i Vi E. and 17 F]}
Over the last two decades, the Sparse FT problem has been extensively studied. The prior works mainly follow two lines: (i) those in the discrete settings (or the compressed sensing literature) (Goldreich & Levin, 1989; Kushilevitz & Mansour, 1993; Mansour, 1995; Gilbert et al., 2002; Akavia et al., 2003; Candes & Tao, 2006; Donoho, 2006; Rudelson & Vershynin, 2008;
In our observation of signal x (t), we receive a time-varying noise, denoted by continuous function g(l) R - C. The observed att) is the sum of the ground-truth signal x (t) and g(t). Formally, we define the model of noisy observa- tions, which is commonly used in the literature (e.g. Price & Song (2015); Chen et al. (2016); Song et al. (2023a)). Definition 1.3 (Noisy observation). We define the observed signal z(t) as follows:
Blumensath & Davies, 2008; Hassamich et al., 2012b;a; Cheraghchi et al., 2013; Iwen, 2013; In-
dyk et al., 2014; Indyk& & Kapralov, 2014; Bourgain, 2014;
Kapralov, 2016; Haviv & Regev, 2016; Kapralov, 2017: Li
& Nakos, 2020; Kapralov al., 2019; Nakos et al., 2019;
h =(():=='(()+ g(1)= = Σ
uze 2 + +g(t)
:-)=="" +1)++
Nakos & Song, 2019; Song, 2019); and (ii) those in the con- tinuous setting (Boufounos et al., 2012; Moitra, 2015; Price & Song, 2015; Chen et al., 2016; Chen & Price, 201 20;;;;a; Song, 2019; Jin et al., 2023; Song et al., 2023a).
j=1
where g(t) is an function.
Currently, all of the previous sublinear CFT algorithms are randomized. It natural to define and study the continuous setting where deterministic algorithm is possible. This work presents positive answer to that.
Although more researchers have concentrated their atten- tion on DFT algorithms, a continuous Fourier transform (CFT) is also essential, since many practical signals are continuous in nature. In the continuous setting, one can ob- serve x=()= = x= (t) + gt), where x² (t) is the ground-truth signal whose frequencies are real numbers, and g(t) is time-varying noise with a suitable signal-to-noise ratio. The heavy frequencies are assumed to have a frequency gap v), i... the minimum distance between two heavy frequencies is at least 1). Moreover, the sparsity parameter lo satisfies k o( (F/n), where F is the band-limit of the signal. CFT algorithms recover the heavy frequencies by sampling in the time domain.
1.2. Our Result
We state main result as follows:
Theorem 1.4 (Main result, informal version of Theo- rem 3.12). 7) F denote the candidates of heavy frequency. Let g(l) denote the noise whose Fourier spectrum spans the entire frequency domain, and it satisfies mild assumptions in the time domain. Let z(t) ==x" (t) + g(t) denote the observed signal. For T 2 (11/n), there exists deterministic algo- rithm that observes the signal at time points in S C [0, T] of size OSk log k log" (F/T)), and recovers all f. and e; accurately in O log k log' (F/1)) time.
-.. 17, 17...., F ,F-
1.1. Problem Formulation
We study the Fourier transform of a continuous k-sparse signal defined as follows.
Definition 1.1 (Continuous-time, k-Fourier-sparse signal). Let ke E Zzo Let 81. (f) denote the Dirac function centered at fi E R. We define the k- k-Fourier-pparse signal E² (f) to
We remark that the straightforward approach of discretiz- ing the signal and applying the standard FFT requires at least F/n = R(FT) samples to achieve the desired reso- lution. However, this method is not robust to noise, as it cannot effectively separate the signal components from the noise gt),, which spans the entire frequency domain. In contrast, our algorithm reduces the sample complexity to Ōk*2), which is sublinear in FT, by leveraging the sparsity structure of the signal. Furthermore, our method robust to noise, enabling accurate recovery of frequencies f. and amplitudes i; with significantly fewer samples compared to traditional FFT-based approaches.
be as follows:
x²(1)= = Σ 1=1
0j 2niht
CFT
F())== = Σ oj ()) 1=1
where by E C is the coefficient and f, E F is the frequency contained in the frequency range F C IR for each j E [k]. We use K to denote the set of f, 's.
Moreover, we assume that the frequency range F is a set of equidistant points in [-F, F). See the formal definition below, and we assume that active frequency of signal xt) can only be taken in a finite set defined as below.
Moreover, our algorithm achieves nearly optimal sample complexity and runtime due to the (2k-2 deterministic lower bound established in Ganguly (2008); Foucart et al. (2010).
2

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
2. Preliminaries
and the Continuous Inverse Fourier Transform is defined as
In this section, we introduce some basic definitions and tools in sparse Fourier transforms. In Section 2.1, we intro- duce the notations in this paper. In Section 2.2, we formally define the discrete Fourier transform and the continuous Fourier transform. In Section 2.3, we define the convolution of two functions. In Section 2.4, we introduce the hash functions used in our algorithms. In Section 2.5, we intro- duce the filter functions that isolate the heavy-hitter in each hashing bucket. In Section 2.6, we define the measurement of the signal under the filter function.
x(t)= - S e
2wiot do.
2.3. Convolution
We define the discrete and the continuous convolution as follows.
Definition 2.3 (Convolution). For two functions f:g with same domain D, we have
/
* g)() = JIED f(t ((t-r) () -(()5.
2.1. Notations
For two vectors f.g with same length n, we have
We use a 2 b denote a 2 C for some constant C > Let n be positive integer, [n]] := 21, nn.. We use i i:= V-1, and we use to represent e 222 for simplicity of notion, e.g., we sometimes write e e as w². For complex number E C with = a + ib where a, E TR. We use |z| to denote va² + G2 2 can also be expressed as 2 = r. e. where r E Ry0 and f E [o. [z..... We define arg(=) = 0. Let [2,} be a sequence of complex numbers. It's median is defined as median 2; = median Re(z.) + i median I=)).. We use Pr] to denote probability. We use E] denote expectation. For R. we use (2) to denote the integer with the closest distance to x. Let x i + where is an integer and E [0, 1), we define x (mod 1) := q. Let xtt): : R + C be a function. For a finite set S C I. we define || == Eies (r(t)] Now, let S be a finite sequence, we define as as the vector in which the 1-th entry is ((,)) where S, denotes the (-th element in S. We use O2 to denote vector formed by zeros.
* (
Eis 9j.
2wi
2.4. Hash Functions
In this section, we introduce some hash functions used in sparse Fourier transform algorithms.
Definition 2.4 (Hashing functions, Definition 4.1 in Li & Nakos (2020), Section 3 in Hassanieh et al. (2012b) Defini- tion A.5, A.6, A.7 in Price & Song (2015)). Let a E R and b E [- F]. Let B be the number of buckets.
We define function To.b : F [0, 1] to be To,b(f) := off bb) (mod 1). We define function ho.b [B] be
horb(S) == round TT,b(
2.2. Fourier Transform
Fix f E F, we define function 0f : F - [0, 1] to be
We define the discrete Fourier transform (DFT) and the continuous Fourier transform (CFT) below.
"f,,((f') == Te,((f)) (
Specifically, ho, hashes a frequency / to one of the B
Definition 2.1 (Discrete Fourier transform). Given a com- plex vector x E C", we say that F is the discrete Fourier transform matrix if
buckets, and (ff',((()) measures the offset of a frequency f' to the center of the bucket containing f-
Definition 2.5 (Pseudorandom Permutation, Definition 4.2 in Li & Nakos (2020), Definition A.1 in Price & Song (2015)). For a E R, a E [0,T),b [-F, F). the permutaa- tion Po.a. is defined as
1 201-i//n Vn
Fiy :=
We define the discrete Fourier transform of x to be
(Pana)))() = x a)) tab
Fx.
Definition 2.6 (Sequence of Hashings, Definition 4.4 in (Li & Nakos, 2020)). We use {(or, Op. by))re(d to denote the parameters of a sequence of d hashings. Each (ar, ar, br,b)) by) specifies three hashing functions: Tar hor 0f.arebet and one pseudo permulation: Pr....h..
Definition 2.2 (Continuous Fourier transform). Given function x(t): [0,T] E C and [ - C, the continuous Fourier transform is defined as
Definition 2.7 (Tuple of Hashing). We use H = (a, b) to denote a tuple of hashing. In a sequence of hashings ((r,, ar, by) )re (d), we use H,, to represent (ar, or.,0r,b) by).
$() f x(r)e 2 2 dr,
_oc
3

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
2.5. Filter Functions
Claim 2.11. Under the conditions of Definition 2.10, we
have
Filtering is one of the most important techniques for sparse Fourier transform, which allows us to isolate each individual frequency and reduces the h-sparse signal to set of "almost" one-sparse signals.
(Gos (mn(((()))ost))) w w
Uy + (Gog.ool)))
Σ
Gornallt op warls' -f)
N'EWW
Definition 2.8 (Filter function in the continuous setting, Definition A.3 in Price & Song (2015), see discrete vari- ations in Definition 4.6 in Li & Nakos (2020), Definition 2.3 in Kapralov (2017), Definition 2.3 in Hassamieh et al. (2012b)), Let B E E be power of two. Lel N be some fixed integer. Let offset o be defined as Definition 2.4. We say G : [0, 1] + R, with G being its Fourier transform, is a flat filter with B buckets, sharpness e if the followings hold:
Proof. By the definition of mn (Definition 2.10), we have
(ān)eo(())) (mH)).wC) w-ars
(Co)aa(t))~1 (E
Goooooty + wool' up)) w waos
PEF
= Uy + (Ga
Σ
G Gosaadtyyya
M'FW(
Property 1: Gog. E [0, for all 0f,rb E [0, 1]
Thus the proof is complete.
Property 2: Goj.or 2 1- - e for all o, E =1- 1 1
2B : 2B
3. Technical Overview
Property 3: Goy... S efor al, E |10, [0,1 1
In this section, we provide an overview of our contribution. We start by summarizing the framework in (Li & Nakos, 2020) in Section 3.1, then present our algorithm's 's motivation and details in Section 3.2.
Property 4: Eiez
Property 5: Supp(G) c [-D,D) where D. is O()og(B)) rounding to the closest integer
3.1. Summary of previous works
Remark 2.9. The construction of (G, G) can be found in (Price & Song. 2015) and (Jin et al., 2023). Notice that G: [m] + IR in their construction, we can simply extend to our setting by scaling.
Sparse FFT algorithm searches for the active frequency by binning them into a small number of bins. In the discrete setting, Hassanieh et al. (2012b;a) introduced new meth- ods for locating the isolated signal and updating the signal by directly filtering the bins, which improved the time and sample complexity. Indyk Kapralov (2014) presented recursive single-entry reduction algorithm which gives a fo norm guarantee. Based on their result and modified HASHTOBINS with initial guess from Kapralov (2017), Li & Nakos (2020) introduced deterministic algorithm by de-randomization w.r.t. the hashing functions. In the con- tinuous setting, Price & Song (2015); Chen et al. (2016) defined the k-sparse continuous signal and used random- ized sampling technique to control viryingrying noise. They extended the guarantee of the fast DFT algorithm to the continuous setting by identifying between CFT, DTFT, and DFT, which is helpful in the analysis of our work. Jin et al. (2023) is a dingeerrdimessional generalization of Price & Song (2015). In this work, we provide the first deter- ministic continuous sparse FT algorithm. We result a mixe-mmixed norm guarantee for error. We also note that another line of work focuses on the sparse Fourier transform over Boolean hypercube or Abelian groups (e.g.. Goldreich & Levvn (1989); Akavia et al. (2003); Iwen (2007); Akavia (2010)). They have important applications in Boolean func- tion analysis and complexity theory. However, the settings of these papers are very different from the compressed sens- ing fashion and thus beyond the scope of our work.
2.6. Measurement
This section defines the notion of measurement. It formal- izes the output of a central subroutine HASUTOBBNS pre- sented later, which recovers the active tones by performing DFT on the filtered signals in each hashing bucket. The following definition is the measurement without noise.
Definition 2.10 (Measurement without noise, implicitly in Lemma 3.4 in Price & Song (2015), see discrete variation in Definition 4.8 in in Li & Nakos (2020)). Let the sig- nal and frequencies R, v be defined as Definition 1.1. Let H (a,a, b) b) be a tuple of hushing. Let G be a flat filter with B buckets and sharpness (refer to Definition 2.8). A measurement mu mz()() E CB is defined as, for all hf, E [B].
(mn (mn(F(Maass))))
Σ Cognssryy wass Uff JEF
where at is hash function induced from H.
The next statement states an equivalent formulation of the measurement.
4

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Contribution of Li & Nakos (2020) and their limitation in the continuous setting. During the hashing and detec- tion of active signal, it is possible that two distinct active frequencies are hashed into the same bin and hence can- not be recovered. I. & Nakos (2020) gave a formal defi- nition of this event and used a de-randomization strategy to find a fixed sequence of hashing functions that prevent this event. Their method uses a pessimistic estimator to upper-bound the possibility of bad events and reduce it by choosing proper bashing parameters. Then, they embed- ded this deterministic H HASHTOBINS algorithm into the & norm reduction algorithm in Indyk & Kapralov (2014) to reach the final result.
rameters of the hash function. We use function of,o, (I") to
measure the distance from the hashing of f' to the center of the bucket' where f is hashed into. (See Definition 2.4 for the formal definitions of the hash functions.) Morally, if of,a.s()) is small and ff.0,5 (f') is big, i.e., f is hashed close to the center of a bucket, while f is not close or in a different bucket, then we can discover s by the filter function. However, two active frequencies. f and f', may hash to the same bucket, obstructing the discovery. This motivates us to define bad events as follows. Intuitively, it says that although we cannot guarantee that the collision of f and f' does not happen in a single turn of hashing, we can control the total time of the collision in a sequence of hashing. Then, we can run the algorithm multiple times and take the median of outputs to reach good approximation.
Notice that the strategy of Li & Nakos (2020) is not directly feasible for continuous signals. Because there is only finite light-hitter in the discrete setting, it can traverse all frequency points and generate a deterministic hashing se- quence. However, we need to deal with the continuous noise function in our algorithm. Moreover, the hashing scheme in the discrete setting cannot be applied in the continuous setting. Unlike DFT, our CFT algorithm takes samples from the time interval of unequal length with the active frequency set, leading to a different hashing and filtering strategy. We must change our de- randomization steps to fit the new hash- ing functions.
Definition 3.1 (Bad Events ), We use d to denote the time we call HASHTOBINS in one round of sparse detec- tion. We use 3 as a factor depending on [F], which will be determined later. Let {(ār, br)] be a sequence of hash- ing parameters. For any f. f E E f & f', we define As, to be the event that
d
G Cofton,, (P) 2 2,3.
Previous CFT research (e.g. Price & Song (2015); Jin et al. (2023)) used a randomized hashing function to control the impact of bad events. They bounded the expectation of error in each stage and repeated multiple stages to reach a small failure probability. Different from them, this work finds sequence of deterministic hashing function {(o,,, 6,) }d= which prevents the happening of bad events. We use h, to denote a pessimistic estimator, tracking the probability of undesirable events (such as hash collisions) given the first selected hash functions. The recursive procedure can be summarised as follows.
3.2. Our techniques
In this work, we generalize Li & Nakos (2020) to the con- tinuous setting and overcome the limitations. In this section, we first discuss the problem setting. Then, we show how to generate the de-randomized hashing sequence under the hashing scheme of sparse CFT. Next, we propose a reason- able noise model ((C, -niss,,, Definition 3.3) that enables an efficient and robust deterministic sparse Fourier trans- form algorithm. We further show how to combine the contin- uous HASHTOBINS with the de-randomized hash sequence. Then we incorporate it with a recursive sparse recovery al- gorithm, which leads to our main theorem (Theorem 3.1 3.)
I) Initial state: Let ff o1, b..... b,) be se-
quence of function satisfying
In Section 3.2.1, we summarize our de-randomization steps. In Section 3.2.2, we define the (C, -)-iieee. In Section 3.2.3, we introduce the continuous variate of essential subrou- tine HASHTOBINS. In Section 3.2.4, we provide our main algorithm.
Σ hol,, <1
Notice that ho is determined at initial state while h f') depends on o,, b, which are chosen later.
2) De-randomization step: Let Pr[AA,r 01. bi....... o,, b, be defined as the probability of bad events conditioned on ((ar, by) ) Given hf, 01, b,, "r,,,,,,,, b,), we choose or br+1 to satisfy the inequalities below.
3.2.1. DE-RANDOMIZATION.
To discover the active frequencies from F, we use a hash- ing and filtering method. First, we hash the points in F into B- = O(k) buckets (where each bucket is the union of comb-like, equispaced intervals on the real line). Then, we use a pair of filter functions (G, G) to select the active frequencies. G is constructed to be close to in the center of its domain and close to 0 elsewhere. Let a, b be the pa-
(f ... ,r-,, br+1) 2 Pr[AAsr o1,b,,.... bi.....,,rr......... Tr+1, br+1],
More precisely, the center of any internal that contains f in that bucket.
5

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
and
A canonical example satisfying the (Cçie-noise condition is any bi-Lipshitz function. A function g [0, T] - IR is (L1, bi-Lipshht if for all &1, 12 E [0, T', it holds that
1 fi; ,rt1, (f, f bi,b,.... ,,,,,,, b,).
L2/41 - 12| s (9((1) - g(<2) S L1/41 - 12).
3) Final state: The procedure ends d.
The next statement shows how it satisfies our assumption.
This process outputs {(o,, br)] such that
Lemma 3.4. Let g be integrable (L1, L2) La)-bi--ipsshhizz function. Then it satisfies the condition of the (C,E) g)-nise.
Σ
Pr(AAs 01, br,,b.....oo. oa, bal < 1.
Proof. Let Jmin minimum value of g() and let t be the time that achieves the minimum. Then we have
Since Ar.5 11.bi, bi.bi.....00 od. by is a determined event, the probability of the occurrence of bad events is zero. Using this specific hashing tplle sequence, we can safely hash the possible active frequency points. We note that this process does not depend on the observed signal, and the good hash- ing parameters can be found efficiently in the preprocessing (see Definition A.6 for more detailed discussion the pessimistic estimator).
g(t) dt -T -Inin
/ g(t)² - -miin dt
(o(t) + (m 9min)
Lemma 3.2 (De-randomization, Informal Version of Lemma A.21). Let F be the range of active frequency defined in Definition 1.2. Let C1 be some fixed constant in ( 1). Let E Zgo be a power of 2. Let e == B. 6 = CT log [F), and d == 3C1 B log [F). Let Ha f(o,, ar, be,be)lre(d be a sequence of hashing chose by pro- cedure in Definition A.6. Let G be a flat filter in accordance of hashing functions in Hr (see Definition 2.8). Then it holds that, for all S FF with J &.,
[ 9min Lilt t L t" 1
2 C(L1) * (Amin 2
I2 T
where the third step follows from the definition of the (L,, bii-b--sphht function, i.c., L2|2; - Ø21 S [g(z))- g ((22) and the last step hides constant ((L1) that depends on L1- On the other hand, let Imax be the maximum value of (l), we have Jmax S Jmin L2T, therefore,
B
Go rE(d]
5
1-e
1 ] f'" g(t) T
P S C(L1,
3.2.2. (C, (NNOISE
where C(L1, L2) is a constant that depends on L1 and Lg- Thus, g(t) satisfies the definition of the (C, nnoise by taking G C(L,, Lz) and 0.
Similar to controlling the effect of bad events, Price & Song (2015); Jin et al. (2023) use the randomness of their sample technique to de-noise. However, it is hard to tackle the noise when we apply a deterministic algorithm, since we can only take samples at finite points. For example, if gt)) extremely large at our fixed sample points compared to its integral, then it will disturb our observation and prevent the active frequency from being detected. Therefore, we need to introduce extra assumptions on the upper bound of the noise function. Our assumption consists of the energy bound and a (ffedddendd factor ç. which describes the suitability of g(t) for a deterministic algorithm. Formally, we define the (C, -n-oie as follows.
Therefore, our assumption mild and suitable for wide variation of noise functions.
3.2.3. DETERMINISTIC HASHTOBINS UNDER CONTINUOUS SETTING
HASHTOBINS is commonly- algorithm in FFT. It takes discrete samples from the time interval and uses DFT to measure the signal in each hashing bucket. This measure- ment reflects the tone of active frequency in the correspond- ing bucket. Kapralov (2017) applies modified HASHTO- BINS algorithm to determine the active tones in the discrete setting recursively. Our work extends this algorithm to the continuous setting.
Definition 3.3 ((C, -)-nois)). Let g(!) : [0,7] + R be the noise function. Let C. 0 be some fixed constant. Let & be parameter depending on g(t). Then we say g(t) is (C, noise if it satisfies
max g(t) < C. T 1 tE
For simplicity of notation, we define a vector Vy E Cl- as below to represent the k-sparse tones of signal 3 (f).
6

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Algorithm 1 HashToBins
by the de de-randomization process. Let uy be the oulput of HASHTOBINS(2, H,). We define
procedure HASHTOBINS(Z, 2, H (o, a. b))
2:
Lemma 3.6
N(
3: for jr E [BD] do
4: Vj < G(G (a.))PP..)))())
Σ fer
[(II++
+
CC log k
J. T
lo(0))de+)) )
5: end for
ak
k
6: for j E [B]do do
UBi+s G (o)oB())(iB))
Then, we have, for all f E F.
7: Uj
8: end for
w
median G-1
( (Ur (orr S (VO)
9: return The DFT u E C of
re|d]
10: end procedure
3.2.4. RECURSIVE SPARSE RECOVERY ALGORIHTSS
Finally, we construct our main algorithm by embedding HASHTOBINS into a recursive sparse recovery algorithm, which is in line with the idea of Indyk & Kapralov (2014) and (Li & Nakos, 2020). In each iteration, we run HASH- TOBINS measure the difference between the true tone uy threshold
Definition 3.5. Consider (1) Si E F as a finite se- quence of points ordered by their magnitude in the frequency interval. Recall E0 (f) = ン U/ ō,, (f). Let v == 0, fi is active frequency; otherwise, vf := O.
and the approximated tone Σ Then, to determine whether to change the approximated tone. We set the recovery threshold v O(N) in the initial stage and scaled by a constant 7 in each iteration. This gives us super-linear time sparse recovery algorithm (see Ap- pendix B). Since detection is applied to each entry of e, this algorithm has an error bound in fo norm.
Given an initial guess 2 FI and a discrete sample of signal z(t), this algorithm can return the bucket-wise mea- surement of the difference between and Σ. The guarantee of this procedure is stated as follows.
Lemma 3.6 (HASHTOBINS, Informal Version of Lemma B.5)). We use B to denote the number of buckets. We use ha,(s) to denote the index of the bucket where f is hashed into. Given a vector 2 c! there exists deterministic procedure HASHTOBINS which computes E " with the following guarantee: for any f E F.
Now, we discuss sublinear algorithm. In each iter- ation, we run HASHITOBINS O(log(F/n)) times to esti- mate Vy - wig0, for each heavy-hitter f. Here, q E Q := (20, 2,,,!.... ,200g=11) is the scaling factor we apply on the phase of each heavy-hitter. Then, we adopt a discrete one- sparse recovery technique in Li & Nakos (2020) to recover each f. The algorithm displayed in Algorithm 2.
Co 2x 2 PEF ( (o()))))e+++)))
Σ
0O log K k
Algorithm 2 One Sparse Recovery
The algorithm takes O(B log( B)) samples. The time com- plexity of the algorithm is O(B log²(B) + Bloog (nn).
1: procedure ONESPARSERRECOVERY(2))
b Lemma 3.8
for q Q do
The analysis of this lemma combines the bound for noise- less input (HASHTOBINS( (t), 2y)) and noise-only input (HASHTOBINS(ggC) 0 F)), where the former has similar performance to the discrete setting, and the latter is con- trolled by our assumption in (C, En-niee. Hence, our upper bound on error is the sum of ||3||2 he and the energy-E bound.
4:
d + 2
+ arg(#1//0))
9-1 di
Ig U 1=0
+
2q
4g
end for
7:
So + 11
8:
for E f1,,,..., ,og [Fl 1} do
9:
Sr,1 t S, n Ig
10:
end for
As mentioned, the de-randomization step finds deterministic sequence of hashing parameters that avoids bad events. Taking the median of output of HASHTOBINS (x, Σ, (a,, by)) for r E [d] gives a close ap- proximation of uy- -2.
11: Find 0 from Stng where f E
12: f' F
2T 13: return f
14: end procedure
Lemma 3.7 (HASHTOBINS with De-randomized hash se- quence, informal version of Lemma B.7)). Let B := (k) be a power of 2. Let Wy := Vf 2z. Let
We next state the guarantee of Algorithm 2.
Lemma 3.8 (One-Sparse Recovery, Lemma 6.1 in Li & Nakos (2020)). Suppose that |F] is a power 2. Let Q ==
(Hr)rew) = -(rr:br) be the sequence of hashing found
7

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
{0,2% 20,20,2,22 22.2222..... 111/223. Let x C² with the discrete Fourier transform T. Let x be the f-th entry of Let O5 FTS mod 2T. Let (xq3aEQ be sequence of metric of Iyf satisfying
$ J' it holds that,
B
Σ G Go
S
1-
aag((,)) (arg +00 4/8
where 3 is chosen the same as Lemma 3.2, then for any S. at least 0.8d indices r E [d] satisfy
Then ON:SAARSEREOVVEYYAooriii 2) recovers f by (TgbeE in Olog F/n) time.
1 Gof S MEN
Σ
B (
E
lugl-
P'E
Instead of traversing through each possible frequency in the super-linear time algorithm, we locate the heavy- hitters first, and then we do the recursive estimation of the tone each heavy-hitter. This reduces the O(F/n) time recovery to an (kk) time recovery, leading to the sublinear result. Algorithm embeds the above one-sparse recovery procedure recover the signal in sublinear time.
Next, once we have "good" hash sketches (Lemma 3.9), and provided we choose large enough, Algorithm 3 recovers all large entries and approximates them well.
Lemma 3.10 (Sublinear-timg sparse recovery for x informal version of Lemma C.4). Let T. v be defined as Definition 1.I. Let 2 C! Let B be chosen Defini- tion B.6. Let Wf - Zz. Let (()) be defined in Lemma 3.7. Let v 2 16N(() be constant to denote threshold for heavy index. Then the output of the Procedure SUBRECOVERY (Algorithm 3) W satisfies:
Algorithm 3 Sublinear-time Sparse Recovery for 3
1: procedure SUBLINEAR(r, ~)
Lemma 3.10
2: S 5to 0
3: for 11-1 + do
4: for E Q do
Tayl 2 (7/16)yfol for all supp(@"))
5:
Ugg + HASHTOBINS(Z, (ar, br))
6:
Lemmaa 3.6
my Tyy S y FTTT/Toor for all supp(w"),
7:
end for
8:
6 1 B do for
if
1 N 2ッ} C supp(
9:
<- ONESPARSERECCOVER (((gg) hEEq)
10:
Lemma 3.8
Finally, similar as Hassanieh al. (2012a) and Li Nakos (2020), we introduce the definition of signal-to-noise ratio R" It measures the ratio between each tone's magnitude and the average noise. We assume R = O (F) (F/n)), which allows us to run only O(log( F/n)) iterations of one- stage sparse recovery.
11:
S S+
12:
Uf.r + G-1
Gofion (s) (w))),())
end for
end for
15:
w'y <
16:
for f E S do
Definition 3.11 (Signal-to-Noise Ratio), We define the av- erage of noise v as
17:
Vy + median,e Vfr
b Lemma 3.9
18:
if |yyl > 2 then
19:
W - Vy
:==0 n
1 KT
end end for
C.
22: return /
Then, the signal-to-noise ratio R is defined as
23:
end procedure
== 1101lo0/11
Next, we provide the guarantee of the sublinear-time sparse recovery for Z. With the guarantee of de-randomization (Lemma 3.2), the following lemma shows how well the hashing sequence separates different heavy indices.
Based on all the above discussions, we obtain the main theorem. Here, we only present the sublinear time result since it outperforms the other algorithm when F/n >> k. Our main algorithm is displayed in Algorithm 4. It calls the SUBLINEAR procedure iteratively with geometrically decreasing threshold v(t), which recovers the sparse signal in log, R' rounds.
Lemma 3.9 (Separating Heavy Indices, informal version of Lemma C.3). Let H, = (ar, ar, by frea be a sequence of hashing defined in Definition 2.6. We have G being a flat filter with e buckets and sharpness e (see Definition 2.8). Let Fr be defined as Definition I. If for all f. E F with
The next statement shows our main result.
8

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Algorithm 4 Sublinear- time sparse recovery for 20
log(F/n) O(Blog(F/n)) Ollog B) O(B) = O(k log k log (F/n))
1: procedure MAIN(a: E (C))
Theorem 3. 12
2: T - log, R
where the first step is because we run T times SUBLINEAR, the 2nd step holds since 7 = O(log( (//n), the 3rd step is because we have hashing tuples (notice that the samples for un are reused in each iteration, so we only run d times HASHToBINs), the 4th step is by Lemma 3.6, the 5th step by choice of d (see Lemma 3.2), the 6th step is by B = (k) (see Lemma 3.6).
3: ;(0) + 0FF//7
4: (()) + Cuy"
5: fort t = 0 + T do
6: g((+1) t- g(0) + SUBLINEAR(C,, u10) b
Algorithm 3
7: v(++1) + v()) /7
8: end for
9: return 2
Proof of Running Time.
10: end procedure
By Lemma 3.6, the time complexity of HASHTOBINS is O log By Lemma 3.8, the time complexity of ONES- PARSERECOVERY is (log(F/n)) Taking the median from d results from HASITOBINS takes time Od))
Theorem 3.12 (Main result, formal version of Theo- rem 3.12). Consider any k-Fourier-sparse signal x (1)= =
- V/ 22ifz with on-grid frequencies fj E F for band-limit F and gap 1) (Definitions 1.1 and 1.2). Let
The time complexity of SUBLINEAR is
d dloo(F/nn) HASHTOBBINS
T 2 ((1/n)- For t. E [0, T), let æ(1) = x" (1) + g(t) be the noisy observation with signal-to-noise ratio R
+ dB ONESPARSERRCOVERY
poly(F) //), where g(t) is (C, -oisse (Definition 3.3) for some C, >> O. We define the noise level
+ log(F/n) T Median
= =dlo((4/nn) k log(k) + dB log(F/n) + log(F/)) d
= O(B (ooglo/)))))))o log(F (/////////////////
N:
1 K
EEE1 fEF
log h: 1yyl+
(//"" l0(t)pdt+))
+ + (F/))))())))))))))))))))))) Bogg))
K
+ +log(F/n) (olg(())))
Then, there exists deterministic algorithm (Algorithm 4) which finds -kk)-sprss vector 2 E Fl such that
= =O log k log2 (F/m))
where the first step follows from the time com- plexity of HASHTOBINS, OXESPARSERECOVERY and Taking Median, the second step is by the choice d, and the last step holds for B = ((:).
log - 23 S O(N) Vj E [k), and 12 S O(N)
of & (ft.....fe..
The algorithm takes Ok log k log(((//)) samples and runs in O(k2 log k log (F/n)) time.
Hence, the time complexity for the main algorithm is T O log k logg (F/n)) = O(2² log k (F/n))
Proof. Proof of Correctness.
since π² = =((F/n)m by the assumption, which allows us to run only T = O(lo((Fnn) itcrations of one-stage sparse recovery.
Notice that we have the same guarantees in Lemma 10 as in Lemma B.8. Therefore, in Algorithm 4, we directly replace the super-linear time sparse recovery algorithm Su- PERLINEAR with the sublinear time sparse recovery algo- rithm SUBLINEAR. Then, the proof of the correctness is the same as that of super-linear time algorithm (Algorithm 6 in Appendix B).
4. Conclusion
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 ran- domized 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. This advancement not only extends the theoretical boundaries of sparse Fourier transforms but also paves the way for prac- tical applications in signal processing, machine learning, and beyond, particularly in scenarios where deterministic solutions are desirable.
Proof of Sample Complexity.
The sample complexity of the algorithm is counted as below,
Sample Complexity
T SUBLINEAR
log(F/n) SUBLINEAR
= Log(F/n) d HASHTOBINS
Log(F/n)-4) (oBlog(())
9

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Acknowledgements
Bringmann, K. A near-linear psendopolynomial time al- gorithm for subset sum. In Proceedings of the Twenty- Eighth Annual ACM-SIAM Symposium Discrete Al- gorithms (SODA), pp- 1073-1084, SIAM, https: mexiv.org// pdf 1 61 0 04712. pdf, 2017
The author would like to thank the anonymous reviewer of ICML 2025 for their highly insightful suggestions.
Impact Statement
Candes, E. J. and Tao, T. Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE transactions on information theory, 52(12):5406 2006.
This paper presents work whose goal is to advance the field of Machine Learning and Signal Processing. There are many potential societal consequences our work, but none of which we feel must be specifically highlighted here.
Chen, S., Li, J., and Song. Z. Learning mixtures of lin- regressions in subexponential time via Fourier mo- ments. In STOC. https: /awxiv.iiivv///ai//eeaa/aaaaa owt.ooggg///oooooo / 97629.pdf, 2020.
References
Ahle, D., Kapralov, M., Knudsen, J. B. T., Pagh, R., Vel- ingker, A., Woodruff, D. P., and Zandieh, A. Oblivious sketching of high-degree polynomial kernels. In Pro- ceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 141-160, 2020.
Chen, X. and Price, E. Active regression via linear- sample sparsification. In Conference on Learning Theory (COLT), pp. 663-695, PMLR, 2019a.
Chen, X. and Price, E. Estimating the frequency of clustered signal. In 46th International Colloquium Automata, Languages, and Programming (ICALP 2019). Schloss-Dagsuuh--LLibiii Zentrum für Informatik, 2019b.
Akavia, A. Deterministic sparse Fourier approximation via fooling arithmetic progressions. COLT, pp. 381-393, 2010.
Akavia, A., Goldwasser, S., and Safra, S. Proving hard-core predicates using list decoding. In 44th Symposium on Foundations of Computer Science (FOCS), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pp. 146-157. IEEE Computer Society, 2003. doi: 10. N0.1109/SFCS.200. 1238189.
Chen, X., Kane, D. M., Price, E., and Song, Z. Fourier- sparse interpolation without frequency gap. In 2016 IEEE 57th Annual Symposium Foundations of Com- puter Science (FOCS), pp. 741-750. IEEE, 2016.
Chen, Y., Huo, J., Li. X., Liang, Y., Shi, Z., and Song, Z. Fast gradient computation for rope attention in almost 2024.
Alman, J. and Song, Z. Fast rope attention: Combining the polynomial method and fast Fourier transform. arXiv preprint wxXi:2255..1880 2025.
linear time. arXiv preprint arXiv:
Cheng, K., Jiang, H.-C., Wei, L., and Wei, Z. On the relative error of random fourier features for preserving kernel distance. In The Eleventh International Conference Learning Representations (ICLR), 2023.
Blumensath, T. and Davies, M. E. Iterative thresholding for sparse approximations, Journal of Fourier analysis and Applications, 14(5-6):629-633 654, 2008
Cheraghohi, M., Guruswami, V., and Velingker, A. Re- stricted isometry of Fourier matrices and list decodability of random linear codes. SIAM Journal on Computing. 42 2013.
Bonev, B., Kurth, T., Hundt, C., Pathak, J., Baust, M., Kashinath, K., and Anandkumar, A. Spherical fourier neural operators: Learning stable dynamics on the sphere. In International conference on machine learning (ICLR), pp. 2806 2800002222..22 PMLR, 2023.
(5):
Choromanski, K. M., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, Q., Mo- hiuddin, A., Kaiser, L., Belanger, D. B., Colwell, L. J., and Weller, A. Rethinking attention with performers. In International Conference Learning Representations (ICLR), 2021.
Boufounos, P., Cevher, V., Gilbert, A. C., Li, Y., and Strauss, J. J. What's the frequency, Kenneth?: Sublinear Fourier sampling off the grid. Algorithmica(A preliminary version of this paper appeared in the Proceedings of RANDOM/APPROX 2012. LNCS 7408, pp.61-72), pp- 1-28. Springer. 2012.
Cooley, J. and Tukey, W. An algorithm for the machine calculation of complex Fourier series. Mathematics of computation, 19(90))297-3011 1965.
Bourgain, An improved estimate in the restricted isometry problem. In Geometric Aspects of Functional Analysis, pp. 65-70. Springer, 2014.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to algorithms. MIT press, 2009.
10

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Diakonikolas, I., Kane, D. M., and Stewart, A. The Fourier transform of poisson multinomial distributions and its algorithmic applications. In Proceedings of the forty- eighth anmual ACM symposium on Theory of Computing (STOC), pp. 1060-1073, 2016a.
forty-fourth annual ACM symposium Theory of com- puting, pp. 363-578, 2012b.
Haviv, I. and Regev, O. try property of subsampled Fourier matrices. In SODA, pp. 288-297. tttpss//arxiv..oo 1507.01760 01w.0116.... pdf,, 2016.
The restricted isome-
Diakonikolas, I., Kane, D. M., and Stewart, A. Optimal learning via the Fourier transform for sums of indepen- dent integer random variables. In Conference on Learning Theory (COLT), pp. 931-849, 2016b.
Helwig, J., Zhang, X., Fu, C., Kurtin, J., Wojtowytsch, S., and Ji, Group equivariant Fourier neural operators for partial differential equations. International Conference Machine Learning (ICML), pp. 12907-12930. PMLR, 2023.
Diakonikolas, I., Kane, D. M., and Stewart, A. Properly learning poisson binomial distributions in almost polyno- mial time. In Conference Learning Theory (COLT), pp. 850-878, 2016c.
Indyk, and Kapralov, M. Sample-optimal Fourier sam- pling any constant dimension. In IEEE 55th An- nual Symposium onFoundations of Computer Science (FOCS), pp. 514-523, IEEE, https: /tpps///rree //taaaixivv.rg../.. pdf 1111143..4 .8.00.5880000 5804 pdd,, 2014.
Donoho, D. L. Compressed sensing. IEEE Trans. Informa- tion Theory, 12(4):2289-133) 2006.
Evans, L. C. Partial disferential equations, volume 19. American Mathematical Society, 2022.
Indyk, P., Kapralov, M., and Price, (Nearly) Sample- optimal sparse Fourier transform. In Proceedings of the Twenty- Fifth Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 480-499. SIAM, 2014.
Foucart, S., Pajor, A., Rauhut, H., and Ullrich, T. The gelfand widths of by-balls for 0 p S 1. Journal of Complexity, 26(6):629-644) 2010.
Iwen, M. A. A deterministic sub-linear time sparse fourier algorithm via non-adaptive compressed sensing methods. arXiv preprint arXiv:0708. 2007.
Fourier, J. B. b. Théorie analytique de la chaleur. F. Didot, 1822.
Fürer, M. Faster integer multiplication. SIAM Journal Computing, 39(3):979-1005, 2009.
Iwen, M. A. Improved approximation guarantees for sublinear-time Fourier algorithms. Applied And Com- putational Harmonic Analysis, 34(1):57-82, 2013.
Ganguly, S. Lower bounds on frequency estimation of data streams. In Computer Science-Theory and Applica- tions: Third International Computer Science Symposium in Russia, CSR 2008 Moscow, Russia, June 7-12, 2008 Proceedings pp. 204-215 Springer, 2008
Jiang, S., Song, Z., Weinstein, O., and Zhang, H. Faster dynamic matrix inverse for faster lps. In STOC. https: // //arxiv. org pptp:/dd///// 2004 ..0.4.0774411 07470. pdf, 2021.
Jin, Y., Liu, D., and Song. Z. Super-resolution and robust sparse continuous fourier transform in any constant di- mension: Nearly linear time and sample complexity. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 4667-4767 SIAM, 2023.
Gilbert, A. C., Guha, S., Indyk, P., Muthukrishnan, S., and Strauss, M. Near-optimal sparse Fourier representations via sampling. In Proceedings of the foury- annual ACM symposium on Theory of computing, pp. 152-161. ACM, 2002.
Goldreich, O. and Levin, L. A. A hard-core predicate for all one-way functions. In Proceedings of the twenty-first annual ACM symposium on Theory of computing (STOC), pp. 25 32, 1989.
Kapralov, M. Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sub- linear time. In Symposium on Theory of Computing Con- ference (STOC). https::///// attps:///arxiq wewiiiiiorrr/oo org/ woggpdf//6/// 00845. pd., 2016.
Hassanieh, H., Indyk, P., Katabi, D., and Price, E. Sim- ple and practical algorithm for sparse Fourier transform. In Proceedings of the thenty-third annual ACM-SIAM symposium on Discrete Algorithms (SODA), pp. 1183- 1194. SIAM, https::tps:.tt / gwwpps..oppppsp/oo//ooo//. csail. .ww.tedu///..... netmit t sFFT hwwFF///sodaaaaeeeeee pdf, 2012a.
Kapralov, M. Sample efficient estimation and recovery in sparse FFT via isolation on average. 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS). https:/ httgs://arxiv.ort pdf 110. 04544, 2017.
Kapralov, M., Velingker, A., and Zandieh, A. Dimension-
Hassanich, H., Indyk, P., Katabi, D., and Price, E. Nearly optimal sparse Fourier transform. In Proceedings of the
independent sparse Fourier transform. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Algorithms (SODA), pp. 2709-2728. SIAM, https:// 1...33 2019.
Mansour, Y. Randomized interpolation and approximation of sparse polynomials. SIAM Journal on Computing, 24 (2):357-368, 1995.
wrxiv.org.o på
Koiliaris, K. and Xu, C. A faster pseudopolynomial time algorithm for subset sum. In Proceedings of the Twenty- Eighth Annual ACM-SIAM Symposium on Discrete Al- gorithms (SODA), pp. 1072-1072. SIAM, https:// 1507. 02318.111110 pdf, 2017.
Moitra, A. The threshold for super-resolution via extremal functions. In STOC. 1408. 1681, pdf, 2015.
/pf//
arxiv. påf/ /
Nakos, V. and Song. Z. Stronger L2/L2 compressed sensing; without iterating. In Proceedings of the 5 Annual ACM Symposium on Theory of Computing (STOC). https: //arxiv. pd / 903. 02742, 2019.
Kushilevitz, F. and Mansour, Y. Learning decision trees using the Fourier spectrum. SIAM Journal on Computing, 1316):133)1 1993.
Le, Q., Sarlós, T., and Smola, A. Fastfood: approximat- ing kernel expansions in loglinear time. In Proceedings of the 30th International Conference on International Conference on Machine Learning (ICML), 2013.
Nakos, V., Song, Z., and Wang, Z. (Nearly) Sample-optimal sparse Fourier transform in any dimension; RIPless and Filterless. In FOCS. https: http://axxvv.oroo pdf/ 1909.11123. 2019.
Lee, J. D., Shen, R., Song, Z., Wang, M., and Yu, z. Gen- eralized leverage score sampling for neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Price, E. and Song, Z. A robust sparse Fourier transform in the continuous setting. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 583-600, IEEE, 2015.
Lee, T., Song, Z., and Zhang, Q. Solving empirical risk minimization in the current matrix multiplication time. In COLT. https: /tt:://axxxxee //axxivvvvvv////////e///aaaaa wwtpaa..wwg/////////////// /10.. 04447. pdf, 2019.
Rahimi, A. and Recht, B. Random features for large-scale kemel machines. In Advances in Neural Information Processing Systems (NeurIPS), 2007.
Rahimi, A. and Recht, B. Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. In Advances in Neural Information Processing Systems (NeurIPS), 2008
Li, C., Liang, Y., Shi, Z., Song, Z., and Zhou, T. Fourier circuits in neural networks and transformers: case study of modular arithmetic with multiple inputs. In The 28th International Conference on Artificial Intelligence and Statistics (AISTAT'S), 2025.
Rudelson, M. and Vershynin, R. On sparse reconstruction from Fourier and Gaussian measurements. Communi- cations on Pure and Applied Mathematics, 61(8):0025- 1045, 2008
Li, Y. and Nakos, V. Deterministic sparse Fourier transform with an la guarantee. 47th International Colloquium on Automata, Languages, and Programming (ICALP). Schloss Dagstuhl-LeibnnizzZennne
für Informatik, 2020.
Smets, B. M., Portegies, J., Bekkers, E. J., and Duits, R. Pde- based group equivariant convolutional neural networks. Journal of Mathematical Imaging and Vision, 65(1):209-
Li, Z., Ton, J.-F, Oglic, D., and Sejdinovic, D. Towards a unified analysis random fourier features. In Interna- tional Conference on Machine Learning (ICML), 2020.
239, 2023.
Song. Z. Matrix Theory; Optimization, Concentration and Algorithms. PhD thesis, The University of Texas at Austin, 2019.
Li, Z., Kovachki, N. B., Azizzadenesheli, K., liu, B., Bhat- tacharya, K., Stuart, A., and Anandkumar, A. Fourier neu- ral operator for parametric partial differential equations. In International Conference on Learning Representations (ICLR), 2021.
Song, Z. and Yu, Z. Oblivious sketching- central path method for linear programming. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
Liang Y., Liu, H., Shi, Z., Song, Z., Xu, Z., and Yin, J. Conv-basis: A new paradigm for efficient attention in- ference and gradient computation in transformers. arXiv preprint arXiv:2405.055 19,2299,000 2024.
Song, 7.., Woodruff, D., Yu, 7.,, and Zhang, L. Fast sketch- ing of polynomial kernels of polynomial degree. In Inter- national Conference Machine Learning (ICML), pp. 9812-9823 PMLR, 2021.
Lu, Y. Dhillon, P., Foster, D. P., and Ungar, L. Faster ridge regression via the subsampled randomized hadamard transform. In Advances in neural information processing systems (NeurIPS), pp. 369-377, 2013.
Song, Z., Sun, B., Weinstein, O., and Zhang, R. Quartic samples suffice for fourier interpolation. In 2023 IEEE
12

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
64th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1414-1425. IEEE, 2023a.
Yu, H., Huang. J., Li, L.,, Zhao, F., et al. Deep fractional Fourier transform. Advances in Neural Information Pro- cessing Systems (NeurIPS), 36:72761-72773, 20223.
Song, Z., Ye, M., Yin, J., and Zhang, L. A nearly-optimal bound for fast regression with & guarantee. In Proceed- ings of the 40th International Conference on Machine Learning (ICML), 2023b.
Zeng, R., Han, C., Wang, Q., Wu, C.,, Geng, T., Huangg, L., Wu, Y. N., and Liu, D. Visual fourier prompt tun- ing. Advances in Neural Information Processing Systems (NeurIPS), 37:5552-5585, 2024.
Song. Z., Zhang, L., and Zhang, R. Training multi-layer over-parametrized neural network in subquadratic time. In 15th Innovations in Theeoretical Computer Science Con- ference (ITCS 2024). Schloss-aasstull-eeini Zentrum für Informatik. 2024.
7hou, T., Fu, D., Sharan, V., and Jia, R. Pre-trained large language models use Fourier features to compute addi- tion. In The Thirty-eighth Annual Conference on Neural Information Processing Systems (NeurlPS), 2024.
Zhou, T., Fu, D., Soltanolkotabi, M., Jia, R., and Sharan, V. Fone: Precise single-token number embeddings via Fourier features. arXiv preprint arXiv:2502.09741, 2025.
Tan, H., Liu, S., Ma, K., Ying, C.,, Zhang, X., Su, H., and Zhu, J. Fourier controller networks for real-time decision- making in embodied learning. In International Confer- ence Machine Learning (ICML), pp. 47607-47626. PMLR, 2024.
Tancik, M., Srinivasan, P. P., Mildenhall, B., Fridovich-Keil, S., Raghavan, N., Singhal, U., Ramamoorthi, R., Barron, J. T., and Ng, R. Fourier features let networks learn high frequency functions in low dimensional domains. In Proceedings of the 34th International Conference on Neural Information Processing Systems (NeurIPS), 2020.
Tran, A., Mathews, A., Xie, L.,, and Ong, C. S. Factorized Fourier neural operators. In The Eleventh International Conference Learning Representations (ICLR), 2023.
Xiao, Z., Kou, S., Zhongkai, H., Lin, B., and Deng. Z. Amortized Fourier neural operators. Advances in Neural Information Processing Systems (NeurIPS), 37:115001- 115020, 2024.
Yang, J., Sindhwani, V., Avron, H., and Mahoney, M. W. Quasi-monte carlo feature maps for shift-invariant kernels. In Proceedings of the 31st International Conference on International Conference on Machine Learning (ICML), 2014.
Yi, K., Zhang, Q., Fan, W., He, H.,, Hu, L., Wang, P., An, N., Cao, L., and Niu, Z. Fouriergnn: Rethinking multi- variate time series forecasting from a pure graph perspec- tive. Advances in neural information processing systems (NeurIPS), 36:69638 (99666 2023.
Yu, E., Lu, J., Yang, X., Zhang, G., and Fang, Z. Learning robust spectral dynamics for temporal domain generaliza- tion. arXiv preprint arxiv: 2505. 12585, 2025.
Yu, F. X. X., Suresh, A. T., Choromanski, K. M., Holtmann- Rice, D. N., and Kumar, S. Orthogonal random features. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
13

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Appendix
Roadmap. We organize Appendix as follow. Section A, we introduce the de-randomization techniques which will be used guarantee the success sparse recovery algorithm. In Section B, we discuss the super-linear time sparse recovery algorithm. In Section C, we provide the missing proof's of our sub-linear time sparse recovery algorithm.
A. De-randomization
In this section, our goal is to find a deterministic sequence of hashing {(or: Or, br) brE( satisfying the following condition (see Lemma A.21):
Σ (G.) Gor.on (,) S 1- rEld
B
This condition will be used to derive a guarantee for algorithm SUBRECOVERY (i.e., the fifth condition in Lemma B.2).
In Section 1, we define several basic parameters and analyze the relationships between those parameters. In Section A.2, we provide the definition of sample range set. In Section A.3, we define the bad event. In Section A.4, we define Pessimistic Estimator. In Section A.5, we provide a round and mod tool. In Section A.6, we provide a lemma for offset function. In Section A.7, we provide an upper bound on Zo (b). In Section A.8, we study the distribution of o of - f) (mod 1). In Section A.9, we study the distribution of In Section A. provide bound for the range of In Section A.11, prove the upper bound for probability of bad event. In Section A. we provide upper bound for (X). In Section A.13, we analyze the initial constraint. In Section 14,,, we analyze the induction steps. In Section A.15, we show how to put everything together.
A.1. Parameter constraints
This section lists our choice for several parameters used in this section.
Definition A.1. We define the following parameters:
A = C where C2 is some fixed constant belongs to ( 1)
20 π
3
log [
C
d 3C1
B log [F|
The parameters in Definition A.l are chosen satisfy below inequalities, which will use in the proofs of this section.
Observation A.2. We assume the parameters satisfy the following conditions:
1. A (0,
2. E 1)
3. 8 2 4ed
4. X3 2 6 6log| [F|
5. 10
B (A(1 c) + < Ac
Proof. Proof of Part
10
10
B (A(1
1))
(A (1+1)
B
xe
10
< +
2
B
< Ae
the first step is by 20, the 2nd step is by the choice of e, the 3rd step by À > 1/2
14

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
A.2. Sample Range Set
This section defines the where sample the hashing parameters and b.
Definition A.3 (Sample range of b). Let be the range of the hashing parameter b. We take = F.
Definition A.4 (Sample range a). Let be the range of the hashing parameter a. define S to the set of positive odd integers [0, F/n], and Σ = F S = {+/F S).
A.3. Bad Event
This section defines the bad events for which two active frequencies are not filtered out. Definition A.5 (Bad events, Definition 5.4 in page 14 in Li & Nakos (2020)). Suppose that
d is defined as Definition A. and
3 is defined as Observation A.2.
For any f E FF f', we define As, to be the event that
Cogans (P) 2 B.
A.4. Pessimistic Estimator
This section defines the pessimistic estimator, which is used in choosing the property parameters in the hashing.
Definition A.6 (Pessimistic estimator, Definition 5.5 in page 15 in Li & Nakos (2020)). Let À >> 0 be fixed parameter. We define the pessimistic estimator as follows:
h,, 01, or,br) exp(-18) exp (1)
Gopors(())) (M())
where
( 220-0)) +
cxp((A))
For 2 1, the value of or, by is determined by the following minimization procedure:
Tr, arg min dEF,bEB IJ'EF:141
Σ
f
b
br-11,
This function can be evaluated in poly(F/n) time.
Remark A.7. Li & Nakos (2020) chose d to be Ok Olglog)) n). In this work, we choose d to be O log( (ooloog((///g F/r)).
A.5. A Round and Mod Tool
This section introduces technical tool to analyze the hashing function.
Fact A.8 (Change order in taking modulus). For any positive integer y and real number x, it holds that
y ||_ round(yz)) mod y .runddy (x mod 1)) c,
where c or 1,
Proof. We assume x' + where x is an integer and q [0, 1), then we have
(y - round(y))) mod (v- round(yx' yg)) mod
15

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
(y (yx' + round(yg))) mod 1
(y round(y4)) mod 1
where the first step because x' + q, the 2nd step is because yo' is integer, the 3rd step is because x' mod 0. Then, consider two cases of qF
Case I: q [0, - 1/(2y)). Then, yq < 1/2, and round(ug) v 1. Thus, y round(yg) E [0, 1). In this case,
L.HS = (y (yg)) mod
(y round(yg))
y round (x mod 1)),
where the last step follows from mod 1. And the fact is proved with = 0 in this case.
Case 2: E [1 - 11(y))), 1). Then, yg E [y - 1/2, y). and round(yg) Then, y round(yg) = 1. In this case,
LHS = (y- 11 round(y4)) mod 1 = 0.
On the other hand,
RHS 11 roundly (x mod 1)) (y :roun(yg))) 1.
Hence, the fact follows with 1 in this case.
As Case and Case consider all possible values of q, the fact is then proved.
A.6. Reformulation of (f.',b(f')
This section introduces simplified version of the offset function f.a.b
Lemma A.9 (Simplified ffobb), Let (f,((f), (f.),((('') be defined as Definition 2.4. We have
f) of,o,(f)) = (f oof - b) B round(Bo b)) mod 1)
1
for some e = 0 or
Proof.
0.,'(('')) = To,((f) - (1/ ho, mod
=ff - b) mod B ro b) mod 1))
=O('' b) mod 1- - round bi)) mod 1)
= =((((' - bb) 1 Bo mod 1) c
1 rood b)) mod 1) - c, = [(o(ff - + ooff - -b) b)
where the first step and second step follows by Definition 2.4, the 3rd step uses Fact A.8 by taking y = B and o(f b), and 0 1, the 4th step holds by property of taking modulus, the last step is rearrangement.
Notice that, the -c will not affect the result showing below since aff - f') mod 1 E [0, 1), so we ignore it.
16

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
A.7. Upper bound (b)
This section introduces auxiliary variable Zo (b), which is used control the distribution of the offset hashing function. Definition A.10. Suppose is uniformly sampled from the set B (Definition A.3), and uniformly sampled from the set (Definition A.4). Define
1 7o(b) ol - b) B
Boo bb)-
The next lemma upper bounds (b)- Lemma A.11 (The range of (b)). Let (b) be defined in Definition A.10. Then, always holds that
1
(b(
2B 2B
Proof. We can show
[z)b lo(s round Bf bb)]
B
1
|Bo - b) round [Bo b))
B
1
$ 2B
where the first step is by definition of Zo (b) (see Definition A.10), the 2nd step is from simple calculation, the 3rd step holds because z - ro)nd(z)) < 1/2 for all x E R.
A.8. Distribution of off - f) (mod 1)
This section analyzes the distribution of of f) (mod 1). We begin with simplified version of off' f).
Lemma A.12 (Reformulation of oJ - f)). Under the following conditions:
Let a be uniformly random from set Σ (see Definition A.4)
Let m := =F
Let (J' - f)/n
then m uniformly distributed over S (see Definition A.4), and
F
(olf' f)) mod (mi mod
(I)
Proof. By Definition A.4), we know that Σ = F S, where S contains all the odd numbers on [F/n]. Since a is uniformly sampled from Σ and m = F,, we get that m uniformly distributed in S.
By the definitions of m and we have
o(s' -f) F in mi "
F
Now suppose a(f' ()) C D, where CE D [0, 1). Then, we have
mi " = D, i.e., mi _ " 11
F -
17

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Since DE E [0, f), implies that 7
F
mi mod
D 11
Now, we can conclude that:
(o' mod 1 = D 7
(mi
mod
F
?
The next statement characterizes the distribution of (o(J" -) mod 1).
Lemma A.13 (Distribution of (o(f' f) mod 1)). Under the following conditions,
Suppose F/n 2", where p is positive integer
Let a be uniformly random from set Σ (see Definition A.4)
Let f' + f be frequencies from F
Let m, i be defined as in Lemma A.12
K where is non-negative integer and K is odd number
then we have
1. (a(f' f) mod 1) is uniformly distributed over its support
2. The support of (a(f' - f) mod 1) is symmetric
3. The support of (a(f' - f) mod 1) is sequence of equidistant points, with wraparound distance D = F 2
In particular, (a f) mod 1) is uniformly distributed over the following set:
[ - 20:00i2----- -.j.EN
Proof. By Lemma A.12,
(o(f' f) mod 1) = 2 (mi mod 2²).
Hence, we only need to consider the distribution of
mi (mod 2²),,
where m is uniformly sampled from odd integers in | and = 2 K E [2%].
if = 2", then supp(a(J" - f) mad 1) = {0). And the lemma trivially holds. In the following proof, we assume that p.
i < 2P, i.e.
Proof of Part 1
Let my, m2 be two possible value of m, when m, m22 2P-5 we have
mi m 2" K (mod 2P)
Hence, the value of (mi mod 2P) has period of length at least 2 And we only need to consider m [20-s].
Let m1, m2 [20-*], my m2. Then
(m² m2)2² 2
18

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap Since K is odd, then (m1 m2) (m² mg)22 K cannot be divided by 2P, which imples that
m1 (mod 2") * mz2 (mod 2*)
Therefore, each odd integer m E [] generates a unique value for mi (mod 2"). And mi = m'i (mod 2") for every m' E {m + j22= m + j2n-* x 2", E NJ. Suppose that < 2P, then each m' in this set is an odd number. Moreover, for any odd m E [20-a],
(m + j2 m j2 < 2 EN 2
Therefore, S, the support of m, divided into 2*-sized equivalence classes, and each class gives a distinct value for mi (mod 2"). Since is uniformly sampled, mi (mod 2n) is uniform on its support, so does a of f) (mod 1).
Proof of Part 2
For any m E [2p-"), we have
mi + (2p-*- -mmi 2PK 0
(mod 2*).
Therefore,
(mi mod 2") + ((20- m) mod 2") 2",
that is, the support of (mi mod 2?) is symmetric in [2"]. Thus, the support of (a(f' f) mod 1) is symmetric in [0, 1] with respect to 0 under wraparound distance.
Proof of Part 3
For any my > m2 E {),- mi m2 can be written as 2g for some integer g + 0 since they are all odd numbers. We have
(ml m2)i = 2 gg+ gK
C. +
where C is an integer and D (0,2%). Then, we know that D can be divided by 2 since 2 gK and C 2" both can be divided by 2
We show that D is the wraparound distance between any two points in the support of (mi mod 2P):
(mmi (mod 2²)) (m2i (mod 2²)) mod 2n)
(mi m2)i mod 2"
-0+1 gg mod 2"
D,
where the first step is by the property taking modulus, the 2nd step is because mi - m2 2g, and the 3rd step follows from the definition of D. Then, know that the wraparound distance between two points is at least 2
On the other hand, we show that the distance is at most 2*+1 By Part of this lemma, know that
Kmi (mod 2?) : m E [2?), m is odd} {m E [2p=*], m odd) = 2p-a-1
Thus,
D 2. < 2D
which implies that < 2-+1
Therefore, we get that the support of (mi mod 2P) is a sequence of equidistant points, with wraparound distance 2*+1 By scaling a factor of $, get the wanted result.
19

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
1/2 + D/2
1/2 - D/2
-5D/2
5D/2
-3D/2
3D/2
-D/2
D/2
Figure 1. The support of (o(5' f) mod 1), where D 2
A.9. Distribution of of,o,((f))
This section analyzes the distribution of o The next statement shows that the offset of f with respect to f is large with high probability.
Lemma A.14 (Analogous to Lemma 5.6 in page 15 in Li & Nakos (2020)). If the following conditions hold:
Suppose F/n == 2", where p is positive integer
Let be uniformly random from set 2 (see Definition A.4)
Let f' + f be frequencies from FF
Let m, be defined in Lemma A.12
Let i: 2 K where s is non-negative integer and is an odd number
Suppose B
then for any J + have,
1 B' B.
5 B
Pr a
-
Proof. By Lemma A.9, we know that
o),,,(())= af - -) 7z(b) mod 1,
where (b) is random variable defined by
1 Zo (b) olf b) (BouddBBo(f b)).
Then, the distribution of (f') is convolution of (b) [- points).
2B and of - mod 1 (a sequence of equidistant
1
We first consider the random variable a, and then conditioned on a, we consider the random variable b.
By Lemma A.13, the distance between two consecutive points the support of mod is D = 72 2t-tt In the following proof, we discuss two cases based on the value of p q
20

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Case 1: p- q 2 8.
We have
B 2 D. D-2P-9---12 D
(2)
2
Then, we have
Pr ".ab(f) E [-
B' |
1
Pr (a(S' [o(s' -1)
1
(b) mod 1) E
B B
E
Pr (a (b) mod 1)
1
-o(f--1) mod 1)
B' B.
xEsupplo(f"-)) mod 1) Prl(o(S'- () mod 1) xi]
3 3
S Pr (o( () mod 1) E
2B'
2B
(1/D) (3/B)+1
1/D
3
+ D
B
< B
where the 1st step is by simple algebra, the 2nd step follows from the conditional probability, the 3rd step is because
Zo (b) E [- 11 (see Lemma A.11), the 4th step is because the uniform distribution of a f) mod 1 on its 2B
support described in Lemma A.13, where the numerator is the maximum number of points inside interval |- 2B 28 the denominator the total number of points in the whole range, the 5th step is a rearrangement, and the last step uses Eq. (2).
3 3
By Lemma A.13, the closest point to the origin in the support off' -f mod 1 is DD/2. Then, in this case, holds that
Case p g S
D 2-t 2 21-1-pts >
2 3
2
B 2B
Hence, by the same analysis as in Case 1, of,),((()) will not take value in
| B 1
The next statement upper bounds the moment generation function Gof.a which used to bound the probability of bad event.
Lemma A.15 (Analogous to Lemma 5.7 in page 16 in Li & Nakos (2020)). Under following conditions
Suppose [F| is power 2
Let be uniformly random from set Σ (see Definition A.4)
Let be uniformly random in set (see Definition A.3)
Suppose B is power 2
Let G be flat filter defined in Definition 2.8
Let M()) be defined as Definition A.6
For all f F.
E (x [ M(2
21

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Proof. By Lemma A.14 have,
5 Pr|G 2 c) = Pr(os, E B B B
S
(3)
where the first step is by the definition of G (see Definition 2.8), the second step uses Part 1 of Lemma A.14. Therefore, we have
E (oxp(AG of & Pr[m 2 dl exp(A sup6) - Pr[. & c exp(Ac)
s Pr[ cl exp(A) Pr|G exp(Xe)
I B
e t
M(X)
where the first step follows from the definition of expectation, the second step follows by G E [0, 1] (see Definition 2.8), the 3rd step is by Eq. (3), and the last step follows from the definition of (A) (see Definition A.6).
A.10. Range of of.o,((s)
This section bounds the value of of,a((()
Lemma A.16. If the following conditions hold:
Let be randomly chose from set E (see Definition A.4)
Let be uniformly random from set B (see Definition B.6)
then for any I E F we have,
1
"),((() E 2B' 2B
Proof.
01,0,(f) =off - f) + Zb(b)
-Zo
1
E 1 2B 2B
where the first step is from Lemma A.9, the 3rd step is by Lemma A.11
A.11. Upper bound for probability of bad event
This section upper bounds the probability of bad event by the pessimistic estimator.
Lemma A.17 (Pessimistic Estimator, Analogous Lemma 5.8 in page 16 in Li & Nakos (2020)). Under following conditions
Suppose [F] is power 2
Let [d]
Let be uniformly random from set Σ (see Definition A.4)
Let be uniformly random in set B (see Definition A.3)
22

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Let hy be defined as Definition A.6
Let H, = ar Or,
be sequence of hashing chose by procedure in Definition A.6
Suppose S F satisfy I {
Let As, denote the bad event defined as Definition A.5, where (0r41;br=1),... (oas ba) are uniformly and indepen- dently sampled from Σ x B
we have,
h U ,r,b,) 2 Pr(Ag,8 lo..b,.....,.. br).
Proof. We define as follows,
2
(5)
Conditioned on σ1, b1....................... ...,, Tr: br. a fixed constant.
Then have
d Σ
Pr[Ag,r or, lo,bi, ",, ,r, br] = Pr(2+ +
G > B]
1=+1
Pr|exp(A(z++
Σ
G
Gonona((())) e0g
1=++1
se se Ne Elexp(A
G Go)o))((P)))
1=++1
= - E ((o
where the step is by Markov inequality, the 4th step follows from the independence, the 5th step is given by Lemma A.15, and the expression in the last line is exactly hy (see Definition A.6).
A.12. Upper bound for M())
This section upper bounds the quantity M().
Lemma A.18 (Upper bound for (A)). Under following conditions
Let (X) be defined as in Definition A.6
Suppose that E (0, 1)
Then have.
M(A) < exp(2Xe)
Proof.
5 M()) exp(de) ( e>((-s) + +1)
S exp (Ae + log(1 + B
((1)))))
23

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
S exp (Ae (1-)))
10
S exp (Λe +
(A(1 c)
B
exp(2Xe)
where the 1st step is due definition of (X) (see Definition A.6), the 2nd is by simple algebra, the 3rd step is because log(x: + 1) S for x * 0, the 4th step is because e S 2x + for x E (0, 1), and X, E (0, 1), the 5th step is by Part 5 of Observation A.2
A.13. Initial Constraint
The following sections upper bound the pessimistic estimator by induction. This section verifies the initial constraint.
Lemma A.19 (Initial constraint, Analogous to Lemma 5,9 in page 17 in Li & Nakos (2020)). Under followiig conditions
Suppose [F] is power of
Let be uniformly random from set E. (see Definition A.4)
Let uniformly random in set (see Definition A.3)
Let h, be defined as Definition A.6
Suppose f satisfy f +
we have,
Σ ho(fif)< <1
1.
Proof.
Σ
holf.f)= = -AB Σ (M()))
1 exp(-18+ 2Xed)
$ F exp( -0.523)
F exp( -3 log FF)
where the first step from definition ho (see Definition A.6), the second step follows from Lemma A.18, the third step by 4ed (Part 3 of Observation A.2), the fourth step follows by XB 2 6 log [F) (Part 4 of Observation A.2), the fifth step is by simple algebra.
A.14. Induction step
This section shows the induction step.
Lemma A.20 (Derandomization, Analogous to Lemma 5.10 in page in Li & Nakos (2020)). Under following conditions
Suppose [F] is power of2
Let be uniformly random from set Σ (see Definition A.4)
Let be uniformly random in set B (see Definition A.3)
Let r E [d-1]
24

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Let H, ag b)))ess)) be sequence hashing chose by procedure in Definition A.6
Let h, be defined as Definition A.6
Suppose S.f E [n]] satisfy ! + l'
we have,
,r,
E
[h (1,,
,0+t1.br41))
Proof. We define follows,
Then we have
E br41
(f
Ele E Mo+ g.000))))) N(ttGog.ast)) (M())) (M
o,
=E --1 T. (ex
a.b
S -e- (M
f' ... ,rr, br)
where the 1st step is due to definition of h, (see Definition A.6), the 2nd step holds since ex and M() are independent of b, the 3rd step uses Lemma A.15, the 4th step is due to definition of hy (see Definition A.6).
A.15. Putting it all together
This section summarizes the analysis above and shows final result.
Lemma A.21. If the following happens
Let B be defined as Definition A.
Let E (0,1) be defined as Definition A.I
Let Ha (orr, ar, br)b)r))r))) bredd be sequence of hashing chose by procedure in Definition A.6
Let G be a flat filter in accordance of hashing functions in Hp (see Definition 2.8)
it holds that, for all f # f
3
Σ
Go
1-e
rE|d
Proof. Note that in each step, we choose a br+1 to minimize
Σ
het (S.S's ai bi. br41)))11)
Then, we know that
Σ
br41)) S
E 1. "eilee (h 144 (4)
Σ
25

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
which follows from the linearity of expectation. By Lemma A.20, it holds that
Σ E
, b
Σ
b . br,
A.fE::f1 54
Hence by induction, we have
E I'E'R:1A
E
bo(f.f') <
SPEFT
where the 2nd step given by Lemma A.19. Therefore, by Lemma A.17,
Σ
Pr[AAs loib,,... .. ,a, bal S
E 1EEE:
hals, ba "a < 1.
IJ'EF
Note that conditioned d1, by od, ba, Ay. is deterministic event. That is, the conditional probability for each pair of f # f' is either zero or one. By the inequality, we get that
Pr[Ay,/ 01,b1,"" ,d, - - VfF
Then by the definition of Arr (Definition A.5), implies that
G (P) SB. r
Σ
(5)
Note that 0f,0, (f) E [- 1.
2B 2 (see Lemma A.16). Thus, by definition & (see Definition 2.8), we have
Gofons (f) [[,-1,].
Then Eq. (5) gives that, for all /
Σ rE(d]
G Cf Cos S 1
The lemma is then proved.
B. Super-linear Algorithm
This section gives a deterministic super-linear algorithm to recover the le heavy-hittes. We first analyze the guarantee of HASHTOBINS, and then we embed it into a recursive algorithm that filters the signal in each bin by a decaying threshold.
In Section B. we show that the measurement gives close approximation to the tones. In Section B.2, present the assumption of the noise function. In Section B.3, we introduce HasnToBins. In Section B.4, we analyze the median of the output of HasnToBins. In Section B.5, we study the guarantee of the algorithm for super-linear time sparse recovery, which is an essential subroutine. In Section B.6, we analyze the guarantee and running time of the super-linear time main algorithm. In Section B.7, we analyze our result for the deterministic continuous Fourier transform.
B.1. The Guarantees of Measurement
According to our choice of parameters in Definition A.1, we have the below relationship between d/ and B. This allows us to normalize the L bound of our algorithm by a factor of 1/k.
Observation B.1. Let B, d, e be chosen as Definition A.I, we have
B
θ
e)d
B
26

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Proof.
(log [F) (1 (1-e)d e)d (1 (1/B)) log((F[))
B
0 1
where the above equation is due Definition A.1.
The next statement shows the guarantee of the measurement.
Lemma B.2 (A variation of Lemma 5.1 in page 11 in & Nakos (2020)). Under following conditions
Let H, = (ar, Or, by frea be a sequence of hashing defined in Definition 2.6
We have G being a Slat filter with B buckets and sharpness (see Definition 2.8)
Let G. u be defined as Definition 1.1
For all f # f' EFF it holds that,
(o G Cotonta 3 1-c
Σ
rEId
where is chosen as Definition A.I.
Then for every vector x [0, T) + CD and every f E F. for at least 0.8d indices r [d] we have
lyy 1-1 ojor (MH, (13 a as S 0 )
Σ
lopl
(6)
B
F'EFUU
Proof. The proof close to Li & Nakos (2020), we keep it here for completeness.
Σ
by
1-1
(n) (mw.))..C))
rEld
O-1 (f) (
Σ
G
rEld
PEAMM
G-1
Σ
rE|d
P'EF(()
Σ
|0gel
Σ
8-1
ogaanon (f) Goyamaad
G
('EFW/
rE[d]
B
Σ
Juy
1-c
PEFWU
where the first step uses Claim 2.11. the 2nd step is given by triangle inequality, the 3rd step a change of summation order, the 4th step is by the condition of this lemma. the last step is by the Observation B.I.
Therefore, at most | fraction of [d] satisfy
lug 1-1 (f (8) (mH, -005
5,
Σ l P'MM
(1 (1-)dd
1
0
Σ lppb.
B
S'EF(())
where the last step is by Observation B.I. Thus, we complete the proof.
27

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
B.2. Assumption of noise function
This section introduces the definition of (C, En-ise function. We will show its restriction on the output of HASIITOBISS algorithm in the next section.
Definition B.3 ((C, {)-oise).. Under following conditions
Let g(t) [0. T] R be the noise function
Let C' be a fixed constant
Let be parameter depend g(t)
then say g(t (C,5) -)-ois if it satisfies
/ le(1))de++ +
C. [a(1)12 SC 7 (0.7)
max
B.3. Hash to bins
This section presents the deterministic HASITOBBNS in the continuous setting. The algorithm is displayed in Algorithm 1. The next lemma states the identities of the pseudo-random permutation and the output of HASHTOBINS.
Lemma B.4 (Identities of DFT and CFT, Lemma 4.3 and Fact 4.1 in Jin et al. (2023)). Under following conditions
Let Po,ab be defined Definition 2.5
Let (1) be the noiseless signal
Let z(t) == EfEF 2mift
Let ū be the output of HASHTOBINS
we have
Property Identity of pseudo-permutation::
t Pa (1) - -- +D)e
Property 2: Identity of output of HASHTOBINN: For any j [B]
G Pa Pa. - -2)/
Proof. Notice that Property Jin et (2023) contains only æ. However, we can extend to our result by linear operation.
The next lemma shows the guarantee of the HASHTOBINS procedure under the noiseless version and the noise-only version. Lemma B.5 (HASHTOBINSS) If the following conditions hold:
let = (as, a. b) be a tuple of hashing defined in Defimition 2.4
Let G be a flat filter (see Definition 2.8)
let ã, v be defined as Definition 1.1
let 2 c be vector,
let g(t) for any E (0, T).
28

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
then there exists deterministic procedure HASHTOBINN( &, H) (see Algorithm 1) which computes CB with the following guarantees:
Noiseless version: Let g(l) = 0, for any I E F,, the oulput à of HAHHSTTTBBSSSS, H) satisfies
Ao - )o)
aS)
PEFF
Noise-only version: Let x² xt) = 0, the output à of HASHTOBIIN((, OB. H) satisfies
d0llo
0 B (C
D
(C.
//d la(1) + ²))² ( //1
The algorithm takes O(B log B) samples.
The time complexity of the algorithm is O log B).
Proof. Part 1: Noiseless version Let 2: = Σyer Zg 65(5), we have
Ulo, = G * Pa. - 22)(k())BB)
= - G(ho,,(f)/B- -E) (), 2)(E)d5
JEER
[ G(ho,,())/BB 1 [ b) 5 + bi) 2 de
JER
[ G(No,(()/B-odt b)) (7(E) - a()) 2
JEER
[ G(hnn -of b)) Σ
(of Et) oy(5)) e 2viant
EER
JEF
E Elhhooli/BB -of - b)) (vf -5p) 2
JEF
EG(-oroo()) (uy - -1) f FEF
where the first step is by Property 2 of Lemma B.4, the 3rd step is by Property 1 of Lemma B.4, the 4th step is by integral substitution, the 5th step is by the definition of sparse signal (see Definition 1.1), the 6th step is by definition of delta function, the last step is by the definition of hashing functions (see Definition 2.4).
The first part is then proved by the symmetricity of G.
Part 2: Noise-only version
For any j [BD]
(3-C-P--(((--0)) ((((t-
5 50 1 R (a(1
< 0 | (C T /'
lo(t) +5)
B
where the first step is by definition in line 4 of Algorithm 1, the 2nd step is by Property 5 of Definition 2.8, the 3rd step is by Assumption B.3. Therefore, we have
| s 01 - (C
7 f lo(t) + +)
29

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
We get the result by timing D (see line 7 of Algorithm 1).
B.4. The Guarantee of median of HASHTOBINS
Combining the previous results, derive the Guarantee of the median of Deterministic HASHTOBINS.
Definition B.6 (Choice B). Let be some constant be determined later. Let be the sparsity of the signal. We define B to be such that
= (k)
B is a power o
we choose the constant in B =((k) such that the upper bound of Lemma B.7 satisfies:
1
D ak
B
Lemma B.7 (Median of HASHTOBINS outputs). Under following conditions,
Let Rt be defined as Definition 1.1
Let GIFl
Let w == 0f žz
We have & being a filter (see Definition 2.8)
Let (Hrrreld = =or, ar ar,b,)))))) by) be a sequence of hashing defined in Definition A.6
Let un be the output of (ASHTOBINS(2, H,,
we have
For all f
median G-1 rE[d]
of or) (ur) -aaof
1
[(f) + 0 ( 1/'
log k
C ())))pat+(())
ak
JEF
Proof. Let uf HASHTOBINS(g, 0|5), H,).
(noise) (noiseless) denote the output of HASHTOBINS((, H,) when g(() = 0. Let u denote the output of
Part 1: Guarantee of noiseless HASHTOBINS
Using Lemma A,21, we know the fifth condition Lemma B.2 should hold. Then we have for least 0.8d indices E [d]
j,y δ-1 of (or) w -ao
(noisalese)
y0y
8-1
ofer (n) (mH, (w (m..((())) (w(f))) (aw-aar f
< 0
B
< ak
|,
(7)
where the first step by Lemma B.5, the 2nd step uses Lemma B.2, the 3rd is given by choice of in Definition B.6.
30

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Part 2: Bounds output of HASHTOBINS with noise function as the input
Since G-1e (0, 1) by Definition 2.8, combining Part 2 of Lemma B.5 we have
median Goj (8) (2) (nosse)
har. agf 1 50
D B
( S. [e(t))
+
(8)
Part 3: Putting them together
(noiseless) (noise)
tp Notice that every operation HASHTOBINS linear. Therefore, we have u, ur
Then by taking the median of outputs for hash functions in Hrr have.
(T)) median T-1 --
os (5) (hor) (1) (/)w-/ar)) aaf|
( w -aos + median G-1 bn) (1) (ur (ur)) (nosse) ( median G-1 or (n) (Ur)
(noiscless)
-aof
hen (1)
1
|0 Awu + median θ-1 of (f) (Ur (noise)
hom (0) u =aar
ak
| Huunn + + ( J. ((t)) +))
ak
where the first step by triangle inequality, the 2nd step is by Eq. (7), the 3rd step is by Eq. (8). Hence, prove the desired result.
B.5. The Guarantee of Super-Linear Time Sparse Recovery
This section presents the super-linear time sparse recovery procedure.
Algorithm 5 Super-Linear time Sparse Recovery for T 2
1: procedure SUPERLINEAR(( C")
Lemma B.8
2: S с+ッ 0
3: for = 1-14 + d do
4: Ur + -.ASHTOOBINSS,,,(00..
Lemma B.5
5: end for
6:
for f F
7:
i'/ + median (o) (Ur)) (n) aaf
Lemma B.7
8:
if 10 > 2/2 then
9:
SU
10: end
end for
return T
13:
end procedure
The next statement shows core guarantees of Algorithm 5.
Lemma B.8 (A variation of Lemma 5.2 Li & Nakos (2020)). the following conditions hold:
let R, v be defined as Definition 1.1
let 2 CI
be defined as Definition B.6
let i - 2,
Let (2) be defined as in Lemma B.7
31

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Let (T) be a constant denote threshold for heavy index
then the oulput of the Procedure SUPERLINEAR (Algorithm 5) To' satisfies:
|لyl 2 v for all f E supp(w")
jوy 1ry,1 - /yl for all supp(ū")
(f F: | 2 v) _ supp((')
Proof. Proof of Part
For any f E F, we have
10
-10y-
median G-1
(4.),)) - w
rE|d]
W
16
where the first step is the output of Algorithm 5, the 2nd step is by Lemma B.7, the last step is by the 5th assumption of this lemma. Then we have,
W 2 |10y| wy 8'/
2 2/22 W0 1/1
2/2 v/16 (7/16)v
(10)
where the first step uses triangle inequality, the 2nd step is by the threshold condition in 8th line of Algorithm 5, the 3rd step due to Eq. (9).
Proof of Part 2
j
8/yl
16
1
<
(16/7)
= |0yl77
16
where the first step is given by Eq. (9), the 2nd step is by Eq. (10).
Proof of 3
2 w - ف - W11
2 リー e - 1'/
2 v v/16 16 > v/2
where the 1st step is by triangle inequality, the 2nd step is since f E {f E F 1 2 v}. the 3rd step is by Eq. (9).
Since | is bigger than the threshold, will recovered.
B.6. Super-Linear time main algorithm
This section analyzes our main algorithm. First, we present the constraints of the constant parameters. Definition B.9 (Constraints of constant parameters). We list some constraints for constant parameters in the main algorithm.
Part 1 C>1 1
Part 2 C(1 16 16 (1+
32

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Part 16 1
Part 77
Below is group of parameters that satisfies the above constraints.
Definition B.10 (Choice of constant parameters). We let C p. 32, 32, 2.
The next lemma shows the guarantee of super-linear time main algorithm.
Lemma B.11 (c norm reduction, analogous to Lemma 5.3 page 13 in Li & Nakos (2020), Lemma 3.8 and Lemma 3.9 in page 10 in Price & Song (2015)). following holds
Let μ be defined as Definition 3.11
Let the SNR R' (see Definition 3. I) satisfy R S (F/1))² for some constant parameter m.
let ã, be defined as Definition 1.1
Let P be some constant to be determined as Definition B.10
Let r = vg 500)
For all S ST",, there is an algorithm (Algorithm 6) outputs a vector G(T') E C which satisfies
Let = (f 1f:luyy 1 2 (),(())= r/0 for all f $
1//915 s/ysll for all f
1 v()
The algorithm takes O(k2 log log(F/n)) samples
The algorithm runs in
log" (F/n)) time.
Proof. The proof of the first three claims is by mathematical induction.
Initial Condition
The first and second claim clearly holds since zf 0 for all f E and hence r a(f).
For the 3rd claim, we have
(0) Cue/² CpR" C/ > ||o|100 = 10)
where the 2nd step is by 7 log, R" the 3rd step by the definition of R (see Definition 3.11), the 4th step by (Part 1 of Definition B.9), the last step is by definition of [lo]e
Induction step
Now, we assume the first three claims hold for t, we want prove its correctness for t
For simplicity, define notation for the integral of noise time intervals,
= 0 log C &
k
We have
16 ak (1)r + JJ = ak
(1
+ 1 I1 +
33

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
16
(k:
1 1 11 1i + J)
ok
16
(k
Cuy + 1 + M J)
ak
16
(k.
Cuty T- + kj
I | + J)
odk
P
ky
(b:
Cuy
+
kp)
ak
16
(k. Opty
-
+ a (1 Ckkp
16
ak
16
1 ak
(b: C2t T
+
a
(1
16
@kkp T" -)
16
a
CCUy - - ((1)
where the first step and 2nd step are trivial calculations, the 3rd step is by the third claim in this lemma and induction hypothesis, the 4th step is by the definition of I, the 5th step is by the definition of μ (see Definition 3. 3.11), the 6th step is derived from Part Definition B.9, the 7th step is by 7: -t
and rearrangement.
Therefore, we' 'e proved the fifth condition for Lemma B.8.
Claim 1:
For index f E L, we have
|[(()] < 1
7
< Cμ
16
7
1 Cuyy" -f (11)
16
where the first step is by definition of 7, the 2nd step is by Part 3 of Definition B.9, the 3rd step is by 72 1.
By Part of Lemma B.8, we know that [a([] will never be recovered in this procedure.
Claim 2:
Notice that rf is defined be ā(f) - -/ then we have,
(1+1) = 10, 1
S 10/1/7
= 1//91/7
(11)
where the first and the third step are by definition of r, the 2nd step uses Part of Lemma B.8
Since we know 1r = [(()], Claim 2 clearly holds.
Claim 3:
For f such that (r < y (t+1), Claim 3 is proved by Eq. (11).
Otherwise, we have 1r100 > (I+1), then have,
//00 + (1+1)
<
where the first step is by Eq. (11), the 2nd step is by induction hypothesis, the 3rd step is by Part 4 of Definition B.9. Therefore, Claim 3 holds and we verify the induction step.
Proof of Sample Complexity.
34

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
The sample complexity of the algorithm is counted as below,
Sample Complexity d HASHTOBINS
d. OB =d)O(Blog(B)
= OB (og(F/n) Olog B)- O(B)
Ok2 log k log(
where the first step is since we have d hashing tuples, the 2nd step is by Lemma B.5, the third step is by choice of d (see Definition A. the 4th step is by B = ((k) (see Definition B.6).
Notice that we can reuse the sample, so we only need to count d times of HASHTOBBINS
Proof of Running Time.
The time complexity of SUPERLINEAR is
d HASHTOBINS + (F/n) Takinn Median = d d-O 10kloog + F/n- Taking Median
= d Oo k) + (F/n)
-Og log k + (F/n)klog(F/m))
= =O((F/n) (og((/)))((/)))
where the 2nd step because we scan the sequence of hashing when taking the median, the 3rd step is by the choice of d, and the 4th step holds for F/n >> k.
Hence, the time complexity for the main algorithm T O((Fnn)")) by the first assumption of this lemma.
O(FFn)) log (F/n)) since R
Algorithm 6 Superlinear-ting time sparse recovery for
1: procedure MAIN(x (C")
Lemma B.
2: T + log, R
3: ş(0) + 0f51/n
4: (0) + Cuy"
5:
for / = 0 + T - do
6: 3((+1) + 2(1) + SUPERLINEARR(,,")) v(1)
b Algorithm
7: v(++) vl)) /
8: end for
9: return &
10:
end procedure
B.7. Main result of the super-linear CFT
This section summarizes the results in previous sections.
Theorem B.12 (Super-linee linear Deterministic CFT), If the following conditions hold
Let x [0, C has Continuous Fourier Transform & [-F,F) C
Let the SNR R* (see Definition 3.11) satisfy R* S (F/n)" for some constant parameter m
Let [F), B be the powers of
Let the noise function g(t) satisfy Definition B.3
Then for any vector x E C satisfying the above assumptions, there is an algorithm that
35

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
it finds an -ppaase vector T' E CCA
We have juy - F ((N) all f E FFF, where
C log k
( S." lo(1) + +)²)
N = ak
Σ SEF
losl
+ O
k
The algorithm takes O(k log k. log(F/n)) samples
The algorithm runs in ((F/n))k (F/n)) time.
Proof. This theorem is direct result of Lemma B.11.
Proof of sparsity output
This is followed by I = (k) and f & is not recovered (Part 1 of Lemma B.1
Proof of Guarantee
|| |1,000
max
max{1lr) (TT) 1l,0 11 f 'looo
max{[I
1oo1 1Il 11)
max ( |1
| Fi [lbo}
S max, 1 (2")) ||/2
S [ax, (1/p)/ = O(N)
where the 2nd step is by Part 3 of Lemma B.11, the 3rd step is by bf Part 2 of Lemma B.11, 11, the 4th step is by definition of 14, the 5th step is by definition of
Proof of Sample Complexity and Time Complexity
They are calculated in Lemma B.11.
C. Sub-linear Time Algorithm
This section provides the missing proofs in Section 3.2, which presents sub-linear time recovery algorithm.
In Section C.I, we state a number of one-sparse recovery tools from previous work. In Section C.2, we prove the guarantee of sub-linear time sparse recovery.
C.1. Sub-linear time one-sparse recovery
Now, we introduce a useful lemma that upper bounds the difference in angles.
Lemma C.1 (Proposition 4.10 in page 11 in Li & Nakos (2020)). If the following holds,
Let x. C satisfy vll /x//3
we have
arg(( + v) argæl S T/8
We present the one-sparse recovery algorithm for the discrete setting in Li & Nakos (2020) here. Lemma C.2 (One-Sparse recovery, Lemma 6.1 in Li & Nakos (2020)). If the following holds,
| is a power 2
36

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
Let Q = 20.
Let r E C with discrete Fourier transform T
Ly be the f-th entry of
Let f = 1 mod 2x
Let ( be a sequence of metric of y satisfying
|arg(1.)) - (arg 90y) n/8
There an algorithm ONESPARSERECOVERY (see Algorithm 2) that recover by (agloEQ in Oloo F/n) time.
C.2. The Guarantee of Sub-linear time sparse recovery
The next lemma proves the noise in each hashing and filtering bucket limited, conditioning on bad event does not oceur. Lemma C.3 (A variation of Lemma 6.2 in page in & Nakos (2020)). If the following conditions hold
Let H, = (ar, Or by brea be sequence of hashing defined in Definition 2.6
We have G being a flat filter with buckets and sharpness (see Definition 2.8)
Let R, be defined as Definition 1.1
For all f + f E F. holds that,
B G-1 Gol (1) Grton... S -
Σ
rE|d
where is chosen Definition A.I.
Then for any J. least 0.8d indices
[d] satisfy
Σ
Go (09
Σ ly
(EFF(
P'F((())
Proof.
Σ
(r = Go Gofoo.
[3g δ-1
os (1) (ma)acrso-a
f'ERWN
< Gof(it 0 1
Σ lu
< 0 1
Σ
lyrl
PEFIU
where the 1st step is derived from Claim 2.11, the 2nd is from Lemma B.2, the 3rd step holds because Gojonn (f) < (see Definition 2.8).
Now, we show that the one-step guarantees in Lemma B.8 still hold for the sub-linear algorithm.
Lemma C.4 (A variation of Lemma 6.3 in Li & Nakos (2020)). If the following conditions hold:
let ã, v be defined Definition 1.1
let 2 e FI
37

---

Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap
let B be defined Definition B.6
let y = V3 - 2z
Let (()) be defined as in Lemma B.7
Let v 2 ( be constant to denote threshold for heavy index
then the outpul of the Procedure SUBRECOVERY (Algorithm 3) w satisfies:
For all f E suppl ('), we have [أكl 2 (7/16)v
For all f supp( W'). we have yw0 T0y S 10y177
( E F: 10 v) C supp(w')
Proof. The proofs of the first and the second statements directly follow Lemma B.8. Now, prove the third statement. For the r-th round, we consider (Ø-) == Goy or....., ( y and we use Ug as the metric to recover the f from (ū-), (see Line 8 in Algorithm 3). From Lemma C.2, to verify f can be recovered by ONESPARSERECOVERYY we only need show
arg(u,) - arg(
or (1) u w( argg(u,) - (arg((())) + m/8
(12)
By Lemma B.5, we have
G-1 of 0f. Wg woB, Ug
1-1 10 By w + =0(
log k.
_ / le(t) + +))
C
(13)
T
PEF(()
For f (f E F: 10yl 2 v),
For at least 8d/ 10 repetitions [d]. we have
2 (1 <) e)00S
2 (1 E)D
2 16(1 cLN(i)
16(1 (
ak Σ
1
[()
O
log k
1 c lo(1) + G)
C
fEF
2 16(1 e) (B(
E ( 0 log k
{ J/ (a(0))d++))))
2
odk:
N'EWM
2 16(1 e)
((k)
Σ
G
(19
log k
& /// 10(0))tt+))))
C
ak
MEFl(
23(1 Σ
a Cos 0
logk
(
///
C T
/'
la())att+ + g))))
h
3/1 Oo (,) Wy w
G-1
where the first step is by G-1 >1 - e, e, the 2nd step is by f E (f E F: |,y 2 v). the 3rd step is by the definition of (ū), the 4th step uses Lemma C.3, the 5th step is by B = Okk), the 6th step is by choosing a proper a according to the constant hided in (kk), the last step is by Eq. (13).
Therefore, using Lemma C.1 with r = G-1
a (1) Dy 9 and x + = uy proves Eq. (12).
For at least &d/ 10 repetitions r E [d], the above argument holds and we can recover the wanted frequency. Therefore, we proved the desired result.
38


Reviews:
[{"review_id": "er8vdujO10", "reviewer": "Reviewer_FmMR", "summary": "This paper adapts Li and Nakos (2020)'s deterministic sparse Fourier transform (SFT) algorithm to the continuous-time setting described by Price and Song (2015) (who had proposed a randomized algorithm), showing that an efficient deterministic method exists in this regime as well. The proposed algorithm has $O(k^2\\log k \\log^2(F/\\eta))$ sample complexity and $O(k^2 \\log k \\log^3(F/\\eta))$ time complexity, where $k$ is the sparsity, $F$ is the bound on possible frequencies, and $\\eta$ is the gap between possible frequencies. The algorithm is sublinear with respect to the frequency domain size $\\Theta(F/\\eta)$, and thus is an improvement over non-sparse algorithms.  The class of $(C, \\xi)$-noise functions is defined in Definition 3.3 so that the algorithm can work in the continuous setting. Proofs of the recovery guarantees and sample/time complexities of the algorithm (as summarized in Theorem 3.11) are provided in the appendices.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback and for recognizing the novelty, significance, and technical contributions of our work. \n### W1: Self-contained Explanation\nWe will include clearer explanations of fundamental Sparse Fourier Transform (SFT) methods (such as hashing, filtering, and convolution) to ensure the paper is easy to understand and complete on its own. For instance, we will clarify the definition of $h_r$ in our revision, stating explicitly: \"In the derandomization phase, each function $h_r$ serves as a pessimistic estimator, tracking the probability of undesirable events (such as hash collisions) given the first $r$ selected hash functions.\" We will carefully define these key concepts throughout the paper.\n\n### W2 and Q2: $(C,\\xi)$-noise model\nWe introduced the $(C,\\xi)$-noise model to guarantee that if the noise function has bounded pointwise deviation relative to its global energy, a deterministic sampling pattern can isolate true signal components from the noise. White Gaussian noise typically has unbounded probability tails, which can lead to arbitrarily large amplitudes at deterministic sample points and hence one cannot “average out” them in a purely deterministic algorithm. However, our model does not strictly exclude Gaussian noise if it is truncated. Suppose that $g(t)$ is i.i.d. over time t. If we consider $g(t) \\sim \\mathcal{N}(0,\\sigma^2)$ condition on $|g(t)| \\leq M$, then it is a $(C,\\xi)$-noise with $C=1$ and any $\\xi > 0$. In fact, any uniformly bounded process (including a truncated normal) is trivially a $(C,\\xi)$-noise. Another example is that $g$ is a polynomial function, e.g. $g(t) = t^c$ for some $c > 0$. Then $g$ is a $(C,\\xi)$-noise with $C = 2c+1$ and $\\xi = 0$.\n### Q1: Optimal recovery guarantee\nBy “optimal,” we mean that up to polylogarithmic factors in $k$. Our algorithm achieves both optimal sample complexity and runtime. This is because the lower bound for sample complexity is $\\Omega(k^2 + k \\log k)$, as established in [1]. Consequently, the lower bound for runtime is also $\\Omega(k^2 + k \\log k) $.\n### Q3: Applications and real-word examples\nSFT problems arise whenever signals are (approximately) dominated by a small number of frequencies. While classical FFT requires sample/time complexity on the order of the entire band-limit $F$, SFT leverages sparsity $k \\ll F$ to reduce complexity. Many continuous-time signals in scientific and engineering contexts are indeed “nearly sparse,” with only a few truly significant frequency components amidst a large potential range of smaller, negligible ones. For example, in many radar systems, the received signal consists of only a few dominant sinusoidal components [2], each corresponding to a strong reflection path. While the overall bandwidth FFF may be large, the effective sparsity (the number of meaningful reflections kkk) is typically quite small. Another example is machinery vibration analysis [3]. Machinery vibrations are inherently continuous signals that often exhibit only a small handful of resonant frequencies—each well spaced from the others. This distinct frequency gap naturally suits a continuous sparse Fourier approach for robust fault detection and monitoring.\n\n[1] Ganguly, Sumit. \"Lower bounds on frequency estimation of data streams.\" Computer Science–Theory and Applications: Third International Computer Science Symposium. 2008\n\n[2] Austin, Christian D., Emre Ertin, and Randolph L. Moses. \"Sparse signal methods for 3-D radar imaging.\" IEEE Journal of Selected Topics in Signal Processing. 2010\n\n[3] Ding, Chuancang, Ming Zhao, and Jing Lin. \"Sparse feature extraction based on periodical convolutional sparse representation for fault detection of rotating machinery.\" Measurement Science and Technology. 2020\n\nWe also thank the reviewer for the editorial comments. We appreciate these suggestions and will refine the final draft accordingly. Thank you for your time and valuable feedback!", "claims_and_evidence": "The main claims of this paper, the correctness and sublinear complexity of the proposed deterministic continuous SFT algorithm, is well substantiated with proofs in the appendix. The required assumptions (e.g., on the noise) are laid out clearly. However, the claim that the algorithm achieves optimal recovery guarantees (see, e.g., the last sentence of the abstract or the second last sentence of the conclusion) lacks justification. The authors should clarify this and explain how the recovery guarantee achieved by the algorithm is optimal.", "methods_and_evaluation_criteria": "The problem definition, recovery guarantees, and use of sample/runtime complexity to evaluate the efficiency of the algorithm are standard in the literature.", "theoretical_claims": "The proofs of algorithm correctness and complexity (presented in the appendices) generally follow those in Li and Nakos (2020). Although the high-level structure of the proof is similar, significant changes are required due to the continuous-time setting. Although I did not check every detail, it seems that all the necessary adjustments for the proof to go through have been made.", "experimental_designs_or_analyses": "N/A (No experiments.)", "relation_to_broader_scientific_literature": "This paper combines the methodology of Li and Nakos (2020) and the setting of Price and Song (2015). Although neither the idea nor the setting is new, the combination seems to be novel. The proposed algorithm is similar to that of Li and Nakos (2020), but has nontrivial differences stemming from the difference in setting.", "essential_references_not_discussed": "The relevant literature on continuous and/or sparse Fourier transforms seems to be adequately represented in this paper.", "other_strengths_and_weaknesses": "1. This paper assumes that the reader is familiar with the general techniques used for sparse Fourier transforms and often defines variables or functions without explaining their purpose. This makes this paper very challenging to read for readers who are not familiar with the subject matter. In addition, this paper borrows many definitions from Li and Nakos (2020), but leaves out the explanations that accompanied them in the original paper. For example, the role of the pessimistic estimator $h\\_r (f, f', \\sigma\\_1, b\\_1, \\dots,\\sigma\\_r,b\\_r)$ defined in line 262 of the left column of page 5 is not explained, making it very hard to understand for readers who have not read Li and Nakos (2020).\n2. It is unclear how useful the setting considered in this paper is. Although the setting allows for continuous-time signals, this is offset by the requirement that all active frequencies be a bounded discrete multiple of some constant $\\eta$, which seems rather limiting. Furthermore, the $(C, \\xi)$-noise model defined in this paper seems to exclude some common types of noise such as white Gaussian noise.", "other_comments_or_suggestions": "1. In the introduction, a brief discussion on the different kinds of continuous settings studied in the context of SFTs might be beneficial to give readers additional context. For example, although Boufounos et al. (2012) is mentioned in the introduction as a paper that studies SFTs in the continuous setting, it focuses on the discrete-time and continuous-frequency setting, while this paper studies the continuous-time and discrete-frequency setting.\n2. There are many minor typographical and formatting errors, which can sometimes impede understanding. For example, the definition of $\\omega$ to be $e^{-2 \\pi \\mathbf{i}}=1$ in the second last line of the right column of page 2 does not make a lot of sense. It seems substituting $e^{-2 \\pi \\mathbf{i}}$ in for every instance of $\\omega$ will fix this issue (e.g., replace $\\omega^{t\\sigma b}$ with $e^{-2\\pi\\mathbf{i} t \\sigma b}$). In addition, in line 233 of the left column of page 5, \"if $o_{f,\\sigma,b}(f)$ is big and $o_{f,\\sigma,b}(f')$ is small\" should probably be either \"if $o\\_{f,\\sigma,b}(f)$ is small and $o\\_{f,\\sigma,b}(f')$ is big\" or \"if $\\hat{G}\\_{o\\_{f,\\sigma,b}(f)}$ is big and $\\hat{G}\\_{o\\_{f,\\sigma,b}(f')}$ is small\".", "questions_for_authors": "1. The paper claims that the proposed algorithm achieves optimal recovery guarantees. Could the authors explain what it means for a recovery guarantee to be optimal, and how the proposed algorithm is optimal in that sense? (see section \"Claims and Evidence\")\n2. Could the authors provide concrete examples of $(C, \\xi)$-noise functions, preferably with exact values for $C$ and $\\xi$? Providing examples of commonly encountered $(C, \\xi)$-noise functions will help justify the definition. (see section \"Other Strengths and Weaknesses\", point 2)\n3. Could the authors provide potential applications of the continuous-time, discrete-frequency SFT? It is true that this is not the first paper that studies this setting, but some examples of real-world uses will help motivate the problem that this paper is solving. Price and Song (2015) did mention piano tuning as an example, but it seemed rather contrived. (see section \"Other Strengths and Weaknesses\", point 2)\n\n## Update after Rebuttal\nThe authors' response was reasonable and addressed most of my concerns. I believe that the final paper will be much stronger if the authors incorporate this discussion in the final version (especially their responses to questions 1-3) and make all the fixes that they promise. Taking this into account, I have increased the overall rating from 3 to 4.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L255lzZ2Ea", "reviewer": "Reviewer_k8uZ", "summary": "This paper introduces a deterministic sublinear-time algorithm for recovering sparse continuous signals with frequency gaps, which addresses a critical gap in prior research by random approaches. The proposed method achieves optimal recovery guarantees in the presence of arbitrary noise.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the recognition of our theoretical and algorithmic contributions.\n### W1, Q1 and Q3: Lack of empirical validation\nThank you for pointing this out. We acknowledge that empirical validation would be beneficial, but our focus in this submission was on establishing theoretical guarantees and sublinear‐time recovery. Like many other works in this line of research, we have chosen to emphasize these theoretical foundations, focusing on the sublinear‐time property and performance guarantees. Such a focus often entails specialized data structures and asymptotic analyses rather than extensive empirical testing.\n\n### W2: Comparison of on-grid compressed sensing\nWe thank the reviewer for this valuable point. We emphasize that our setting is fundamentally different from standard on-grid compressed sensing methods, which assume discretized frequency domains. Our problem formulation assumes continuous-time signals with non-zero frequency gaps, where naive discretization would suffer from sparsity blow-up and noise sensitivity.\n\n### W3 and Q2: Grid assumption\nThank you for the thoughtful feedback. We acknowledge this concern and would like to clarify. Our current algorithm assumes frequencies lie on an equispaced grid with a known frequency gap, as is standard in prior deterministic SFT work. This assumption allows us to design deterministic hashing and filtering strategies with provable guarantees. Extending deterministic sparse recovery to off-grid frequencies is more challenging. We believe one potential way is to refine the grid resolution so that frequencies are only “mildly off-grid,” at the cost of increased sample complexity.\n\nWe are grateful for the reviewer’s insightful comments. Thank you for your time and valuable feedback!", "claims_and_evidence": "Yes, the claims are strictly proven.", "methods_and_evaluation_criteria": "The proposed methods are theoretically novel and address a critical gap in continuous sparse recovery. However, the evaluation criteria rely excessively on theory, lacking empirical validation and baseline comparisons, which limits practical credibility.", "theoretical_claims": "Part of them. And I think they are right.", "experimental_designs_or_analyses": "The work lacks experiments.", "relation_to_broader_scientific_literature": "The key contributions of this paper address critical gaps in the sparse Fourier transform (SFT) literature, particularly in the context of continuous signals with frequency gaps. Its deterministic guarantees and noise resilience position it as a critical step toward reliable, real-world sparse signal processing systems.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n- Deterministic algorithm for continuous sparse Fourier transform. The paper introduces a deterministic *sublinear-time* algorithm for recovering sparse continuous signals with frequency gaps.\n- Tight theoretical guarantees. Theoretical guarantees ensure stable recovery even with arbitrary noise, which addresses a key challenge in continuous signal processing.\n\n\n\nWeaknesses:\n- Lack of empirical validation. The paper provides no experiments to validate the results.\n- No comparison to on-grid compressed sensing. The work does not compare its approach to on-grid compressed sensing methods, which discretize the frequency domain and achieve good sample complexity under the same setting.\n-  Grid Assumption is too strong. Real-world signals often exhibit off-grid frequencies, and the algorithm’s performance would degrade significantly in such cases, limiting its applicability.\n\n## update after rebuttal\nAs the empirical validation is yet to be incorporated, I'll maintain my score as it is.", "other_comments_or_suggestions": "No.", "questions_for_authors": "1. How does the algorithm perform on synthetic signals with varying noise levels?\n2. Is there a mechanism to handle the grid mismatch?\n3. Could you compare the experimental performance of  on-grid compressed sensing and your algorithm by conducting experiments?  For fairness,  they can use the same samples.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4z6uF7Bbfz", "reviewer": "Reviewer_gLST", "summary": "The paper introduces the first deterministic algorithm for computing the sparse Fourier transform (SFT) of continuous signals that have a minimum frequency gap. In contrast to earlier approaches that relied on randomness, the authors develop a method that deterministically recovers a k‑sparse signal (i.e., one with only k significant frequencies) using far fewer samples than traditional FFT methods. Their algorithm uses a de‑randomized hashing scheme combined with specialized filtering functions to isolate individual frequency components even in the presence of noise. A novel (C, ξ)-noise model (defined below) is employed to guarantee robust recovery under an ℓ₁/ℓ₂ mixed norm error bound. Overall, the method achieves sublinear sample complexity and runtime—specifically O(k² polylog(FT/η))—making it an optimal deterministic solution for continuous sparse Fourier transforms when frequencies are separated by a gap.\n\nA noise function g(t) defined on the interval [0, T] is considered (C, ξ)-noise if its maximum squared magnitude over [0, T] is upper-bounded by a constant multiple of its average energy plus an additive term. Formally, this means that\n\n  max₍ₜ∈[0,T]₎ |g(t)|² ≤ C · (1/T · ∫₀ᵀ |g(t)|² dt) + ξ,\n\nwhere C is a fixed constant and ξ is a parameter that depends on the specific characteristics of g(t). This condition ensures that even if g(t) has occasional high peaks, the overall noise level remains controlled relative to its average energy.\n\n## Update After Rebuttal:\n\nI think the authors have responded to my review sufficiently and I will keep my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comment and we greatly appreciate the reviewer's recognition of our contributions. We believe that our work represents a substantial advancement in the theoretical understanding of Fourier transforms. We also appreciate the reviewer’s perspective regarding the practical applicability of our framework. While our main focus has been on establishing the theoretical foundations, we share the reviewer’s interest in examining real‐world deployments and it would be interesting to see our deterministic method can be evaluated under a variety of practical conditions. Please let us know if you have any further comments regarding our work. Thank you again for your positive feedback.", "claims_and_evidence": "Yes, the claims made in the submission are supported by proofs.", "methods_and_evaluation_criteria": "N/A (this is a theoretical paper)", "theoretical_claims": "I read the first 9 pages, and the arguments there seem fine.", "experimental_designs_or_analyses": "N/A (this is a theoretical paper)", "relation_to_broader_scientific_literature": "The paper extends deterministic sparse Fourier techniques from the discrete setting—drawing on work by Li & Nakos (2020), Hassanieh et al. (2012), and Indyk & Kapralov (2014)—to continuous signals by introducing a deterministic hashing scheme and a (C, ξ)-noise model. In contrast to previous randomized methods (Price & Song, 2015; Chen et al., 2016; Jin et al., 2023) that rely on random time sampling for sublinear recovery, this work adapts tools such as hash-to-bins and one-sparse recovery to achieve optimal deterministic recovery guarantees.", "essential_references_not_discussed": "I think the references are adequate.", "other_strengths_and_weaknesses": "The paper offers an original contribution by extending deterministic sparse Fourier techniques from the discrete to the continuous setting. Its strengths include:\n\n• A creative combination of ideas from discrete SFT (e.g., Li & Nakos, Hassanieh et al., Indyk & Kapralov) with continuous signal analysis, leading to a deterministic algorithm that avoids randomness.\n\n• Rigorous theoretical analysis with optimal sublinear sample and runtime guarantees under a (C, ξ)-noise model.\n\n• Clear advancement in theory by removing randomness, which is significant for applications where deterministic performance is critical.\n\nI don't have any significant weaknesses to mention, other than perhaps checking the applicability of this algorithm in a practical context.", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes the first sublinear deterministic algorithm for continuous-time sparse further transform with guaranteed sample and time complexities which appear to be optimal. Naturally, the paper adopts tools from existing papers, but as the reviewers point out the adaptation seems nontrivial, and techniques developed in doing so could be of interest to the theoretical ML community.

The authors' rebuttal further addressed most of reviewer's FmMR initial concerns, particularly regarding the inclusion of necessary background, examples, and definitions to help the reader understand the setting and techniques. Further, the reviewers unanimously agree that the paper's contribution is solid and recommend acceptance.

While the paper is outside the expertise of AC, upon further examination, the AC further agrees with the reviewers and believe the paper is a solid theoretical contribution to the ICML community and clearly exceeds the acceptance bar.
Decision: Accept (poster)