Efficient $k$-Sparse Band–Limited Interpolation with Improved Approximation Ratio
Authors: Yang Cao
Xiaoyu Li
Zhao Song
Chiwun Yang
Venue: NeurIPS 2025 poster ()
Keywords: band–limited interpolation
approximate algorithm
Primary area: general_machine_learning

Abstract: We consider the task of interpolating a $k$-sparse band–limited signal from a small collection of noisy time-domain samples. Exploiting a new analytic framework for hierarchical frequency decomposition that performs systematic noise cancellation, we give the first polynomial-time algorithm with a provable $(3+\sqrt{2}+\epsilon)$-approximation guarantee for continuous interpolation. Our method breaks the long-standing $C > 100$ barrier set by the best previous algorithms, sharply reducing the gap to optimal recovery and establishing a new state of the art for high-accuracy band–limited interpolation. We also give a refined ``shrinking-range'' variant that achieves a $(\sqrt{2}+\varepsilon+c)$-approximation on any sub-interval $(1-c)T$ for some $c \in (0,1)$, which gives even higher interpolation accuracy.

Efficient k-Sparse Band-Limited Interpolation with Improved Approximation Ratio
Yang Cao
Xiaoyu Li University of New South Wales 7. xiiaouuu.... @gmail..ccom
Wyoming Seminary yyaa4&@ryomingseeinnrry org
Zhao Song
Chiwun Yang
University of California, Berkeley magic. Linuxkde@gmail com
Sun Yat-sen University
chrristiiemmaang3@@mma...cc com
Abstract
We consider the task of interpolating a k-sparse collection of noisy time-domain samples. Exploiting new analytic framework for hierarchical frequency decomposition that performs systematic noise cancella- tion, we give the first polynomial-time algorithm with provable (3 + v2 s)- approximation guarantee for continuous interpolation. Our method breaks the long-standing > 100 barrier set by the best previous algorithms, sharply re- ducing the gap to optimal recovery and establishing a new state of the art for high-accuracy band-limited interpolation. We also give refined "shrinking-range" variant that achieves (v2 + + c) aappoxximation on any sub-interval c)T for some e (0, 1), which gives even higher interpolation accuracy.
signal from small
Introduction
The fast Fourier transform (FFT) (Cooley and Tukey, 1965) stands as a cornerstone across engineering, signal processing, mathematies, and theoretical computer science, underpinning both theoretical advances and practical applications. Over time, numerous FFT variants have been proposed, tailored different signal domains and time-invariance assumptions (Oppenheim al., 1997; Osgood, 2002; Oppenheim, 20. In this work we focus on the sparse Fourier transform (SFT), which assumes the signal is limited (or Fourier-sparse), i.e., observed in the time domain (either discrete or continuous) but is k-sparse in the frequency domain, i.e., its spectrum E contains only k non-zero components. Our main results concern one-dimensional continuous signals, though we discuss extensions to higher dimensions and the discrete setting. Formally, the band-limited signal is defined as follows.
Definition 1.1 (Band-limited signal), Let k Zoo. Let 8y, (f) denote the Dirac function centered fi E IR. We define the k-sparse band-limited signal 3xt (J) to be as follows:
xx x1 = Σ
2n15ee
CFT
F² = Σ my- 15--5,,0 (5)
1=1
3=1
where vj E C is the coefficient and fú E Fis is the frequency contained in the frequency range C for each [k). We use K. to denote the set of f
R
Band-limited signals are ubiquitous practice, underpinning tasks such as image compression and analysis (Watson, 1994), compressed sensing (Donoho, 2006), and (deep) learning with frequency- invariant kernels (Mei et al., 2021). Fourier methods have also emerged as a powerful tool machine
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

learning, inspiring diverse models such as random features for kernel approximation (Rahimi and Recht, 2007), Fourier neural operators for parametric PDEs (Li et al., 2021b), and spectral methods for temporal domain generalization ( (Yu et al., 2025). Efficient algorithms for computing sparse Fourier transforms are thus of fundamental importance to both signal processing and modern machine learning pipelines. A canonical challenge in this context is band-limited signal interpolation (Chen et al., (016)-closely related to the' Fourier Set-Query problem (Price, 2011)- seeks to reconstruct (part of) signal from only a handful of noisy samples (observations x (f:) + g(t;) at chosen time points t2 E [0, TT, ideally on the order of k, taken from the time domain [o, TT The band-limit F constrains all frequencies to lie in [- F.. We give the formal definition as follows.
Definition 1.2 limite signal interpolation). Assume that the orignal signal x" (t) is k-sparse band-limited limited. Given the observations of the form x² (t) + g(t) where g is an arbitrary noisy function, with the signal-to-noise ratio bounded below by constant (e.g.. ||x" l| 2 llgl|r, where | := T Storry [ denotes the signal's energy), the goal is to output the reconstructed signal y(t) such that
Bly - 11 S Cllgllz + 1|
where C > 0 is constant and ō E (0, 1) is accuracy parameter:
In general, this kind of sparse recovery problems has a long history in signal-processing and computer seience (Cooley and Tukey, 1965; Reynolds, 1989; Aibinu et al., 2008; Voelz, 2011: Hassanieh et al., 20;2a.b; Ghazi et al., 2013; Indyk and Kapralov, 2014; Indyk et al., 2014; Boashash, 2015; Kapralov, 2016, 2017: Kapralov et al., 2019; Nakos et al., 2019; Jin et al., 2023; Song et al., 2023). A fundamental fact, pointed out in Moitra (2015), is that when the frequency gap is small (1) = min I/e ʃز 1/T), exact recovery of the signal is informationall-heorrtiii impossible. Complementing this negative result, Price and Song (2015) gave k polylog(k, FT/ time --error reconstruction algorithm for -ie-dimensional signals where F is the band-limit, assuming the time domain satisfies T > ((log2(k+/5)) /n), and that the frequency gap is known. Chen et al. (2016) strengthened this result by showing that even if the frequency gap is unknown, approximate reconstruction of one- mie-dimessional signals in poly(k. (k: ) the sense that the output signal is close the original signal in the time domain albeit with worse sparsity in the frequency domain?. Subsequent works (Chen and Price, 2019b,a; Li et al., 2021 have improved this result, both in sample-complexity and decoding time. Recently, Li et al. (2021a) improved the sparsity of the output signal from poly(k) to k poly log(k)), settling for a somewhat weaker notion of approximation" than that of Chen et al. (2016).
and time is possible, in
Unfortunately, despite this steady algorithmic progress, the approximation ratio achieved by all prior band-limited interpolation methods has stubbornly remained above large constant factor (around 100). This gap is not merely an artifact of loose analysis: it stems from a fundamental criangle-inequalie bottleneck" the three dominant error sources (frequency truncation, polynomial approximation, and linear regression) accumulate additively, and each was previously controlled only up to constant factor. Closing this gap is crucial both for theory to understand the true limits of sparse recovery under noise and for practice, where large constant blow-ups translate into prohibitively low signal-to-noise requirements.
Our contributions. We break this long-standing barrier and obtain the first high-accuracy algorithm whose approximation factor is strictly below 5. Concretely, for any k-sparse band-limites signal observed over [0, T] and frequency domain F = [- F] with additive noise g()), our main result guarantees a reconstructed signal y(( satisfying
lly x 1| S (3 + v2 lll1 + 61|2" 1|r
for arbitrary accuracy parameters E, 8 E (0, 1), using only poly = (og(FT(6)) samples and + v2 + e quantifies the multiplicative
nearly- time. Here, the approximation ratio
"Classical work on band mimiied interpolation typically first estimates frequencies and then magnitudes. The latter step can be cast as Set- Set-Query problem: given a collection of locations, recover the Fourier coefficients at those positions. When the frequencies lie on a lattice, the two formulations coincide.
More precisely, the error guarantee is lly(()) - x= (t)]lr & ((]g(())l + 8||=* (1))((())))) where x (t) is the original signal, 2/(t) is the reconstructed signal, and g()) is the noise distribution.
[Iv(() - x= (t)lla eyr I poly(log(k/co)) [t=(() || 6||=*1| I|

---

noise factor by which the reconstruction error ly - 122 can exceed the unavoidable noise floor ligllz; it is the standard measure of solution quality in approximation algorithms for signal recovery. This sharply improves the best previous constant C > 100 of Chen et al. (2016), narrows the gap to the information- theorrti optimum of 1, and resolves an open question posed by Li et (2021a). We also give a refined "shrinking-rand -range" variant that achieves (v2 + ε + -aaappoxximation on any Sub-interval (1 c)T with the same sample complexity.
Technical novelties.
Our improvement hinges on two new analytic ingredients.
Ultra-high-sennitiiity frequency estimation. We design filter family that amplifies each true cluster's energy while canceling an equal-scale portion of the adversarial noise. This raises the recoverable energy threshold from (11) (1 + Vε), eliminating an entire factor of 2 in the first error component.
2. Hierarchical noise-cancellation analysis. We view band-limited interpolation through a unified two-step lens frequency estimation followed by signal estimation and track the flow of noise across levels. A refined coupling argument shows that the filtered noise passed to the second step is correlated with the unrecoverable signal energy; bounding them jointly yields the multiplicative factor (3 + v2) instead of the additive sum of three constants.
Beyond improving the approximation ratio, our framework is conceptually modular: swapping in any future advances in either sub-routine immediately propagates to a tighter end-to-end guarantee. We believe the tools introduced here- part-paatillllrly the systematic lattice-frequency viewpoint-ww be valuable well beyond the specific interpolation task, offering a blueprint for pushing other sparse-recovery algorithms past long- standinnnn constant-facto factor barriers.
cancellacnl bound and the
1.1 Main results
Recall that existing algorithms for band-limited interpolation achieve only coarse error bounds of the form
- 17--"'1> ClggT + +
with a constant Rs 100 in the best published result (Chen et al., 2016); repeated uses of the triangle inequality prevent C' from dropping below 3. We introduce three new ingredients- control, an ultra-sensitive frequency estimator, and an efficient signal-estimation routine- and combine them in refined error analysis that collapses these additive losses into single multiplicative term. This yields the first algorithm with provable approximation constant strictly below 5, and remains near-optimal in both sample complexity and running time.
Our first result uses a sharper error analysis improves C 3 + v2 + & for any small > 0, which is stated as follows.
limited interpolation, informal version of Theorem H.42), Let x' (t) be a k-sparse band-limited signal with frequencies in [-F, F). Assume the minimum freiquuufreqeeee frequency separation is (21/TT) and the signal-to to-noise ratio satisfies ||x" ||T Z l|g||r. Given observations art) = x (t) + gt) in time duration [0. T}. where g is arbitrary noise. For e, ō E (0, 1), there exists algorithm that uses poly(k, -1 log(1/5) (1/5) log(FT) samples and runtime, and outputs poly(k, - log(11 --))r-ssaaseeeeeeeee -parse band-limited signal y(t) such that, with high probability,
Theorem 1.3
y x =1 < (3 + v2 e)llgI 8||="||T.
Our techniques extend to a "shrinking-range" variant that attains an even tighter constant on any sub-interval (1 e)T, which leverages additional "spatial slack" to lower the approximation ratio to /2 + cc.
Theorem 1.4 (Ultra-high-accuracyy band-limited interpolation with shrinking range, informal ver- sion of Theorem 1.4). Let (t) be k-sparse band-limited signal with frequencies [-F,F], Assume the minimum frequency separation is 2 2(1/T) and the signal-to-noiss ratio satis- fies || Z [|g[|.. Given observations x(() = (1) + g(t) (t) in time duration [0, T7, where g is arbitrary noise. Let T' T(1 c). For e E (0, there exists algorithm that uses poly(k, -l,ooo((1/0)) log(FT) samples and poly -
log(1/8)) log2( ,,o,,o((()))) runtime, and
3

---

-sparss outputs poly(k,E"), , (log(1/6)) sparse band-limited signal y(t) such that, with high probabil-
ity.
llv - x 1r - + + + 6||="||r.
We remark that Li et al. (2021a) obtain a related but incomparable guarantee. For any å >> 0, their algorithm outputs reconstruction v(4 satisfying
(tv(t) x (t)ll(--)r I allg(t)llr + 6
where is the approximation ratio, where poly(log(k/((e)) and (f) is the Fourier transform of 2t)... The procedure uses poly(k, (1)) (FT( samples and poly(k, c 1og(1//)) (FT) time, returning a k, poly(1/c, ( signal. Hence their result achieves near-optimal sparsity, but the approximation factor grows polylogarthhmicaly with k, 1/6, and 1/c, whereas our algorithm attains a constant (v2+ + + c) ratio.
(0,1) is the shrinking parameter,
1.2 Notations
For any positive integer we use [n] to denote {1,2, .... complex number z E C where
,n). 11, + and a, b R. We use denote the complex conjugate - ib. Then it is obvious that |=|² 2- a² ls?
We use i to denote V-1. For
of z, i.e.,
We use f g denote that there exists a constant C such that f s Cg, and f g denote I 9 - ʃ. We use Ō(J) to denote / log (f)) We say æ(1) is a k-sparse band-limited when <<t) = Σ Uj exp(2xifzt). We use E(f) to denote the Fourier transform of (t).. More specifically, f(ʃ) - s(() (osp(-22ifil)
We define our discrete norm as (1g()))| 1sT Eies (s(1)2 for function g. We define our weighted discrete norm (t)).) Eies w.(g(t)1² for function We define the continuous Toomr as [9(() + fo (t) for function g.
In general, we assume x² (1) is our ground truth and is a k-sparse band-limited signal. We can observe function s(()= xx (t) (() for g(() being noise function. We observe sr(1) in duration [0, 7]. The ground truth x (t) has frequencies in [- [-F, FFFF). F).
Technical Overview
Section 2.1 introduces the framework of discrete Fourier set query. Section 2.2 shows how to apply our discrete Fourier set query estimation algorithm to obtain high-accuracy band-limited interpolation algorithm in Theorem 1.3 and Theorem 1.4.
2.1 Discrete Fourier Set Query
Many signal processing tasks can be phrased query problems in different domains. For instance, the sparse Fourier transform examines only the coefficients at a small set of frequencies eececclyeeeeeecllyyyyyeeeeecacyy exactly set-query problem in the frequency domain. Another example is recovering the actual Fourier coefficients when their support (the set of non-zero frequencies) is known.
For concreteness restrict attention one-dimensional discrete signal sx()) of length n, written as xtf) Σ/= 2niit/n ,t E [n]. Given a k-subset S [ni], the set-query task is to recover Zg. Equivalently, define (t) = Σ jes 3 eaiftt/n; this a k-sparse signal.
Algorithm overview. Our algorithm can be viewed as three-step pipeline, which collapses into three concrete stages in practice:
meaning sup, (x)))22 < R [. Consequently, uniform sample So C [n]] of size O(k log k) already preserves the signal's energy up to constant factor and forms faithful oblivious sketch.
Uniform sketching. Any discrete k-sparse signal has energy bound

---

2. Sketch distillation. We refine So via the Sketch Distillation procedure: well-balanced sampler chooses a linear-size subset S₁ C So and weights w such that | || la/n for every signal supported on S, while simultaneously ensuring the weighted energy of the orthogonal component 3ig + g is not amplified, i.e. 1|rg + glls,. = 0 + gllr).
3. Weighted regression. With samples (x(())ees and weights w, solve the weighted least- squares problem min /wo (Av' 2 where A., 2 and b; xx(4). The solution (51 o/ yields reconstruction whose emror obeys 1ssl 1 1| +lll..
Together, these steps give linear-sample high-accuracy solution to the discrete Fourier set-query problem, achieving (1 + e) approximation with high probability. A routine analysis gives an (1) approximation; below refine it to + =).
Algorithm Discrete 1-D Fourier Set-Query
1: procedure SETQUERY(I;, n, k S, E)
2: {JI,.... [x] S
/t Step I: Uniform sketching */
3: So Sample O log k) points i.i.d. from Uniform([z))
|* Step 2: Sketch distillation */
4:
F + 2///////t/n
bj E
5:
(f41,...,4,) 1.,,,,,,,) w) + RANDBSS+(K; F Uniform(So), (E/4))) 1* Step 3: Weighted regression */
b Algorithm
6:
for (i,j) E [s] x [k] do
7:
Ai, f- 2m1f,4//n end for
8:
9:
for E [s] do
10:
b. s xxt,)
D> observe at t,
11:
end for
12:
o' f- arg min
Vl (Av' - -b)ll
w'ec
13: return
14:
end procedure
Composition of well-balanced samplers. To obtain (1+ guarantee we must show that the final sketch (Si, w) arises from a single well-balanced sampling procedure (WBSP). In general, composing two WBSPs may violate bellebaaanceddees:: while the first property (accurate energy estimation for every f E F) preserved, the second property concerning weight sum and condition number can fail.
Our setting is special: the first sampler draws each point uniformly from [n]. We prove that, under this choice and with the tight energy bound I = k for band-limited signals, each sample produced by the two-stage composition iittriuutioneqquivlleee sampler is itself well-balanced, allowing us to invoke the sharper error analysis and conclude that
to fresh uniform draw. Hence the composite
JØs Esll2 s e 51
with high probability, Thus we obtain a linear-sample, high-accuracy algorithm for the discrete Fourier set-query problem.
2.2 High-accuracy band-limited interpolation
In this section, we introduce how to obtain a high-accuracy one-dimensional land-limited inter- polation algorithm (Theorem 1.3), which improves the constant-accuracy algorithm by Chen et al. (2016).
Let us briefly summarize the previous algorithm in Chen et al. (2016). The high-level idea is to first find some small intervals the frequency domain such that each contains some significant frequencies of the signal x². (These intervals are called "heavy-clusters" in their paper.) Then, they use some filter techniques (also used in Price and Song (2015)) to reduce the problem of reconstructing a", signal with multiple heavy-clusters to several single heavy-cluster signals. Then, for each single
5

---

heavy-cluster signal, since the band-limin is small, they can efficiently estimate its frequencies. Finally, they reconstruct a (ooly())-pprr signal that is close x" via a robust polynomial learning algorithm. More specifically, their algorithm consists of the following steps:
1. They show that the ground-truth signal x² x²(1) = Σ 2 can be approximated by (t) Ejes "y where S {j [R:] [3 some heavy-cluster C₁} is the set of frequencies in the heavy-clusters. This step will cause approximation error E1 := || - øg||ı & 1.2A/* where 2² := | f- + ò ||x appears in the approximation enror of the
interpolation problem.
2. They solve Frequency Estimation problem for ay using the filter techniques and multiple- to-one heavy-cluster reduction, and get a list I of O(k) candidate frequencies so that for each j E S. fj is close to some Jp; E L.
22 x; (t), where 2t 3. The signal st(() can be decomposed into e fi) is one-cluster signal with small band-limit. For each 2 (t), they prove that there exists a low-degree polynomial (t( that can approximate it. Let's de- note the hytyyomial-approxxmmae approximation error E₂ == ||æs - Po - 8||=5||7.
signal Σ c2mftt (t(t) by ptyy)ty which has an
[4]
4. It remains to reconstruct poSy (4), which is variant of Signal Estimation problem. They use a sampling-ane aenplligg-nd-eerreeeee red-resression approach to obtain a poly(k)-span signal y(!) with an approximation error Eg := lyy 25 5 S 2200N.
By triangle inequality, the total approximation error is lly x= x=11 E1 E2 + ES S C C.N, where
C > 1000 is an absolute constant.
3-approximation barrier To achieve high-accuracy band-limited interpolation, we need to control the errors F,, E2, and Ez.
For F1, is coupled with the second step, since the approximation error of 2g is connected to the significance of each heavy-cluster. If we choose too-small E,, Is will contain some not-so-signiffcant frequencies, and the Frequency Estimation algorithm may not be able to find them. Thus, with the techniques in Chen et al. (2016), we cannot make Ej be less than N. Even worse, due to the noise in the observed signal, the error will be at least 2N.
For Eg, it only depends on the eтrоr parameter 8. Since the sample and time complexities of the algorithm only depend logarithmically on 1/5, allows us to re-scale and make Eg very small.
For Fs, where we lose big constant, we need high-accuracy Signal Estimation algorithm to recover the previous sections, the error of the Signal Estimation will be at ..
signal ss (t). However, as we discussed the
Therefore, there is 3-approximation barrier in Chen et al. (2016)'s approach due to the triangle inequality.
In the remainder this section, we first introduce our techniques to achieve a (7 + +))))-aoa approxxxitntoo
error. Then, we show how to overcome the barrier and achieve a (3 + v2 + + apappoxximaiion error.
2.2.1 (7 appproxmmaai algorithm
High sensitivity frequeney estimation We first improve Ej from 1. 1.2N to (1 + e)W by proposing high sensitivity frequency estimation method. More specifically, to identify the heavy-clusters of
*Due to the noisy observations, not every frequency in the heavy-clusters is recoverable. This gap causes an extra implicit error term in Chen et al. (2016), which is about 12N. Section 2.2.1 has more detailed discussion. *We remark that even if the ground -trtt signal x =t) can be apllxxapro by a mixed Fourier- polynomial signal (()), we are unable to recover every basis of Ø(t) due to the limitation of the frequency estimation procedure. Thus, directly applying linear regression to partially reconstruct Ø(t) will not guarantee to be approximmaao of 2² (t).

---

the signal x², Chen et al. (2016) designed filter function H such that H xx has high energy in each heavy cluster C; that is,
Co. H (H T N2.
(I)
Moreover, H's frequencies contained in small interval of length A. These properties imply that for any true frequency fi E C, the signal H x² with frequency domain restricted to [fi A. fi + A] is a one heavy-cluster signal with small band-limit, which allows us use Price and Song (2015)'s approach to estimate fi. The filter function H in Chen et al. (2016) is only O()s-sensitvv,, which means it can concentrate a constant fraction of the signal's energy. And for those less important frequencies, they cannot be clustered by H and will be lost in the frequency estimation procedure.
We manage to modify their filter construction and obtain a (1 - =) sensitive filter function H such that the signal æ:5- consisted of the frequencies in the new heavy-clusters has about (1 e)-fraction of energy of x². More specifically, we have
FTT 1| xz- 1r S (1 + e)W.
To prove that point: the energy condition of heavy-cluster and the energy condition of frequency estimation are inconsistent due to the noise in observations. To be able to estimate the one heavy-cluster signal's frequency, is required that
actually estimate the frequencies in the new heavy-clusters, observe subtle
Jo. (I |H
T k
N?
which is different from Eq. (1). other words, not all frequencies S* are recoverable, but only most of them. Since Chen et al. (2016) only wants a constant approximation error, they may simply ignore this difference by losing a constant factor in accuracy. For us, however, we need to make precise. We define S to be subset of S* containing the frequencies in the heavy-clusters satisfying Eq. (2). We analyze the effect of H g and show that by strengthening the RHS of heavy-cluster's energy condition (Eq. (1)) to 1T A/2 we can bound the unrecoverable part's energy by
K
F
| æs||r < (2 + e)W
For the recoverable part æs. we can just follow Chen et al. (2016)'s approach to estimating the frequencies each heavyreluster.
Generalized high-accuracy signal estimation We apply our three-step Fourier set-query frame- work to solve the signal estimation problem in the forth step of Chen et al. (2016)'s algorithm and improve Eg from 2200A/ to (4 + e)W. We first define the problem more formally. By frequency estimation, obtain list of candidate frequencies of iy and in the third step, we know that it can be approximated by (t)) := D 2 degree-d polynomials. We can rewrite polyy in the Fourier monniir- mixed basis:
(t(t) with very tiny error Ez, where (t) are some
[r]]
oag 2niddp
S.Sy (1)
where Ui.j E C and f. E L are known. That is, we need learn {v,,) ) given noisy observations P. (t) + g'((), which is a Signal Estimation problem for the following family of signals:
Fmix == span { 2atiic
e i [[4]),] E (0....,d) ......
We apply our three-step framework as follows.
In Step 1, we first need an energy bound Fmix. Chen et al. (2016) showed that sup, |u(t))² < Ō(IT)+d*
Rmix
sup Tm)
Then we can get that uniformly sample O( points in [0, 7] gives an oblivious sketching for S,oyy Furthermore, show that this sampler is e-well-balaneed.
7

---

In Step 2, since we aim at achieving regh-accurayy. we do not distill the sketch but directly apply the sharper error analysis control the energy of the orthogonal part of noise.
In Step 3, solve a weighted linear regression estimate the coefficients and obtain signal (1) E Fix such that
p. || & (1 e)] SS - (4 144+6) e)W. Figa 11v'
Then, we can transform back to a poly poly(k)-sppass signal with error || - y'llr S Eg. Combining them together and re-scaling & and 6, we get that
|yy - x= || I |V - 1/|l + ||y poyy I|T + || - xs|l + 112 - x ||T + I x x²|[T
I Es + Fige Fg + F1.5 5 + FT
- (7 + )|ll|r - 5 61|0=1| ||T-
Therefore, obtain band-limited interpolation algorithm with (7 a) approximaaiio error.
+s(ss(0) (/ss BU)
Ss. is((5) B()
Fa ( AC
2s. (f) B()
( - 3z)(() +B) (a) (1) (#s; ( (U)l
(# ( 2s; H (b) [((()) 2s, (()lrr
Figure 1: An illustration of the signal-noise cancellation effect (Eq. (3)). In (a), the blue region corresponds to the first term of Eq. (3), which roughly equals the energy of x rsy- In (b), the red and blue regions correspond to the second term, where most of the energy is canceled. Thus, their total energy very close to ||x - zs; I|.
2.2.2 (3+ + /2 + +)) approximation algorithm
How can we further improve this algorithm? We observe that Egew can be written more precisely as + +)llgg/r+++ + (3 e... On the other hand, Ey and FL5 only depend on A. can take smaller value for 2 i.e. e(1gg]? + o1|z117), then we will improve approximation error. We show that it is possible via an ultra-high sensitivity frequency estimation method.
Ultra-high sensitivity frequency estimation To improve the sensitivity of the frequency estimation method, let N²2 e\² and consider the heavy-clusters with parameter Mr. Let S denote the of frequencies of (t) (t) in the Ny-heavy-clusters. By the same analysis as in our previous frequency estimation approach, we have E.ew+ = || - æs; Ir I (1+
However, due to the inconsistent energy conditions, only those frequencies in the heavy-clusters satisfying Eq. (2) are recoverable, Let S₁ denote the set of such frequencies, and we need to upper bound ||55 Is, [|z. Previously,
strengthen the heavy-cluster's condition (Eq. (1)) and get
ELS < (2 + =)llgl bound. Here, instead, we relax the RHS of Eq. (2) to E TNN Intuitively, more frequencies will satisfy the new frequency estimation condition; and if there is a unrecoverable frequency f E S it indicates that its contribution in filtered signal
x cancelled out by the filtered noise H g. Using this signal-noise cuncellation effect, we prove that:
[H xs; |l + [[( - æs, 1 < [1+ V=) xs; 11?
(3)
which saves a factor of from E, by introducing an extra term || | 2s, IlT. Recall || - 2s l|T is related to Egew the error of the signal estimation procedure. We can decompose it into the "passing energy" H (xr - Jss IrT and "filtered energy" [I(Td H)(x - xs, lll and bound them by:
|| zs lr < [[ 2s, Mlr + 11lllr + O(=)]l>* Is I.

---

Thus. Eq. (3) can be considered as upper- bounding E1.s and E3 simultaneously. Combining them together, we get the following eπror guarantee for the frequency recoverable signal rs,
x æsillr + || - =sıllr S $1 v2
+ +
(4)
Then, by careful analysis of the HASHTOBINS approach used by Chen al. (2016) for Frequency Estimation, we show that æs, 's frequencies can be efficiently approximated, which gives an ultra-high sensitivity frequency estimation method.
The remaining part of the algorithm almost identical to the previous one. We run the high-accuracy signal estimation algorithm reconstruct æs, Let y(t) denote the output aaddlimmited signal. By Eq. (4) and re-scaling E and ö, we have
1y x I|r s (3 + e)løllz 5|
Therefore, we achieve +3+ + 2 + apaproxxmmaaion error for the band- limited interpolation.
2.2.3 (v2 + appppooxiinttoon algorithm with shrinking range
When we only care about the signal the interior window [0, (1 e)T], the two "edge strips" of length cT/2 at the beginning and end become disposable budget. We exploit this slack with shrinking-raan rrange filter H that (i) leaves the interior almost unchanged and (ii) suppresses the contribution of every frequency band whose energy is already comparable to the noise. This ensures that, after filtering, all irrecoverable energy cancels with the adversarial noise, so the residual must approximate is strictly smaller than in the full-range setting.
Using the same high-sensitivity filter construction, but tuned the relaxed threshold E E1|19118- identify a set S of "truly heavy" frequencies inside each cluster. We show that (see Lemma I.1)
2 - xsllr + ||ts- IT s (v2 + O(VE c))lllII O(Vō)]l="
Then we can recovers, for every fj E S, an approximation 7, with resolution O(AnVA.T) using only poly(k, 1=1, log(FT) samples. See Corollary I.2 for more details.
Then we can replace each narrow band around f, by low-degree polynomial (t) (degree d O(TA 3/2 + k- log k:)) whose Fourier support stays inside the band and whose time-domain error is (6)]|==
On T" = (1 e)T we run the high-accuracy signal- -ignal-estimation routine (Section G.2), but now with the uniform sampler restricted 1". Because the filter already tames boundary energy, a linear-sized bell-balanced sample suffices to learn the coefficients with relative error 1 E
Putting it together. Summing the four error sources- cluster trimming, frequency rounding. polynomial patching, and weighted regression-and and rescaling 5, yields Theorem 1.4: for any e 1),
By - ---=""|r- & (V2+ +c) + ||00
with sample complexity and runtime poly folyykke=! c log(1/))) log ou) and output sparsity poly (k, - c- (ogg(/))) Thus, shrinking the range lets us push the approximation constant all the way down to v2 + +
3 Conclusion
In this work, we break the long-standing constant-factor barrier for noisy band-limited interpolation.
Our primary algorithm delivers (3 + /2 + -papppoximmaaionn with poly (k: - Iog (1/8)) sample and time complexity. refined "shrinking-range" variant pushes the constant down to (v2 + + c) on any interior window (1 e)T, demonstrating that additional spatial slack can be traded directly for reconstruction accuracy. Two technical ingredients drive these improvements: We introduce new filter family simultaneously magnifies cluster energy and cancels adversarial noise, allowing

---

reliable recovery at an energy threshold arbitrarily close to the information-theoredee optimum. We also proved a unified view of frequency and signal estimation tracks how residual noise propagates through each stage, replacing three additive enror terms with single multiplicative bound and collapsing the approximation constant. These techniques are modular and extend naturally to broader sparse-recovery settings, opening avenues for even tighter guarantees in higher dimensions, alternate transform domains, and streaming environments.
Our guarantees rely on several idealised assumptions: the signal must be exactly k-sparse in the frequency domain (or perfectly lattice-alignn alignedd, the signal-to-noiss ratio must exceed constant threshold, and the analysis is fully worked out only in one dimension; relaxing any of these conditions can inflate the hidden polynomial factors in our sample and runtime bounds or even invalidate recovery. Moreover, the ultra-sensitive filters we employ require high numerical precision coooon-round---eee round-off error or model mismatch may erode the stated constants in practical deployments. It remains the open whether these assumptions can be relaxed and further improve the approximation ratio.
Acknowledgment
We thank anonymous NeurlPS reviewers for their constructive comments.
References
Aibinu, A. M., Salami, M.-. E., Shafie, A. A., and Najeeb, A. R. (2008). Mri reconstruction using discrete fourier transform: a tutorial.
Alman, J. and Williams, V. V. (2021). A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522-539. SIAM.
Batson, J., Spielman, D. A., and Srivastava, N. (2012). Twice-ramanujan sparsifiers. SIAM Journal Computing, 41(6):1004-1211.
Boashash, B. (2015). Time-frequency signal analysis and processing: a comprehensive reference. Academic press.
Borwein, and Erdélyi, T. (2006). Nikolskii-type inequalities for shift invariant function spaces. Proceedings of the American Mathematical Society, 134(11):3243-33
Chen, X., Kane, D. M., Price, E., and Song, Z. (2016). Fourier-sparse interpolation without frequency gap. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 741-750. IEEE.
Chen, X. and Price, E. (2019a). Active regression via linear-sample sparsification. In Conference on Learning Theory (COLT), pages 663-695, PMLR.
Chen, X. and Price, E. (2019b). Estimating the frequency of clustered signal. ICALP.
Chernoff, H. (1952). A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics, pages 493-507.
Cooley, J. W. and Tukey, J. W. (1965). An algorithm for the machine calculation of complex fourier series. Mathematics of computation, 297-331
Donoho, D. (2006). Compressed sensing, IEEE Transactions on Information Theory, 52(4):1289- 1306.
Ghazi, B., Hassanieh, H., Indyk, P., Katabi, D., Price, E., and Shi, L. (2013). Sample-optimal average-case sparse fourier transform in two dimensions. In 2013 51st Annual Allerton Conference Communication, Control, and Computing (Allerton), pages 1258-1266 IEEE.
Hassanieh, H., Indyk, P., Katabi, D., and Price, E. (2012a). Nearly optimal sparse fourier transform. In Proceedings of the fouth-fourth annual ACM symposium on Theory of computing, pages 563-578.
10

---

Hassanich, H., Indyk, P., Katabi, D., and Price, E. (2012b). Nearly optimal sparse fourier transform. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 563-578.
Indyk, P. and Kapralov, M. (2014). Sample-optimal Fourier sampling in any constant dimension. In IEEE 55th Annual Symposium onFoundations of Computer Science (FOCS), pages 514 523. IEEE.
Indyk, P., Kapralov, M., and Price, (2014). (nearly) sample-optimal sparse fourier transform. In Proceedings of the twenty-fith annual ACM-SIAM symposium on Discrete algorithms,, pages 480 499. SIAM.
Jin, Y., Liu, D., and Song. (2023). A robust multi-dimennional sparse fourier transform in the continuous setting. In SODA.
Kapralov, M. (2016). Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time. In Proceedings of the sorty-eighth annual ACM symposium on Theory of Computing, pages 264-277.
Kapralov, M. (2017). Sample efficient estimation and recovery in sparse FFT via isolation on average. In Umans, C., editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 651-662 IEEE Computer Society.
Kapralov, M., Velingker, A., and Zandieh, A. (2019). transform. In Proceedings of the Thirtieth Annual Dimension-independenn sparse Fourier Symposium on Discrete Algorithms (SODA), pages 2709-2728. SIAM, https:/ //wpvvaa//vv////aa//////aaaaiav org/ http/dff11900 10633. pdf.
Kós, G. (2008). Two turán type inequalities. Acta Mathematica Hungarica, 119(3):219-226,
Le Gall, F. (2014). Powers of tensors and fast matrix multiplication. In Proceedings of the 39th international symposium on symbolic and algebraic computation (ISSAC), pages 296-303. ACM.
Lee, T. and Sun, H. (2015). Constructing linear-sized spectral sparsification in almost-linear time. In Guruswami, V., editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 250-269, IEEE Computer Society.
Li, J., Liu, A., and Moitra, (2021a). Sparsification for sums of exponentials and its algorithmic applications. arXiv preprint arXiv: 100.02774.
Li, Z., Kovachki, N., Azizzadenesheli, K., Liu, B., Bhattacharya, K., Stuart, A., and Anandkumar, A. (2021b). Fourier neural operator for parametric partial differential equations. In ICLR.
Mei, S., Misiakiewicz, T., and Montanari, A. (2021). Learning with invariances in random features and kernel models. In Belkin, M. and Kpotufe, S., editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorudo, USA, volume 134 Proceedings of Machine Learning Research, pages 3351-3418. PMLR.
Moitra, A. (2015). The threshold for super-resolution via extremal functions. In STOC. arXiv preprint arXiv:1408.
Nakos, V., Song, Z., and Wang, Z. (2019). (nearly) sample-optimal sparse fourier transform in any dimension; ripless and filterless. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1568-1577. IEEE.
Oppenheim, A.
https://ocw.aprende..cm (2011). wtwp:///eeeeeeeo-00oooooaa-aaaaa notes/MITRES 0075 lec099.d..
Lecture notes:
Fourier transform properties. 1/lectuee
Oppenheim, A. V., Willsky, A. S., Nawab, S. H., Hernández, G. M., et al. (1997). Signals systems. Pearson Educación.
Osgood, B. (2002). Lecture notes for 261 the fourier transform and its applications.
Price, E. (2011). Efficient sketches for the set query problem. In Randall, D., editor, Proceedings the Twenty-Secone Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 201 San Francisco, California, USA, January 23-25, 2011, pages 41-56. SIAM.

---

Price, E. and Song, Z. (2015). A robust sparse Fourier transform in the continuous setting. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 283-600. IEEE.
Rahimi, A. and Recht, B. (2007). Random features for large-scale kernel machines. NeurIPS, volume 20.
Reynolds, G. O. (1989). The New Physical Optics Notebook: Tutorials in Fourier Optics. ERIC.
Song, Z., Sun, B., Weinstein, O., and Zhang, R. (2023). Quartic samples suffice for fourier interpola- tion. In FOCS. arXiv preprint arXiv:2210.12495.
Voelz, D. G. (2011). Computational fourier optics: a MATLAB tutorial. SPIE press Bellingham, Washington.
Watson, A. B. (1994). Image compression using the discrete cosine transform. Mathematica Journal, 4:81-88.
Williams, V. V. (2012). Multiplying matrices faster than coppersmith-inngrrad.. In Karloff, H. J. and Pitassi, T., editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 22, 2012, pages 887-898. ACM.
Yu, E., Lu, J., Yang, X., Zhang, G., and Fang, 7. (2025). Learning robust spectral dynamics for temporal domain generalization, arXiv preprint arXiv:2505.1255 12585.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the claims made, including the contributions made in the paper and important assumptions and limitations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We include the limitation discussion in Section 3.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification: All assumptions of this work are made within the statement of theorems or lemmas. For each theoretical result:
The formal version of Theorem 1.3 is Theorem H.20, where the proof is in Section H.
The formal version of Theorem 1.4 is Theorem I.4, where the proof is in Section I.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
wttps.cc/ppblccc//eccccccpcppppp gewic//gugee...ee CoodeSummii agionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http///nurrpp.pp/
Answer: [Yes]
Justification: All authors have reviewed and confirmed that the research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We include the broader impacts discussion in Section J.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments and poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https : httpa/rrpp..cc/ooeeeeeeeeeeeeeee / for what should or should be described.
19

---

Appendix
A
Preliminaries
This section is organized as follows. In Section A. we provide some technical tools in probability theory and linear algebra. In Section A.2, we review the Fourier transformation for different types of signals.
A.1 Tools and inequalities
Lemma A.1 (Chernoff Bound Chernoff (1952)). Let X1, X2, Xxn be independent random variables. Assume that O < X; S always, each E [n]. Let X Xi + X2 + Xn and
1 [ Σ [[x]] Then for any
Pr[x 21 +6)+ S exp( 2 10) and Pr(x S (1 =) S exp( 2 m))
Definition A.2 (E-net). Let T be a metric space with distance measure d. Consider a subset K C T and let E > 0. A subset N C K is called an e-net of K if every point in K is within distance of some point of N, i.e.
Vo E K, Fy EN s.t. d(r,y)) S.
Fact A.3 (Fast matrix multiplication). We use [maa(a, (a, b, c) to denote the time of multiplying an x b matrix with another с matrix.
We use w to denote the exponent of matrix multiplication, i.e., Tmat n, n) = n²" Currently 2.373 Williams (2012); Le Gall (2014); Alman and Williams (2021).
Fact A.4 (Weighted linear regression). Given a matrix A E Caxd, a vector E C and a weight vector RS it takes O(nd-=1) time output an x' such that
a' arg min|| /aain///WWW// VW(Ar b)1(2 (A'WA)
where VW == diag( / //W......... w E B and w = 2.373 is the exponent of matrix multiplica- tion Williams (2012); Le Gall (2014); Alman and Williams (2021). Fact A.5. For any x E (0, 1), have cos(x) S exp(-2²/2),
A.2 Basics of Fourier transformation
The definition of high dimensional Fourier transform is follows:
*()) S /= a11)
()), where f TRdd
and the definition of high dimensional inverse Fourier transform is as follows:
xt)) / (- exp((xi))i where f Rd.
Note that when replace d = 1 in the definition of high dimensional Fourier transform and inverse Fourier transform above, we get the definition of one-dimensional Fourier transform and inverse Fourier transform.
The definition of discrete Fourier transform is follows:
24 exp((2mift/m)) where f [n],
and the definition of discrete inverse Fourier transform as follows:
3 exp (xpp2rift/n)) where t [n].
20

---

A continuous k-Fourier sparse signal zzt) R= C can be represented as follows:
s(1) = Σ by exp(2ni(Sz,,) ()) ec, E R vj e [+]
==1
Thus, 2(f) is:
H() = Σ 85ō(L - 1s)-
discrete k-Fourier sparse signal C can be represented follows:
St = Σ
Bj expp(2mijl/n) S [s], = k. eCCYjes.
jES
So, y is:
3y = {00
U .JES s O.W.
B Definitions of Semi-Continuous Fourier Set Query and Interpolation
In this section, we give the formal definitions the problems studied in this paper. Section B. define the Fourier set query for discrete and continuous signals. In Section B.2, define the limdeli interpolation problem and its two sub- aub-problems: frequency estimation and signal estimation. And in Section B.3, we discuss the importance sampling method.
B.1 Formal definitions of Fourier set query
The discrete Fourier set query problem is defined as follows:
Definition B.1 (Discrete Fourier set query problem). Let C and E be its discrete Fourier transformation. Let O. Given a set S C [n] and query access to x, the goal is to use a few queries to compute vector x' with support supp(æ') C S such that
((x' s) 1 < 11s
We also define the continuous Fourier set query problem as follows:
Definition B.2 (Continuous Fourier set query problem). For 2 1, let (t) be a signal time duration [o, TJd. Let (f) denote the continuous Fourier transformation of x" (I). Let > 0. Given set S C Rd frequeencss such that supp(x*) C S, and observations of the form xxt) = x (t) gt),, where gt) denotes the noise. The goal is output Fourier- Courier-sparse sparse signal x' (t) with support
supp(x') C S such that
- S (1++)- -1911.
B.2 Formal definitions of semi-continuous band-limited interpolation
In this section, we provide the following formal definition of the semi-continuous band-limited interpolation problem, where assume that the frequencies of the signal are contained in lattice.
Problem B.3 (Semi-continuous band-limited interpolation problem). Given a basis B of m known vectors by by, bm E Rdd, let A(B) IRd denote the lattice
m
A(B) = = :2= Σ
Sbb, & E EzEe
Suppose that f2. fo E A(B), Vi E [K) S F. Let xt) Ei 2 and let g(l) denote the noise. Given observations of the form x(1) = x1(1) + g(), LE [0, Let 7 minggs Ilfa filloo. There are three goals:
21

---

1. The first goal is to design an al algorithm that output f1, f2. : fk exactly given query access to the signal r(t) for E [0.
2. The second goal is to design an algorithm that ouiput a of frequencies such that, for each fú there is f E L, |If, - filla S D/T.
3. The third goal is design an algorithm that output y(1) Σラ 1i 2x1f3t such that Joorraa lu(t) dtt) X Jo.ry (o
Then, we extract two sub-urobie problems from Problem B.3: Frequency Estimation and Signal Estimation. We give their definitions below.
We first define the d-dimensional frequency estimation under the semi-continuous as follows. this problem, we
recover each frequencies small range.
Problem B.4 (Frequency estimation). Given basis B of m known vectors b1. b2, ... bm E Rd let
A(B) C Red denote the lattice
A(B) = f 2 Rd
Σ
cb Z. Zi [m]}
Suppose that J2....... A(B). Let x²) Ej= 20 and let g(l) denote the noise.
Given observations of the form x(t) = (1) + g(t), E [0, Let = minizs [lf - fell folloo-
The goal is to design an algorithm that output set L of frequencies such for each fú, there is f/ L. IIʃ. f/ l12 D/T.
We remark that the recovered frequencies in are not necessary to be in A(B), and is a parameter that can depend on k.
Next, we define the d-dimensional Signal Estimation under the semi-continuous setting as follows. In this problem, we want to recover signal that can approximate the ground-truth signal in the time domain.
Problem B.5 (Signal Estimation problem). Given a basis B of known vectors bi, b2. bm Rd. lei A(B) C IRd denote the lattice
A(B) = = :2=
Cabiace E a [ml]
2m1
Suppose that f2, fA A(B). Let x² x²) = Ej 0j 2 and let g(t) denote the noise. Given observations of the form r(t) = x (t) g(t), 179. Letn = mingz Iif fa oc.
The goal is to design an algorithm that outputs y(t) = EE 1// . 2 such that
Jom (b(() - =tt) (()))==())(dt$
Jomp dtt
Note that outpulting u(t) = Ef 2niif. means outputting
Remark B.6. We note that given the solution of Frequency Estimation (Problem B.4), Signal Estimation (Problem B.5) can be formulated as a Fourier set query problem (Problem B.2). More specifically, by Frequency Estimation. we will find a set that contains all frequencies of the ground truth signal x" (t). Then, we only need to recover the coefficients with frequencies in this set, which is equivalent to a set query problem.
B.3 Facts about importance sampling
Important sampling try to estimate a statistic value in one distribution by taking samples in another distribution. In particular, Chen and Price (2019a) considered the importance sampling for estimating the norm of functions in a linear family F.
In this followings, first provide some basic definitions about linear function family.
22

---

Definition B.7 (Condition number of sampling distribution). Let G' be any domain and F is a linear function family from G to C. Let be an arbitrary distribution over G. Then the condition number of D with respect to F. is defined as follows:
KD == sup sup [(1) teG fer Il
where
11flB II1l: := J D(0) 1(t)
Definition B.8 (Orthonormal basis for linear function family). Lel G be any domain. Given a linear function family F from G C. and probability distribution D over G. We say (u1,--.. Ud form an orthonormal basis of F with respect to D, if they satisfy the following properties:
for any i.j E [d], D(I)u, (D))))() -i=jj and
* *for any f F. span( U1....,.0 va]. Fact B.9. Let {VI,..., v be an orthonormal basis of F with respect to D. For any function f F, let (ff) denote the coefficients under the basis {uI,.... val, i.e, h = E (hh); U2. Then,
||a(h)]l2 ||A]]
For an unknown function f FF, the goal of importance sampling is estimate [[ D. given samples from another distribution D'. The following definition introduces the importance sampling procedure and condition number of the importance sampling distribution.
Definition B.10 (Definition 3.1 of Chen and Price (2019a)). For any unknown distribution D' over the domain G and any function f F, let (iD' = V function for some known distribution D such that
f(t) D'
D(t)
be the importance sampling
E
(t) (t)
E
D(t) D'(t)
f(0P
E
E [If(t)]]
Then, we can samples from D) to estimate
[If(D')
1|,s which gives an estimate of [|
When the family F and D is clear, we use Kis,D' denote the condition number of importance sampling from D':
(t)) If
( D(t) (D(t) 1 sup ( D'(1) (D())))
sup 1 [ft JEF [I1 }
KGS sup
sup JEF
(5)
From Definition 1. know that the efficiency of importance sampling depends on how many samples we need to estimate I|f Ilrr. The following lemma provide a criteria for judging whether set of samples gives good estimation for the norm of function.
Lemma B.11 (Lemma 4.2 in Chen and Price (2019a)). For any E (0. let S (ti...., t and the weight vector E RS00 Define matrix A Raxd be the s x d matrix defined as Ai.j = / v. (I,(),, where {ui,..., va) is an orthonormal basis for F. Then
||A||
=1=6 =5]==]]110 11Al1B Σ my (o(())())))
for every h E F
#=1
if and only if the eigenvalues of A" A are in 6, 1,,, 1
The following lemma shows that the sample complexity depends on the condition number Kis Lemma B.12 (Lemma 6.6 in Chen and Price (2019a))- Let D' be arbitrary distribution over G and let Kis be the condition number of importance sampling from D' (defined by Eq. (5)). There exists an absolute constant C such that for any E (0, 1) and E (0,1), let S = {lI,...,4. be set i.i.d samples from the distribution D' and w be the weight vector defined by wy TDD)
D(t,)
for each E [ss. Then, as long as
C
d Kis o log 8¹
the 8 X matrix Aij Vwz- (1(4:) satisfies
| Ill2 < with probability at least 1 8.
23

---

C Energy Bounds for Band-limited Signals
The energy bound shows that the maximum value of band-limited signal in certain interval can be bounded by its energy on the interval. One interesting fact is that the approximation ratio in the energy bound is only relate to the sparsity k, and have relationship with time duration T and band-limit F. An application of energy bound is preserving the norm, that is what is the least size of set S, such that [| || for any function f in certain function family. The relationship between energy bound and norm preserving can be build by Chernoff bound.
Borwein and Erdélyi (2006); Kós (2008); Chen et al. (2016); Chen and Price (2019b) proved energy bounds for sparse Fourier signal under one-dimensional continuous Fourier transform. We further generalize these results to discrete band-limite signal under discrete Fourier transform and high- dimensional band-limited signal under continuous Fourier transform.
This section is organized as follows:
Section C.I reviews previous results for one-dimensional continuous Fourier- Fourier-sparse sparse signals. Section C.2 builds the connection between energy bound and the concentration property.
C.1 Energy bound for one-dimensional signals
In this section, we review the energy bound proved in prior work Borwein and Erdélyi (2006); Kós (2008); Chen al. (2016); Chen and Price (2019b).
Kós (2008) proved the following energy bound:
Theorem C.1 (Kós (2008); Chen et al. (2016)). Define family of F-band--iiia k-sparse Fourier signals:
k Σ Ø=1
F
xr1()
Bj
2
1s [
Then, for any & E (-1,1),
lx()) -
S k2
sup -
Borwein and Erdélyi (2006) also proved time-dependent energy bound for one-dimensional signal: Theorem C.2 (Borwein and Erdélyi (2006); Chen and Price (2019a)). Define a family of F--band-limt k-sparse Fourier signals:
k Σ J=1
F
x((1)
Bj
2
fj [
Then, for any t (-1,1),
|x=tt 2
k
sup zEF
|
1
|t]
C.2
Energy bounds imply concentrations
By using Chernoff bound, we prove the following lemma to show the performance of uniformly sampling.
C.2.1 Continuous case
Lemma C.3. Let E Ey.. Let be a parameter. Given any function xxt) : Rd - with
max |x(t)]2 Rl] Let S denote set of points chosen uniformly random from [0, 27d.
<E <E
We have that
Pr
(x41) -((1))-12((0011 2 e110(1112
s exp(-Q(6\\S(/1R).
24

---

where |x(t)]] = Tta fo.rjJ dt..
Proof. Let M denote max [a(1) Replacing X; by |x(() ke|0,1]
and n by [S] Lemma A.I, we obtain
that
8²
Pr[|X- a EnI S 2exp
3 3
The above equation implies
(x(4)
- 1s| ||x(1)] M
=|S] =|5||121/ 1zx(t))
< 2 expl - 8²
Pr
(4)
M
M
FES
Multiplying M on the both sides
1 S
s 22exp(-0 E2
[x11)12 - (
2 2
-111
IE
Applying bound on j
c² (ttt,)] | 2 2
|=((1)
Pr
S
[S]
3
M
iES
which is less than 2 cxxp(-3 1app(-51111 1S/RR), thus completes the proof.
D Uniform Sketching Band-Limited Signals
In this section, we show an intermediate step in the reduction from Frequency estimation to Signal estimation: constructing a small sketching subset S of the time domain obliviously (without making any query to the signal), so that the signal discretized by S has norm close to the original continuous signal. More formally, we define the uniform sketching Fourier signal problem as follows:
Problem D.1 (Uniform sketching band-limited signal problem). Suppose f1, J2, S& E Rd,, and
01,---33 Ug C. Define the continuous signal at(t)= Σ}=1 2) Let n minizs [I filloe-
Let E (0, 0.1) denote the accuracy parameter. Find a set S = (.1,...,4)) S [0, 77 of size 8 such that
(1 (1-=)]l=llT- S |ælls & (1 +1++))l +|]1lT,
where
1
|
[x(()) and |
(x(11)
T 10.37
S SE(s]
In Section D.I, show how sketch one miedemmnsional signals with nearly-optimal weighted sketching.
D.1 Weighted uniform sketching one-dimensional signals
For one-dimensional signals, the most natural approach to uniform sketching is to uniformly sample some points in the time domain. However, by a standard concentration argument, we know that the sample complexity is (k)y(k), which is not time-elficient for our task. In this section, more efficient sketching method for one-dimensional band-limited signals by assigning different weights each sample point. More precisely, let S (f1.....tt tx} S [0, T be discrete sketching set and let w E R be the weight vector. We define the weighted sketching norm of the signal as follows:
show
||0|||.w =
Σ my 1x((),))2 sE(3)
25

---

And the goal of weighted uniform sketching is to find a small set S and weight vector to such that | R ||
In the following lemma, we give a sketch for any one-dimensional band-limited signal with nearly- optimal size:
Lemma D.2 (Nearly-optimal weighted sketch for one-dimensional signals). For lo E N+, define probability distribution D(t) as follows:
for [d] S T(1 1//h c/(1 It/TI), D(t) (e. k.
(6)
for [ E [T(1 1/k:); T]
where c 0(T -oonr-loog-- log (k)) is normalization factot such that 1" D(tddt= =
For any fi,..., Sh E F-F,F] and U1,-. Uk E C, let the continuous signal x(t) = ΣS=1 b/ exp(2rifzt). For any p (0, let SD = [tt....,ttt) ,t&) be set of i.i.d. samples from D(t) of size s 2 ((g=2klo((k) log(1/p)). Let the weight vector w E R be defined by w4 = (Ts(((() for (s). Then with probability at least 1 P. we have
(1 (1-=) =)]]||=/| I | w I (1 =)|12|12.
where ||0| + E dt
Proof. For the convenient, in the proof, we use time duration [-T, T.. Let be defined as:
F = s(1) Σ by 2
ERN
==1
Let (t), (t) be orthonormal basis for F with respect to the distribution D, i.e.,
[' D(t) e (t)j(tt) 1;jj, Vi,j E [k).
We first prove that the distribution D is well-defined. By the condition that f", D(t)dt = 1, we have
T(1 (8)))
dt +2 2 I
2
c.k2kdt = 1,
(1 1(TT))
T(1-1/(K)
which implies that
T(1-1/k)
1
T kd
2
dt +
J
(1-1t/T)
T(1-1/H)
22'llg 2T
( (k)))
Thus, we get that c= -(T log log->()))
To show that sampling from distribution D give a good weighted sketch, we will use some technical tools in Section B.3. Applying Lemma B.12 with D' = D, D = Uniform([- Ti), d = k. 5 = we have that, with probability at least p, the matrix A E C defined by A == /wz uz satisfying
A I1I S,
as long as S Kis log A. Then, by Lemma B. it implies that for every F,
[)>)||=> < | S + ))
It remains to bound the size of Sp: equivalently, need to upper-bound the condition number of the importance sampling (see Definition B.):
Kis supf D(I)
[(())²
sup
}}
D'(t)
JeF I
26

---

sup [x()]
supl
1I }}
(TD(()
FEF
S suup (t)
min! {
1 It/Ti k²}}
(1 (1-tt/T))
k
1
S max
2cTh: k22)
2c.
11/T1
k
2cT O log
where the first step follows from the definition, the second step follows from D(1) (T))) 27,, the third step follows from Theorem C.I and Theorem C.2, and the remaining steps follow from direct calculations. Thus, get that
3
SSpl 2 22 log((( log(1/p)).
The lemma is then proved.
D.2 e-net for sparse band-limited signals
In this section, we construct e-nets for high high-dimensional sparse Fourier continuous and discrete signals.
Lemma D.3 (s-net construction for continuous signals). Given E 24 unknown frequencies f2, f& [- F, FjJ. Let V = (c2nk(44) | [K]] be a family of Fourier basis. Let Q {u E span u / 1} be the set of all signals in [0, T7d with frequency f1,..., fb. where ||>1 Tu So.ry dtt
Then, there exists an s-net Pa Q such that
1. Vu E Q, Be E Pa, I|u wilr- S e.
2. PPal < )
2h
Proof. We first construct an net for the unit disk in C, fa C |2| < 1}. Let P' denote
2k
2k
p'
2% J1 22 j1.52 2, -
|ia| S
Notice that le/(2k)j < =/(2) 2k/E 1: and similarly, |e/ (2k) S Thus, for any C, |a| < 1, there a E p' such that
la - b/ $ e/(2k + e/(2k) & e/k.
Moreover,
IP' S (2- (2) + 1) ( +1
Hence, we conclude that,
P' is n-tet in the unit circle of C.
p' has size at most &4 + 1)
Then, we use P' construct an e-net for Q. Since the dimension of at most k. we take an orthonormal basis ",,".. Wy E Q such that,
Sarp we((),, 1=
27

---

And we define
p"
a; Vi [k), P
First, for any 2, we have
Σ expp((2r (})
Σ a/wi,
i=1
which implies that lay| I 1 for all i E [b.. So, for any E Q. there is b E p" such that ||a - bllz S k- E/k E. Moreover, [P"| I ((4 + 1)3 s (5 Therefore, we conclude that p is an e-net for Q and |P'| < (5 2k
Then define
Pa== {u E Q Vu E P" argmin,eeg [||r--
therefore we have that, for any a E 2, there is a b E p" such that ||a - bllT S e, because there c Pa. such that ||c -blir minde elld b|ß I lla bl| S E. Then, ||c
allr <
||c
blr + |b allr S 2E.
E Fast Implementation of Well-Balanced Sampling Procedure
Well-balanced sampling procedure was first defined in Chen and Price (2019a) to study the active linear regression problem. Our signal estimation algorithm will call as a sub-procedure. In this section, we give fast implementation of well-balanced sampling procedure based on the Randomized BSS algorithm Batson et al. (2012); Lee and Sun (2015).
First, we restate the definition of well-balanced sampling procedure in Chen and Price (2019a).
Definition E.1 (Well-balanced sampling procedure (WBSP), Chen and Price (2019a)). Given a linear family F and underlying distribution D, let P be random sampling procedure that terminates in m iterations (m
necessarily fixed) and provides a coefficient as and a distribution D; to sample I; D; in every iteration i E [m].
We say P is an E-WBSP if it satisfies the following two properties:
1. With probability 0.9, for weight w, =a;
D(z.) D.(a.) of each i [mm]
wy [M(x))) E 10--,0 1 10V5 1N1B th
2. The coefficients always have Em 04 and a; Kis.D, S for all [m].
This definition describes a general sampling procedure that uses few samples represent the whole continuous signal, and the sampling procedure should satisfy two properties: one guarantees that the norm of any function in a function family is preserved, and another guarantees that the norm of noise is also preserved.
In Section E. review some results in Chen and Price (2019a) and show that WBSP can be implemented via randomized spectral sparsification. In Section E.2, we design data structure and improve the time efficiency of the WBSP. In Section E.3, discover tradeoff between the preprocessing cost and the query cost, which can improve the space complexity.
E.1 Randomized BSS implies WBSP
In this section, we review the result of Chen and Price (2019a), which shows that the Randomized BSS algorithm Batson al. (2012); Lee and Sun (2015) implies a well-balanced sampling procedure. Lemma E.2 (Lemma 5.1 in Chen and Price (2019a)). Ler G be any domain. Given any dimension linear function family F of function f G C,
F (f(t) Σ Uy (1)e, E cJ.
28

---

where uj G + C. Given any distribution D over G. and any O, there exists an efficient
procedure (Algorithm 2) that runs in Og G| + -e" --1d==1) time and outpus a set C G and weight w such that
| O(d/s), E RIS),
the procedure is an &-WBSP,
holds with probability 1-
200
Algorithm A well-balanced sampling procedure based on Randomized BSS (see Chen and Price (2019a))
1: procedure RANDBSS(d, FF e)
2: Find an orthonormal basis U1,..., Ug of F under D 4d/7
3:
Set <- fe/3 and mid &- 17(1-7)-1/(+7)
4:
0. Bg t- 0
5:
to t -dd7/ 4g +- 2
6:
while uj+1 - 11+1 < 8d/7 do
7:
$ < ir[(uy] 1 - B,) tr((Br 1,1))
P The potential function at iteration j.
8:
Set the coefficient aj + mid
9:
Set v(x) + (x)....... u(()))
for x E supp D) do
11:
Set the distribution
(o(o) BB) (B)-BBB)-(() (((())+((3)) + (1,1)~((()) 10;
12:
end for
Sample 2; ~ Dj and set a scale 8j + 7. D(zs)
13:
0; D3(1s)
Bj+1 + B, 83 ((z))o(Zz))
15:
Uj+1 + új + 2,(1-))' l5+1 t 11 + $, (1+++) jtj+1
16:
17:
end while
18:
j
19:
Assign the weight wj t 83/ /md for each return {I Am,, ),
20:
21:
end procedure
E.2
Fast implementation of WBSP
In this section, we give fast implementation of Algorithm 2: Theorem E.3 (Fast implementation of WBSP), Let G be any domain. Given any dimension d linear function family F of function f C.
F -=(((t) Σ (t))())) EC,, j=1
where Uj C. Given any distribution D over G. and any E > O, there exists an efficient procedure (Algorithm 3) that runs in G] log [G] + time and outputs a set C G and weight w (RS such that the following properties hold with probability at least 0.995:
S Odd/s)
* the procedure is an 8- &BBSPP
Our algorithm is based on data structure for solving the online quadratic-form sampling problem defined as follows:
29

---

Algorithm 3 Our fast implementation of well-balanced sampling procedure
1: procedure (,
b Theorem E.3
2: /*Preprocessing*/
3: Find an orthonormal basis U...... dd of F under D
4:
f VE/3 and mid f- 1/(1-9)-1/4+7)
1d/7
5:
< 0, Bo 0
6:
lo t -2d/7, uo + 2d/7
7:
ò l/poly(d)
8:
Let v(x) (vI(x),.... vd(x)) R DS. DS. d, (u(x1), (((p)))) R (D(x))......). D(E)))) c R) Algorithm
9:
10:
#Iterative step*/
while uj+1 fi+1 <
8d/7 do
3 - tr[[ugl
1111)
The potential function at iteration
13:
0j 4
14:
E, + ( (B 1111
q DS. QUERYEEYY 13)
DS.
g [I] Algorithm
16:
Xj + mig and set a scale 8j o(K,) E,0(s)
17:
Bj+1 + Bj + +o ((x))
18:
Uj+1 & Uj ",1(-73 11+1 x- 1 ,,(ीا
j jtj+1
20:
end while
21:
m j
22:
Assign the weight w +- 5 /mi for each xy
23:
return {x1. X2, xm )m
24:
end procedure
Problem E.4 (Online Quadratic-Fomn Sampling Problem). Given n vectors Viy...y Un Rdd and ,0 for any PSD matrix A E IRdxd output a sample E [ni] from the following distribution DA:
coefficients o
04 u Av; ΣØ=1 03 2/ Au
Pr[ DA
Vie E [n].
Theorem E.5. There is a data structure (Algorithm 4) that uses (ndd²) spaces for the Online Quadratic-Form Sampling Problem with the following procedures:
INIT(n, d, (Vi...., Jn) C Rd, fai......................... C R): the data structure preprocesses in time (ndd.).
QUERY((A Raxd); Given a PSD matrix A, the QUERY operation samples E [n] exactly from the probability distribution DA defined in Problem E.4 in O log n--time.
Proof. The pseudo-code of the algorithm given as Algorithm 4. The idea build a binary tree such that each node has an interval in ,,,...,7 .r] C [l.... n.] and stores a matrix Σ 04 U.u. For each internal node with interval [/...., r), its left child node has interval ....., [[1 + r)/2 and its right child node has interval [1
+ 1,...,
We first prove the correctness. Suppose the output of QUERY is í E [n]. We compute its probability. Let vo = root, u1,..., ue be the path from the root of the tree to the leaf with id = i. Then, we have
II Eie, ak 2 Auk
O9 m. Av Σ
Pr[ue] II Pr(uz|uz-1l 1=1
j=1 Ek an of Av
0g U2 Au
where ......, ry] is the range of the node uy, the first step follows from the conditional probability, the second step follows from Line 34 in Algorithm 4, and the last step follows from the telescoping products. Hence, we get that
Pr|QUERY = PP Vi E [n].
DA
30

---

Hence, the sampling distribution is the same as the Online Quadratic-Fone Form Sampling Problem's 's distribution.
For the running time, in the preprocessing stage, we build the binary tree recursively. It is easy to that the number of nodes in the tree is (n) and the depth is Ologg n). For leaf node, take O(im)-time to compute the matrix O;; U E Rdxd, For an internal node, we take ) to add up the matrices of its left and right children. Thus, the total preprocessing time is Ondd).
In the query stage, we walk along path from the root to a leaf, which has Ollog n) steps. In each step, we compute the inner product between and the current node's matrix, which takes (ad )time. And we compute the inner product between A and its left child node's matrix, which also takes -ttme. Then, we toss coin and decide which subtree move. Hence, each query takes (dd log -t)ttmme.
The theorem then proved.
Lemma E.6 (Running time of Procedure RANDBSS+ in Algorithm 3), Algorithm 3 runs in
((D)de)-tiiee for preprocessing.
(d log( + )time per iteration, and
dd iterations.
Thus, the total running time is,
DiD + lolog log |D| + )))).
Proof. In each call of the Procedure RANDBSS+ in Algorithm 3,
Finding orthonormal basis takes O()))d)).
In the line 9, it runs O(DDdd) times.
The while loop repeat O( times.
Line 14 is computing
Caxdd (u,l-B,)) This part takes Odd)) time
- Note that line 15 of Procedure RANDBSS in Algorithm 3 runs (dd log DI) times.
So, the time complexity of Procedure RANDBSS+ in Algorithm 3 is
OiDD + + d (d² log D + d))).
Lemma E.7 (Correctness of Procedure RANDBSS+ Algorithm 3). Given any dimension d linear space any distribution D over the domain of F. and any 0, RANDBSS+(d,F, is an e-WBSP that terminates in (d/e) rounds with probability 1 - 1/200.
Proof. We first claim that, for each j E [m], Xj has the same distribution as Dy. where
Dy(x) D(x) (v(x) E,o(x))/O, Vo E
Notice that sampling from distribution Dj can be reformulated as an Online Quadratic-Form Sampling Problem: the vectors are {u(x))=eD) the coefficients are (D(x))ee) and the query matrix is FYJ : F /. Then, we have Dj = 'Ey defined Problem E.4. Hence, by Theorem E.5, we can use the data structure (Algorithm 4) to efficiently sample from Dj-
Therefore, the sample x, in each iteration is generated from the same distribution the original randomized BSS algorithm (Algorithm 2). Then, the WBSP guarantee and the number of iterations immediately follow from the proof of (Chen and Price, 2019a, Lemma 5.1).
The proof of the lemma is then completed.
'Note that this step seems to be very difficult to speed up via the Sherman-Morrison formula since uy changes in each iteration and the update of high rank.
31

---

Algorithm 4 Quadratic-form sampling data structure
1: structure Node
2: V Raxd
3: left, right
b Point to the left/right child in the tree
4: end structure
5: data structure DS
6: members
7: n E N
The number of vectors b d-dimensional vectors > Coefficients The root of the tree
8: 01....::
Un IRd
9: a1...... E IR
10: root: Node
11: end members
procedure BUILDTREE(1,)
...... the range of the current node
13:
- new Node
14: if = r then
Leaf node J-time
15:
P.V t aq 101)
It takes )-ime-time Internal node
16:
else
17:
mid (1++
18:
llleft + BUILDTRREE mid)
19:
p.right BUILDDREEEmid 1,r)
20: P.V < (p.left). + (p.right).V
It takes )-ime
21: end if
22: return P
23: end procedure
24: procedure INIT(n, d, { hejnj C RRd Kashiem R
25: Us f Ui a; < 0; for i E [n]
26: root < BUILDDDREEELL...
27: end procedure
28: procedure QUERY(A Rdxd)
29: - root, 1 < 1, r
0 31: while + do
> There are O n) iterations It takes ( ttmme
w (p.V,A) + ((p.left).V.A
33:
Sample from Bernouli(w:z/w)
35:
if c = 0 then
p plleft, + [(1+r//2
37:
else
38:
- prrghht, r)2+r +
39: end if
40:
end while
41: return /
42:
end procedure
43:
end data structure
Proof of Theorem E.3. The running time of the algorithm follows from Lemma E.6, and the correct- ness follows from Lemma E.7.
E.3 Trade-off between preprocessing and query
In this section, we consider the preprocessing and query trade-off in the data structure for quadratic form sampling problem. In the following theorem, we give a new data structure that takes less time preprocessing and more time for each query than Theorem E.5, and the space complexity is also reduced from (nd?) to O(nd).
Theorem E.8. There a data structure (Algorithms 5 and 6) that uses ( spaces for the Online Quadratic-Fone Form Sampling Problem with the following procedures:
32

---

InIT(n, d. fui...., en, Pn C R foi..... and C R): the data structure preprocesses in time (nd )
QUERY((A E Rdxd); Given a PSD matrix A, the QUERY operation samples E [nd] exactly from the probability distribution D defined in Problem E.4 in O (og(n/d) d )-fime.
Proof. The time and space complexities follow from Lemma E.9, And the correctness follows from Lemma E.
Algorithm 5 Quadratic-form sampling with preprocessing- query trade-off: Preprocessing
1: structure Node
2: V1, V22 E Raxd
3: left, right
> Point to the left/right child in the tree
4: end structure
5: data structure DS+
D Theorem E.8
6: members
7: n E N
The number of vectors The number of blocks b d-dimensional vectors The root of the tree
8: m E N
9: 01.-..; Un RRd
root: Node
11: end members
12: procedure BUILDTREE((,
1...... r] is the range of the current node
13:
new Node
14: if = then
b Leaf node
15:
P.V/ PQ--1)441 via
p.Vi t (2) -p.V))
It takes (dd)) )-time
17:
p.matl
Ei (1=11))++ 0
ld
18:
else
> Internal node
19:
mid+ (1. rr/2)
20:
p.left + BUILDTRREE( mid)
p.right BUILDTREEE 1,r)
22:
P.Ví < (p.left).V/ + (p.right).Vi
It takes (Od )-tim
23: end if
24: return
end procedure
26: procedure INIT(n, d, (rr S RR, (auhiem S IR)
27:
U: + u..vay for E [n]
28:
m mn/d
We assume that is divisible by
29: Group {u Jejn into m blocks BI...., Bn
b B, (1(--))4+1:.... Vid} } for E [m]]
30:
root < BUILDTREE(1,w
31:
end procedure
32:
end data structure
Lemma E.9 (Time and space complexities of Algorithms 5 and 6). The INIT procedure takes 0(nd--1)-tinn -imee. The QUERY procedure takes Odd log(n/d) + )time. The data structure uses O(nd)-space.
Proof. We prove the space and time complexities of the data structure as follows: Space complexity: Let m n/d. is easy see that there are ((m) nodes in the data structure. And each node has two d-by-d matrices. Hence, the total space used by the data structure is O(n/d) ( O(nd).
Time complexity: In the preprocessing stage, the Line-consuming step is the call of BUILDTREE. There are ((m) internal nodes and ((m) leaf nodes. Each internal node takes construct the matrix Vi (Line 22). For each leaf node, it takes (td)) to form the matrix V/2 (Line 15). And it takes O(dd)-time to compute the matrix (Line 16). Hence, the total running time of BUILDTREE is O(md") O(nd~11).
to
33

---

Algorithm 6 Quadratic-form sampling with preprocessing- trade-off: Query
1: data structure DS+
P Theorem E.8
2: members
3: n E I
The number of vectors
4: E
The number of blocks > d-dimensional vectors The root of the tree
5: U1...., Un Rd
6: root: Node
7: end members
8: procedure BLOCKSAMPLINGGD. N A E Rdxdd
b p is leaf node with index I D It takes (dd )
9:
U - (p.1/) A (p.Vk)
10: Define a distribution D, over [d] such that Di(i) x U1
11: Sample i E [d] from Dr
D It takes O
return 1jd +
13:
end procedure
14: procedure QUERY (A E Rdxd)
15:
p p root, 1 5 +-
16:
6-0
0
17:
while + do
There O(log m) iterations > It takes (dd) )
18:
w t (p.V/, A)
We ((p.left..Vi,A) A)
20:
Sample e from Bernoull(wwz/w))
21:
if 0 then
22:
- p.left, + [(1+r//2
else
24: end if
- prightt / + [(1 r)2] +
26:
end while
return BLOCKSAMPLING(O. 1, A)
28:
end procedure
29:
end data structure
In the query stage, the While loop in the QUERY procedure (Line 17) is the same as in Algorithm 4. Since there are (mm) nodes in the tree, it takes Odd log m)-time. Then, the ALOCLNA procedure, it takes (Od") )-time to compute the matrix U (Line 9), and it takes Odd)-time to sample an index from the distribution D, (Line 11). Hence, the total running time for each query is (dd log m + d (dl log(n/d) d²).
The proof of the lemma is then completed.
Lemma 10 (Correctness of Algorithm 6). The distribution of the output of the QUERY (A) is DA defined by Eq. (7).
Proof. For simplicity, we assume that all the coefficients O; 1.
Let ug = root, ....... de be the path in the While loop (Line 17) from the root of the tree to the leaf with index [m]. By the construction of leaf node, we have
(1-1)dd 13d+1
id
Vi = V32, = [Baa-1j411
via]
=
Σ
(=(11)d+
Djd+1
which is the same as the V-matrix in Algorithm 4. Hence, similar to the proof of Theorem E.5, we have
Ed (1 11-1 oa Av
Pr[u.] II Pr[ugluz-1]
Σn 8s Au
where {(1 1)d + 1.... (d) is the range of the node and {l,... n2 is the range of uo-
34

---

Then, consider the BLOCKSAMPLING procedure. Let fui..... e be the vectors in the input block. At Line 9, we have
V1
U 1/2 AV2
=
A 10
val
Vd
For E [d], the i-th element in the diagonal of is
U1 = v. Avs.
Hence,
0. Av
Pr|BLOCKSSMPLIING =
Σラ=1 1/ Av,
Therefore, for any & E [n], if (1 1)d + for some L, N, then the sample probability is
Pr(QUERY(A) k] Pr(BL.OCKSAMPLING = ve = Block Z] Pr(ue = Block 7]
2 Auk
E1 (1-1)441 U/ Av;
(1-1)) U. Au,
Ei= U/ Au,
UK Avk
Ei=1 of Au
(k))).
The lemma is then proved.
As corollary, we get a WBSP using less space:
Corollary E.11 (Space efficient implementation of WBSP). By plugging-in the new data structure (Algorithms 5 and 6) to FASTERRANDSAMPLINE
(Algorithm 3), we get an algorithm taking O(D + 2 (d2 log D --time and using O(ID d)-space.
Proof. In the preprocessing stage of FASTERRANDS Gram-Schmidt process and D-D))==I)-time for initializing the data structure (Algorithm 5).
we take O(DDdd)-tt )-mmme for
The number of iterations 7 2d. each iteration, the matrix E, can be computed O(d')-tima And querying the data structure takes ( log(ID) /d) + d )-tmme
Hence, the total running time is
O + (D|d--1 (DD]=+IDDd'>1 +7
dd log ( +*) (ID + - + + 22d2 log DD)
For the space complexity, the data structure uses dd)s/ccc....e. The algorithm uses (dd)) extra
space in preprocessing and each iteration. Hence, the total space complexity is O(D)d).
F Sketch Distillation for Fourier Sparse Signals
In Section D. we show an oblivious approach for sketching Fourier sparse signals. However, there two issues of using this sketching method in Signal estimation: 1. The sketch size too large. 2. The noise in the observed signal could have much larger energy on the sketching set than its average energy. To resolve these two issues, in this section, we propose method called sketch distillation to post-process the sketch obtained in Section D that can reduce the sketch size to O(k) and prevent the energy of noise being amplified too much. However, signal x= (t): we assume that the frequencies of the noiseless signal xxt) are known. But the sketch distillation process still be done partially oblivious, i.e., do need access/sample the signal.
need some extra information about the
In Section F.I, we show our distillation algorithms for one-dimensional signals.
35

---

F1 Sketch distillation for one-dimensional signals
In this section, we show how to distill the sketch produced by Lemma D.2 from O log (loog))ssizee -ize to O(k) using an weell-balanced sampling procedure developed in Section E.
Lemma F.1 (Fast distillation for one mee-imensional signal), Given fi, f2..... ffk E R. Let x² (t) Σj=1 " exp(2xifz(). Let = minszj [fz -fl-- For any accuracy parameter & E (0, (0,0.1), there an algorithm FASTDISTILL (Algorithm that runs in Og--2 --ime and oulputs a S C [-T.T]] of size ( and a weight vector w R8zo such that,
(1 -1- (t)lz s (t)lss,, S =1)=))=="(t)l
holds with probability 0.99.
Furthermore, for any noise signal g(t), the following holds with high probability:
|19 w Z 11917
where |
2T 1_ dl
Proof. For the convenient, in the proof, we use time duration [-T,T]. Let Dtt) be defined as follows:
1/(1111/T) (t/T))
for It| S T(1 1/k)
D(1) (c-
c. k.
for |t| [T(1 T/
where c = O0T-1(11lg log--log---- (A:)) fixed value such that __, D(t)dt=
First, randomly pick up set So ftr..... tea) of so O 2k log(k) log(1/Po)) i..d. samples from (t). and let w/ := 2/(Tso for E [so] be the weight vector, where Eo, Po are parameters to be chosen later.
By Lemma D.2, we know that (So, w/) gives good weighted sketch of the signal that can preserve the norm with high probability. More specifically, with probability 1 Po:
- [0)]o)](= =x))))=="(t)1E < (t)l()) S (1 =o)]l=>(()11
(8)
Then, we will select 8 = (kk/s?) elements from So and output the corresponding weights wi, w2,--. W. by applying RANDBSS with the following parameter: replacing by k, by ef, and D by D(4)) = / Ejetsol w/J for i E [so]-
By Theorem E.3 and the property of WBSP (Definition E.1), we obtain that with probability 0.995,
(1 E (1)l S (1 (1 (1II,,,
Combining with Eq. (8), we conclude that
||>
3 N, E [1 E1. + =1] |
E [(1 =0 - -1). (1 (1 + ei)] |x*1|
E [1 - e, + +]] -|
where the second step follows from Eq. (8) and the last stpe follows by taking Eo = E1 = s/4
The overall success probability follows by taking union bound over the two steps and taking = 0.001. The running time of Algorithm follows from Claim F.2. And the furthermore part follows from Claim F.3.
The proof of the lemma is then completed.
Claim F22 (Running time of Procedure FASTDISTILLLID in Algorithm 7). Procedure FASTDIS- TILLID in Algorithm runs in
0( 0 2
time.
36

---

Algorithm 7 Fast distillation for one-dimensional signal
1: procedure WEIGITTESSKETCHC:: e, S,T,A.
Lemma D.2
2: C+ c+- O log - '(k))
3:
(t) is defined follows:
[e/((1-11/7)))) log if < T(1 1/k),, if E [T(1 - 1/k),
D(t) - c-
4:
So -0c i.idd samples from D
5:
for 1 E So do
6:
W/ T. D(J
7: end for
8: Set new distribution (1())= +- wi/ EeeeErss wy for & E So
9: return D'
10:
end procedure
11: procedure FASTDISTILLIDGS F (fi.... .ff.....ff........... f,), T)
Lemma F.1
12: Distribution D' < WEIGHTEDSKETCH E, B)
13: Set the function family F as follows:
F: F (10)
Σ oy exp((2iffz) by c.
14: 8, (t1,, t..... tt), +- RANDBSS (k, D', (s/4)²)
DS= O(k/E)), Algorithm
15: return {t1, b2, .. tts and w
16: end procedure
Proof. First, is easy to see that Procedure WEIGHTEDSKETCH takes ( log())))
By Theorem E.3 with |D| O( -k log(k)), d k, we have that the running time of Procedure RANDBSS+ is
O (k2 . - 2k = 222logg log (e 1c-2k log((()) + 2(++1)
= 0s
Hence, the total running time of Algorithm is O (5 (k=2).
Claim F3 (Preserve the energy noise). Let (S,w) the outputs of Algorithm Then, we have that
(1(()) S l19(t))
holds with probability 0.99.
Proof. For the convenient, in the proof, we use time duration [-T, Algorithm 7 has two stages of sampling.
In the first stage, Procedure WEIGHTEDSKETCH samples a set S, = ft,,... "ig...,,,, th,)) of i.i.d. samples from distribution D, and weight vector w'. Then, we have
E [1((0) s. = E
E
(1)))
50
E
Tso D(L) (((4))
2
37

---

90
E
1.0 (9(t))
t U
E Uniform([[TTT])
[l9(1)1
llg(())
where the first step follows from the definition of the norm, the third step follows from the definition of we the forth step follows from (y) (o [()) Di()) (t))-
(1(0)
In the second stage, let P denote the Procedure RANDBSS+ With high probability, P is WBBP (Definition E. By the Definition E.I, each sample t, ~ Di(t) and w, = a4 D2(
D'(t.) in every iteration
i [s], where Ei= a4 5/4 and D'(t)= Eres, "y." As result,
w/
wy (())(()))
[no s(:))11)
NitDi(tt)
a, ('(ts)
E Di(tttt))
D.((.) [
E
[(rl)(()))
4/ (',))(t)) (t,)
< sup P
E ())
[1((
sup
as Hla
wp)--1
< (11
where the first step follows from the definition the norm, the third step follows from wy D'(t.) the forth step follows from E,-Da(t) Date) f(t) E,-Di(t) f(t). the sixth step follows wf w, and the definition of the norm, the last step follows from Σi= Os S 5/4
D.(0)
a; D.(G.'' from D'(t) = Eecso
and (Eres,
with probability at least 1 p/2.
Hence, combining the two stages together, we have
E [Ell)(()),.. pp- E [II(()) = -lall.
And by Markov inequality and union bound, we have
Pr [ll(()) S p----1lo (11(() < p-
F.1.1 Sharper bound for the energy of orthogonal part of noise
In this section, we give a sharper analysis for the energy of g+ on the sketch, which is the orthogonal projection of g to the space F. More specifically, we can decompose an arbitrary function into gl + where gil E FF and Jo.ry h(t)g (f)dt = 0 for all e F. The motivation of considering 9* is that g is also Fourier sparse signal and its energy will not be amplified in the Signal Estimation problem. And the nontrivial part is to avoid the blowup of the energy of g-, which is shown in the following lemma:
Lemma E.4 (Preserving the orthogonal energy). Let F. be an m-dimensional linear function family with an orthonormal basis {U1,..., vm with respect distribution D. Let P. be the e- c-BSSP that
38

---

generate sample set S (ti.....tt} and coefficients E Bizo- where each tę is sampled from
distribution D. i [s). Define the weight vector w E R be such that w; == as D.(t.) for E [s].
D(t,)
For any noise function g(t) that is orthogonal to F with respect to D, following property holds with probability 0.99:
V0, S EellllB
where (g. u)S,w= == Ei=
==E;= Wyb(tt)o(t))
Remark F.5. We note that this lemma works for both continuous and discrete signals.
Remark F.6. Kg,v2) s.ul² corresponds to the energy of g on the sketch points in S. On the other hand, if we consider the energy the whole time domain, we have (g, vz) = 0 for all E [m]. The above lemma indicates that this part of energy could be amplified by at most O as long as the sketch comes from WBSP.
Proof. We can upper-bound the expectation of Em= Kg Uz) 1 as follows:
E
Kg. v S.w 22)
E Di....
|
E (t)(t)
D2
Wy U; (t,)))
Dio.,, D.
j=1
wy (1))((1))
f=1
wylm,(t)) wy [(t,))
((P))) E. (1))))(())
sup
where the first step follows from Fact F.7, the second step follows from the definition of D', the third follows from the lincarity of expectation, the forth step follows from Fact E88, the last step follows by pulling out the maximum value of wj Em= [t)(1) from the expectation. Next, we consider the first term:
D(t) sup { { (t( i=1
2y (t)))] rED,
Σ (tt(t))
sup rED,
1=1
D(t) sup
lh(t) 12
{
=0 sup IED; (t)(t)
hEF
= a Kis,D,
where the first step follows from the definition of wy, the second step follows from Fact F.9 that sup 12(e,) her
TA ] = (x,())),, the last step follows from the definition of Kis.D, (Eq. (5)).
Then, we bound the last term:
D(1)
[(ws)o(t))1]
E tynDD
0ij
Dy(t,) [((p))]]
= a, E , ())_))(((())) [lo(t))))) = as1le113.
39

---

Combining the two terms together, we have
m
Kg Us) 8,ml 12 S
la D, a,l191B))
(is,,, -1911B
jE
j=1
where the last step follows from P being a EBBSP (Definition E.1), which implies that Σ₁ aj and ay D, S 5/2
for all j E [s].
Finally, by Markov's inequality, we have that
m
Σ
Kg s, 12 P E||g|l
holds with probability 0.99. Fact F.7.
Σ w. = -1 > E (((()g(t))(
wa
where D' is a distribution defined by D'(t:) =
Tw| for i E [s].
wi
Proof. We have:
m
m
Kg S,00
3,
w uor (t,(tt)((tt)
1=1
==1
W w ((toe(t)g((tt)
Σ wyy)
2
Σø= Wyy
j=l
f'=1
Wyy
E
0 (t)(g(()))
3 3'=1
Fact F88. For any i E [m], we have
m Σ j=1
E
E
Di....
D Dr...,,, D.
Proof. We first show that for any E [m] and j E [s].
[aj D(t,)
E [1c,v((())9((4)]] = D, D, (t,)
vi (((5))(1)))
GrDD
=aj E [c:(1)99(15) 4~
0.
(9)
where the first step follows from the definition of w,, the third step follows from g(t) is orthonormal with (t) for any E [k)-
Then, we can expand LHS as follows:
E
((,t(t)))(t))1
Dr....D.
40

---

E
D,
E
Di
D
=d'=1
Σ (lugla((t)Pllltt))))
2 (wseeyyl Dimn,
RHS +
2
E
wyre(ty)g(tt)
(yye:(ty)g(ty,))
Di
RHS
Σ i<j<j'S
2 Dimn.D
(wsvi(t))g((t,) 0]
RHS,
where the third step follows from the linearity of expectation, the fifth step follows from ty only depends on t t...,,,t-11 and the sixth step follows from Eq. (9).
Fact F.9. Let (UI...., v be an orthonormal basis of F with respect to the distribution D. Then, we have
|A(t)
Σ (tt(t)
sup KEF
|1A113
Proof. Then,
|
Σ 1= (11:
sup k
sup aeC*
|
|| 22
h (1);(()
sup aec*:|lal|a
(2:(1))?
where the first step follows from each h E can be expanded as h Et= a and [/((t) |a (Fact B.9), the second step follows from the Cauchy-Schwarrd Schwartz inequality and taking a [[(())]ll
v(t)
G One-dimensional Signal Estimation
In this section, apply the tools developed in previous sections show two efficient reductions from Frequency Estimation to Signal Estimation for one-dimensional semi-continuous Fourier signals. The first reduction in Section G.I is optimal in sample complexity, which takes linear number of samples from the signal but only achieves constant accuracy. The section reduction in Section G.2 takes nearly-lineal number of samples but can achieve very high-accuracy (i.e., (1 + e)-esimmation error).
G.1 Sample-optimal reduction
The main theorem of this section is Theorem G.1. The optimal sample complexity is achieved via the sketch distillation in Lemma F.1.
Theorem G.1 (Sample-optimal algorithm for one-dimensional Signal Estimation). For n E R. let A(B) E denote the lattice A(B) {cn c E Z}. Suppose that ft, -......ff. A(B).
41

---

Let (t) = Ej= exp(2xif,t), and let g(t) denote the noise. Given observations of the form
a(t) = xx g(), [0,
Let mingz If, - fil.
Given D, Rt. Suppose that there an algorithm FREQEST that
takes Sirea samples,
runs in Trreq- -time, and
outputs a set L of frequencies such that with probability 0.99, the following condition holds:
D
Vi [b], 3f. E S.t. Ifs fil - T
Then, there is algorithm (Algorithm 8) such that
takes O + Sirea) samples
runs OK + Threa) time,
outputs y(t) Σz= t/y exp(2miff)) with T O(I4((1 D/(TT))) such that with probability at least 0.9, have
llv(t) =(t)| S l[)(t)
Algorithm 8 Signal estimation algorithm for one-dimensional signals (sample optimal version)
I: procedure SIGNALESTIMATTIOFASTTG, k
Theorem G.
2:
f 0.01
3:
L K,,
4:
3 EL - -|< FASTDISTILLI 8, (2,,,t2." ... E (fihee)))) T,
(fi.5,,.. , (
5:
> k w.weR. R
Algorithm 7
Ar, t exp(2rifftt), Ae Caxk
6:
7:
b+ ((((1),(((2), ((()))
8:
Solving the following weighted linear regression
Fact A.4
o' f- arg min/m V ww (Av' - b)ll2. e'Eci
9: return y(t) Eド uf exp((2ifft).
end procedure
Proof.
First, recover the frequencies by utilizing the algorithm FREQEST. Let L be the set of frequencies output by the algorithm FREQEST((r, k, D,T,F,F)
We define L as follows:
L: b: (T= A(B) 3f L, 18' -1 D
We le denote the size of set L. And we use J. Fz, ... F denote the frequencies in the set T. It is easy to see that
< (1 D/(Tn)).
Next, we focus on recovering magnitude o' E C First we run Procedure FASTDISTILLID in
Algorithm 7 and obtain a set S (ti,te, tt) [0, of size O(k) and weight vector
42

---

E IR50- Then, we sample the signal at f1.....f, ts and let a(t1)...... xtt,) be the samples. Consider
the following weighted linear regression problem:
min E'ECk
II o (Av' - b)]l2.
(10)
where vio== == (ywi:-... .... ww,), and the coefficients matrix A Cexi and the target vector b C are defined as follows:
(exp(2rifitt) exp(2xif2(1) exp(2rifi(2)
exp(2nifz11) exp(2Tifzl2)
xx(1) )
exp(2xi/2(2)
xxt2)
A =
and :=
exp((nifitta)
exp(2rif2ts)
exp(2nif(tt))
(x((t))
Then, we output a signal
k (t) Σ o' exp(2nij,t),
where of an optimal solution of Eq. (10).
The running time follows from Lemma G.2. And the estimation error guarantee l| - x(t)ll 2 ([)(())lr follows from Lemma G.3.
The theorem then proved.
Lemma G.2 (Running time Algorithm 8). Algorithm takes (k giving the output of Procedure FREQEST.
Proof. At Line 5, we run Procedure FASTDISTILLID, which takes (ilk-t1)-timm by Lemma F.l.
At Line 8, we solve the weighted linear regression, which takes
-(s O(K))
time by Fact A.4.
Thus, the total running time is O(k*+1).
Lemma G.3 (Estimation error of Algorithm 8). Let y(t) the output signal of Algorithu 8, With high probability, have
llv(t) <tt)lr S llg(t)]lr.
Proof. We have
ll((t - x(t)llr S (lb(() - -00l
< (1 (1+s)llv(() -000()))="(())))))))) (1)lls, l1o(0
< +1+))ll)(t)
+1+ lr(())r
< (1 =))==) + + llg(t))lz
24 2A 25 [1))(1) =()]ls,, 1g((1)r
(1) = l((())
(1g(
(11)
where the first step follows from triangle inequality, the second step follows from Lemma F.I with
0.99 probability, the third step follows from triangle inequality, the forth step follows from v(4) is the optimal solution of the linear system, the fifth step follows from Claim F3,, the sixth step follows from Lemma F.I, and the last step follows from the definition of g(t).
43

---

G.2 High-aceuracy reduction
In this section, we prove Theorem G.4, which achieves (1 + esstimattio error by sharper bound on the energy of noise in Lemma F.4.
Theorem G.4 (High-accuracy algorithm for one-dimensional Signal Estimation). For n E I. ler A(B) C IR denote the lattice A(B) {en | c E 2}. Suppose that f1, ... E A(B). Ler x (1) Σj=1 Dj exp(2rif,t); and let g(t) denote the noise. Given observations of the form fel- fel-
a(t) (t) g(t), [0. T). Let = min 1f,
Given D, 17 E Rt,. Suppose that there is an algorithm FREQEST that
takes Streq samples,
runs in Threq time, and
outputs a set L of frequencies such that, for each fú there exists an S E L with [s: S'l S D/T, holds with probability 0.99.
Then, there is an algorithm (Algorithm 9) such that
log runs 0(= log (k) + T) time,
takes O(e (og({) + S) samples,
outputs 7(1) = Ejn1t v/g exp(2niff)) with To 0(12(( D/((T))) such that with probability at least 0.9, we have
lly(t) x xt) S (1++))1()))
Remark G.5. For simplicity, we state the constant failure probability. is straightforward to get failure probability by blowing up a log(1/ p) factor in both samples and running time.
Proof. Let L be the set of frequencies output by the Frequency Estimation algorithm FREQEST. We have the guarantee that with probability 0.99, for each true frequency ft, there exists f e C with Ifs fll < D/T. Conditioning on this event, we define a L as follows:
İ :: (f A(B) Eaf' L, If'
fl D/T).
Since we assume that {fi...., fa) C A(B), we have iff....,ffll C Σ. We use denote the size of set L, and we denote the frequencies in by
Next, we need to recover magnitude v' Ck
We first rum Procedure WEIGHTEDSKETCH in Algorithm 7 and obtain set S t2, ... .t. C
[) of size 0 log=2) log(k) and a weight vector w IR Then, we sample the signal at f1,..., ty and let xt1),, ..,....... ., (t.)) ) be the samples. Consider the following weighted linear regression
problem:
min VIV (Av' -))l12
(12)
deck
where V = (v::=
WiWi.... W.), and the coefficients matrix C and the target vector b E C
defined as follows:
(exp(2rif(41) exp(2xi/211) exp(2nifit2) exp(2mif2t2)
exp(2mi/z(1)
r((h) )
exp(2mif2t2)
x((2)
A
and b:=
exxp(2mifit.)
exp(2nif2ta)
exp(2mif(t.)
(xx(te)
Note that if of corresponds to the coefficients v, then we have I (Av' - b)]l |l g(S)|22 = lIgll Let v' be the exact solution of the weighted linear regression in Eq. (12), i.e.,
o' == arg min v'ECk VV (Av' - -)]l
44

---

And we define the output signal to be:
v(() = Σ r/ exp(22rffj) j=1
The estimation eтror guarantee (|v(t) x= (t)llx - (1 + +)ll((t)ll follows from Lemma G.7. The running time follows from Lemma G.6. The theorem is then proved.
Algorithm 9 Signal estimation algorithm for one -icedimnsio signals (high-accuracy version)
1:
procedure SIGNALESTIMATIONAAEE
E, F,T,
Theorem G.4
2:
L+ FREQEST k k, F,T,T. B)
3:
ff1:12 f1 t (f A(B) E If D/T
4:
8, (ti, 11, ... ,t,), w + WEIGHTEDSKETCHHA VB, Arj t exp(2mifftt),,
kk, w R Algorithm
Cax
5:
6:
b+ (a(ti), ... ,(()))
7:
Solving the following weighted linear regression
bi Fact A.4
e c arg minl u (Av' - b)ll2. eecc
8: return y(t) = Ej= vr exp(2mifft).
9:
end procedure
Lemma G.6 (Rumning time of Algorithm 9). Algorithm takes O T log(k)))-timg) giving the output of Procedure FREQEST.
Proof. At Line 7, the regression solver takes
0(kk~11) = ((= - log(k) 1--1))= = O log(k))
time. The remaining part of Algorithm 9 takes at most (ss)mimme.
Lemma G.7 (Estimation error of Algorithm 9). Let y(t) be the output signal of Algorithm 9, With high probability, we have
Ilı(t) - x (t)llr s (1 (1+)))a())lr.
Proof. Let F be the family of signals with frequencies in Z:
t F -= h(t) Σ
2
Vaz C,j [
oj
1=1
Suppose the dimension of F is m I kt Let {ur, "2 um) be an orthonormal basis of F, i.e.,
T I (o.T)
(t)t),(t)dtt 1=5s Vi.j E [m],
On the other hand, since u, F, we can also expand these basis vectors in the Fourier basis. Let V e Cm be linear transformation? such that
Vi exp(2mifft) Vi e [m].
U;
When < 1., V is unique, and we take any of such linear transformation.
45

---

Then, we have
(xx((2mffit)
u1
V
exp(2mifftt
Um
where V+ Clxm is the pseudoinverse of V; or equivalently, the i-th row of V+ contains the coefficients of expanding exp(2rif,t) under {uI...., um Define linear operator a - C such that for any h(t) = E5=1 exp(2 2t
a(h) = V -22
which gives the coefficients of h under the basis {ui,-... , ug).
Define an s-by-m matrix B as follows:
uz((1) (1))
Umm (41 Um (12)
un (12) uz((2)
B B==A.VT
Lt (to)
(t,)
Um (t&)
B AV. is easy to see that Tm(B) (B) Im(A). Thus, solving Eq. (12) is equivalent to solving:
min
V (B2 b)ll2-
(13)
=EC
Since y(t) an solution of Eq. (12), we also know that a(y) is an solution of Eq. (13).
For convenience, we define some notations. Let vW dida(s/v /w) and define
B == VW B,
X == vW [x(t)) a(t2) x(ts))
x = VW (ta(t) (t2) =t)))))
By Fact A.4, we know that the solution of the weighted linear regression Eq. (13) has the following closed form:
aly) =
B-bb BB
(14)
Then, consider the noise in the signal. Since is an arbitrary noise, let gll be the projection of g(z) to F and g- g gll be the orthogonal part to F such that
g0( F, and / 10.m1
(1))
Similarly, we also define
Iw VW.[g(t)) g(12) s((a))
9!! v W (1)) (12)) .....g (1a)]
- VW. (t)) (ta) g (ts))
By Claim G.8, the error can be decomposed into two terms:
Ilv(t) x (f)lT = (00ll=s|((BB)) (BB B", oth ll| + BwB Br, 99e
By Claim G.10, we have
BwB Br, s < $ $|| (t)]
And by Claim G.13, we have
(B Bw) BB, oll 1² ||00
46

---

Combining them together (and re-scaling E be an constant factor), we have that
[lv(t) - x² (t)llr < llg lIr + Vellg-1lz.
Since |/ + 1 1 = 11.1l by Schwarz incquality, we have that
(Il + vēllg l1r) (llg + 1 11 (1 + + = + -1917
That is,
l1 - x² (1)1 < (1+ ()
Claim G.8 (Error decomposition).
(1v(t) - x² (1)llr & (By Bw)) Bw) - g0l12 (B Bu) 9 12
Proof. Since v F and fui...., ux is orthonormal basis, have ly x= 1| la(y) ((xx)]]2 Furthermore, by Eq. (14), have aly) (m) B X And by Fact G.9, since x² E, we have a(x*)= = (B Bw)) B X
Thus, we have
||a(y) a(x*))() [I(B" BB)
By (X X
1l(By, "1 -B Iel12
= [1 Bw)) -B (gw + g 112
< Bw) ge +
B" - 12
where the second step follows from the definition of gw. the forth step follows from Iw gll + gt, and the last step follows from triangle inequality.
Hence, we get that [1v(t) x= (t) V [I Bwd) - - I ll + [[ Bw) - B gHlll.
Fact G.9. For any h E F.
a(h) (B, Bw)) B Bayy
where hw = (/[hh
A(G.))
Proof. Suppose h(() = oj exp(2nif,() We have
Bma(h) = /WB a(h)
-WBB (V+v)
where the second step follows from V a change of coordinates.
Hence, by the Moore-Penrose inverse, we have
a(h) By, hw (Be he
Claim G.10 (Bound the first term). The The following holds with high probability:
Bl: 'B,, 9 < =111 (t)l
47

---

Proof. By Lemma D.2, with high probability, we have
(1 (1==)|<=||r> I | I (1+ ()|rl],
where (S, w) is the output of Procedure WEIGHTEDSKETCH. Conditioned on this event, by Lemma B.11,
B( e 1 s|,
since B.d the same as the matrix A in the lemma.
Hence,
Bw) Br gh S Amax (Bar 1 -
51 - 5) 3 Iw
Eellg (1)1
where the second step follows from Amax Bw) S -)--))_+ and the third step follows from Lemma F.4 and Corollary G.12.
Lemma G.11 (Lemma 6.2 of Chen and Price (2019a)). There exists a universal constant C1 such that given any distribution D' with the same support of D and any >> 0, the random sampling procedure with m = C1 py log d + k>' i..d random samples from D' and coefficients 01 Ol 1/m is e-well-balanced sampling procedure.
Corollary G.12. Procedure WRIGHTEDSKETCH in Algorithm 7 is &- WBSP (Definition E.
Claim G.13 (Bound the second term).
(B Br Ile 1| 1101
Proof.
[BB B" glu (ا =و1 12
where the first step follows from Fact G.9 and g"l E F, the second step follows from the definition of a.
48

---

H High-Accuracy Fourier Interpolation Algorithm
In this section, we propose an algorithm for one-dimensional continuous Fourier interpolation problem, which significantly improves the accuracy of the algorithm in Chen al. (2016).
This section is organized as follows. In Sections H. and H.2, we provide some technical tools for Fourier-sparse signals, low-degree polynomials and filter functions. In Section H.3, we design high sensitivity frequency estimation method using these tools. In Section H.4, we combine the frequency estimation with our Fourier set query framework, and give (9 + { Fourier interpolation algorithm. Then, in Section H.5, we build a sharper error control, and Section H.6, we analysis the HASHTOBINS procedure. Based these result, in Section H.8, develop the ultra-high sensitivity frequency estimation method. In Section H.10, we show the a (3 v2 -aaaproxiiatee Fourier interpolation algorithm.
H.1 Technical tools I: Fourier-polynomiall equivalence
this section, we show that low-degree polynomials and Fourier-sparse signals can transformed to each other with arbitrarily small errors.
The following lemma upper-bounds the error of using low-degree polynomial to approximate Fourier- sparse signal.
Lemma H.1 (Fourier signal to polynomial, Chen et al. (2016)). For any A > 0 and any ō > 0, let x (t) Eje( tye 2mifft where [fyl S for each j [k]] There exists a polynomial P(t) of degree
at most
d = O(TA + h log k + klog 1/6)
such that
PP x 11 8 1
As corollary, we can expand Fourier-sparse signal under the mixed Fourier-monomice basis (i.e., [e2mifd 12 }eee Je(d))
Corollary H.2 (Mixed Fourier-polynomia approximation), For any A > 0, 8 0, ny E Z [k], Ee), ny = k. Let
x²(1)= = Σ 2miszt
JE[K]
where S3al S A for each j E [kc], E [my]. There exist l polymomials for E [K] of degree at most
= O(T + log log 1/6)
such that
Σ 2 (3(1) -1)) 5ol0=00)
jE[K]
The following lemma bounds the error of approximating a low-degree polynomial using Fourier- sparse signal.
Lemma H.3 (Polynomial to Fourier signal, Chen et al. (2016)). For any degree-d polynomial
d Q(t) = Σ cg any T > 0 and any > 0, there always exist y > and
1=
x (+)
Σ aye 2ri(()))
with some coefficients oo.".. such that
Vt [0, (t) Q(t)) Ss.
49

---

H.2 Technical tools I:: filter functions
In this section, we introduce the filter functions and designed by Chen et al. (2016), and we generalize their constructions to achieve higher sensitivity.
We first construct the H-filter, which uses rect and sinc functions.
Fact H.4 (rect function Fourier transform). For > O, let rect, |//$/22 Then, we have
rect, (f) sinc(sf) = sin(sf)
TTF
Definition H.S. Given 81,82 >> 0 and an even number l E N4, we define the filter function H1 and its Fourier transform (f) follows:
(1(t) = 8o
* rectsz (t)
(f) = so (rect *... rect,, (f) sine (f82)
where 8o = C.s81 VL is normalization parameter such that H1(0) = 1, and * means convolution.
Definition H.6 (H -filter's construction, Chen et al. (2016)). Given any 0 < $1, 83 < 0,00 define H 5 (t) from the filter function (t(t) (Definition H.5) follows:
let é = ((klog(k/0)) $2 ==
2, and
shrink H1 by a factor s3 in time domain, i.e.,
Ha Hi(t/s3) H (f
(15)
(sHf(
(16)
We call the "filtered cluster" around a frequency fo to be the support of (8 Hon.ss))(f) in the frequency domain and use
81
An |supp H (.))
(17)
$3
to denote the width of the cluster.
Lemma H.7 (High sensitivity H-filter's properties). Given (0,0.1), 81,83 (0,1) with min( - .1) 2 ((K))EE, and 8 (0, 1). Let the filter function H H(l defined in Definition H.6. Then, H satisfies the following properties:
1
2
Property T:
H(t) [1 - 6, 1], when |1|
<
(
-
-)83.
2
H(I) [0, 1], when 1
2
1
Property IT:
)83
|0|
83-
2
81
(t) < 5o (s1( |t|
Property II1:
+ +)=
when |t|
>
83.
2
2
Property IV: supp A C [- 81e s1e.
283 283
For any exact k-Fourier-sparce signal x² (t), we shift the interval from [0. to [-1/2, 1/2] and consider x" (t) for E -1/2, to be our observation, which is also x² (t) rect, (t).
of to0
L (x)(t) rect (t) dt.
Property V xx (t) [t)) (1 rect recti (t)) <
(t) H(t) rect, (t) E [1 11- 1, f (x) rect, (t.
Property VI:
Remark H.8. By Property I, and II, and III, have that H(t) for forttert E [0,T].
50

---

Proof.
The proof of Property 1- V easily follows from Chen et al. (2016). We prove Property in
below.
First, because of for any 1, (1) & 1, thus we prove the upper bound for LHS,
1 (1) (1) recti (1) - x (1) recte (1))²
Second, as mentioned early, we need to prove the general case when 1 1/poly(k). Define interval S = ( - +) 83(2 } by definition, S C [-1/2,1/2]. Then define S = [-1/2, 1/2] S. which is [-1/2,- -sa + (sa( +,,, 1/2]. By Property I, we have
(1) H(1) (1 - 6)2 / xx (t))
(18)
Then show
x (1)
33
$ |5|-
max
(t)2
LE(- 1//-1//.1/2
$ (1 83(1 2) O(12) )))((13))
1" (0)
81
$ E
xx" (t)
(19)
-
where the first step follows from 5 C [-1/2,1/2] the second step follows from Theorem C.I, the third step follows from (1 s3(1 - 0(k2)
Combining Equations (18) and (19) gives a lower bound for LHS,
x (1) (() rect, Rt)
x' (t)
2 (1 28)
1x" (d)
(t) - (1-) / xx" (t)
(1 28)
SUS
1x0 (1) (1 -25)E / (t)
2 (1 28)
SUB
SUB
= (1 - 25- - E)
(1)
2 (1 2x)
|x" (t) rect, dt)
where the first step follows from S (-12,,1//2] the second step follows from Eq. (18), the third step follows from S S 0, the forth step follows from Eq. (19), the fifth step follows from SUS 1-12, 1/2], the last step follows from > d.
As remarked in Chen et al. (2016). to match (H()), (f) on 11/2, with signal z(t) on [0, T]. we will scale the time domain from [-1/2, 1/2] (-T/2, and shift to [0, T]. Then, in frequency domain, the Property IV in Lemma H.7 becomes
supp (f)) i A A 2 2
where A = E1e
(20)
s
51

---

We also need another filter function, G, whose construction and properties are given below.
Definition H.9 (G-filter's construction, Chen et al. (2016)). Given B > 1, ó 0, > 0. Ler
I = (llo((k/))) Define (B,,, and its Fourier transform (B, as follows:
(B, == bo (rect [03] (t)) sinc(t 27))
(B,aa(f):= = bo (sinc( B f)) rect (f),
1B
where bn = ((B[//a) is the normalization factor such that (()) =
Lemma H.10 (G-filte'ss properties, Chen et al. (2016)). Given B 1, 0, >>>>>> let G =
GB, (t) be defined in Definition H.9. Then, G satisfies the following properties:
G(f) E [1 8/k, 1), if S (1 a) 2x
Property I:
2B
2T
2T
Property IT:
G(J) E [0, if(1 - a.)
S 1/1
-
2B
2B
2T
Property III:
G()) E 1-6/k, if
2B'
supp(G((t) C / ( 2 ιa 2 Tа
-B 1 B
Property IV
Property V
max G(I)) < poly(B,1)
H.3 High sensitivity frequency estimation
In this section, we show a high sensitivity frequency estimation. Compared with the result in Chen et al. (2016), we relax the condition of the frequencies that can be recovered by the algorithm.
Definition H.11 (Definition 2.4 in Chen et al. (2016)). Given x² (1) E Enge2mbis any N >
j=1
and a filter function H with bounded support in frequency domain. Let L5 denote the interval of supp(e2xifzt.. H) for each j [k.]. Define an equivalence relation the frequencies fi as follows:
f f3 iff L, 0 Vi.j E [b].
Let Si...., Sn be the equivalence classes under this relation for some S k.
Define C U for each i [ni] We say Ce is --haavy cluster iff SES.
/o. |H H (PPaf TT.
The following claim gives a tight error bound for approximating the true signal x (t) by the signal xg- (t) whose frequencies are in heavy-clusters. It improves the Claim 2.5 in Chen et al. (2016).
Claim H.12 (Approximation by heavy-clusters). Given xf (1) = Σ 2misst and any N 0, let
C1,11 Ci be the N-heavy clusters from Definition H.I.. For
S 5- {3 E [k] ( (ciu.....
we have xg-(t)= JES-
Σ 2, approximating x² within distance
|as-- x11 < (1 - 1/8) + e
Proof. Let H be the filter function defined in Definition H.6.
52

---

Let
jE
Notice that ||2* - zz- | = 1 1
By Property VI in Lemma H.7 with setting 5 = 50 == E/2, we have
(1 5b) 7 73- 1 = (1- Eo) / (tg=(t)
(1 Eo) / (xg=(()) rectr rectr(())
+00
(1z-(1) (t) recty (t) drr
$
Izg= (t) dt)
where the first step follows from the definition of the norm, the second step follows from the definition of recty (t) 1, Vt E [0, T), the third step follows from Lemma H.7, the forth step follows from
recty (t) S 1.
From Definition H.11, we have
+00
(1= (1))
Igg. .H())as
x (f)
$ (I: -1 TNN2/k
where the first step follows from Parseval's theorem, the second step follows from Definition H.11, Property IV of Lemma H.7, the definition of S*, thus, supp(zs- H (f)) C1 U...UC.
supp(zs- H(f)) n supp(rg- H()))) = 0. the last step follows from Definition H.11.
Overall, we have (1 Eo) | 12 S 2 Thus, || (t) - x= (t)ll < (1 - 1/k) + =>>² by the basic algebra fact: T- I 1 + for any E [0, 1].
Due to the noisy observations, not all frequencies heavy-clusters are recoverable. Thus, we define the recoverable frequency as follows:
Definition H.13 (Recoverable frequency). Let C be an Ni cluster. We say C is Ne-recoverabbl it it satisfies:
I.
A frequency f is (2) if is in an Ni-heavy, Ng-recoverable cluster C.
The following lemma shows that most heavy clusters are also recoverable.
Lemma H.14 (Heavy-clusters are almost recoverable). Let (t) = Ei= 2 and a(t) = x² (L) + g(l) be our observable signal. Let N/2 = || + 11. Lel Ci,... Or are the 2N- heavy clusters from Definition H.ll. Let S denotes the set of frequencies f {fibiem such that, f E C. for some E (t). Let C S be the set of (2N, (N)),,N frequencies.
Then we have that,
| x0 (3 1/k + s)N.
53

---

Proof. If a cluster C₁ is 2N-heavy but not N recoovera,,,,, then it holds that:
Ja 11 11 (.)xaPass2 4T / H -())a
Jc.
(21)
where the first steps follows from C. C Us,Es Cj. the second step follows from C. & 1, Cz. So,
Jc I -lffff / H 20--==)(ffaa
Ja H H.. a())pss
H -T)
1 H. 11xx
(22)
4 Cr:
where the first step follows from gt) = xzt) x (t), and the second step follows from triangle
inequality, the last step follows from Eq. (21).
Let C' == UrEesss C₁ i.e., the union of heavy not recoverable clusters. Then, we have
|| 0113 2 E Lc H (H-
Σ Σ / C.EC C..
H (
(23)
C,EC
where the first step follows from the definition of the norm and C.C.s 0, vi + j. the second step follows from Eq. (22).
Then have that
T
T Is 11 -
| H|?
1 - E/2
S + E)
Σ
H (
C,EC
S 54(1+c)]]1 H| g1
= =4(1+ =4(1+))7|| gllt
$ {41
< <((1+))AN2
where the first step follows from Property VI of H in Lemma H.7 (taking & there to be e/2), the second step follows from E E [0, 1] and the definition C.. the third step follows from Eq, (23), the forth step follows from g(t) = 0, Vi & [O, the fifth step follows from Remark H.8, the last step follows from the definition of A/2 Thus, we get that:
|| Ir S (2 - 1l-1/K+eWN,
(24)
which follows from v1 + t 1 1 e/2.
Finally, we can conclude that
| x S ||ss xg. ||r + læs- x 201
= || 1| + I|rs- - x 1r
< | l| +
- 1/ + 2,)N,
where the first step follows from triangle inequality, the second step follows from the definition of Is,ys, the third step follows from Claim H.12, the last step follows from Eq. (24). The lemma follows by re-scaling to e/2.
54

---

H.4 + (epe))ppppxiaall Fourier interpolation algorithm
The goal of this section is to prove Theorem H.20, which gives Fourier interpolation algorithm with approximation error (9 + E). It improves the constant (more than 1000) error algorithm in Chen et al. (2016).
Claim H.15 (Mixed Fourier pannier-polyoomial energy bound, Chen et al. (2016)). For any
u(t) span 2mifit t² j (0. .d,; i [k]]
have that
|u(t)|² & (kd)* log)(kd) ||u11
max tE|0,7]
Claim H.16 (Condition number of Mixed Fourier-polyy paarrir-polyommia)). Let F is linear function family as follows:
span { 2aifas . j to, ,d, [m].
Then the condition number of Uniform (0, T| with respect to F is as follows:
[f(t) ((kd)* log (kd)
Uniform((,T]]
sup sup tElo.T If
The following definition extends the well-balanced sampling procedure (Definition E.1) to high probability.
Definition H.17 ((e, p)- sampling procedure). Given a linear family F and underlying distribution D, let P be a random sampling procedure that terminates m iterations (m is not necessarily fixed) and provides a coefficient and distribution D, to sample x; ~ Dr in every iteration i [m].
We say P is an e-WBSP if it satisfies the following two properties:
D(v.) 1. With probability - P. for weight wi = 0. D((x.) ofeach E [m].
m
Σ
w. (M(x)) E 1001,,11,1 10VE 1i1BB Wh E
2. The coefficients always have Em a; S 5 and a; Kis,D, S for all E [m].
4
The following lemma shows (c, WWBSP for mixed fourier-polynonee family. Lemma H.18 (WBSP for mixed Fourier polyooial family). Given any distribution D' with the same support of D and any O, the random sampling procedure with O Df log(d/p) p)) ii.d. random samples from D' and coefficients 01 =... Om = 1/m is an (c, P)-BS.
Proof. By Lemma B.12 with setting E = VE, we have that, as long as m 2 0 Kis log g), then with probability
|| - T1l2 Ve
By Lemma 1111, we have that, for every F.
Σ wy (h(x)( [6] !I
where S is the m i.i.d. random samples from D', w. a,D()))) Moreover, Em 0g 5/4 and
Kis
05
Kis
log(d/p) S e,
m
where the first step follows from the definition of as, the second step follows from the definition of m, the third step follows from log(d/p) 1.
55

---

Now, we can solve the Signal Estimation problem for mixed Pourier-polynone signals. Lemma H.19 (Mixed Pourier-polynonee signal estimation). Given d-degree polynomials (t E [k]] and frequencies f E [k]. Let =s(() Σラ= (t) exp(2mif, and let g(t) denote the noise. Given observations of the form æ(t) == Is (t) + g'() for arbitrary noise g' in time duration E (0.T].
Then, there is an algorithm such that
takes O(s pply log(1/p)) samples from xz(),
runs poly log(1/p)) time,
outputs y(t) Σ j=1 (t(() exp(2xif,t) with d-degree polynomial Pt()), such that with probability at least 1 - P. we have
llv xs el S (1 + 1lgl11
Proof sketch. The proof almost the same as Theorem G.4 where we follow the four-step Fourier set-query framework. Claim H.15 gives the energy bound for the family of mixed Fourier-polynomial signals, which implies that uniformly sampling m Os [[ points in [0, T] forms oblivious sketch for x². Moreover, by Lemma H.18, we know that is also an (e, P)-WBBPP which gives the emror guarantee. Then, we obtain mixed linear regression.
signal (t) by solving weighted
Now, are ready prove the main result of this section, algorithm.
Fourier interpolation
Theorem H.20 (Fourier interpolation with (9 + e) approxxmmatin error). Let xx(1) = x (1) + g().
where x² is k-Fourier-sparss signal with frequencies in [-F, F). Given samples of over (0, 7) we
can output y(t) such that with probability at least 1 2 (2k))
My - x ==| S (9 + 1)l1 0| Ir.
Our algorithm uses poly (k: -- Logg (TT( samples and poly(k, log(1/6)) log (FT) time. The output y is poly(k, Log(111 (1/6)) 6))= -oorrer--parrreeeeeeeee signal.
Proof. Let == ((((t) + _||=5 (t) be the heavy cluster parameter.
First, by Lemma H. 14, there is set of frequencies S c [k] and xs(()
Σ Ujjettifzt such that
jES
| - x = l|r S (3 + Wc))
(25)
Furthermore, each fj with j E S belongs to N -haav cluster Cj with respect the filter function
Н defined in Definition H.6.
By Definition H.11 of heavy cluster, it holds that
[ c,
H 20)Pa TN2
By Definition H.1I, we also have |C,l S k A.. where An is the bandwidth of H. Let A E R,, and A > k. An, which implies that C, S S - A.J₁ + A). Thus, we have
bs+A (n 2 TN
H
Now it is enough recover only ss, instead of x² By applying Theorem H.36, there is an algorithm that outputs set of frequencies L C. such that, |L] = 0(k), and with probability at least -(k), for any fq with j E Sy, there a f such that.
-
56

---

We define map p.: R + L as follows:
p()) == arg min FEL.
| 51 AA ER.
Then, (t) can be expressed
ss (1) = Σ
jES,
Σ
(2mb)(1--((1)
JES;
Σ
2m1fe
Σ
uje 3
JEL
JESy: PU,)=
where the first step follows from the definition of æg, the last step follows from interchanging the summations.
For each fo L, by Corollary H.2 with x²' IS,, AVAT, we have that there exist degree d = O(TAVAT + & log k + k log 1/5) polynomials (t( corresponding to ft L such that,
| (1) Σ
ami P:(1)]IT s ,||2,, (4)lr
(26)
7.EL
Define the following function family:
F ===span span 2 . Vf L,j 10, 10. dt}.
Note that Ejer 2n p R(()
By Claim H.16, for function family F, K Uniform((oT)] = O()[T)))) Iog log (ILl))
By Lemma H.18, we have that, choosing set W of O( Uniform((,11 log( L[d/p) i..dd samples uniformly at random over duration [0, T] is (e, W)BBPP.
By Lemma H.19, there is an algorithm that runs ([ (9g((1)))-timm using sam- ples in W, and outputs y' (t) F such that, with probability P.
(1 Σ
2n 2.(0ip s (1 + e)]l=(())
Σ
P.00ll
(27)
J.LL
T.EL
Then by Lemma H.3, we have that there is Okkd) ((kk))-Foureer-sparss signal y(t,, such that
(t) (t) 8'
(28)
where 8' is any positive real number, thus, y can be arbitrarily close y/- Moreover, the sparsity of vt) is kd RO(TAVAT + 13 logk + k log 1/8) E 1.5 -1.55 lo))))))))
Therefore, the total approximation error can be upper bounded as follows:
ly - x=IlT < Ily - 3/Il +
110/ Σ
2mifi
Pi(O
- -1E 2n P.(1) - x"11,
(Triangle inequality)
F.EL
J.EL
< (1 <(1+ (1))(1))\ Σ 2 (3(()) 11,,+11111 +
2 Pi(t) - -2/11
(Eq. (28))
TREL
T.EL
< <(1+)) Σ
2n P.(t) ||+ +| Σ
2n1ht P.(t) -z²
(Eq. (27))
F.EL
F.LL
57

---

< (1+ ++)1lll1 + 22) Σ
2xthi P.(t) =x11
(Triangle inequality)
fELL
S (1 + 22 11)11 + +2+ e)
Σ
2n1 P.(t) (x(1) Iss 1r
- x211
(Triangle inequality)
< +1+ <(++2)000|-11++220000::+++++++11 xx" 1''1
(Eq. (26)
< (1 + 28 +=] 8)||ss, x" z²Ir
(Triangle inequality)
$ (1+ 2:) [1++ 6| - xslr + | x= (1r)
(Triangle inequality)
S (1 + + +00- ((E)W (Eq. (25) and Lemma H.41)
= (1 + +1000
Since we take
N v ||g13 + 8112*11 - 1 + V8l
we have
1y - 17 < + By re-scaling e and ō, we prove the theorem.
0
H.S Sharper error control by signal-noise cancellation effect
In this section, we significantly improve the error analysis in Section H.3. Our key observation is the signal-noise cancellation effect: if there is frequency f in a Naahe cluster but not for some N22 < Ni. then it indicates that the contribution of f to the signal x²'s energy are cancelled out by the noise g.
In the following lemma, we improving Lemma H. by considering g's effect in the gap between heavy-cluster signal and recoverable signal.
Lemma H.21 (Sharper error bound for recoverable signal, an improved version of Lemma H.14).
Let x² (1) = Σ Uze2xifz² and x(() = (1) + g() be our observable signal. Let N/ == llg(t) + 8||2² (t)).. Let Cg. CC are the N1 Ni-heavy clusters from Definition H.ll. Let S denotes the set of frequencies f* E (fybee such that, f E C2 for some i E [1]. Let S C S* be the set of (Ni, (E2N1) recoverrbbe freequeebbeeeequeeniccee (Definition H.13).
Then we have that,
|H IS. H xsll + || H 2sll (1 (1
Proof. Let (() = gtt + (t) - rg. (t) = xt) - xs. (t).
In order for cluster C₁ to be missed, we must have that
1 / H Hf)
TNG
(29)
E2 cc.
where the first steps follows from C2 C UfJes-Ci Cj, the second step follows from C, & UpeeSCj. Thus,
1 H T-ggAaaf----
/
H ( -2-1)ax-)ff)aar
x.S (f)1s - V/.. H (F--a()Paa))
1)2 / H (x)(f))d))
V22
c.
58

---

1 11 xxf
(30)
282 Jc,
where the first step follows from the definition g', the second step follows from triangle inequality, the third step follows from Eq. (29), the last step follows from S 0.1.
Bound || x 11 xS|lT.
Let l' ( then we have that,
T x H xxsl7 <
H x(t) - -H ass
(( x - -H.Is)
|H x - -H-2s)(
1(H x (1)
(31)
where the first step follows from the definition of the norm, the second step follows from Parseval's theorem, the third step follows from I' UT' = 1-,0, oo].
Bound H rs. H xsll
We can upper-bound it as follows:
THH g- H x512 V
H- 1.xss- (1) H (l)
(H 25 - -H -H-xs)(f)
(H IS-- H HHxss) + J [H rs- H H-ss)(
|H -.S- -H a.)
(32)
where the first step follows from the definition of the norm, the second step follows from Parseval's theorem, the third step follows from I' U I' [-oo, oo]. the last step follows from (Unes*
F'
Putting it all together. By Eqs. (31) and (32), we get that
T Fs. H x.s T H xsll
< (H rs- xs) ( + (H. x-- - ( + [ 1H 1 Н (a)
For the first integral, have
J1 (II zs. H1 (f)ss(
H -. (f)
H H-2(f) + J. H (f)
25a J. ( H'DPAa + VI H -f-
S,, H. H- (())a
(1 + /222)
(33)
where the first step follows from C,) = 0. the second step follows from triangle inequality, the third step follows from Eq. (30), the last step is straightforward
For the second integral, we have
[
x H H.rs)())aa) = / H 2())
59

---

J, H g' (f)ssss
S 2
(34)
J1
where the first step follows from (U)}esC)) n 0, the second step follows from Eq. (30).
For the third integral, together with the Jr. H g' df term in the first integral's upper bound (Eq. (33)), have
(H H -. J, I. ('
I1 (IS) + =s)(f) 1. [
{ H g'(1) + J, IH (()))
H -.NPa
H | g'())
T (0)2
- T
(35)
where the first step follows from the definition of g', the second step follows from (UAE Css-CCCnT-- (U)) ), the third step follows from theorem, the fifth step follows from gt) = 0, vt & [o, T]. the last step follows from (() by Remark H.8.
[-o0, oo). the forth step follows from Parseval's
Furthermore, we have that
J, (H..(())aas- L H g (
(36)
Therefore, conclude that
T x5- H xss 1 T H xs
(H 1H -- -.. 2Hs-)))))aas + J (H H ass)())aaa))
< T H -..- - H 2
< 31 [H .s. H -xss
H (f) (H - H as)
S(1+ )
H H-g(M)aa (HT -H H.Ds)(PPas (H H Hs)
H. (T-J()Ps++2)) /, II IH-JUPPss+ III x HI (s)
s(1+ (
H ('('(P) + S, H()PPs I(H x H. H.2s))(Paa < SOVERIIIE J. I 70PPar+ / [ITT - HH
-((E))
< SO Tll
(1 O
where the first step follows from Eq. (31), the second step follows from Eq. (32), the third step follows from Eq. (33), the forth step follows from Eq. (34), the fifth step follows from (1 + /2 S
1 1 ((ve2) the sixth step follows from Eq. (36), the seventh step follows from Eq. (35), the last step is straightforward.
The lemma is then proved.
60

---

As consequence, we can easily bound |æs-- 2s lr as follows.
Corollary H.22. Let S and S be defined as in Lemma H.21 Then, have that,
Iss-- =sl1 = (1 + O(ve2)) x5- 17
Proof. We have that,
Jas. - =sll S (1 + 2 -25- zg- H xs 11 & (1 21)(1 + O(Vez))]l - xg. 11
where the first step follows from Lemma H.7 Property VI, the second step follows from Lemma H.21 and
In Lemma H.21, we introduce extra term || -z - H xsllr. The following lemma shows that this term appears in the approximation error || 2g l|r, which can be used to upper-bound the Signal Estimation's is error.
Lemma H.23 (Decomposing the approximation error of recoverable signal), Let 2²(t) Σj=1 Uye and ar(t) x² (t) + g(t) be our observable signal. Let Net == llg(t))l + 8||=" (2)
Let Cr.... Ci are the Nı-heavy clusters from Definition H.l1. Let S denotes the set of frequencies f" E {ff]je(M) such that, f C, for some i [1] and
1 x H(f) 2
f S* such that, f E Cj for some E [1 and Let S denotes the set of frequencies
1 x. 2
Then we have that,
| xsllr H =s)ll + llllr O(e)]l=* xsllr.
Proof. We first decompose ||x - xs |r into the part that passes through the filter and the part that does not pass through H!:
| xs s
1/
W H(x - x + I1(1 - H)(x - rs)
< (x 11 + [I(1 - ()(x==)()))))) -
- < H [x 2xs) ) + [[(1 H)9l + I(11 H)( -z))=1
+ (1(1 -
where the first step follows from triangle inequality, the second step follows from triangle inequality, the last step follows from the definition of
For the second term, we have that
I1 Holl S 1
by Remark H.8.
For the third term, we have that,
( (1=")(z=* xs)1? = || - xsl?? - |H( - xs) < El|a= xsl?
where the first step follows from 1- 0, the second step follows from x² us is k- k-Fourier-sparrs, thus combine Property VI of Lemma H.7, we have that [x - xs) 122 Z (1 - =) xs 2
Combining them together, prove the lemma.
61

---

H.6 Technical tools III: HASHTOBIN
In this section, we provide some definitions and technical lemmas for the HASHTOBINS procedure, which will be very helpful for frequency estimation.
HoSHTOBINS partitions the frequency coordinates into B = (k) bins and collects rotated magni- tudes in each bins. Ideally, each bins only contains a single ground-truth frequency, which allows us to recover its magnitude.
More specifically, HASHTOBINS first randomly hashes the frequency coordinates into the interval [0, 1]. After equally dividing [0. 1] into O(k) small bins, each coordinate lays in different bin. This step can be implemented by multiplying the signal in the frequency domain with a period pulse function Ghi Then, even if the signal does not have frequency gap, the HASHTOBINS procedure can still partition it into several one-cluster signals with high probability.
Definition H.24 (Hash function, Chen et al. (2016)). Let (o,((f) o (f+bb (mod 1) and h (..(()) round (f)) B) be the hash function that maps frequency f E FF,F) into bins (0. B - 1}. Claim H.25 (Collision probability, Chen et al. (2016)). For any Ag > let be a sample uniformly Then, we have:
at random from
1BA0 2B2
If S 15f 5 2(B 1) then Pr(h ho,
II. 2 183--1a 11)40 - then P = hf n¹
Definition H.26 (Filter for bins). Given B > 1. 8 > 0 let G(t) == G ((TT(( where G.Bbba. is defined in Definition H.9. For any > 0,b E I and j [B). define
201 = e 2 B-obj/o
and its Fourier transformation:
(
Σ VEZ
G +
i
of - -bb).
B
Definition H.27 (Coo An)-one-cluste signal, Chen et al. (2016)). We say that a signal z(t) is an (Eu, clneecceer signal around fo iff z(t) and 2(f) satisfy the following two properties:
Property I So+
[(() 2 (1 - 6D) / (3())aaf
Property II
|x(1)Pal 2 (1 - 60)
Definition H.28 (Well-isolation, Chen et al. (2016)). We say that frequency f is well-isolated under the hashing (a, b) if. for = (f*) and I = (-oc, 00) \ (8* Do. f + An),
|ITT S.rr--00000 G2) as TNG/k.
where N² = c ~11z0 (2)).
Lemma H.29 (Well-isolation implies one-cluster signal, a variation of Lemma 7.20 in Chen et al. (2016)). Let f satisfy
H() TN2/K.
where N3 = =1 + (1)=0(t) Let H 2D) where j hrrl(*)) If f is well-isolated, then z and 2 satisfying Property Il of one-cluster signal (Definition H.27), i.e.,
L (ttt) 2 (1 - (o)
1ttt)
Lemma H.30 (Well-isolation by randomized hashing, Chen et al. (2016)). Given ((kk(E0011)) and a E 14 2n2,, chosen uniformly at random. Let f be any frequency. Then f is well- isolated by a hashing (a, b) with probability at least 0.9.
62

---

Proof. Let S' = (e OZy.. By Claim H.25, with probability at least (1 - 1/B) 1 k/B2 1- E0E112 2 0.99, for all the frequencies f E S', we have that ho, o (f,
Hence,
8² df
x²
H 2G)
0
a((f)
R2
8²
r" df
h2
1=" Htt)
k2
8
=*+H(tt) + 8²
/
xx-
dtt
R2 10,7"
8²
8²
xx* dH +
1:2
k22
[-00,00]|10.77
8
(1 + 8)
1
(37)
k2
where the first step follows by the Property IIII in the Lemma H.10 that IG(f)) = 6/k, which implies that ( (f) & ((6/k) for E S", the second step follows from Ty- C [-00, oo]. the third step follows from Parseval's theorem, the forth step is straight forward, the fifth step follows from the property VI of Lemma H.7, the sixth step follows from V of Lemma H.7.
Moreover, let I' denote the set of frequencies that hash into the same bin as f", then we have that,
|_- 1g H. (.) Go <
J 1g. H.H. T...BRUPPPS
[ 1g. GD) G.P
2 1 - H.))P)
J
8²
<
1g ((HH)) +
[g Hff
122
8
1g H(f) + 122
(38)
where the first step follows from I'OT' = 1-00, oo). the second step follows from for any f R. (LR S the third step follows from for any P7 G.) S 8/k, the last step follows from
f HUNPas L 1g (g-H())aaf=
/ Ig H()) Tigg HIG S Tlgl
where the first step follows from I' [-),, the second step follows from Parseval's theorem, the third step follows from g(t) = 0, & [0, T". the last step follows from Remark H.8.
Next, we consider
J, Ig o.b
E
H
1g. H(DPas
B
E T
where the first step follows from a, b are chosen randomly, the second step follows from f -g- H(f < T
Thus, by Markov inequality, with probability at least 0.99,
f 9. HHMPass 1o
g
T
(39)
k
63

---

Finally, we can conclude that
J 2.M
/
1111 (x* +g) ( ..00
14-
1xt (T.GG)(()) - { 1g. H. 22
2
8 + 8)
7| 117 +
1g H G.BLPP
12
Ts-
(1 + 8)
8²T
T| 1 +
|191 + lg H()))aff
122
122
(1 + 8) T| + 8²T
|191 + 2 1gll
122
122
6(1 + 8)
8²
Ep5162k S0E15>T66| " +
+ 1)
$ E05152T8| x 1 22
S E0 TN2/1 kk,
where the first step follows from the definition of g. the second step follows from (a+ 2 < 2a 2h2 the third step follows from Eq. (37), the forth step follows from Eq. (38), the fifth step follows
from Eq. (39), the sixth step is straightforward, the seventh step follows from 6(1+6) B05152R < 1 and
CoCLeck + 1) < 2, the last step follows from the definition of No
Lemma H.31 ((Chen et al., 2016, Lemma 7.21)). Given any noise g(t) [0,7] C and g(t) 0, Vt & [0, T). We have, Vj E [B],
lo())(()) Go (0
x (0())(())Fd
1
H.7 High signal-to-noise ratio (SNR) band approximation
In the this section, we will give the upper bound of ||-s, (t) - xt(()]lr.
Definition H.32 (High SNR and Recoverable Set). For [B], let 27 = (x* H) G(.) we define the set as follows
Sg. = j ( (1- (1--))))))
where e is constant. And we also give the definition of recoverable set which is the same with 8 above
5 +'
Sg, :=:= {i [B] 3fo. ho (fo) = and f I -H()PdffIXG)
where N3 = (1)) 8||0> (1)=
And then define High SNR and recoverable set as follows
S = Sg S
Let Sy: = {j [k]])).((f)) s,,, We have xs, (t) E 2.
Remark H.33, In the left part of the paper, we focus on the frequency in set Sy which is subset of the recoverable frequency set S.
The following lemma shows that for any recoverable frequency (i.e., those satisfy Eq. (40)), HASH- ToBINS will output one-cluster signal around with high probability. Now we will consider f" satisfy the assumption introduced in Definition H.32.
64

---

Lemma H.34 (HASHTOBINS for recoverable and HSR frequency). Let f E [[-F,F] satisfy:
++
H(f)) TN2/k.
(40)
where = (11=0(1))
For random hashing (a, b). let ha.b( be the bucket that f maps to under the hash such that 2 = (x H) G()), and = x H (6) Given that Sn and e is defined in Definition H.32. j E Sy. With probability at least 0.9, (t) is an (co, -on-one-clest (See Definition H.27) signal around f"
Proof. The proof consists of two parts. In part 1, prove that =(I) satisfies Property I of the one-cluster signal around f* (Definition H.27). In part 2, we prove that z(1) satisfies Property II of Definition H.27
Part Let region 1.. (f* A, + A) with complement Ty. = (-00, (4 1p.
Next, with probability at least 0.99, we have that
J,, [f (1 8/k) / 1,-
Jz- 12-H(f) 2 T
where the probability follows from A. > 1000 the first step follows from Property I of in Lemma H.10, the second step follows from Eq. (40).
On the other hand, f* is well-isolated with probability 0.9, thus by the definition of well-isolated, we have that
(z() S TTTNG/K
Hence, 2 satisfies the Property I (in Definition H.27) of one-mountain recovery.
Part By Lemma H.29, we know that (x* H) GlB always satisfies Property (in Definition H.27):
J (1(0))))))))))))))))))))) (1)00))))))))
(10 22 (1 (1-50) / (z)(t)((t) G.
As result, by --x,,00)
1o" (1)(() G2 /" (x(())(()) G2 + L (x(())(( * C20
8o
(41)
Then, we claim that
200
(x(()) H(t) c0(0))
x H()) G.
x. ..) G
2V
TNG/K.
(42)
where the first step follows from Parseval's theorem, the second step follows from [f AA. C (-oo, the third step holds with probability least 0.99 and follows from Ag > 10004 and Property I of Lemma H.10, the last step follows from the definition of f*
By Definition H.32, we have that
lg(() H(I) * 22(()) [" (g(t) H(t) ())
(43)
65

---

T <
(t)(t)
S 09
(z)
ce|x(1) H()) GROPP
where the first step from (tt 0, vt & [0, T], the second step follows from Definition H.32, the third step follows from simple algebra, the last step is due to Definition of zz (1).
Then, we claim that
x+ H Goppdis S
/ ((0*+)) + +)) H 2.
00
lg H + G
2d
0,b
1(x* + + G.R
(44)
where the first step follows from triangle inequality, the second step follows from Eq. (43).
Next, we consider
V1 1( +))
J
600
G 2dt S
x * G +
1g H = G 2t
V
/. 1g H. * G Pdt
x GLi dd +
E0
80
((J) b,b
2dl + 80
x
G dd
0,b
55
x H Gdl
(45)
where the first step follows from triangle inequality, the second step follows from Eq. (41), the third step follows from Eq, (43), the forth step follows from Eq. (44).
Similarly,
0 VL 100 + + 9))
0
clipat $
$100
L x.. H * G.lPa
(46)
Combine equations above, we have that,
1a +g) Gol 1 00
1(x* +9) G.
fT
(aa +g) cul + / 1(x* + * G. Pdt
x G 2dt
Eu
where the first step follows from Va +b S Va + Vb, the second step follows from Eq. (45) and Eq. (46).
Hence, we have that (x* +g) H C satisfies Property II (in Definition H.27) with probability 0.95.
66

---

with H.8 Ultra-high sensitivity frequency estimation
In this section, we improve the high sensitivity frequency estimation in Section H.3 with even higher sensitivity, using the results in previous sections. More specifically, we show how to estimate the frequencies of the signal zs whose frequencies are only e'--heavy, while in section H.3 the recoverable signal's 's frequencies are A-hhevy.
Lemma H.35 (Frequency estimation for one-cluster signal, Lemma 7.3 in Chen al. (2016)). For a sufficiently small constant En > O, any fo E []F and Do > 0, given an (En.Ao) one-cluster signal z(t) around fu. Procedure FREQUENCY
CLUSTTER, returns fo with
I fol - Ao VAnT with probability least 1 - --
The following theorem shows the algorithm for ultra-high sensitivity frequency estimation.
Theorem H.36 (Ultra-high sensitivity frequency estimation algorithm with low success probability). Let x= (1) = Ej=nvee2<if; and x<()= x² (L) + g(l) be our observable signal where (lg(()) S KCLUSTER (t)l for a sufficiently small constant c. Then Procedure FREQUENCY
returns set L of ((k((50812)) frequencies that cover all N2-heavy clusters and have high SNR
(See Definition H.32) of x², which uses poly(k,g-t,e ,e0 ; ,6g
, -1 log(1/8)) log(FT) samples and
poly(k, 0 1 E2 (0g(1/))) (FFT time.
In particular, for Do 'ooy (k. log(1/6))/T and N3 (162(19((t + 8 (12((t)) with probability 0.9, for any f with
x df TN2/kk
(47)
there exists an f satisfying
A A.T
Proof. By Lemma H.34 and Lemma H.35, we prove the theorem.
Theorem H.37 (Ultra-high sensitivity frequency estimation algorithm with high success prob- ability). Let x² (f) Σj= uj and æxt) =x"(t) + g(t) be our observable signal where (1g(t))13 (1)l for sufficiently small constant c. Then Procedure FREQUEN- SSECOVERYKCIIUSTER returns a set L of ((k((E0(1)2) frequencies that covers all N heavy clusters of x², which uses poly(k,E-1,Ej . ,6 .log(1/8) log(FT) samples and poly(k, ,e0 1T E
-1 log(1/5)) log((FT) time.
In particular, for Do '-Opoly (ks, log(1/6))/T and N3 2122(119(t)1B3 + +8 -1(²(())13 probability 1 2 R2k) for any f with
AA
x.. H(D) TNG/k,
(48)
there exists an J E L satisfying
|f J Do AOT.
The following lemma shows the approximation error guarantee for the recoverable signal æy of the ultra-high sensitivity frequency estimation algorithm (Theorem H.37).
Lemma H.38 (Recoverable signal's approximation error guarantee). Let Let (t) = Ei= 2a and sx(1) x=( (1) g(l) be our observable signal. Let N/ Ex ((gg(()) (1)1() Let
Ci,..., CC are the -y-heavy clusters from Definition H. 11. Let S denotes the set of frequencies
f E {fsbee such that, f for some i [1, and
[ x H(f TN
67

---

Let S denotes the set of frequencies f E S such that, f E Cj for some j E [ and
/
1 H( 2
C2
Then, we have that,
a - xslr + 100 - x= 1z - (1 2 o(ve))loll +
Proof. Following from the fact that vT+ = (e)) for & < we have
Ni V (1l9) + S V V vōe | ||
We have that
11=0" x.slT < |::-- - nz + -
(1++
- - + || zz- 1|
(1 <1++ x (2+ /12)) x. 1|
< (1 + +[>+ 0 W)WW1
(49)
where the first step follows from triangle inequality, the second step follows from Corollary H.22, the third step follows from triangle inequality, the forth step follows from Claim H.12.
Thus, we have that
| xs- |T | - x" || + ||x0 xS- ||T
|gghT ||0 xg- l1
| T + (1 +)W
(50)
where the first step follows from triangle inequality, the second step follows from the definition of the third step follows from Claim H.
Therefore.
| - xs l + - 2'
< (I)(( 1r ligll1 0())| xsllr) + ||-----0 "/
$ (I) xs)
xs|(r) + - Zs-
||s.- - x'I|
S ([] (I ll) -
+ (1+
xs- 25-)]lr || x ||
+ +[)]]:=====/+((+(((0000))))----- [[[( -asfss-=ss-llll -z5)))l)) + + N
-
- 25- )[(T) + | x 20I|r
< [ O(s)]==* +
< 1// + O(e)]== - =
xs. )| + (1 + WW
< 1 + 0(E)]=" ==l1-==(((0000110000=)))>>---=-- rs- 1r (1+
< +011+0000))
< (10+=+00000+00000))+++++++++1110
+ +V2++0(++-=30000++++++++ (1 WW
where the first step follows from Lemma H.23, the second step follows from triangle inequality, the third step follows from zs- z=- being 4-Fourier-sparte sparse and Property VI of Lemma H.7, the forth step change the order of the terms, the fifth step follows from Claim H.12, the sixth step follows from [x I + [H
|H[ss Fs- M the seventh step follows from Lemma H.21, the eighth step follows from Eq. (49), the ninth step follows from
x. )//T S /221H H[ xs) 1
|
Eq. (50), the last step follows from ED E1 E2.
68

---

The following lemma shows that the recoverable signal ss(t)'s energy is close to the observation signal xtt).
Lemma H.39 (Recoverable signal's 's energy). Let (t)= ef and x(t)= + g(t) be our observable signal. Let N? == (i(lg(t)) = Let C1.... CI are the N2 hhavy clusters from Definition H.11. Let S* denotes the set offrequencies f E (fybiej such that, f E C,
for some i [4]. and
I C
- H(OP 2 TN
Let S denotes the of frequencies
S such that, S Cj for some E and [1]
x ((1))af2eeTM)) c,
Then, we have that,
| X ||g||r + 1r
Proof. We have that,
| < 12 x" || [2 zs- || + ||x* ||
< |g ||r | - xg- l| + ||2 ||r
[g x² ||r | xx I| + ||
< 1glr + lzr,
where the first step follows from triangle inequality, the second step follows from Corollary H.22, the third step follows from triangle inequality, the forth step follows from Claim H.12.
H.9 High SNR and recoverable signals
Lemma H.40 (High SNR and recoverable approximation error guarantee). Let xt) Eje2dee and xxt) x (t) + g(t) be our observable signal. Let N? == E (llg(t)]l - 812" (t)l()) Let Ci.... CC are the Ni-heavy clusters from Definition H.ll. Let S* denotes the set of frequencies f E (ffbiel such that, f E for some i E [l]. and
[ F H--H(f)Pff 2H TNP/k.
Let S denotes the set of frequencies f S* such that, f E C3 for some j E [4] and
Jc o H.)HA) 22NN//k
And Sy is defined in Definition H.32. Then, we have that,
| xs|r S (1 (1+)(s)) (l
(51)
Proof.
We have that
S C S.
And then for any f E SES) ho,(f), we have that
[1(g H()) G. (t) 2(1 c- =)]l(=" H())) * G00
where the first step follows from Definition H.32, the second step is from simple algebra.
Let T = S And for any j E [B], if [B] S,, T = {i (fh,, = j}. Otherwise,
T, = 0. Moreover, we have that for any f E supp(fT, * H),
2 21
(52)
69

---

From Property VI of Lemma H.7, we have that
x (t) H(t) E [1-E, 1] / (t)
(53)
By Lemma H.29, we know that (x* H) Gli always satisfies Property II (in Definition H.27):
T| (t) 2200
S (=)()(()) Pd
21 60)
(((())(())))))) G.
(1 su)
(f) * (()) 22
((* -0000)000)100000 L ((+ (((()(((())))))))))))))()))))))) -00
(1 sn)
2 so)
(f* [(() -
/ (+* f (
(1 so)
(54)
where the first step follows from the definition of the norm, the second step is from Lemma H.29, the third step is due to Parseval's Theorem, the forth step is based on the Large Offset event not happening, the fifth step is based on simple algebra, the last step is because of Lemma H.29.
We also have that
T| (t) (t)1
= 1
$ (T/(1 - -)) [IT((1) H())
(TT(() Pdt
1 - g2
(TT()) dtt
1- 2
1
[T(()) A)))
1- ?
B
TT, (f) x A(())
1 2
J=1
12
<
Σ
TIl (1)- -(()) CZO
(1 2k 8)2
jER
Σ T(l((t) H()) CZOE JEBYS
(55)
(1 - (1-c))(1-)33( 8)2
where the first step follows from Definition of T. the second step follows from Eq. (53), the third step is based on definition of norm, the forth step follows from simple algebra, the fifth step follows from Parseval's Theorem, the six step is due to Large Offset event not happening, the seventh step is due to Lemma H.29, the eighth step follows from Eq. (51).
In the following, we have that
Σ T (()))))) H()) G2 JE(B)
70

---

Σ
(t) H(t) C20
]E[B]
Σ
(t) -(())((())))))))))))))))))))._ * (l)
-
]E[
Σ
(1)) A()) CR
A2
T(f) H())
(h. 6)
k2
(s(1) H(
(k: 6)22 k2
lg(t) dtt)
(k- 6){ 122
(k- 6)² (g(t))
222
(k - 8)2 (9(())1
(56)
where the first step is due the definition of norm, the second step follows from g(t) 0 when I E [0, Ti the third step follows from Parseval's Theorem, the forth step is because of Lemma H9 the fifth step is from Parseval's Theorem, the sixth step is based on g()) when & [0, T). the seventh step is from (1)) < 1, the last step is from the definition of norm. We have that
T s., (t) st((1)1
222
Σ
(1)( (()-H(()) + G2
$
(1 cE)(1 =)2(kK- -))²
JEBYS,
22
Σ TIl(o(() H()) CZOO
S (1 cE)(1
=)² 8)2
jE(B]
$ (1 cz)(1 =}2(k 8) [l9(t)
< (1 + (()))
where the first step follows from Eq. (55), the second step follows from simple algebra, the third step is due to (5.), the forth step is because of the reason that ó is much smaller than and E < O
Lemma H.41 (High SNR signal's energy). Let x (1) = E 2ni2 and =(1)=x)(1)) + s(1)
be our observable signal. Let N? == en (Ig((t)) +11="" + Let Cr.... Ci are the Ni-heavy clusters from Definition H. Let S* denotes the set oreequenciis f E (fibiem such that, f E C.
for some i [I], and
[ C.
F - 2NT/
Let S denotes the set of frequencies
fo E S* such that, f E Cj for some j E [1] and
[ le
Let Sy be defined in Definition H.32. Then, we have that,
[ lr (1 (c)) + |
71

---

Proof. We have that,
[ l| s r,s, F$ [ + as | + I z-- l| + ||0 lr
2
1 2s |T + Is x² I + || - Is. || + || l|
X | 2s || lass x= Ir + 1| x" l1 | l|
< | zs|l + 1 ||
< (1 (()))llollr ||>",
where the first step follows from triangle inequality, the second step follows from Corollary H.22, the third step follows from triangle inequality, the forth step follows from Claim H.12, where the last step follows from Lemma H.40.
H.10
(3 + 2 + approximate algorithm
In this section, prove the main result: a (3 + 2 () -ppproximate Fourier interpolation algorithm, which significantly improves the accuracy of Chen al. (2016)'s result.
Theorem H.42 (Fourier interpolation with (3+r/+t))aprroximatton error). Let x(t) = x²(()) (t) (t)++((t), where x² is k- S--FFourrr-ppae sparree--pareeeeeeeee signal with frequencies in -F, F). Given samples of over [0, T we can output y(t) such that with probability at least 1 2 -2(()))
1l x" z0Ilr I (3+ v2+ glr 8|22"|1.
Our algorithum uses poly(k, e-1, - (lg(ll/))) log((T) samples and poly(k, log((18)) llog (FT)
time. The output y is poly(k, logg (o))) Fourier-sparse signal.
Proof. Let N3 == c1e2(1lo(()1) + 611=)0)) NP == e1 (11)(()) + (1)1))) be the heavy cluster parameter.
First, by Lemma H.12, there is set of frequencies S* [k] and xs- (1) E
2 such that
JES
|x - x1 S (1 (1++)) e)M
(57)
Furthermore, each f, with j E S* belongs to an Ni -heavy cluster Cj with respect to the filter function H defined in Definition H.6.
By Definition H.1 of heavy cluster, it holds that
[ H of
By Definition H.11, we also have |Cyl S h: An. where An is the bandwidth of म. Let A R4, and A An. which implies that Cj S [fz A, + A]. Thus, we have
x (f) 2 TWP/k.
By Corollary H.22, there is a set of frequencies S S* and 2s(() Σ 2 1s* such that
jes
| x.- 11 < (1 (( -rp 11
Let g' Tg"
In the following part, we will only focus on recovering the high SNR frequency. Let Sy defined in Definition H.32. It's know Sy C S By applying Theorem H.37, there is algorithm that outputs of frequencies I. C RR such that, [T.| Okk/ ((k////od (008160))))))))) 122)), and with probability at least 2 for any fj with j E Sy, there a / E L such that,
- -
72

---

We define map p: R + L as follows:
p(f) arg min 1f fl Afe e.
JEL
Then, (t) can be expressed as
Es, (t) =
Uz
JES;
Σ
use
2xinp(()
22
JES,
Σ 2
Σ
JEL
jES,: ((S))}
where the first step follows from the definition of 2g (t), the last step follows from interchanging the summations.
For each Ji L, by Corollary H.2 with x² rs, A AVAT, have that there exist degree O(TAVAT + 13 log l + k log 1/8) polynomials (t()) corresponding fa such that,
| (t) Σ 2 Vollzs, (t)llr
(58)
FiEL
Define the following function family:
F == ( P. VJ E L,j (0, 10......,d) .3].
Note that Ejer 2
By Claim H.16, for function family F, [uniformjo,1] = O(([=dd)* log ([L))).
By Lemma H.18, we have that, choosing set W of uniformly at random over duration [0, I'' is (e, W)BSPP.
log( Lld/p) i.i.d. samples
By Lemma H.19, there is algorithm that runs in O( ([ log(1/)))) using sam- ples in W, and outputs y/ (t) E F such that, with probability P.
1V'(0- Σ 2 P.C0 S (1 e) p00
Σ
2niid 2 P.00
(59)
J.EL
N.EL
Then by Lemma H.3, we have that there is (ka) Foors-F--rri-spareee signal ytt), such that
|y s/ || < 8'
(60)
where 8' is any positive real number, thus, y can be arbitrarily close y/. Moreover, the sparsity y(t) is
kd = ROTTAVATT + 33 log k + k log 1/0) = = pol(()))_,..o((11))))
Therefore, the total approximation error can be upper bounded as follows:
ly - x= ='|
< ly - y || +
1|'' Σ
2
P.(0
+||
+
2n P.(1) - -201/1
(Triangle inequality)
J.EL
J.EL
< (1+
Σ
2mifit Pi(t)
11, + +1E
2niiit Pi(t) -x"1/
(Eq. (60))
T.EL
T.EL
<11+2)
x Σ
2m1id pt(t) ||++|
Σ
2 P,(t)
-2'
(Eq. (59))
N.EL
F.EL
73

---

S (1 + 2e) -s, + lss, x=((r) + 2(1 26)1 Σ
2 P:(1) -8, ||r
feEL
(Triangle Inequality)
< ++)e([(xx -xss|r + 21 xslsr++ |2g x² l1r) 2(1 + 2:)l
Σ
2 P:(t) Is, ||
fiet
(Triangle Inequality)
S1+ ++)=(((l== + 1011::0----0111111--000000000000
xs||r
(Eq. (58))
$1 21)(1 22 0,000000000000000000000000000000
(1) + 2(1 2e) 2 xg | (Lemma H.38)
<1++2) + -000--00000000000000000000-0---0
+|~>*|>>> + 2(1 + 2c) + (())) (Lemma H.39)
5 V2 0 +
By re-scaling and 6, prove the theorem.
I Improving Band-Limited Interpolation Precision in a Smaller Range
In this section, we show that the approximation error of the Fourier interpolation algorithm developed in Section H can be further improved, if we only care about the signal in a shorter time duration [0, (1 T) for e E (0, 1). The main result of this section Theorem I.4.
L1 Control noise
Lemma 111 Let x² = (t)= ux and x(t) = x² + g(t) be our observable signal. Let
N? = (1lg(())) + 8|12"
(t)li)) Let Ci, ,C the Ni-heavy clusters from Definition H. 11 Let S* denotes the set of frequencies f E {Uibieja such that, f E C2 for some i E [[] and
[ r TT-HHOPPF TNP/k.
Let S denotes the set of frequencies
f E such that, f E for some E [1] and
c x H()) T2N//
Then, we have that,
o x + || x²1rr (v2+ 0 +) + O(Vō)
Proof. Following from the fact that /I + 1 (s)) for < 1, we have
NG (119 1 + (1 < Valllole + V8e, ||="
We have that
| - xz |r S || - x² || + ||00 - xs 1|
|gl|r || xz- l llllr + (1 s)Mi,
(61)
where the first step follows from triangle inequality, the second step follows the definition of g, the third step follows from Claim H.12.
74

---

Therefore.
| zs lr + [2 x² 12
x 2S T' 12 g8 |r +
|1.-- x² x21
< | 2ς r + |25 Is. +1+ 2c) x 12-
S (1 26) H()==s))lrr (1+2)
zs. 11r (1+4 2'111
<
(1+ | |
< -
(1++)(( (100+)+)(+++)))))))) ((c))i
$ (v2 +0+++ +0)++++++][++++
where the first step follows from triangle inequality, the second step follows from for any function
: R C, (1 | < || the third step follows from Property I of Lemma H.7 and c < 3 2 1883 the forth step follows from Claim H.12, the fifth step follows from
|H( xr) + (xg xg-)llr /2V||H<> æg)] [[ xz-) the sixth step
follows from Lemma H.21, the seventh step follows from Eq. (49), the last step follows from 50 E1 E2.
Parameters setting By Section C.3 in Chen et al. (2016), we choose parameters for filter function (H),, (f)) as follows:
By Eq. (19) in the proof of Property VI of filter function (H()), ((f)). we need (1 s3
2)) 0(x4) s E, thus we have that min( ---g,,1) 81) 2 ((k))/E.
* In the proof of Property V of filter function ((), we set l ž log(k/8).
In the proof of Lemma I.1, set c)2 < ( 81 )s3. Thus, we have that min (53,
11) 2 or cquivalently min(1-a3 $1/4) 2 2.
A
is
determined by the parameters of filter (H(1), A() in Eq. (20): Combining the setting of 81. f, we should set An N
Ah
S.f TT.
max(OO(k5 ((()//))/(T),
I.2 + a)aproxitiatioi ratio
Corollary 1.2 (Corollary of Theorem H.37). Let x1)())))))
Ey=roe2ali; and x(l)==)==t))) g(l)
be our observable signal where ([ < (1) for a sufficiently small constant cg- Then Procedure
returns set L of ((kk(Eoe)))) frequencees that covers all N2-heavy clusters of x², which uses poly(k, -- 16 , logg samples and pkly(k, c= _,_ .6 " , S5 (10)) log2((T] time.
In particular, for An c-le-' "oly (ogg//))))11/))))/ and and N3 c + 8|12" (t)) with probability 1 2 (kk) for any f with
r- 2f TN2/k.
(62)
there exists an j satisfying
Remark I.3. The proof is similar with the proof of Theorem H.37
Theorem 1.4 ((v2 + apprroxiie Fourier interpolation algorithm with shrinking range). Let
(ttt x" (t) + g(t.. where x" is k-Fourier-sparr signal with frequencies in F}F Let T"
75

---

T(1 - c). Given samples of x over [], we can output y(t) such that with probability at least
1 - --))
lyy -~=011 1r I (v2 + c)llglrr 61|="117 ||- Our algorithm uses p c
log 1 (og((T) samples and poly(k, ,,",,,"",oo,,,,,,,,,,,,,, log'(F time. The output y is poly(k, E -1 c logg(1/)) fourree----ss--spprrsss signal.
Proof. Ne E1(1g(()) (1)l be the heavy cluster parameter.
First, by Lemma H.12, there is set of frequencies S C [k] and Is- (t)
E uje2misit such that JES-
|z x013 S (L+
(63)
Furthermore, each f3 with j E S belongs an - cluster C with respect the filter function H defined in Definition H.6.
By Definition H.ll of heavy cluster, it holds that
Jog H x- +') T
By Definition H.11, we also have |Cyl k- A., where A, is the bandwidth of H. Let A R4, and A k Ars which implies that Cj S [fz A. + A]. Thus, have
1 G1 H (f TN//k.
By Corollary H.22, there is a set of frequencies S C S* and xs(() = E
Uje2ni/st such that
jES
| xs- (1 ( (( xg- 11?
Let g' x 55
Now is enough to recover only Is, instead of x².
By applying Theorem I.2, there is algorithm that outputs set of frequeeniies L R such that, LL (EoEee))) and with probability at least 2 (2)) for any fy with j E S, there is such that,
Iss fi-JsAve AVAT.
We define map p: R + L as follows:
p()) = arg min
1 51 VfER.
JEL
Then, (t) can expressed as
(t) =
Σ 2ze2nlfzt
JES
Σ uye
2 p(ss) p (
=
JES
Σ 2m
Σ
JEL
JES: r(,)=}
where the first step follows from the definition of (t), the last step follows from interchanging the summations.
For each F. E L. by Corollary H.2 with x" = æs, A = AVAT, we have that there exist degree d O(TAV AT + 13 log & + k log 1/5) polynomials Pt(t) corresponding to f L such that,
[c Σ
2nl. p,(t) 6l]xs(t)]lr
(64)
7.eL
76

---

Define the following function family:
F span 2 P VJ L,j e (0, (0.1,...,dd .J].
Note that EjeL f P.(1) EF.
By Claim H.16, for function family F, (
By Lemma H.18, have that, choosing set W of
log( Lld/p))
i..d. samples uniformly at random over duration [0, 7) is (c, P)-
By Lemma H.19 19,9, there is algorithm that rums in O (( log log((/p)) using sam- ples in W, and outputs y (t) E F such that, with probability
(t)
Σ 2 P.(t)lzz & (1 + e)|lx(t)
Σ 2 P,(t)llr
(65)
RELL
FELL
Then by Lemma H.3, we have that there is (kdd) ((kd))Fouries Fourier-sparse signal yt), such that Ilv(t) s/ (T) S 8'
(66)
where 8' > 0 is any positive real number. Thus, can be arbitrarily close to y/-
Moreover, the sparsity of u(t) is kd = RO(TAVAT + log + A: log 1/6)
=
poly(k,e_1, lo,.,__),,,,
Therefore, the total approximation error can be upper bounded as follows:
ly x= ||
1y V'lTT:
Σ
2mild
Pi(1)
||_ + + 2 P.(t) x²
her.
fiet
S (1+ (1+0011))
Σ
2 P.(C) + +|| 2mifi Pi(1) - -zill
J.EL
Ī.EL
<11 28)
Σ
2mifit (e(l)
+|| Σ
2xifi Pi(l) -111
F.EL
J.EL
<11 + 23)(
xs
+
||05- x² (
+ 2(1 +E]l Σ 2 P.(
J.EL
(1 + 2=) - xs
2S x²
) + 0 (z)((
< 22 +
+ ||=*|]r)
$ (1+ (0L-22/2220004+40000----00000110
< (V2 + +
where the first step follows from triangle inequality, the second step follows from Eq. (66), the third step follows from Eq. (65), the forth step follows from Triangle Inequality again, the fifth step follows from Eq. (64), the sixth step follows from Lemma I.1, the seventh step follows from Lemma H.39, and the last step is straightforward.
By re-scaling e and d, we prove the theorem.
J Broader Impact
By cutting the approximation constant from ~ 100 to + 22, our methods could materially shorten scan times in MRI, reduce power consumption compressive sensing devices, and improve fidelity in spectrum-sparse communication systems, thus benefiting healthcare, environmental monitoring,
77

---

and data transmission. At the same time, higher-qualin reconstructions from fewer samples may amplify surveillance capabilities or aid in generating convincingly doctored audio/video; responsible adoption therefore demands privacy safeguards, transparent validation on non-ideal data, and ethical oversight whenever the technology is applied sensitive domains.
78


Reviews:
[{"review_id": "2lQtbQLwav", "reviewer": "Reviewer_aWR8", "summary": "The paper proposes new guarantees of \"interpolation\" of a k-sparse band-limited signal using very few noisy time-domain samples. The 'interpolation' referred to here is signal reconstruction. While prior works exhibit a high approximation ratio of >100, the paper claims to bring it down to 5. This work has connections with a huge literature on sFFT and its own results rely on discrete Fourier set theory. A large number of theoretical results have also been derived. While this reviewer has not been able to verify all theoretical derivations in the Appendix, the primary content in the main file appears to be technically correct.", "questions": "It is not clear if a minimum frequency separation is required here or only k-sparsity suffices.\n\nWhat is the usual order of the four sources of error? Is anyone more dominant the others?\n\nThere are many signals which are multi-band. Would it be a simple extension of this work? Multi-band spectral recovery is a well-investigated topic using atomic norm minimization. Some prior works also employ mild prior knowledge in such cases. See the (separate) works of Weiyu Xu and Gongguo Tang on this.", "limitations": "Lack of numerical experiments makes it difficult to validate the claims.\n\nProbabilistic guarantees, while common in sFFT, are not very practical.\n\nMinimum frequency separation is another bottleneck. It is not very clear how the paper avoids it.\n\nThe conditions on recovery are not mild. Again, using some typical values of realistic SNRs and sparsity, the paper could have shown the practicality of the proposed method via numerical experiments,", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Reducing the approximation ratio from the existing 100 to 5 is remarkable, although this is accomplished under not-s-mild assumptions on SNR, sparsity, on-grid frequencies, and probabilistic guarantees. In this context, the result may also be interpreted as weak because sFFT, while theoretically elegant, is not very practical because of probabilistic guarantees.\n\nThe paper is very detailed and the writing is lucid. I enjoyed going over the main paper. As for the very long appendix, it requires more time to review than the provided NeurIPS review time.\n\nThere are no numerical experiments to validate the claims of signal reconstruction. This is reflected in my low rating on Clarity.\n\nThe paper also does not very well connect itself with ML, the focus of the conference.", "was_revised": true, "final_justification": "Based on the responses provided by the authors, I have increased the score on significance and quality. However, validation concerns because of lack of numerical experiments remain. Sampling theory results requires such validation, in the opinion of this reviewer.", "rebuttal": "Thank you for the insightful review and recommending for acceptance. We are glad that you find our results are remarkable and the paper is well-written. Below, we address your concerns and questions.\n\n## W1: Lack of empirical validation.\nThank you for your question regarding the real-world empirical validation of our algorithms. While empirical validation would be interesting, demonstrating these guarantees experimentally would require a substantial engineering effort and domain‑specific datasets that lie outside the paper’s scope since our primary contribution is intentionally theoretical. We focused on rigorous analysis and proofs. We would like to clarify that our work is purely a theoretical study, which does have a large place in the top machine learning conferences, like NeurIPS, ICLR, and ICML. For instance, NeurIPS accepts papers [1,2,3,4], all of which are entirely theoretical and do not contain any experiments. Moreover, ICLR and ICML also accepted papers [5,6], which are purely theoretical. Our work is similar to theoretical studies like [6], concentrating on the theoretical aspects of Fourier transform.\n\n\n\n\n## W2: Connection with ML conferences. \n\nIn recent years, Fourier transform has also emerged as a powerful tool within machine learning research, inspiring diverse models and algorithms [7,8,9,10,11,12]. Due to its significance in both theory and practice, finding an efficient algorithm to compute the Fourier transform is of utmost importance, especially for machine learning. The most remarkable one is the random feature method [13], which has extensive applications in neural networks [14,15,16].\n\n## Q1: It is not clear if a minimum frequency separation is required here or only k-sparsity suffices. What is the usual order of the four sources of error? Is anyone more dominant the others? \n\nThank you for pointing this out. Yes, consistent with the standard continuous‑SFT literature, our analysis assumes an $\\Omega(1/T)$ minimum separation between any two true frequencies. We might miss this in the condition and will fix it in the revised version.\n\n## Q2: What is the usual order of the four sources of error? Is anyone more dominant the others?\n\nIn prior works, the heavy‑cluster truncation error $E_1$ is always the dominant contributor because it scales as $\\mathcal{N}^4$​. The sampling‑and‑regression error $E_3$ is the next‑largest, growing only linearly with $\\mathcal{N}$, so it can approach, but rarely surpass, $E_1$ when the SNR is low. Polynomial approximation $E_2$ is proportional to the chosen tolerance $\\delta$ and stays much smaller. In our proposed scheme,  all structural errors scale only linearly in $\\mathcal{N}$, so their sizes are determined by the leading constants.  The weighted‑regression term is largest, $E_{3}^{\\text{new}} \\leq (4+\\epsilon)\\mathcal{N}$ . Next comes the energy of frequencies that fail the reinforced cluster condition, $E_{1.5} \\leq (2+\\epsilon)\\mathcal{N}$, followed by the initial heavy‑cluster truncation, $E_{1}^{\\text{new}} \\leq (1+\\epsilon)\\mathcal{N}$.  The polynomial‑approximation error remains proportional to the chosen tolerance $\\delta$ and stays much smaller. Hence the typical hierarchy is $E_{3}^{\\text{new}} \\geq E_{1.5} \\geq E_{1}^{\\text{new}} \\gg E_{2}$.\n\n\n\n## Q3: There are many signals which are multi-band. Would it be a simple extension of this work? Multi-band spectral recovery is a well-investigated topic using atomic norm minimization. Some prior works also employ mild prior knowledge in such cases. See the (separate) works of Weiyu Xu and Gongguo Tang on this.\n\nThank you for pointing out the works on multi-band spectral recovery. We will cite these works in the revised version and discuss the potential extension in the revised version. We believe a detailed, formal treatment of this extension, along with a comparison to atomic‑norm guarantees, is an interesting direction for future work.\n\nWe sincerely thank you for your time and valuable comments. We hope that the above clarifications address your concerns, and we are happy to discuss further if needed.\n\n## Reference\n[1] Alman, J., & Song, Z. Fast attention requires bounded entries. NeurIPS’23. \n\n[2] Sarlos, T., Song, X., Woodruff, D., & Zhang, R. Hardness of low rank approximation of entrywise transformed matrix products. NeurIPS’23.\n\n[3] Dexter, G., Drineas, P., Woodruff, D., & Yasuda, T. Sketching algorithms for sparse dictionary learning: PTAS and turnstile streaming. NeurIPS’23.\n\n[4] Song, Z., Vakilian, A., Woodruff, D., & Zhou, S. On Socially Fair Low-Rank Approximation and Column Subset Selection. NeurIPS’24\n\n[5] Kim, J., & Suzuki, T. Transformers Provably Solve Parity Efficiently with Chain of Thought. In The Thirteenth International Conference on Learning Representations. ICLR’25\n\n[6] Li, X., Song, Z., & Xie, S. Deterministic sparse fourier transform for continuous signals with frequency gap. ICML’25.\n\n[7] Lee, J. D., Shen, R., Song, Z., Wang, M., and Yu, z. Generalized leverage score sampling for neural networks. NeurIPS’20\n\n[8] Choromanski, K. M., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J. Q., Mohiuddin, A., Kaiser, L., Belanger, D. B., Colwell, L. J., and Weller, A. Rethinking attention with performers. InInternational Conference on Learning Representations\n. ICLR’ 2021\n\n[9] Li, Z., Kovachki, N. B., Azizzadenesheli, K., Liu, B., Bhattacharya, K., Stuart, A., and Anandkumar, A. Fourier neural operator for parametric partial differential equations. ICLR’ 21\n\n[10] Yang R, Cao L, YANG J. Rethinking fourier transform from a basis functions perspective for long-term time series forecasting. NeurIPS’24\n\n[11] Alman, J. and Song, Z. Fast rope attention: Combining the polynomial method and fast Fourier transform. arXiv preprint arXiv:2505.11892, 2025\n\n[12] Yu, E., Lu, J., Yang, X., Zhang, G., and Fang, Z. Learning robust spectral dynamics for temporal domain generalization. arXiv preprint arxiv: 2505.12585, 2025\n\n[13] Rahimi, A., & Recht, B. Random features for large-scale kernel machines. NeurIPS'07\n\n[14] Yehudai, G., & Shamir, O. On the power and limitations of random features for understanding neural networks. NeurIPS'19\n\n[15] Frei, S., Chatterji, N. S., & Bartlett, P. L. Random feature amplification: Feature learning and generalization in neural networks. JMLR, 2023.\n\n[16] Sato, R., Yamada, M., & Kashima, H. Random features strengthen graph neural networks. ICDM'21"}, {"review_id": "hDPZgePaSS", "reviewer": "Reviewer_kZRg", "summary": "This paper addresses the problem of interpolating band-limited signals with sparse frequency components from noisy time-domain samples. The authors propose a novel algorithmic framework based on hierarchical frequency decomposition and systematic noise cancellation, to obtain a certain improvements in the approximation constant. Furthermore, the paper introduces a refined variant that achieves an even tighter approximation constant of $ C = 2 + \\omega + c $ on any sub-interval of the time domain. These results represent a substantial improvement over existing work, both in terms of theoretical guarantees and practical relevance.\n\nThe key contributions include:\n1. A high-accuracy algorithm with a provable approximation constant of $ C = 3 + \\sqrt{2} + \\omega $, which is much closer to the information-theoretic optimum than exiting work.\n\n2. Some technical innovations which include an ultra-sensitive frequency estimation method and a refined noise-cancellation analysis.", "questions": "How to extend the theoretical framework to higher-dimensional signals, which would be very interesting.", "limitations": "One may relax the assumptions of exact sparsity and constant SNR. The algorithm may be analysized under approximate sparsity or varying SNR conditions.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper makes several contributions:\n1. The authors provide a rigorous theoretical framework for band-limited signal interpolation, achieving an improvement in the approximation constant.\n\n2. The hierarchical noise cancellation method effectively reduces error accumulation by combining multiple sources of error into a single multiplicative term.\n\n3. The proposed shrinking-range variant demonstrates how spatial slack can be utilized to further improve interpolation accuracy.\n\n4. The results are well-supported by detailed theoretical analyses.\n\n\nWeaknesses.\n\n1. The author use Approximation Ratio. But it seems that the improvement is only for the approximation costant.\n\n2. The paper assumes that the signal is exactly $ k $-sparse in the frequency domain and that the signal-to-noise ratio (SNR) exceeds a constant threshold. These assumptions may not hold in many practical scenarios, where signals often exhibit approximate sparsity or have varying SNR. Relaxing these assumptions would enhance the practical applicability of the results.\n\n3. The proposed algorithm relies on ultra-sensitive frequency estimation and finely tuned filters, which require high numerical precision. In real-world deployments, numerical round-off errors or model mismatches could degrade the performance and erode the stated approximation constants.\n\n4. The analysis and results are restricted to one-dimensional signals. Extending the framework to higher-dimensional settings, such as images or multi-dimensional time-series data, remains an open challenge.\n\n5. The paper focuses on theoretical results and does not provide any numerical experiments.\n\n6. While the authors claim that the algorithm has nearly linear runtime complexity, the dependence on parameters may lead to high computational costs for the large-scale problems. A more detailed analysis of the algorithm's scalability would be useful.", "was_revised": true, "final_justification": "I would like to keep the score.", "rebuttal": "Thank you for the constructive review and recommendation for acceptance. We appreciate your recognition of our rigorous framework, technical contributions, and theoretical analysis. Below, we address the noted weaknesses and questions.\n\n## W1: The notion of approximation ratio\n\nThanks for pointing this out. The approximation ratio is the standard terminology in approximation algorithms, which refers to the factor by which an algorithm's solution deviates from the optimal solution for a given computational problem.  In our setting, it quantifies how much larger the reconstruction error $\\\\|y-x^*\\\\|_T$​ can be, relative to the best achievable error. We will define it clearer in our revised version.\n\n## W2: Assumption on $k$-sparsity in the frequency domain.\n\nThis is an interesting question. In fact, as quoted from [7]: “Many applications rely on the fact that most of the Fourier coefficients of the signals are small or equal to zero, i.e., the signals are (approximately) sparse. Thus it is very natural to study the setting where the Fourier spectrum is approximately $k$-sparse, and it has been studied over the last two decades, see [6,7,8,9,10].\n\n## W3: Numerical issue.\n\nThank you for flagging the potential numerical challenges. Our present work concentrates on the algorithm design and theoretical guarantees. We defer the development of a robust, industrial‑grade implementation to future work.\n\n## W4 & Q1: Extension to high dimension\n\nYes, our present algorithm is formulated for one‑dimensional signals. The main challenge for extending it to high dimension setting is the curse of dimensionality since naively treating a $d$-dimensional signal as a flattened $1$-dimensional signal would inflate both sample and time complexity exponentially in $d$. A more scalable route is to exploit structure, e.g., separable band‑pass filters and tensor‑product sketching, so that each dimension is processed independently before a joint sparse regression stage. This would raise complexity only by a factor polynomial in $d$. Whether the same order of constant factor accuracy can be preserved requires a more detailed analysis. Formalising this extension is an interesting direction for future work.\n \n## W5: Empirical validation\nThank you for your question regarding the real-world empirical validation of our algorithms. While empirical validation would be interesting, demonstrating these guarantees experimentally would require a substantial engineering effort and domain‑specific datasets that lie outside the paper’s scope since our primary contribution is intentionally theoretical. We focused on rigorous analysis and proofs. We would like to clarify that our work is purely a theoretical study, which does have a large place in the top machine learning conferences, like NeurIPS, ICLR, and ICML. For instance, NeurIPS accepts papers [1,2,3,4], all of which are entirely theoretical and do not contain any experiments. Moreover, ICLR and ICML also accepted papers [5,6], which are purely theoretical. Our work is similar to theoretical studies like [6], concentrating on the theoretical aspects of Fourier transform.\n\n## W6: Detail analysis of scalability\n\nSince our focus is on developing the high-accuracy algorithm, we didn’t include the detailed runtime analysis of some less important parameters. In fact, the major runtime cost of our high‑accuracy algorithm come from sketch distillation and solving weighted regression. With carefulled analysis, in sketch distillation first, our algorithm repeats the constant‑factor loop just $\\Theta(1/\\epsilon)$ times so every candidate signal’s energy is preserved within a $(1+\\epsilon)$ factor, incurring only $\\Theta(\\epsilon^{-1} k)$ arithmetic operations and samples. The weighted regression involves a $k \\times k$ weighted least‑squares system, which costs $k^\\omega$ time using fast matrix multiplication where $\\omega$ is the exponent of matrix multiplication and $\\omega \\approx 2.37$. Thus the $\\mathrm{poly}(\\epsilon^{-1},k)$ can be roughly expressed as $O(\\epsilon^{-1}k^\\omega)$. Evaluating the algorithm’s scalability in real‑world deployments is an engaging avenue for future work. Thank you for raising this point.\n\nWe sincerely thank you for your time and valuable comments. We hope that the above clarifications address your concerns, and we are happy to discuss further if needed.\n\n## Reference\n[1] Alman, J., & Song, Z. Fast attention requires bounded entries. NeurIPS’23. \n\n[2] Sarlos, T., Song, X., Woodruff, D., & Zhang, R. Hardness of low rank approximation of entrywise transformed matrix products. NeurIPS’23.\n\n[3] Dexter, G., Drineas, P., Woodruff, D., & Yasuda, T. Sketching algorithms for sparse dictionary learning: PTAS and turnstile streaming. NeurIPS’23.\n\n[4] Song, Z., Vakilian, A., Woodruff, D., & Zhou, S. On Socially Fair Low-Rank Approximation and Column Subset Selection. NeurIPS’24\n\n[5] Kim, J., & Suzuki, T. Transformers Provably Solve Parity Efficiently with Chain of Thought. In The Thirteenth International Conference on Learning Representations. ICLR’25\n\n[6] Li, X., Song, Z., & Xie, S. Deterministic sparse fourier transform for continuous signals with frequency gap. ICML’25.\n\n[7] Indyk, P., & Kapralov, M. Sample-optimal Fourier sampling in any constant dimension. FOCS’14\n\n[8] Price, E., & Song, Z. A robust sparse Fourier transform in the continuous setting. FOCS’15\n\n[9] Hassanieh, H., Indyk, P., Katabi, D., & Price, E. Nearly optimal sparse Fourier transform. STOC’12.\n\n[10] Hassanieh, H., Indyk, P., Katabi, D., & Price, E. Simple and practical algorithm for sparse Fourier transform. SODA’12"}, {"review_id": "ALb4wIjsok", "reviewer": "Reviewer_yu3y", "summary": "This paper addresses the problem of interpolating a band-limited signal from a small number of noisy samples. It presents a new algorithm with a significantly improved approximation ratio compared to previous methods, breaking the long-standing barrier of a constant factor greater than 100. This paper propose ultra-high sensitivity frequency estimation and hierarchical noise cancellation analysis, and combine these two techniques to propose an algorithm that achieves continuous interpolation (3+√2+ε)-approximation guarantees, which is a significant improvement over the previous best result. A variant of the above algorithm is also proposed, which can approximate the signal by (√2+ε+c) on any subinterval. Overall, this paper provides a significant advancement in the field of band-limited interpolation, offering a new framework and techniques that can be applied to other sparse recovery problems.", "questions": "1. Can the noise tracking and filter family structure proposed in extend to higher dimensions? What are the obstacles?\n2. The paper mentioned that the running time of the algorithm is close to linear. Can a more detailed computational complexity analysis be provided, including the time complexity of different steps, and the overall complexity as a function of signal length, sparsity, and frequency range?\n3. What are the effects of different parameters such as frequency gap, SNR, etc. on the performance of the algorithm?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper delivers the first polynomial-time algorithm achieving an approximation ratio strictly below 5 for noisy band-limited interpolation—breaking the longstanding constant-factor barrier of ≈ 100 in prior work—and further refines this to (3 + √2 + ε) and even (√2 + ε + c) under a “shrinking-range” regime.\n2. Definitions for band-limited interpolation and discrete Fourier set-query are crisply stated, grounding the reader before diving into algorithmic details.\n3. Novel two-stage composition. Showing that a two-stage well-balanced sampler composes into a single uniform distribution is both subtle and powerful, enabling the sharper (1 + ε) set-query guarantees.\nWeaknesses:\n1. The article has some appendix dependencies. Key formal proofs (e.g., Theorems H.20 and I.4) are deferred to later sections, which may interrupt the flow for readers seeking immediate understanding of the guarantees\n2. The high-level pipeline (filtering→frequency estimation→polynomial approximation→regression) parallels prior works (e.g., Chen et al. 2016); the novelty lies in tightening constants rather than introducing wholly new paradigms.\n3. While theoretical constants shrink dramatically, there are no experiments demonstrating performance on synthetic or real data to confirm that the improved ratios translate to practice.", "was_revised": true, "final_justification": "Based on the content of the article and the author's response, I have a clearer understanding of this job. The author gave reasonable and detailed responses on Empirical validation, dimension expansion, running time analysis and the influence of some parameters. However, some detailed proof contents require the author to provide appendix contents for further reading. Although this work is purely theoretical research, through rigorous and reasonable theoretical analysis, it solves the problem of multiplicative noise elimination >100 and reduces the approximation ratio to about 5, which shows its importance in this task. Therefore, the scores in terms of Quality and Significance have been modified from 3 to 4, and the Rating has been changed from \"Borderline accept\" to \"accept\".", "rebuttal": "We thank the reviewer for the thoughtful comments and the recommendation for acceptance.\nWe appreciate that you highlight the first polynomial‑time algorithm with an improved approximation ratio, the clear definitions and presentation, and the subtle two‑stage composition that enables the sharper bound on each stage. Below, we address the weakness and questions.\n\n## W1: Proofs are deferred to Appendix.\nTo keep the main text streamlined, we placed the detailed proof in the appendix while keeping every theorem’s key steps and proof sketch in the technique overview. We will try to improve the presentation and readability of the algorithms in the revised version. Thanks for pointing this out.\n\n## W2: Novelty\n\nThanks for the question. We would like to clarify the novelty and contribution of our paper. Although the high‑level pipeline resembles prior work, our multiplicative noise‑cancellation analysis breaks the long‑standing $>100$ constant barrier, cutting the worst‑case approximation ratio to $\\approx 5$ within a small factor of the information‑theoretic optimum. Achieving this required new, tighter energy bounds and a refined sketch‑distillation step that eliminates the additive‑error accumulation present in all earlier methods. This, in turn, demands a more delicate control of error propagation across stages, which we believe is nontrivial.\n\n\n## W3: Empirical validation\nThank you for your question regarding the real-world empirical validation of our algorithms. While empirical validation would be interesting, demonstrating these guarantees experimentally would require a substantial engineering effort and domain‑specific datasets that lie outside the paper’s scope since our primary contribution is intentionally theoretical. We focused on rigorous analysis and proofs. We would like to clarify that our work is purely a theoretical study, which does have a large place in the top machine learning conferences, like NeurIPS, ICLR, and ICML. For instance, NeurIPS accepts papers [1,2,3,4], all of which are entirely theoretical and do not contain any experiments. Moreover, ICLR and ICML also accepted papers [5,6], which are purely theoretical. Our work is similar to theoretical studies like [6], concentrating on the theoretical aspects of Fourier transform.\n\n\n## Q1: Extension to high dimension\n\nOur present algorithm is formulated for one‑dimensional signals. The main challenge for extending it to high dimension setting is the curse of dimensionality since naively treating a $d$-dimensional signal as a flattened $1$-dimensional signal would inflate both sample and time complexity exponentially in $d$. A more scalable route is to exploit structure, e.g., separable band‑pass filters and tensor‑product sketching, so that each dimension is processed independently before a joint sparse regression stage. This would raise complexity only by a factor polynomial in $d$. Whether the same order of constant factor accuracy can be preserved requires a more detailed analysis. Formalising this extension is an interesting direction for future work.\n\n## Q2: Detailed run time analysis\n\nThanks for the question. Since our focus is on developing the high-accuracy algorithm, we didn’t include the detailed runtime analysis of some less important parameters. In fact, the major runtime cost of our high‑accuracy algorithm come from sketch distillation and solving weighted regression. With carefulled analysis, in sketch distillation first, our algorithm repeats the constant‑factor loop just $\\Theta(1/\\epsilon)$ times so every candidate signal’s energy is preserved within a $(1+\\epsilon)$ factor, incurring only $\\Theta(\\epsilon^{-1} k)$ arithmetic operations and samples. The weighted regression involves a $k \\times k$ weighted least‑squares system, which costs $k^\\omega$ time using fast matrix multiplication where $\\omega$ is the exponent of matrix multiplication and $\\omega \\approx 2.37$. Thus the $\\mathrm{poly}(\\epsilon^{-1},k)$ can be roughly expressed as $O(\\epsilon^{-1}k^\\omega)$.\n\n\n## Q3: Effects of parameters\nOur guarantees depend on the noise level only through the composite term $\\mathcal{N}^2 = \\\\|g\\\\|_T^2+\\delta \\\\|x^*\\\\|_T^2$. Hence SNR enters linearly: doubling the noise variance roughly doubles every error term. With respect to frequency gap, the theory requires a minimum separation of $\\eta \\geq \\Omega(1/T)$ to avoid aliasing. Hence the $\\log(FT)$ factor in runtime can be replaced with $\\log(F/\\eta)$.\n\nWe sincerely thank you for your time and valuable comments. We hope that the above clarifications address your concerns, and we are happy to discuss further if needed.\n\n[1] Alman, J., & Song, Z. Fast attention requires bounded entries. NeurIPS’23. \n\n[2] Sarlos, T., Song, X., Woodruff, D., & Zhang, R. Hardness of low rank approximation of entrywise transformed matrix products. NeurIPS’23.\n\n[3] Dexter, G., Drineas, P., Woodruff, D., & Yasuda, T. Sketching algorithms for sparse dictionary learning: PTAS and turnstile streaming. NeurIPS’23.\n\n[4] Song, Z., Vakilian, A., Woodruff, D., & Zhou, S. On Socially Fair Low-Rank Approximation and Column Subset Selection. NeurIPS’24\n\n[5] Kim, J., & Suzuki, T. Transformers Provably Solve Parity Efficiently with Chain of Thought. In The Thirteenth International Conference on Learning Representations. ICLR’25\n\n[6] Li, X., Song, Z., & Xie, S. Deterministic sparse fourier transform for continuous signals with frequency gap. ICML’25."}, {"review_id": "ahg40DWScI", "reviewer": "Reviewer_jo7g", "summary": "This paper discusses the estimation of $k$-sparse signals, defined as continuous signals over $x: [0,T] \\rightarrow {\\mathbb C}$ which are sums of $k$ frequencies, i.e., $x(t) = \\sum_{j=1}^k v_j e^{2\\pi i f_j t}$ for some set of frequencies $\\\\{f_j\\\\}_{j=1}^k$.\n \nWe are to estimate a $k$-sparse signal $x^\\*(t)$ from noisy samples $\\\\{x^\\*(t_j) + g(t_j)\\\\}_{j=1}^N$. The frequencies $f_j$ are unknown, but we are allowed to choose the sampling points $t_j$. \n\nThe authors propose an estimation algorithm and prove that the generated estimate $y(t)$ satisfies\n$$ \\\\|y - x^\\*\\\\|_T \\\\le C \\\\|g\\\\|_T + \\\\delta \\\\|x^\\*\\\\|_T $$\nwhere $\\\\|\\\\cdot\\\\|_T$ is the $L_2$ norm on $[0,T]$, and $\\delta>0$ is a user-selected accuracy parameter determining the time complexity of the algorithm and the number of samples it requires. Such results have previously been shown; this papers' contribution is in a significant reduction of the constant $C$, from around 100 to below 5.", "questions": "Please address the comments above regarding clarity of the paper, making especially certain that terms are defined and that the problem context is addressed early in the text. I have no other requests from the authors.", "limitations": "n/a", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Caveat: I have background in classical sampling theory but with no familiarity with sparse Fourier signals or the theory of sampling such signals. My comments are therefore mostly about the paper's presentation and clarity for someone not within this specific field. The results in the paper look worthwhile, impressive, and valuable, but I have no way of judging their importance or novelty. Hence my review is submitted with relatively low confidence.\n\nThat said, the results in the paper appear strong and worthwhile, significantly reducing the bounds on sampling error guarantees. I believe the paper is worthy of publication.\n\nThe main weakness from my point of view is that the authors do not always properly define the setting and terminology before using it. Especially for a big-tent conference such as NeurIPS, such definitions are very important. In particular, I was able to formulate the summary above only after reading about four pages of the manuscript, during which I was constantly asking myself questions about the setting: are we talking about discrete or continuous signals? do we have a single measurement $x^\\*(t) + g(t)$, or multiple noise realizations? and other questions, detailed below. Some of these questions were answered only in Section 1.2 (or even later), but this appears only on p.4, after the background and main results have already been stated. In particular:\n\n1. There are many versions of Fourier transforms (discrete/continuous, finite-time/infinite-time, 1-dimensional/$d$-dimensional) and it is unclear for a long time which version you are talking about: in some cases an integral over $x(t)$ is performed (e.g. L.33) but in other cases it is stated that $x(t)$ is a discrete signal with $n$ values (L.141). In some cases $t$ is one-dimensional (L.97) and in other cases it is multi-dimensional (integral over $[0,T]^d$ in L.33).\n1. \"Band-limited\", in my experience, means that $\\hat{x}^*(f) = 0$ for all $|f| > f_c$, without any further sparsity requirements for $|f| \\le f_c$. Though the sense meant here is given in Def. 1.1, I think it would be helpful to the reader if the Fourier sparsity assumption were stated in the title and abstract. Otherwise, a reader such as myself gets a decidedly different impression of the fundamental topic of the paper (and even the degree to which it is related to my field of study).\n1. The form of measurements from which the estimate is generated is never explicitly specified. I would state explicitly (and early) that algorithmic approaches require observing samples of $y(t)$, with the number of samples required related to the desired accuracy. Again, this becomes clear implicitly but only in L.46, after the problem definition.\n1. The band limit $F$ is mentioned in L.43 but only (implicitly) defined in L.62.\n1. Theorem 1.3 is a simplified version of the actual theorem, given in the Appendix. While it's fine to put the proof in the Appendix, I think it is desirable to have a precise statement of the theorem in the main text. In particular, the fact that the claim holds only with high probability is stated in the appendix but missing from the main text.\n\nI further encourage the authors to correct the following small notation errors:\n1. L.32: should be $\\\\|x\\\\|_T^2$ and not $|x|_T^2$.\n1. L.125: For consistency, it would be better to use $\\\\|g(t)\\\\|_S^2$ instead of $\\\\|g(t)\\\\|_W^2$ (especially since $w$ is used with a different meaning in the next line).\n1. L.146: I think it would be clearer to state $\\sup_t |x(t)|^2 \\le k \\\\|x\\\\|_T^2$, and avoid the definition of $R$.\n1. L.154: The symbol $\\circ$ is not defined.\n1. L.314: \"simultaneously\" should be \"which simultaneously\".\n1. L.326-327: \"the open\" should be \"an open question\".", "was_revised": true, "final_justification": "no change in assessment", "rebuttal": "We thank the reviewer for the thoughtful comments and the recommendation for acceptance. We appreciate your recognizing our results are strong and worthwhile. Below, we address the weakness and questions.\n\n## W1: Version of Fourier transform\nThank you for the question. Our main results focus on the one‑dimensional continuous sparse Fourier transform on a regular grid. When discussing techniques, however, we sometimes describe them in a dimension‑agnostic way, which may have caused confusion. In the revision we will clarify this distinction, tighten the wording, and ensure the notation remains consistent throughout.\n## W2: The notion of ‘’band-limited’’\n\nThank you for raising this point. In our paper, “band‑limited signal” specifically means a signal that is both band‑limited and $k$-sparse in the Fourier domain. We will clarify this in the revision by consistently writing ‘’$k$-sparse band‑limited signal.”\n\n## W3 & W4: The form of measurements and the band limit $F$ are mentioned implicitly in the text.\n\nThanks for pointing out this. We will define these notations more in a clearer way.\n\n## W5: The informal version of theorems.\n\nFor brevity and readability, we included only an informal version of main theorems in the main text. We agree, however, that more precise statements should appear there. In the revision, we will explicitly state that the guarantee holds with high probability in the main theorems.\n\n## Typos\n\nThanks for spotting the typos. We will fix them in the revised version.\n\nWe sincerely thank you for your time and valuable comments. We hope that the above clarifications address your concerns, and we are happy to discuss further if needed."}]

Author rebuttal:

Meta-review: This paper addresses the problem of interpolating band-limited signals with sparse frequency components from noisy time-domain samples. 
All reviewers basically appreciate that the authors provide a rigorous theoretical framework for band-limited signal interpolation, achieving an improvement in the approximation constant.
During the rebuttal period, the concerns from the reviewers are mostly resolved.

There is one major concern remains:
Reviewer aWR8 & Reviewer yu3y & Reviewer kZRg  : Lack of empirical validation or numerical results
Even for a theoretical work, empirical validation is also important. The AC strongly suggests that the authors need to provide some empirical results to validate the proposed method since for the references the authors cited (e.g.,  the gounp (Hassanieh, H., Indyk, P., Katabi, D., & Price), the authors have also employed their algorithms for practical use.
So, the authors are suggested to validate their theoretical methods.

Besides, the concerns on the use of notations & terminologies, raised by Reviewer jo7g, must be clearly clarified in the revised version.
 
Overall, based on the reviewers' responses, this work will be suggested to be accepted.
Decision: Accept (poster)