# Quartic Samples Suffice for Fourier Interpolation

Zhao Song<EMAIL_ADDRESS>Adobe Research.  Baocheng Sun
<EMAIL_ADDRESS>Weizmann Institute of Science.  Omri Weinstein
<EMAIL_ADDRESS>The Hebrew University and Columbia University. Ruizhe
Zhang<EMAIL_ADDRESS>The University of Texas at Austin.

We study the problem of interpolating a noisy Fourier-sparse signal in the
time duration $[0,T]$ from noisy samples in the same range, where the ground
truth signal can be any $k$-Fourier-sparse signal with band-limit $[-F,F]$.
Our main result is an efficient Fourier Interpolation algorithm that improves
the previous best algorithm by [Chen, Kane, Price, and Song, FOCS 2016] in the
following three aspects:

  * •

The sample complexity is improved from $\widetilde{O}(k^{51})$ to
$\widetilde{O}(k^{4})$.

  * •

The time complexity is improved from $\widetilde{O}(k^{10\omega+40})$ to
$\widetilde{O}(k^{4\omega})$.

  * •

The output sparsity is improved from $\widetilde{O}(k^{10})$ to
$\widetilde{O}(k^{4})$.

Here, $\omega$ denotes the exponent of fast matrix multiplication. The state-
of-the-art sample complexity of this problem is $\sim k^{4}$, but was only
known to be achieved by an _exponential-time_ algorithm. Our algorithm uses
the same number of samples but has a polynomial runtime, laying the groundwork
for an efficient Fourier Interpolation algorithm.

The centerpiece of our algorithm is a new sufficient condition for the
frequency estimation task—a high signal-to-noise (SNR) band condition—which
allows for efficient and accurate signal reconstruction. Based on this
condition together with a new structural decomposition of Fourier signals
(Signal Equivalent Method), we design a cheap algorithm to estimate each
“significant” frequency within a narrow range, which is then combined with a
signal estimation algorithm into a new Fourier Interpolation framework to
reconstruct the ground-truth signal.

###### Contents

  1. 1 Introduction
    1. 1.1 Related works
  2. 2 Technical Overview
    1. 2.1 High-level approach
    2. 2.2 Our techniques for frequency estimation
      1. 2.2.1 Two-level sampling for significant samples generation
      2. 2.2.2 Energy estimation and Signal Equivalent Method
      3. 2.2.3 Time-domain concentration of filtered signals
    3. 2.3 Our techniques for Fourier Interpolation
  3. 3 Organization
  4. A Preliminaries
  5. B Energy Bounds of Fourier Sparse Signals
  6. C Filter in Frequency Domain
    1. C.1 Frequency domain filter construction
    2. C.2 Frequency domain covering
  7. D Hashing the Frequencies
    1. D.1 HashToBins procedure
    2. D.2 Frequency isolation
    3. D.3 Large offset event
  8. E Filter in Time Domain
    1. E.1 Time domain filter construction
    2. E.2 Normalization factor of the filter
    3. E.3 Fluctuation bound
    4. E.4 Energy preserving of the time domain filter
  9. F Ideal Filter Approximation
    1. F.1 Swap the order of filtering
    2. F.2 Approximation error bounds
  10. G Concentration Property of the Filtered Signal
  11. H Energy Bound for Filtered Fourier Sparse Signals
    1. H.1 Energy bound for untruncated ideally filtered signals
    2. H.2 Energy bound for filtered signals
    3. H.3 Technical claim
  12. I Local-Test Signal
    1. I.1 Ideal local-test signal
    2. I.2 Ideal post-truncated local-test signal
    3. I.3 Energy bound for local-test signals
  13. J Empirical Energy Estimation
    1. J.1 Sampling and reweighing
    2. J.2 Energy estimation for Fourier-sparse signals and filtered signals
    3. J.3 Partial energy estimation for filtered signals and local-test signals
    4. J.4 Technical lemmas
  14. K Generate Significant Samples
    1. K.1 Energy estimation for noisy signals
    2. K.2 Significant sample generation for a single bin
    3. K.3 Significant sample generation for multiple bins
    4. K.4 Technical claims
  15. L Frequency Estimation
    1. L.1 Frequency estimation via significant samples
    2. L.2 Simultaneously estimate frequencies for different bins
    3. L.3 Vote distributions in ArySearch
  16. M Signal Reconstruction
    1. M.1 Preliminary
    2. M.2 Heavy cluster
    3. M.3 Fourier set query
    4. M.4 High signal-to-noise ratio band approximation
    5. M.5 Fourier interpolation with constant success probability
    6. M.6 Min-of-medians signal estimator
    7. M.7 Main algorithm for Fourier interpolation
  17. N Structure of Our Fourier Interpolation Algorithm

##  1 Introduction

Fourier transforms are the backbone of signal processing and engineering, with
profound implications to nearly every field of scientific computing and
technology. This is primarily due to the discovery of the well-known Fast
Fourier Transform (FFT) algorithm [9], which is ubiquitous in engineering
applications, from image and audio processing to fast integer multiplication
and optimization. The classic FFT algorithm of [9] computes the _Discrete
Fourier Transform_ (DFT) of a length-$n$ vector $x$, where both the time and
frequency domains are assumed to be discrete. This algorithm takes $O(n)$
samples in the time domain, and constructs $\widehat{x}=\mathrm{DFT}(x)$ in
$O(n\log(n))$ time. The discrete setting of DFT limits its applicability in
two main aspects: The first one is that many real-world signals are continuous
(analog) by nature; Secondly, many real-world applications (such as image
processing) involve signals which are _sparse_ in the frequency domain (i.e.,
$\|\widehat{x}\|_{0}=k\ll n$) [18, 32, 27]. This feature underlies the
_compressed sensing_ paradigm [8], which leverages sparsity to obtain
_sublinear_ algorithms for signal reconstruction, with time and sample
complexity depending only on the sparsity $k$. Unfortunately, the continuous
case cannot simply be reduced to the discrete case via standard discretization
(i.e., using a sliding-window function), as it “smears out” the frequencies
and blows up the sparsity, which motivates a more direct approach for the
continuous problem [26].

The study of Fourier-sparse signals dates back to the work of Prony in 1795
[11], who studied the problem of exact recovery of the “ground-truth” signal
$x$ in the vanilla _noiseless_ setting. By contrast, the realistic setting of
reconstruction from _noisy-samples_ [26] is a different ballgame, and exact
recovery is generally impossible [23]. In the _Fourier Interpolation_ problem,
the ground-truth signal

$\displaystyle
x^{*}(t)=\sum_{j=1}^{k}v_{j}e^{2\pi\mathbf{i}f_{j}t},~{}~{}v_{j}\in\mathbb{C},f_{j}\in[-F,F]~{}\forall
j\in[k],$

is a $k$-Fourier-sparse signal with bandlimit $F$. Given noisy access to the
ground truth $x(t)=x^{*}(t)+g(t)$ in limited time duration $t\in[0,T]$ (which
means that we need to recover $x^{*}(t)$ by taking samples from $x(t)$), the
goal is to reconstruct a $\widetilde{k}$-Fourier-sparse signal $y(t)$ (i.e.,
$y(t)=\sum_{j=1}^{\widetilde{k}}\widetilde{v}_{j}e^{2\pi\mathbf{i}\widetilde{f}_{j}t}$
for some $\widetilde{v}_{j}\in\mathbb{C},\widetilde{f}_{j}\in[-F,F]$ for all
$j\in[\widetilde{k}]$) such that

$\displaystyle\|y(t)-x^{*}(t)\|_{T}^{2}\leq
c(\|g\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2})$

holds for some $c=O(1)$, where the $T$-norm of any function
$f:\mathbb{R}\rightarrow\mathbb{C}$ is defined as

$\displaystyle\|f(t)\|_{T}^{2}:=\frac{1}{T}\int_{0}^{T}|f(t)|^{2}\mathrm{d}t.$

We note that it is not necessary for $y(t)$’s frequencies and magnitudes
$(\widetilde{f}_{j},\widetilde{v}_{j})$ being close to the ground-truth signal
$x^{*}(t)$’s frequencies and magnitudes $({f}_{j^{\prime}},{v}_{j^{\prime}})$.

Prior to this work, the state-of-the-art algorithm for the Fourier
interpolation problem was given by [5], which achieves $\widetilde{O}(k^{51})$
sample complexity, $\widetilde{O}(k^{10\omega+40})$ running time,
$\widetilde{O}(k^{10})$ output sparsity, and $c\geq 2000$ approximation ratio.
In [30], the approximation ratio was improved to $\approx 1+\sqrt{2}$, but the
sample complexity remained large, and runtime remained slow. For calibration,
we note that $o(k^{4})$ sample complexity for Fourier interpolation is not
known to be achievable even with _exponential_ decoding time. In this work, we
focus on improving the _efficiency_ of [5]’s algorithm across all aspects: (i)
runtime, (ii) sample complexity, and (iii) output-sparsity. Our main result
is:

References | Samples | Time | Output Sparsity
---|---|---|---
[5] | $\widetilde{O}(k^{51})$ | $\widetilde{O}(k^{10\omega+40})$ | $\widetilde{O}(k^{10})$
[6, 30] | $\widetilde{O}(k^{4})$ | $\exp(k^{3})$ | $k$
Ours (Theorem 1.1) | $\widetilde{O}(k^{4})$ | $\widetilde{O}(k^{4\omega})$ | $\widetilde{O}(k^{4})$
Table 1: Summary of the results. All the algorithms obtain $O(1)$
approximation ratio. We use $\omega$ to denote the exponent of matrix
multiplication, currently $\omega\approx 2.373$ [33, 1].

######  Theorem 1.1 (Main Theorem).

Let $x(t)=x^{*}(t)+g(t)$, where $x^{*}(t)$ is $k$-Fourier-sparse signal with
frequencies in $[-F,F]$. Given samples of $x(t)$ over $[0,T]$, there is an
algorithm that uses

$\displaystyle k^{4}\log(FT)\cdot\mathrm{poly}\log(k,1/\delta,1/\rho)$

samples, runs in

$\displaystyle k^{4\omega}\log(FT)\cdot\mathrm{poly}\log(k,1/\delta,1/\rho)$

time, and outputs a $k^{4}\cdot\mathrm{poly}\log(k/\delta)$-Fourier-sparse
signal $y(t)$ s.t with probability at least $1-\rho$,

$\displaystyle\|{y(t)-x^{*}(t)}\|_{T}\lesssim\|{g}(t)\|_{T}+\delta\|{x^{*}}(t)\|_{T}.$

###  1.1 Related works

##### Sparse Fourier transform in the discrete setting

The Fourier transform $\widehat{x}\in\mathbb{C}^{N}$ is a vector of length
$N$. The goal of a sparse DFT algorithm is, given a bunch of samples $x_{i}$
in the time domain and the sparsity parameter $k$, to output a $k$-Fourier-
sparse signal $x^{\prime}$ with the $\ell_{2}/\ell_{2}$-guarantee

$\displaystyle\|\widehat{x}^{\prime}-\widehat{x}\|_{2}~{}\lesssim~{}\min_{k\text{-sparse}~{}z}\|z-\widehat{x}\|_{2}.$

There are two different lines of work solving the above problem. One line [12,
13, 14, 17, 16, 20, 21] is carefully choosing samples (via hash function) and
obtaining sublinear sample complexity and running time. The other line [10,
28, 3, 15, 24] is taking _random_ samples (via RIP property [10] or others)
and paying sublinear sample complexity but nearly linear running time.

##### Sparse Fourier transform in the continuous setting

[26] defined the sparse Fourier transform in the continuous setting. It shows
that as long as the sample duration $T$ is large enough compared to the
frequency gap $\eta$, then there is a sublinear time algorithm that recovers
all the frequencies up to certain precision and further reconstructs the
signal. [19] improves and generalize several results in [26]. In particular,
[26] only works for one-dimensional continuous Fourier transform, and [19]
generalizes it to $d$-dimensional Fourier transform. In order to convert the
tone estimation guarantee to signal estimation guarantees, [26] provides a
positive result which shows $T=O(\log^{2}(k)/\eta)$ is sufficient, and [23]
shows a lower bound result where $T=\Omega(1/\eta)$. [29] asked an open
question about whether this gap can be closed. [19] made positive progress on
that problem by providing a new upper bound which is $T=O(\log(k)/\eta)$.

From the negative side, [23] shows that in order to show tone
estimation111Tone refers to a (frequency, coefficient) pair in [26]. E.g.,
$(f_{i},v_{i})$ is a tone of the signal
$x(t)=\sum_{i=1}^{k}v_{i}e^{2\pi\mathbf{i}f_{i}t}$. And tone estimation means
estimating each $(f_{i},v_{i})$ precisely., we have to pay a lower bound in
sample duration $T$. In [26], it shows that once we have tone estimation, we
can obtain a signal estimation guarantee. Since [26] and [23], there is an
interesting question about whether we can reconstruct the signal without
having a tone estimation guarantee, which is defined as the Fourier
interpolation problem. [5] shows a positive answer to this problem. They
provide a polynomial time algorithm to solve this problem. However, both
sample complexity and running time in [5] have a huge polynomial factor in
$k$. The major goal of our work is to significantly improve those polynomial
factors.

##  2 Technical Overview

###  2.1 High-level approach

The high-level approach of Fourier Interpolation (also Fourier Signal
reconstruction) has two steps: frequency estimation and signal estimation
(also called signal recovery or Fourier set query). This work mainly
contributes to the first frequency estimation step.

##### Filters and HashToBins

The core technique in Fourier sparse recovery and interpolation algorithms is
filtering. There are two kinds of filters we are using. The first filter
function applied to the signal is $H(t)$ (Figure 1a), which is the bounded
band limit approximation of the rectangular window function
$\mathrm{rect}_{T}(t)$. Intuitively, since the time duration is restricted to
$[0,T]$, we should view the ground truth signal as
$x^{*}(t)\cdot\mathrm{rect}_{T}(t)$. However, handling
$\widehat{\mathrm{rect}}_{T}(f)$ is not easy due to its unbounded support in
the frequency domain. Therefore, we use $H(t)$ instead, which truncates the
frequency domain of $\mathrm{rect}_{T}(t)$ and makes the analysis much easier.

Another kind of filters we use is $G^{(j)}_{\sigma,b}(t)$ (Figure 1b), which
“isolates” the signal through the procedure HashToBins and extracts the one-
cluster signal in the $j$-th bin. More specifically, HashToBins divides the
frequency domain into $B=O(k)$ bins. We can show that with high probability
over the randomized hashing function, each bin contains a single cluster of
frequencies. Hence, in the following frequency estimation step, we can just
focus on recovering the frequency of a one-cluster _filtered signal_ in each
bin $j\in[B]$:

$\displaystyle z_{j}(t)=(x\cdot H)(t)*G^{(j)}_{\sigma,b}(t).$

(a) Time domain filter $H(t)$. (b) Frequency domain filter
$\widehat{G}_{\sigma,b}^{(j)}(f)$ for the $j$-th bin.

Figure 1: Time and frequency domain filters.

##### Frequency Estimation

This step is the main focus on this work. To estimate the frequencies, our
algorithm has two levels. The first level generates significant samples of the
_local-test signal_ :

$\displaystyle d_{z}(t)=z(t)e^{2\pi\mathbf{i}f^{*}\beta}-z(t+\beta),$

where $z(t)=z_{j}(t)$ is the filtered signal in the $j$-th bin and $\beta$ is
a perturbation parameter. A time point $\alpha\in[0,T]$ is defined to be
significant with respect to the target frequency $f^{*}$ if $|d_{z}(\alpha)|$
is small. In this case, $z(\alpha+\beta)/z(\alpha)$ is a good approximation of
$e^{2\pi\mathbf{i}f^{*}\beta}$,which further implies the target frequency
$f^{*}$. The second level is a searching algorithm that iteratively estimates
the target frequency $f^{*}$. In each iteration, it calls the significant
sample generation algorithm and uses the significant sample to narrow the
possible range of the target frequency until reaching the desired accuracy.
Based on the two-level strategy, we design an efficient, high-accuracy
frequency estimation algorithm, improving the time complexity, sample
complexity, and the estimation error of the frequency estimation algorithms in
previous works [5, 7]. The theorem is stated as follows.

######  Theorem 2.1 (Frequency estimation, Informal version of Theorem L.2).

There exists an algorithm takes $O(k^{2}\log(1/\delta)\log(FT))$ samples, runs
in $O(k^{2}\log(1/\delta)\log^{2}(FT))$ time, returns a set $L$ of $O(k)$
frequencies such that with probability $1-\rho_{0}$, for any “important
frequency” $f$, there exists an $\widetilde{f}\in L$ satisfying

$|f-\widetilde{f}|\lesssim\Delta,$

where $\Delta=k\cdot|\mathrm{supp}(\widehat{H})|$, where $\widehat{H}$ is the
Fourier transform of $H$.

##### Signal Estimation

In signal estimation, a set of estimated frequencies of $y(t)$ has been found,
and it remains to interpolate the signal under these frequencies. This is
often done via _set-query_ techniques [25]. This step is not the focus of this
paper, and more discussions can be found in [5, 30]. 222We stress that this
paper is self-contained and we provide all the technical details of signal
estimation in Section M.

###  2.2 Our techniques for frequency estimation

In the frequency estimation part, there are two central questions that need to
be answered:

  1. 1.

_Which frequencies or hashing bins are worth recovering?_

  2. 2.

_How to recover a key frequency in a bin?_

Our answer to these questions substantially deviates from previous works, as
we discuss below.

##### Answer to the first question:

For the first question, [5]’s answer is the _heavy-cluster condition_ , which
is defined as follows:

$\displaystyle[f^{*}-\Delta,f^{*}+\Delta]~{}~{}\text{is heavy if
}~{}~{}\int_{f^{*}-\Delta}^{f^{*}+\Delta}|\widehat{H\cdot
x^{*}}(f)|^{2}\mathrm{d}f\geq T\cdot\mathcal{N}^{2}/k,$ (1)

where $\mathcal{N}^{2}:=\|g\|_{T}^{2}+\delta\|x^{*}\|_{T}^{2}$ represents the
noisy-level of $x(t)$. However, only considering the energy of the ground-
truth signal is not enough333For example, consider the ground-truth signal
$x^{*}(t)=ve^{2\pi\mathbf{i}f^{*}t}+ve^{2\pi\mathbf{i}(f^{*}+10\Delta)t}$ and
the noise $g(t)=-ve^{2\pi\mathbf{i}f^{*}t}$. Even if $f^{*}\pm\Delta$ is a
heavy cluster, it is impossible to recover $f^{*}$ from the observation
$x(t)=x^{*}(t)+g(t)$, since $\widehat{x}(f)$ is zero around $f^{*}$.. Indeed,
their algorithm only works for “recoverable” clusters, which are defined as:

$\displaystyle[f^{*}-\Delta,f^{*}+\Delta]~{}~{}\text{is recoverable if
}~{}~{}\int_{f^{*}-\Delta}^{f^{*}+\Delta}|\widehat{H\cdot
x}(f)|^{2}\mathrm{d}f\geq T\cdot\mathcal{N}^{2}/k.$

The gap between heavy clusters and recoverable clusters is a bottleneck for
improving the approximation ratio of the Fourier interpolation algorithms in
[5] to an arbitrarily small constant. This gap also introduces many other
technical difficulties in designing more efficient frequency estimation
algorithms.

(a) Low-noise band recovery: high-accuracy frequency estimation is needed. (b)
High-noise band recovery: any frequency estimation output is acceptable.

Figure 2: The high SNR band condition. The red curves are the filters. On the
left, the blue curves are the filtered noisy observation signal in the time
domain, and the green curves are corresponding reconstructed signals. On the
right, the light blue regions are the filtered frequencies of the ground-truth
signal $x^{*}$, and the orange regions are the filtered frequencies of the
noise $g$. Figure 2a shows a high-SNR case, where we can recover a good
approximation of $x^{*}$ in this band. Figure 2b shows an extremely low-SNR
case, where $g$ has almost the same energy as $x^{*}$, and a trivial signal
($y(t)=\text{constant}$) suffices for the recovery of this band.

To overcome this gap, we introduce a new criterion for the frequency bands
that need to be non-trivially reconstructed, which we call the _high signal-
to-noise ratio (SNR) band condition_. Formally, we say a hashing bin $j\in[B]$
has a high SNR if the filtered signal $z^{*}_{j}(t)=(x^{*}\cdot
H)*G_{\sigma,b}^{(j)}$ satisfies:

$\displaystyle\|(g\cdot H)*G_{\sigma,b}^{(j)}(t)\|_{T}^{2}\leq
c\cdot\|z_{j}^{*}(t)\|_{T}^{2},$ (2)

where $c$ is a universal small constant. Our frequency estimation algorithm
focuses solely on recovering _heavy frequencies in high-SNR bins_. The
intuition behind this condition is as follows: if the noise in a band (i.e.,
$(g\cdot H)*G^{(j)}_{\sigma,b}(t)$) is too large, then we can simply use an
all-zero signal as the reconstruction of the filtered signal. We show this new
condition brings many advantages for designing more efficient frequency
estimation algorithms. In particular, we show that the remaining frequencies
in the low-SNR bins are inconsequential for the reconstruction error, and
ignoring them in the signal estimation can still achieve the approximation
guarantee of Fourier interpolation.444We remark our algorithm never attempts
to decide whether a bin satisfies the high-SNR condition or not, but rather
assumes all bins are “good”. The low-SNR bins may therefore produce totally
wrong frequency estimates. However, for accurate signal estimation, we only
need to guarantee that all the good frequencies are reconstructed by the
frequency estimation algorithm, so even if the output set contains some wrong
frequencies, they can be simply ignored.

Figure 3: A case that violates our high SNR band assumption but [5] tries to
recover. $\widehat{x}^{*}(f)*\widehat{H}(f)$ (in blue) is the filtered ground-
truth signal, and $\widehat{g}(f)*\widehat{H}(f)$ (in green) is the filtered
noise. This signal does not satisfy the high SNR band condition since the
noise $\widehat{g}(f)*\widehat{H}(f)$ is too strong. However, the combined
signal $(\widehat{x}^{*}(f)+\widehat{g}(f))*\widehat{H}(f)$ still satisfies
the recoverable-cluster condition since it has enough energy in the frequency
domain.

##### Answer to the second question:

As we discussed earlier, the key to answering this question is our novel
“significant-samples” generation procedure (which produces samples $\alpha$
such that $|z(\alpha)e^{2\pi\mathbf{i}f^{*}\beta}-z(\alpha+\beta)|$ is small,
where $z(t)$ is the filtered signal and $\beta$ is a parameter). This is the
content of the following lemma.

######  Lemma 2.2 (Significant Sample Generation, Informal version of Lemma
K.4).

There is a Procedure GenerateSignificantSamples in Algorithm 2 such that for
$\beta\leq O(1/\Delta)$, it takes $\widetilde{O}(k^{2})$ samples in $x(t)$ and
runs in $\widetilde{O}(k^{2})$ time. For each frequency $f^{*}$ with
$j:=h_{\sigma,b}(f^{*})$, if the $j$-th bin has “high SNR”, and $f^{*}$ is
“heavy”, then the output $\alpha_{j}$ satisfies:

$|z_{j}(\alpha_{j}+\beta)-z_{j}(\alpha_{j})e^{2\pi\mathbf{i}f^{*}\beta}|^{2}\leq
0.01|z_{j}(\alpha_{j})|^{2},$

with a high constant probability, where $z_{j}(t):=(x\cdot
H)*G^{(j)}_{\sigma,b}(t)$.

We first sketch the proof of Theorem 2.1 using Lemma 2.2. Intuitively, if
$z(t)$ is exactly one-sparse, i.e., $z(t)=e^{2\pi\mathbf{i}f^{*}t}$, then we
have $z(t)e^{2\pi\mathbf{i}f^{*}\beta}-z(t+\beta)=0$, and
$\frac{z(t+\beta)}{z(t)}$ gives the exact value of
$e^{2\pi\mathbf{i}f^{*}\beta}$. More generally, by the guarantee of the
significant sample, that ratio can well-approximate
$e^{2\pi\mathbf{i}f^{*}\beta}$, which gives a good estimate of
${f^{*}\beta}\mod{1}$ in a small constant range:

$\displaystyle
f^{*}\approx\frac{1}{2\pi\beta}\Big{(}\arg\Big{(}\frac{z(\alpha+\beta)}{z(\alpha)}\Big{)}+2\pi
s\Big{)}$

for some unknown $s\in\mathbb{Z}$. To determine $s$, we use a search technique
to narrow down the potential range of $f^{*}$ from $[-F,F]$ to
$[f^{*}-\Delta,f^{*}+\Delta]$. In each iteration, we divide the region of
interest into $\mathsf{num}=O(1)$ regions, and repeatedly run the Procedure
GenerateSignificantSamples with several different $\beta$ and pick up the
heavy-hitter among all possible regions, which can exponentially increase the
success probability of finding the correct interval. Now, we consider the
costs of this process. The initial frequency range is $[-F,F]$, and in the
last iteration, the frequency range is
$[f^{*}-\Theta(\Delta),f^{*}+\Theta(\Delta)]$. Thus, we can take the number of
iterations to be $O(\log(F/\Delta))\leq O(\log(FT))$. In each iteration, we
call Procedure GenerateSignificantSamples for $O(\log\log(F/\Delta))\leq
O(\log\log(FT))$ times. Note that each run of Procedure
GenerateSignificantSamples can generate significant samples for all $B$ bins.
Therefore, by Lemma 2.2, the total time and sample complexity for frequency
estimation is $\widetilde{O}(k^{2})\cdot O(\log(FT))\cdot
O(\log\log(FT))=\widetilde{O}(k^{2})$.

Algorithm 1 Frequency Estimation Algorithm, Informal version of Algorithm 4,
3, and 5

1:procedure FrequencyEstimationX($x,(\sigma,b)$)

2: for $j\leftarrow[B]$ do

3:
$\widetilde{f}_{j}\leftarrow\textsc{FrequencyEstimationZ}(x,H,G^{(j)}_{\sigma,b})$
$\triangleright$ recover the heavy frequency of $z^{(j)}$

4: $L\leftarrow L\cup\\{\widetilde{f}_{j}\\}$

5: end for

6: return $L$

7:end procedure

8:procedure FrequencyEstimationZ($x,H,G^{(j)}_{\sigma,b}$)

9: $\mathsf{num}\leftarrow O(1)$$\triangleright$ $\mathsf{num}$-ary search in
each iteration

10: $D\leftarrow O(\log(\frac{FT}{\Delta}))$$\triangleright$ number of
iterations

11: $\mathsf{left}_{1}\leftarrow-F$, $\mathsf{len}_{1}\leftarrow
2F$$\triangleright$ initial searching interval
$[\mathsf{left}_{1},\mathsf{left}_{1}+\mathsf{len}_{1}]$

12: for $d\in[D]$ do

13:
$\mathsf{left}_{d+1}\leftarrow\textsc{ArySearch}$($x,H,G^{(j)}_{\sigma,b},\mathsf{left}_{d},\mathsf{len}_{d},\mathsf{num}$)$\triangleright$
new searching interval’s left-end

14: $\mathsf{len}_{d+1}\leftarrow
5\frac{\mathsf{len}_{d}}{\mathsf{num}}$$\triangleright$ new searching
interval’s length

15: end for

16: return $\mathsf{left}_{D+1}$

17:end procedure

18:procedure
ArySearch($x,H,G^{(j)}_{\sigma,b},\mathsf{left}_{i},\mathsf{len}_{i},\mathsf{num}$)

19:
$I_{q}\leftarrow[\mathsf{left}_{d}+(q-1)\mathsf{len}_{d}/\mathsf{num},\mathsf{left}_{d}+q\mathsf{len}_{d}/\mathsf{num}]$
for $q\in[\mathsf{num}]$$\triangleright$ candidate regions

20: $v_{q}\leftarrow 0$ for $q\in[\mathsf{num}]$ $\triangleright$ votes
counter

21: $R\leftarrow O(\log({\log(FT)}))$

22: for $r=1\to R$ do

23: Sample
$\beta\sim\text{Uniform}([\frac{1}{2}\widehat{\beta},\widehat{\beta}])$ for
$\widehat{\beta}=O(\frac{\mathsf{num}}{\mathsf{len}_{d}})$$\triangleright$
perturbation

24:
$z(\alpha+\beta),z(\alpha)\leftarrow\textsc{GenerateSignificantSamples}(x,H,G^{(j)}_{\sigma,b})$
$\triangleright$ significant sample

25:
$\widetilde{S}\leftarrow\frac{1}{2\pi\beta}(\arg(\frac{z(\alpha+\beta)}{z(\alpha)})+2\pi\mathbb{Z})$$\triangleright$
all possible frequencies

26:
$\widetilde{I}\leftarrow\\{q\in[\mathsf{num}]~{}|~{}I_{q}\cap\widetilde{S}\neq\emptyset\\}$$\triangleright$
all possible regions

27: $v_{q}\leftarrow v_{q}+1$ for $q\in\widetilde{I}$$\triangleright$ add
votes to these regions

28: end for

29: return $\mathsf{left}_{d}+(q-1)\mathsf{len}_{d}/\mathsf{num}$ for any $q$
such that $v_{q}+v_{q+1}+v_{q+2}\geq R/2$

30:end procedure

Then, we sketch the proof of Lemma 2.2, which contains three parts:

  1. I.

A two-level sampling procedure (see Section 2.2.1).

  2. II.

Energy estimation and Signal Equivalent Method (see Section 2.2.2).

  3. III.

Time-domain concentration of filtered signals (see Section 2.2.3).

####  2.2.1 Two-level sampling for significant samples generation

We may assume that in frequency domain, the energy of $\widehat{z}(f)$ is
concentrated around $f^{*}$:

$\int_{f^{*}-\Delta}^{f^{*}+\Delta}|\widehat{z}(f)|^{2}\mathrm{d}f\geq
0.7\int_{-\infty}^{+\infty}|\widehat{z}(f)|^{2}\mathrm{d}f.$

This is a very natural and necessary assumption for the frequency estimation
problem. 555For the filtered signals that do not satisfy the frequency domain
energy concentration assumption, it basically means that they do not contain
enough information to recover $f^{*}$, and we can just ignore those “useless”
clusters. Then we can show that:

$\displaystyle\|z(t)e^{2\pi\mathbf{i}f^{*}\beta}-z(t+\beta)\|_{T}^{2}<\gamma\|z(t)\|_{T}^{2}$
(3)

where $\gamma\in(0,0.001)$ is a small constant. We show how to find an
$\alpha$ such that
$|z(\alpha)e^{2\pi\mathbf{i}f^{*}\beta}-z(\alpha+\beta)|^{2}<\gamma|z(\alpha)|^{2}$.
For ease of discussion, we scale the time domain from $[0,T]$ to $[-T,T]$.

The main idea is to use a two-level sampling procedure, which is motivated by
[7]. In the first level, we take a set $S=\\{t_{1},\dots,t_{s}\\}$ of
$O(k\log(k))$ i.i.d. samples from the following distribution:

$\displaystyle D_{z}(t)=\begin{cases}{c}\cdot(1-|t/T|)^{-1}T^{-1}&\text{if
}|t|\leq T(1-1/k)\\\ c\cdot kT^{-1}&\text{if
}|t|\in[T(1-{1}/k),T]\end{cases}~{}~{}~{}\forall t\in U,$ (4)

where $U=\\{t_{0}\in\mathbb{R}~{}|~{}H(t)>1-\delta_{1}~{}\forall
t\in[t_{0},t_{0}+\beta]\\}$. Then, we assign weights
$w_{i}:=1/(2T|S|D_{z}(t_{i}))$ for each sample $t_{i}\in S$.

In the second level of the sampling procedure, we sub-sample a $t_{i}$ from
the set $S$ as the output according to the following distribution:

$\displaystyle
D_{S}(t_{i})=\frac{w_{i}\cdot|z(t_{i})|^{2}}{\sum_{j\in[s]}w_{j}\cdot|z(t_{j})|^{2}}~{}~{}~{}\forall
i\in[s].$

Now, we explain why the two-level sampling procedure works. By the energy
estimation method discussed in Section 2.2.2, we know that:

$\displaystyle\|z(t)\|_{T}^{2}\approx$
$\displaystyle\|z(t)\|_{S,w}^{2}:=\sum_{i=1}^{s}w_{i}\cdot|z(t_{i})|^{2},~{}~{}\text{and}$
$\displaystyle\|z(t)e^{2\pi\mathbf{i}f^{*}t}-z(t+\beta)\|_{T}^{2}\approx$
$\displaystyle\|z(t)e^{2\pi\mathbf{i}f^{*}\beta}-z(t+\beta)\|_{S,w}^{2}:=\sum_{i=1}^{s}w_{i}\cdot|z(t_{i})e^{2\pi\mathbf{i}f^{*}\beta}-z(t_{i}+\beta)|^{2}.$

The second level of the sampling procedure ensures that

$\displaystyle\operatorname*{{\mathbb{E}}}_{t\sim
D_{S}}\left[\frac{|z(t)e^{2\pi\mathbf{i}f^{*}\beta}-z(t+\beta)|^{2}}{|z(t)|^{2}}\right]=$
$\displaystyle~{}\frac{\sum_{i=1}^{s}w_{i}|z(t_{i})e^{2\pi\mathbf{i}f^{*}\beta}-z(t_{i}+\beta)|^{2}}{\sum_{j=1}^{s}w_{j}|z(t_{j})|^{2}}$
$\displaystyle=$
$\displaystyle~{}\frac{\|z(t)e^{2\pi\mathbf{i}f^{*}\beta}-z(t+\beta)\|_{S,w}^{2}}{\|z(t)\|_{S,w}^{2}}.$

Hence, we get that

$\displaystyle\operatorname*{{\mathbb{E}}}_{t\sim
D_{S}}\left[\frac{|z(t)e^{2\pi\mathbf{i}f^{*}\beta}-z(t+\beta)|^{2}}{|z(t)|^{2}}\right]\approx\frac{\|z(t)e^{2\pi
if^{*}\beta}-z(t+\beta)\|_{T}^{2}}{\|z(t)\|_{T}^{2}}<\gamma,$

where the last step follows from Eq. (3). Then by Markov’s inequality, we get
that the sample $\alpha$ generated by the two-level sampling procedure
satisfies $|z(\alpha)e^{2\pi
if^{*}\beta}-z(\alpha+\beta)|^{2}\lesssim\gamma|z(\alpha)|^{2}$ with high
probability.

The costs of this two-level sampling procedure are calculated as follows. In
the first level, we takes $|S|=\widetilde{O}(k)$ samples from $z(t)$, where
each sample $z(t_{i})=((x\cdot H)*G^{(j)}_{\sigma,b})(t_{i})$ can be computed
by $|\mathrm{supp}(G^{(j)}_{\sigma,b}(t))|=\widetilde{O}(k)$ samples from
$x(t)$ in $\widetilde{O}(k)$ time. Thus, the total time and sample complexity
for the first level sampling procedure is
$\widetilde{O}(k)\cdot\widetilde{O}(k)=\widetilde{O}(k^{2})$. In the second
level, we further select one sample from the output of the first level, which
can be done in $\widetilde{O}(|S|)=\widetilde{O}(k)$ times and does not need
any new sample.

We further discuss how large $\beta$ we can choose in the sampling procedure
since it controls the estimation accuracy of $f^{*}$.666By comparing
$z(t+\beta)$ and $z(t)$, we get an estimate of $f^{*}\beta$ within some error
$\pm b$, which implies an estimate of $f^{*}$ within an error $\pm b/\beta$.
Hence, larger $\beta$ gives a higher accuracy of the frequency estimation.  We
note that the range of $\beta$ is determined by Eq. (3), which is an
underlying assumption of our sampling procedure. To satisfy this inequality,
we need to guarantee that
$|e^{2\pi\mathbf{i}f^{*}\beta}-e^{2\pi\mathbf{i}f\beta}|\leq\gamma$ for any
$f\in f^{*}\pm\Delta$, which implies that $\beta\leq O(\gamma/\Delta)$. For
comparison, the upper bound of $\beta$ in [5] is only
$O(\gamma/(\Delta\sqrt{\Delta T}))$ due to a stronger accuracy requirement
there.777[5] give an $\ell_{1}$-norm error guarantee in the frequency domain,
i.e.,
$\int_{f^{*}-\Delta}^{f^{*}+\Delta}|e^{2\pi\mathbf{i}f^{*}\beta}-e^{2\pi\mathbf{i}f\beta}|\mathrm{d}f$
is small. To obtain an $\ell_{2}$-norm guarantee (like Eq. (3)), they need to
apply Cauchy-Schwarz inequality, which results in an extra $\sqrt{\Delta T}$
factor in their upper bound of $\beta$.

####  2.2.2 Energy estimation and Signal Equivalent Method

In this section, we show that the sampling and reweighing method we use in the
significant sample generation procedure can accurately estimate the energy of
$z(t)$ and $z(t)e^{2\pi\mathbf{i}f^{*}t}-z(t+\beta)$ with a sample complexity
almost reaching the information-theoretic limit.

######  Lemma 2.3 (Informal version of Lemma K.1 and Lemma K.2).

Suppose $f^{*}$ is a heavy frequency hashed to the $j$-th bin which satisfies
the high SNR condition. Let $z^{*}(t)=(x^{*}\cdot H)*G_{\sigma,b}^{(j)}$ and
$z(t)=(x\cdot H)*G_{\sigma,b}^{(j)}$. Let $U\subseteq[0,T]$ be an interval.
Let $S=\\{t_{1},\dots,t_{s}\\}$ be a set of $O(k\log(k))$ i.i.d. samples from
the distribution $D$ defined by Eq. (4) with weights $w_{i}=1/(TsD(t_{i}))$.
Then, with probability at least 0.8,

$\displaystyle\|z(t)\|_{S,w}^{2}\gtrsim\|z^{*}(t)\|_{U}^{2}~{}~{}\text{and}~{}~{}\|z(t)e^{2\pi\mathbf{i}f^{*}t}-z(t+\beta)\|_{S,w}^{2}\lesssim\|z^{*}(t)\|_{U}^{2},$

where $\|z(t)\|_{U}^{2}=(1/|U|)\cdot\int_{U}|z(t)|^{2}{\rm d}t$.

To prove Lemma 2.3, we develop a _Signal Equivalent Method_. Below, we sketch
the proof of the first half of Lemma 2.3 on the energy estimation for $z(t)$.
The second half follows similar ideas.

Energy estimation is also used in prior works [5, 6, 7, 30], where a key
component is the following energy bound for the interested function family
${\cal F}$:

$\displaystyle\sup_{f\in{\mathcal{F}}}\sup_{t\in[0,T]}~{}\frac{|f(t)|^{2}}{\|f(t)\|_{T}^{2}}.$

However, this approach is unlikely to work directly for our filtered signal
$z(t)$ since it depends on the randomized hashing function. And under some
hashing parameter $(\sigma,b)$, there always exists some signal $x(t)$ such
that $z(t)=(x\cdot H)(t)*G^{(j)}_{\sigma,b}(t)$ is in ill-condition (e.g., the
frequencies are not well-isolated, or large offset events happen). As a
result, bounding $\frac{|z(t)|^{2}}{\|z(t)\|_{T}^{2}}$ for all $z(t)$ of the
form $(x\cdot H)*G_{\sigma,b}^{(j)}(t)$ by a small number is not easy. We
bypass the issue by proving an energy bound only for those $z(t)$ under some
well-hashed conditions (e.g. frequency is isolated and do not have a large
offset), and showing that such a “refined energy bound” is still sufficient to
derive the sample complexity of our algorithm.

(a) Signal with non-ideal filter $\widehat{G}^{(j)}_{\sigma,b}(f)$. (b) Signal
with ideal filter $\widehat{I}(f)$.

Figure 4: The Signal Equivalent Method. This figure demonstrates that
$(\widehat{x}*\widehat{H})(f)\cdot\widehat{G}^{(j)}_{\sigma,b}(f)$ (left) can
be approximated by $(\widehat{x}*\widehat{H})(f)\cdot\widehat{I}(f)$ (right).
$\widehat{I}(f)$ (red curve on the right) is the ideal filter that approximate
$\widehat{G}^{(j)}_{\sigma,b}(f)$ (red curve on the left).

The motivation of the Signal Equivalent Method comes from the special
structure of $z(t)=(x\cdot H)(t)*G^{(j)}_{\sigma,b}(t)$ in the frequency
domain. Notices that the observed signal $x(t)$’s Fourier transform
$\widehat{x}(f)$ only contains some spikes (assuming small noise). By
convolution with $\widehat{H}(f)$ (which corresponds to multiplying by $H(t)$
in the time domain), $(\widehat{x}*\widehat{H})(f)$ fattens the spikes in the
frequency domain (and by Parseval’s theorem, the area of the signal in
frequency domain equals to its energy). Then, convolution with
$G^{(j)}_{\sigma,b}(t)$ “zooms-in” to a narrow band around a single frequency.
This construction of $z(t)$ motivates us to build a new signal
$\overline{z}(t)=(x\cdot H)(t)*I(t)$, where $I(t)$ is a filter function such
that $\widehat{I}(f)=1$ when $G_{\sigma,b}^{(j)}(t)>1/2$, and
$\widehat{I}(f)=0$ otherwise. To analyze the equivalent signal
$\overline{z}(t)$, we improve the analysis of the filter $H(t)$ in [7] and
give a tighter bound on its value in a sub-interval of $[0,T]$. Then, we show
that the equivalent signal $\overline{z}(t)$ is _almost equivalent_ to $z(t)$
under some “good conditions” (i.e., the frequency is isolated and no large
offset). We also prove that the ideal filter has several useful properties
that can mush simplify the analysis (e.g., the function $I(t)$ is randomized,
and with high probability, $I(t)$ commutes with $H(t)$).

By the Signal Equivalent Method, we can first prove an energy bound for the
equivalent signal $\overline{z}(t)$, which follows from the Fourier-sparse
signals’ energy bounds (see Section B). Then, it remains to show that the
equivalent signals’ energy bound can approximate the original filtered signal
$z(t)$’s energy bound. We find that the approximation error comes from two
sources: the observation noise $g(t)$ and the approximation error
$\overline{z}(t)-z(t)$. The first part of the error is small due to the high
SNR band condition (Eq. (2)). And the second part of the error is mitigated by
the tail-bound for $G^{(j)}_{\sigma,b}(t)$ and the heavy-cluster condition
(Eq. (1)). More specifically, the HashToBins procedure and the filter
$G_{\sigma,b}^{(j)}(t)$ can bring some interference noise from other bins to
$z(t)$, which is perfectly eliminated by the ideal filter $I(t)$ in the
equivalent signal $\overline{z}(t)$. Hence, we need to bound this part of
noise when we transfer back from the equivalent signal to the true filtered
signal. The tail bound of $G_{\sigma,b}^{(j)}(t)$ ensures that adding small
interference noise with frequencies far away from the center of the cluster
will not drastically affect $z(t)$. However, by this argument, we can only
bound the distance between $\overline{z}(t)$ and $z(t)$ by $\|x^{*}(t)\|_{T}$,
which can be much larger than $\|z(t)\|_{T}$. Hence, we need to use the heavy-
cluster assumption to ensure that $\|x^{*}(t)\|_{T}\lesssim\|z(t)\|_{T}$.
Using these error-control techniques, we can prove that an energy bound for
$\overline{z}(t)$ implies an energy bound for $z(t)$.

Figure 5: An illustration of a filtered noisy signal.
$\widehat{G}^{(j)}_{\sigma,b}$ (the red curve) is the HashToBins filter for
the $j$-th bin. The noise in the filtered signal comes from two parts: one is
$\widehat{g}(f)*\widehat{H}(f)$ (the green signal), and another is the
interference by signals outside the bin (the blue and green signals in the
middle).

We give a comparison between ours and previous approaches for proving the
energy estimation guarantee. [5] considers $z(t)$ as a generic signal that
satisfies the time and frequency domains concentration properties888It means
that most of the energy of $z(t)$ (i.e., $\|z(t)\|_{2}$) lies in $[0,T]$ and
most of the energy of $\widehat{z}(f)$ lies in a $\mathrm{poly}(k)/T$ length
interval in frequency domain.. We exploit “finer” structure of $z(t)$ and
obtain a stronger energy bound and reduce the number of samples required in
norm preserving. [7] also proves a similar property (but only for $(x\cdot
H)(t)$). However, they assume that all the frequencies of $x^{*}(t)$ are
contained in a small interval, making the task much easier. Our filtered
signal $z(t)$ does not satisfy this condition due to the interference noise
caused by the HashToBins procedure.

####  2.2.3 Time-domain concentration of filtered signals

Figure 6: A bad case that may break the time domain concentration of
$z(t)=(x\cdot H)(t)*G^{(j)}_{\sigma,b}(t)$ in $[0,T]$ when the filter decay
slowly. $x^{*}(t)$ (in blue) is a $k$-Fourier-sparse signal.
$G^{(j)}_{\sigma,b}$ (in green dashed) is the filter of frequency domain.
$H(t)$ (in red) is the filter in time domain. On the one hand, since
$x^{*}(t)$ is very small in $[T/\mathrm{poly}(k),T(1-/\mathrm{poly}(k))]$, and
$H(t)$ is very small in
$[0,T/\mathrm{poly}(k)]\cup[T(1-/\mathrm{poly}(k)),T]$, the filtered signal
has very small energy within $[0,T]$. On the other hand, since the convolution
with $G^{(j)}_{\sigma,b}(t)$ can bring some energy of $x^{*}(t)$ passing the
boundary of $[0,T]$, and the signal $x^{*}(t)$ could be very large outside
$[0,T]$, $(x\cdot H)(t)*G^{(j)}_{\sigma,b}(t)$ may contain very large energy
in $\mathbb{R}\backslash[0,T]$. In this case,
$\|z(t)\|_{L_{2}}^{2}\gg\|z(t)\|_{T}^{2}$.

The proof of Lemma 2.2 relies on an underlying assumption: the most of the
energy of the filtered signal is contained in the observation window $[0,T]$.
That is, we need the following lemma:

######  Lemma 2.4 (Informal version of Lemma G.2).

Let $j\in[B]$ be a bin that contains a heavy frequency. Let $z(t)=(x^{*}\cdot
H)*G_{\sigma,b}^{(j)}$ be the filtered signal. Then, we have

$\displaystyle\int_{-\infty}^{+\infty}|z(t)|^{2}\mathrm{d}t\leq
1.35\int_{0}^{T}|z(t)|^{2}\mathrm{d}t.$

A similar concentration property is also proved in [5], using a very strict
requirement on the $H(t)$ filter that it decays at an exponential rate near
the boundary. More specifically, they require that $H(t)$ is exponentially
small not only outside the time duration $[0,T]$, but also in the shrinking
boundary $[0,T/\mathrm{poly}(k)]\cup[T-T/\mathrm{poly}(k),T]$. The additional
constraint allows them to show that $x(t)$’s energy near the boundary cannot
“pass” the $H$ filter, and the energy concentration of $z(t)$ easily follows.
However, it also results in a large support of $H$ in the frequency domain,
which leads to a large error in the frequency estimation, and further causes
large output sparsity and time/sample complexity of their Fourier
interpolation algorithm.

We resolve this issue by changing the filter function to the one defined in
[7], which has much smaller support and thus saves time and sample
complexities. However, it is exponentially small outside $[0,T]$, but only
_polynomially_ small near the boundary. To prove Lemma 2.4, we use our Signal
Equivalent Method again. We construct an equivalent signal
$\overline{z}(t)=(x^{*}\cdot H)*I(t)=(x^{*}*I)\cdot H(t)$, where
$x^{*}(t)*I(t)$ is a Fourier-sparse signal. Then, by some finer analysis on
the $H(t)$ filter (see Lemma E.9), we can show that most of the energy of
$x^{*}(t)*I(t)$ is preserved in $[0,T]$, i.e.,

$\displaystyle\int_{-\infty}^{+\infty}|\overline{z}(t)|^{2}\mathrm{d}t\leq
1.1\int_{0}^{T}|\overline{z}(t)|^{2}\mathrm{d}t.$

Finally, by the approximation guarantee of Signal Equivalent Method, we get
that the energy concentration of $\overline{z}(t)$ implies the energy
concentration of $z(t)$.

###  2.3 Our techniques for Fourier Interpolation

(a) High SNR, where $j_{1}=h_{\sigma_{1},b_{1}}(f^{*})$ (b) Low SNR, where
$j_{2}=h_{\sigma_{2},b_{2}}(f^{*})$

Figure 7: The SNR of the same signal changes with different hash functions. In
(a), the noise $g\cdot H$ is hashed outside the bin and suppressed by
$G^{(j_{1})}_{\sigma_{1},b_{1}}$. Thus, this bin has high SNR. In (b), by a
different hash function, the noise is hashed inside the bin and
$G^{(j_{2})}_{\sigma_{2},b_{2}}$ preserves its energy. Thus, the SNR of the
bin becomes very low, even if the signal doesn’t change.

In this section, we discuss how to obtain a Fourier interpolation algorithm
with improved efficiency and output sparsity (Theorem 1.1) based on our
frequency estimation algorithm (Theorem 2.1).

We first remark that simply applying the original framework of Fourier
Interpolation (e.g., [5, 30]) and combining with an existing signal estimation
algorithm is still not enough to improve the previous algorithm, since the
frequency estimation algorithm has a low success probability and we cannot
apply the success probability boosting trick in [5] to increase it to
$1-\rho$. More specifically, [5] first boosts the success probability of their
frequency estimation algorithm by their merge-stage algorithm (which runs the
frequency estimation algorithm for $R=\log(1/\rho)$ times, sorts all recovered
frequencies, and picks every $R/2$-th entry of the sorted list), and then runs
the signal estimation algorithm. It does not work here because our high SNR
band condition makes frequency estimation and signal estimation “entangled”.
More specifically, whether a frequency is contained in a high SNR bin (which
_needs_ to be recovered) or not depends on the randomized hash function.
However, if the outputs of multiple runs of the frequency estimation algorithm
are mixed together, it is hard to justify which frequencies are necessary,
since different runs use different hash functions, resulting in different high
SNR bins. In other words, if we still use [5]’s boosting strategy, we cannot
guarantee the final output of the frequency estimation satisfies the
requirement of the signal estimation algorithm.

We propose a new Fourier Interpolation framework that boosts the success
probability after the signal estimation step. That is, in each run of the
constant success probability frequency estimation algorithm, we reconstruct
the signal immediately. Let $y_{1},\dots,y_{R_{p}}$ denote the reconstructed
signals of $R_{p}$ runs. Then, we boost the total success probability by
outputting the signal $y_{j^{*}}$:

$\displaystyle
j^{*}=\underset{j\in[R_{p}]}{\arg\min}~{}\underset{i\in[R_{p}]}{\mathrm{median}}~{}\|y_{j}(t)-y_{i}(t)\|_{T}^{2}.$

By Chernoff bound, there are more than a half of $y_{i}$’s being good
approximations of the ground-truth signal $x^{*}(t)$. Using the median trick,
we can show that $y_{j^{*}}$ satisfies the recovery guarantee with an
exponentially small failure probability.

It remains to estimate the distance $\|y_{j}(t)-y_{i}(t)\|_{T}^{2}$ between
different reconstructed signals. Naively, it takes $O(\widetilde{k}^{2})$-time
since $y_{1},y_{2}$ are $\widetilde{k}$-Fourier sparse, and it is enough to
obtain the time complexity of our Fourier interpolation algorithm in Theorem
1.1. We further propose an $\widetilde{O}(\widetilde{k}\cdot k)$-time
approximation algorithm for estimating a Fourier-sparse signal’s energy, which
could be of independent interest. The main idea is to use
$\|y_{i}(t)-y_{j}(t)\|_{S,w}^{2}$ to approximate
$\|y_{i}(t)-y_{j}(t)\|_{T}^{2}$, where the sample set $S$ and weights $w$ are
defined by the significant sample generation procedure in Section 2.2.1. We
show that if we take $|S|=\widetilde{O}(\widetilde{k})$, we can achieve a
constant approximation ratio in $\widetilde{O}(\widetilde{k}\cdot k)$ time. In
addition, we prove that even if we use the approximated distances, the output
signal $y_{j^{*}}$ still satisfies the recovery guarantee of Fourier
interpolation.

##  3 Organization

In Section A, we define our notations in this paper. In Section B, we review
several energy bounds for Fourier-sparse signal. In Section C, we define and
show several properties of the frequency domain filters $G_{\sigma,b}^{(j)}$.
In Section D, we review the HashToBins strategy and prove that bad events only
happen with small probability. In Section E, we define and show some
properties of the time domain filter $H(t)$.

Based on the analysis of the filters, in Section F, we study the ideal filter
and develop the Signal Equivalent Method. In Section G, we show that the
filtered signal satisfies some concentration properties in both time and
frequency domains.

Based on the Signal Equivalent Method and the concentration properties, in
Section H, we prove an energy bound for filtered Fourier-sparse signals. In
Section I, we further extend the energy bound for local-test signals. Then, in
Section J, we apply the energy bounds and describe how to use samples to
empirically estimate the energy of filtered signals and local-test signals. In
Section K, we introduce our algorithm for generating significant samples. In
Section L, we use the significant samples to do frequency estimation for
Fourier sparse signals. Finally, in Section M, we combine our frequency
estimation algorithm with a signal estimation procedure and boost the success
probability of Fourier Interpolation.

Section N presents a flowchart of the key theorems/lemmas for our Fourier
interpolation algorithm.

##  Appendix A Preliminaries

For any positive integer $n$, we define $[n]$ to be the set
$\\{1,2,\cdots,n\\}$. We define $\mathbf{i}$ to be $\sqrt{-1}$. For a complex
number $z=a+b\mathbf{i}$, we define $|z|$ to be the magnitude of $z$, i.e.,
$|z|=\sqrt{a^{2}+b^{2}}$. For a function $f$, we use $\mathrm{supp}(f)$ to
denote the support set of $f$. We use $f\lesssim g$ to denote that there
exists a constant $C$ such that $f\leq C\cdot g$. We use $f\eqsim g$ to denote
that $f\lesssim g\lesssim f$. For any function $f$, we use $\mathrm{poly}(f)$
to denote $f^{O(1)}$, and $\widetilde{O}(f)$ to denote
$f\cdot\mathrm{poly}\log(f)$. For an interval $U\subseteq\mathbb{R}$, we use
$|U|$ to denote the size of the interval, and we use $\text{Uniform}(U)$ to
denote the uniform distribution over $U$.

We use $\omega$ to denote the exponent of matrix multiplication, i.e.,
$n^{\omega}$ denote the time of multiplying an $n\times n$ matrix with another
$n\times n$ matrix. Currently $\omega\approx 2.373$ [33, 1].

For two functions $f$ and $g$, we use
$(f*g)(t)=\int_{-\infty}^{\infty}f(s)g(t-s)\mathrm{d}s$ to denote the
convolution of two functions $f$ and $g$. And we use $f^{*l}$ to denote the
$l$-fold convolution of $f$, i.e., $f^{*l}(t)=f(t)*f(t)*\cdots*f(t)$. For
$a\in\mathbb{R}_{+}$, we use $\mathrm{rect}_{a}(t)$ to denote the box function
with support set length $a$, i.e.,
$\mathrm{rect}_{a}(t)=\mathbf{1}_{[-a/2,a/2]}(t)$. For $a\in\mathbb{R}$, we
use $\delta_{a}(f)$ to denote $\delta(f-a)$, where $\delta(f)$ is the
Dirichlet function. We use ${\rm round}(x)$ to denote rounding
$x\in\mathbb{R}$ to the nearest integer. For
$x\in\mathbb{R},y\in\mathbb{R}_{+}$, we use $x\pmod{y}$ to denote the smallest
positive $z\in\mathbb{R}_{+}$ such that $z\in x+y\mathbb{Z}$.

We say $x(t)$ is $k$-Fourier-sparse if:

$\displaystyle x(t)=\sum_{j=1}^{k}v_{j}e^{2\pi\mathbf{i}f_{j}t}.$

We define $\widehat{x}(f)$ to be the Fourier transform of $x(t)$:

$\displaystyle\widehat{x}(f)=\int_{-\infty}^{\infty}x(t)e^{-2\pi\mathbf{i}ft}\mathrm{d}t.$

We use ${\cal F}_{k,F}$ to denote the following family of signals:

$\displaystyle{\cal F}_{k,F}:=\Big{\\{}x(t)=\sum_{j=1}^{k}v_{j}\cdot
e^{2\pi\mathbf{i}f_{j}t}~{}\Big{|}~{}f_{j}\in[-F,F],v_{j}\in\mathbb{C}~{}\forall
j\in[k]\Big{\\}}.$

Then, we define several norms for signal.

  * •

For any discrete set $S\subseteq\mathbb{R}$, the _discrete norm_ of $x$ with
respect to a set $S$ is defined as

$\displaystyle\|x(t)\|^{2}_{S}=\frac{1}{|S|}\sum_{t\in S}|x(t)|^{2},$

and the _weighted discrete norm_ with weights $w\in\mathbb{R}^{S}$ is defined
as

$\displaystyle\|x(t)\|^{2}_{S,w}=\sum_{t\in S}w_{t}|x(t)|^{2}.$

  * •

For any continuous interval $U\subset\mathbb{R}$, the continuous $U$-norm of
$x$ is defined as

$\displaystyle\|x(t)\|_{U}^{2}=\frac{1}{|U|}\int_{U}|x(t)|^{2}\mathrm{d}t.$

  * •

For any $T>0$, the _continuous $T$-norm_ is defined as

$\displaystyle\|x(t)\|^{2}_{T}=\frac{1}{T}\int_{0}^{T}|x(t)|^{2}\mathrm{d}t.$

  * •

Let $D$ be a probability distribution over $\mathbb{R}$. The _continuous
$D$-norm_ is defined as

$\displaystyle\|x(t)\|^{2}_{D}=\int_{-\infty}^{\infty}D(t)|x(t)|^{2}\mathrm{d}t.$

  * •

The $L_{2}$-norm of $x(t)$ is defined as

$\displaystyle\|x(t)\|^{2}_{L_{2}}=\int_{-\infty}^{\infty}|x(t)|^{2}\mathrm{d}t.$

Throughout this paper, we assume that $x^{*}(t)\in{\cal F}_{k,F}$ is our
ground-truth signal. And the observation signal is $x(t)=x^{*}(t)+g(t)$, where
$g(t)$ is an arbitrary noise function. Furthermore, we assume that $x(t)$ can
be observed at any point in $[0,T]$.

######  Lemma A.1 (Chernoff Bound [4]).

Let $X_{1},X_{2},\cdots,X_{n}$ be independent random variables. Assume that
$0\leq X_{i}\leq 1$ always, for each $i\in[n]$. Let
$X=X_{1}+X_{2}+\cdots+X_{n}$ and
$\mu=\mathbb{E}[X]=\overset{n}{\underset{i=1}{\sum}}\mathbb{E}[X_{i}]$. Then
for any $\varepsilon>0$,

$\displaystyle\mathsf{Pr}[X\geq(1+\varepsilon)\mu]\leq\exp(-\frac{\varepsilon^{2}}{2+\varepsilon}\mu)\textit{
and
}\mathsf{Pr}[X\leq(1-\varepsilon)\mu]\leq\exp(-\frac{\varepsilon^{2}}{2}\mu).$

##  Appendix B Energy Bounds of Fourier Sparse Signals

The energy bound of a function family $\cal F$ is the largest value achieved
by a function $f\in{\cal F}$ normalized by its norm (total energy)
$\|f\|_{T}$. It connects the extreme value and the average value of the
functions in ${\cal F}$, and is very useful in analyzing the concentration
property.

In our setting, we take ${\cal F}={\cal F}_{k,F}$ to be the set of $F$-band-
limit, $k$-sparse Fourier signals. [22] showed an energy bound that only
depends on the sparsity $k$, without any dependence on the time point $t$,
band-limit $F$, time duration $T$, frequency gap $\eta={\min}_{i\neq
j}|f_{i}-f_{j}|$:

######  Theorem B.1 ([22]).

For any $t\in[0,T]$,

$\displaystyle\underset{x\in{\cal
F}_{k,F}}{\sup}\frac{|x(t)|^{2}}{\|x\|_{T}^{2}}\lesssim k^{2}.$

The $k^{2}$ energy bound can be further improved if we only consider the
functions’ value at a fixed time point $t$:

######  Theorem B.2 ([6, 2]).

Let $D:=\mathrm{Uniform}([-1,1])$. For any $t\in(-1,1)$,

$\displaystyle\underset{x\in{\cal
F}_{k,F}}{\sup}\frac{|x(t)|^{2}}{\|x\|_{D}^{2}}\lesssim\frac{k}{1-|t|}.$

##  Appendix C Filter in Frequency Domain

Filtering is one of the most important techniques in sparse Fourier transform
literature. In this section, we introduce the frequency domain filter function
$\widehat{G}^{(j)}_{\sigma,b}(f)$, which is the key to implement the
HashToBins strategy. We first review the the construction given by [5] with
some different parameter settings and show some known properties (see Section
C.1). Then, we prove a new property of the filter functions: the frequency
domain covering property (see Section C.2).

###  C.1 Frequency domain filter construction

In this section we review the construction and several basic properties of the
frequency domain filter $G^{(j)}_{\sigma,b}(t)$,
$\widehat{G}^{(j)}_{\sigma,b}(f)$.

######  Definition C.1 ($G$-filter’s construction, [5]).

Given $B>1$, $\delta>0$, $\alpha>0$. Let $l:=\Theta(\log(k/\delta))$. Define
$G_{B,\delta,\alpha}(t)$ and its Fourier transform
$\widehat{G_{B,\delta,\alpha}}(f)$ as follows:

$\displaystyle G_{B,\delta,\alpha}(t):=$
$\displaystyle~{}b_{0}\cdot(\mathrm{rect}_{\frac{B}{(\alpha\pi)}}(t))^{\star
l}\cdot\operatorname{sinc}(t\frac{\pi}{2B}),$
$\displaystyle\widehat{G_{B,\delta,\alpha}}(f):=$
$\displaystyle~{}b_{0}\cdot(\operatorname{sinc}(\frac{B}{\alpha\pi}f))^{l}*\mathrm{rect}_{\frac{\pi}{2B}}(f),$

where $b_{0}=\Theta(B\sqrt{l}/\alpha)$ is the normalization factor such that
$\widehat{G}(0)=1$.

######  Definition C.2 (Filter for bins).

Given $B>1$, $\delta>0$, $\alpha>0$, let

$\displaystyle\widehat{G}(f):=\widehat{G}_{B,\delta,\alpha}(2\pi(1-\alpha)f)$

where $G_{B,\delta,\alpha}$ is defined in Definition C.1. For any
$\sigma>0,b\in\mathbb{R}$ and $j\in[B]$, define

$\displaystyle G^{(j)}_{\sigma,b}(t):=$
$\displaystyle~{}\frac{1}{\sigma}G(t/\sigma)e^{2\pi\mathbf{i}t(j/B-\sigma
b)/\sigma},$

and its Fourier transformation:

$\displaystyle\widehat{G}^{(j)}_{\sigma,b}(f)=\sum_{i\in\mathbb{Z}}\widehat{G}(\sigma
f+\sigma b-i-\frac{j}{B}).$

Then, we provide several properties of $G$ and $G^{(j)}_{\sigma,b}(t)$, which
is proven by [5].

######  Lemma C.3 ($G$-filter’s properties, [5]).

Given $B>1$, $\delta>0$, $\alpha>0$, let $G:=G_{B,\delta,\alpha}(t)$ be
defined in Definition C.1. Then, $G$ satisfies the following properties:

$\displaystyle\mathrm{Property~{}\@slowromancap i@}:$
$\displaystyle\widehat{G}(f)\in[1-\delta/k,1],\text{~{}if~{}}|f|\leq(1-\alpha)\frac{2\pi}{2B}.$
$\displaystyle\mathrm{Property~{}\@slowromancap ii@}:$
$\displaystyle\widehat{G}(f)\in[0,1],\text{~{}if~{}}(1-\alpha)\frac{2\pi}{2B}\leq|f|\leq\frac{2\pi}{2B}.$
$\displaystyle\mathrm{Property~{}\@slowromancap iii@}:$
$\displaystyle\widehat{G}(f)\in[-\delta/k,\delta/k],\text{~{}if~{}}|f|>\frac{2\pi}{2B}.$
$\displaystyle\mathrm{Property~{}\@slowromancap iv@}:$
$\displaystyle\mathrm{supp}(G(t))\subset[\frac{l}{2}\cdot\frac{-B}{\pi\alpha},\frac{l}{2}\cdot\frac{B}{\pi\alpha}].$
$\displaystyle\mathrm{Property~{}\@slowromancap v@}:$
$\displaystyle\underset{t}{\max}|G(t)|\lesssim\mathrm{poly}(B,l).$

######  Lemma C.4.

Let $G^{(j)}_{\sigma,b}(t)$ be defined in Definition C.2. Let offset function

$\displaystyle o_{\sigma,b}(f)=|(\sigma f+\sigma
b-\frac{j}{B})-\frac{1}{2}{\pmod{1}}|-\frac{1}{2}.$

Then,

$\displaystyle\mathrm{Property~{}\@slowromancap i@}:$
$\displaystyle\widehat{G}_{\sigma,b}^{(b)}(f)\in[1-\delta/k,1],\text{~{}if~{}}|o_{\sigma,b}(f)|\leq(1-\alpha)\frac{2\pi}{2B}.$
$\displaystyle\mathrm{Property~{}\@slowromancap ii@}:$
$\displaystyle\widehat{G}_{\sigma,b}^{(b)}(f)\in[0,1],\text{~{}if~{}}(1-\alpha)\frac{2\pi}{2B}\leq|o_{\sigma,b}(f)|\leq\frac{2\pi}{2B}.$
$\displaystyle\mathrm{Property~{}\@slowromancap iii@}:$
$\displaystyle\widehat{G}_{\sigma,b}^{(b)}(f)\in[-\delta/k,\delta/k],\text{~{}if~{}}|o_{\sigma,b}(f)|>\frac{2\pi}{2B}.$
$\displaystyle\mathrm{Property~{}\@slowromancap iv@}:$
$\displaystyle\mathrm{supp}({G}_{\sigma,b}^{(b)}(t))\subset[\frac{l}{2}\cdot\frac{-B}{\pi\alpha},\frac{l}{2}\cdot\frac{B}{\pi\alpha}].$
$\displaystyle\mathrm{Property~{}\@slowromancap v@}:$
$\displaystyle\underset{t}{\max}|{G}_{\sigma,b}^{(b)}(t)|\lesssim\mathrm{poly}(B,l).$

Figure 8: Filters with the frequency domain covering property. The red, green,
and blue curves represent the filters $\widehat{G}^{(j)}_{\sigma,b}$,
$\widehat{G}^{(j+1)}_{\sigma,b}$, and $\widehat{G}^{(j+2)}_{\sigma,b}$,
respectively. The frequency domain covering property ensures that for each
frequency $f\in\mathbb{R}$, there are _at least one but no more than two_
filters satisfying $\widehat{G}^{(j)}_{\sigma,b}(f)\geq 1-\delta$.

###  C.2 Frequency domain covering

In this section, we show that the filter functions
$\\{\widehat{G}_{\sigma,b}^{(j)}\\}_{j\in[B]}$ form a proper cover for the
frequency domain. Roughly speaking, for any frequency $f\in\mathbb{R}$, we
show that the sum of all filters’ values (squared) at $f$ is very close to
one. This property is very important for our high SNR band assumption.

######  Lemma C.5.

For any $f\in\mathbb{R}$, there exists at least one $j\in[B]$ such that

$\displaystyle\widehat{G}^{(j)}_{\sigma,b}(f)\geq 1-\frac{\delta}{k}.$

###### Proof.

We first prove that the lemma holds for those $f^{*}$ where there exists a
$j\in[B]$ such that

$\displaystyle f^{*}\in[-b+\frac{j}{\sigma B}-\frac{1}{2\sigma
B},-b+\frac{j}{\sigma B}+\frac{1}{2\sigma B}]+\frac{1}{\sigma}\mathbb{Z}.$

For such $f^{*}$, we have

$\displaystyle\widehat{G}^{(j)}_{\sigma,b}(f^{*})=$
$\displaystyle~{}\sum_{i\in\mathbb{Z}}\widehat{G}(\sigma f^{*}+\sigma
b-i-\frac{j}{B})$ $\displaystyle\geq$ $\displaystyle~{}\widehat{G}((\sigma
f^{*}+\sigma b-\frac{j}{B})\mod{1})$ $\displaystyle\geq$
$\displaystyle~{}1-\frac{\delta}{k},$

where the first step follows from the definition of
$\widehat{G}^{(j)}_{\sigma,b}(f^{*})$, the second step is straight forward,
the third step follows from

$\displaystyle\sigma f^{*}+\sigma
b-\frac{j}{B}\mod{\frac{1}{\sigma}}\in[-\frac{1}{2B},\frac{1}{2B}]$

and Lemma C.4 Property i@ and Definition C.2.

It remains to show that for an arbitrary $f\in\mathbb{R}$, the condition still
holds. Let

$\displaystyle j:=\mathrm{round}((\sigma f+\sigma b\mod{1})\cdot B).$

We have

$\displaystyle j\in[(\sigma f+\sigma b\mod{1})\cdot B-\frac{1}{2},(\sigma
f+\sigma b\mod{1})\cdot B+\frac{1}{2}],$

which implies that

$\displaystyle j\in[(\sigma f+\sigma b)\cdot B-\frac{1}{2},(\sigma f+\sigma
b)\cdot B+\frac{1}{2}]+B\mathbb{Z}.$

Thus,

$\displaystyle f\in[-b+\frac{j}{\sigma B}-\frac{1}{2\sigma
B},-b+\frac{j}{\sigma B}+\frac{1}{2\sigma B}]+\frac{1}{\sigma}\mathbb{Z}.$

The lemma is then proved. ∎

######  Lemma C.6.

For any $f\in\mathbb{R}$,

$\displaystyle\sum_{j=1}^{B}|\widehat{G}^{(j)}_{\sigma,b}(f)|^{2}\eqsim 1.$

###### Proof.

By Lemma C.5, we have that for any $f\in\mathbb{R}$, there exist at least a
$j_{0}\in[B]$ such that

$\displaystyle\widehat{G}^{(j_{0})}_{\sigma,b}(f)\geq\frac{1}{2}.$ (5)

Moreover, we have that

$\displaystyle B\frac{\delta}{k}=O(\delta)\leq 0.01.$ (6)

where the first step follows from $B=O(k)$, the second step follows from
$\delta=o(1)\leq 0.01$.

In the followings, we give lower and upper bounds for
$\sum_{j=1}^{B}|\widehat{G}^{(j)}_{\sigma,b}(f)|^{2}$.

##### Lower bound:

$\displaystyle\sum_{j=1}^{B}|\widehat{G}^{(j)}_{\sigma,b}(f)|^{2}\geq|\widehat{G}^{(j_{0})}_{\sigma,b}(f)|^{2}\gtrsim
1.$

where the first step follows from Lemma C.4 Property i@, ii@, and iii@, the
second step follows from Eq. (5), the third step follows from Eq. (6) and
${\delta}/{k}\leq 1$.

##### Upper bound:

$\displaystyle\sum_{j=1}^{B}(\widehat{G}^{(j)}_{\sigma,b}(f))^{2}\leq
2+B(\frac{\delta}{k})^{2}\lesssim 1$

where the first step follows from the definition of
$\widehat{G}^{(j)}_{\sigma,b}(f)$, the second step follows from Eq. (6) and
${\delta}/{k}\leq 1$.

Combining them together, the lemma follows. ∎

##  Appendix D Hashing the Frequencies

In this section, we review the HashToBins strategy, which an important tool
for Sparse Fourier Transform [13, 17, 26, 5, 20, 21, 19]. Ideally, the
HashToBins procedure randomly splits the frequency domain into $B$ bins so
that each bin contains at most one frequency. Then, the $k$-sparse Fourier
reconstruction problem is reduced to a much easier one-sparse Fourier
reconstruction problem.

We first describe the hashing strategy(see Section D.1). However, there are
two kinds of bad events such that the HashToBins procedure cannot work as good
as we want: two frequencies are hashed to the same bin, or some frequency lies
close to the boundary of a bin. We show that these bad events only happen with
small probabilities (see Sections D.2 and D.3) .

###  D.1 HashToBins procedure

Here, we introduce the hash function and how to compute the resulting signal
of the HashToBins procedure.

We first give the definition of the hashing function:

######  Definition D.1 (Hash function, [5]).

Let $\pi_{\sigma,b}(f)=\sigma(f+b)\pmod{1}$ and
$h_{\sigma,b}(f)=\mathrm{round}(\pi_{\sigma,b}(f)\cdot{B})$ be the hash
function that maps frequency $f\in[-F,F]$ into bins $\\{0,\cdots,B-1\\}$.

Intuitively, the $j$-th bin corresponding to $f$ such that
$\widehat{G}^{(j)}_{\sigma,b}(f)\geq 1-\delta/k$. In general, we set
$B=\Theta(k)$ and $\sigma\in[\frac{1}{B\Delta},\frac{2}{B\Delta}]$ chosen
uniformly at random, where $\Delta=k\cdot|\mathrm{supp}(\widehat{H}(f))|$.

Then, we show how to compute the HashToBins:

######  Lemma D.2 (Lemma 6.9 in [5]).

Let $z_{j}(t)=x(t)*G^{(j)}_{\sigma,b}(t)$. Let $a:=t/\sigma$ Let
$u\in\mathbb{C}^{B}$ and for $j\in[B]$,

$\displaystyle u_{j}:=\sum_{i\in\mathbb{Z}}x(\sigma(a-j-
iB))e^{-2\pi\mathbf{i}\sigma b(j+iB)}G(j+iB).$

Then, we have that for all $j\in[B]$,

$\displaystyle\widehat{u}_{j}=z_{j}({\sigma a}).$

Note that when we apply Lemma D.2, we take $x(t)=x(t)\cdot H(t)$, where the
latter $x(t)$ is the observable signal, the $H(t)$ is the filter of time
domain (see Section E).

###  D.2 Frequency isolation

Figure 9: An example of the well-isolation event in the frequency domain.
$\widehat{G}^{(j)}_{\sigma,b}$ (the red curve) is the filter of frequency
domain for the $j$-th bin and $H(t)$ is the filter of time domain.
$\widehat{x}^{*}(f)*\widehat{H}(f)$ (the blue curve) is the filtered ground-
truth signal. Under the well-isolation event, there is one small interval that
contains most of the energy. In other words, each bin only contains one-
cluster of frequencies.

The goal of this section is to define and analyze the Frequency Isolation
event. Frequency Isolation requires that the energy of the hashed signal in
each bin is concentrated in a small band in the frequency domain. This
condition is roughly equivalent to say that each bin only contains one cluster
of frequencies. This condition is very useful in proving the concentration of
the filtered signal in the frequency domain, which serves as one of the basic
assumptions of our significant sample generation procedure.

We first introduce Claim D.3. This claim states that if two frequencies are
not close to each other, with large probability, they also not hashed into the
same bin.

######  Claim D.3 (Collision probability, [5]).

For any $\Delta_{0}>0$, let $\sigma$ be a sample uniformly at random from
$[\frac{1}{4B\Delta_{0}},\frac{1}{2B\Delta_{0}}]$. Then, we have:

  1. 1.

If $4\Delta_{0}\leq|f^{+}-f^{-}|<{2(B-1)\Delta_{0}}$, then
$\mathsf{Pr}[h_{\sigma,b}(f^{+})=h_{\sigma,b}(f^{-})]=0$.

  2. 2.

If ${2(B-1)\Delta_{0}}\leq|f^{+}-f^{-}|$, then
$\mathsf{Pr}[h_{\sigma,b}(f^{+})=h_{\sigma,b}(f^{-})]\lesssim\frac{1}{B}$.

We then provide the formal definition of the well-isolation event:

######  Definition D.4 (Well-isolation condition).

We say that a frequency $f^{*}$ is _well-isolated_ under the hashing
parameters $(\sigma,b)$ if, for $j=h_{\sigma,b}(f^{*})$, the hashed signal (in
frequency domain) $\widehat{z}^{(j)}(f):=\widehat{x\cdot
H}(f)\cdot\widehat{G}^{(j)}_{\sigma,b}(f)$ satisfies

$\displaystyle\int_{\overline{I_{f^{*}}}}|{\widehat{z}^{(j)}(f)}|^{2}df\lesssim\varepsilon\cdot
T\mathcal{N}^{2}/k,$

over the interval
$\overline{I_{f^{*}}}=(-\infty,\infty)\setminus(f^{*}-\Delta,f^{*}+\Delta)$.

The following lemma shows the probability of the Frequency Isolation event
under the randomized hashing functions:

######  Lemma D.5 (Lemma 7.19 in [5]).

Let $f^{*}$ be any frequency. Then $f^{*}$ is well-isolated by hashing
parameters $(\sigma,b)$ with probability $\geq 0.9$.

###  D.3 Large offset event

Large offset event is another kind of bad event for the HashToBins procedure,
which happens when a ground-truth frequency is hashed into the changing edge
of the filter $G^{(j)}_{\sigma,b}$. The large offset event breaks the
guarantee of our signal equivalent method, and thus affects the performance of
our significant sample generation and frequency estimation. Fortunately, this
bad event only happens with a small probability.

We first state a tool for analyzing the hashing procedure, which intuitively
says that the modular of a random sampling from a long interval is almost
uniformly distributed:

######  Lemma D.6 ([26, 5]).

For any $\widetilde{T}$, and
$0\leq\widetilde{\varepsilon},\widetilde{\delta}\leq\widetilde{T}$, if we
sample $\widetilde{\sigma}$ uniformly at random from $[A,2A]$, then

$\frac{2\widetilde{\varepsilon}}{\widetilde{T}}-\frac{2\widetilde{\varepsilon}}{A}\leq\mathsf{Pr}\left[\widetilde{\sigma}{\pmod{\widetilde{T}}}\in[\widetilde{\delta}-\widetilde{\varepsilon},\widetilde{\delta}+\widetilde{\varepsilon}~{}]\right]\leq\frac{2\widetilde{\varepsilon}}{\widetilde{T}}+\frac{4\widetilde{\varepsilon}}{A}.$
(7)

Then, we define the large offset event:

######  Definition D.7 (Large offset event).

Given $\sigma\in\mathbb{R}_{+},b\in\mathbb{R}$. Let ${G}^{(j)}_{\sigma,b}$ and
$\delta$ be defined as in Definition C.1. For any $k$-Fourier-sparse signal
$x$, we say the _Large Offset event_ happens, if for any
$f\in\mathrm{supp}(\widehat{x\cdot H})$ and any $j\in[B]$,

$\displaystyle\widehat{G}^{(j)}_{\sigma,b}(f)\in\Big{[}\frac{\delta}{k},1-\frac{\delta}{k}\Big{]}.$

We analyze the probability of large offset event in the following lemma:

######  Lemma D.8.

Let $\Delta_{0}=O(\Delta)$, $\widehat{\sigma}=1/\Delta_{0}$. Given
$b=O(\max\\{F,1/\widehat{\sigma}\\})$, suppose
$\sigma\sim[0.5\widehat{\sigma},\widehat{\sigma}]$ uniformly at random. Then,
with probability at least $0.99$, the Large Offset event does not happen.

Furthermore, with probability at least $0.99$, for any $j\in[k]$, for any
$f\in f_{j}+\mathrm{supp}(\widehat{H})$, it holds that
$\widehat{G}_{\sigma,b}^{(j)}(f)\notin[\delta/k,1-\delta/k]$.

###### Proof.

Let $\alpha$ be defined as in Definition C.1. Let
$I_{G}:=\\{f\in\mathbb{R}~{}|~{}\widehat{G}^{(j)}_{\sigma,b}(f)\in[\delta/k,1-\delta/k]\\}$.
Following from Lemma C.4 Property ii@, we have that
$s_{G}:=|I_{G}{\pmod{1/\sigma}}|\leq 10\alpha\Delta_{0}/B$.

Let $\delta_{f^{*}}(f)$ be the Dirichlet function at $f^{*}$. For any $f_{j}$
with $j\in[k]$, let $I_{f_{j}}:=\mathrm{supp}(\widehat{H}*\delta_{f_{j}})$. We
also define

$\displaystyle
I^{\prime}_{f_{j}}:=\\{f\in\mathbb{R}~{}|~{}[f-s_{G},f+s_{G}]\cap
I_{f_{j}}\neq\emptyset\\}.$

Since $\mathrm{supp}(\widehat{x\cdot
H})=\mathrm{supp}(\widehat{H}*\widehat{x})\subseteq\bigcup_{j=1}^{k}\mathrm{supp}(\widehat{H}*\delta_{f_{j}})$,
we know that the Large Offset event happens if

$\displaystyle\Big{(}\bigcup_{j=1}^{k}I_{f_{j}}\Big{)}\cap
I_{G}\neq\emptyset.$

Thus, it suffices to bound $\mathsf{Pr}[(\cup_{j=1}^{k}I_{f_{j}})\cap
I_{G}\neq\emptyset]$.

First, for any $j\in[k]$, we have

$\displaystyle|I^{\prime}_{f_{j}}|\leq$
$\displaystyle~{}|I_{f_{j}}|+2s_{G}\leq\Delta/B+2s_{G}\leq O(\Delta/B)$ (8)

where the first step follows from the definition of $\Delta$, the second step
follows from $s_{G}\leq 10\alpha\Delta_{0}/B$ and the setting of $\alpha$.

We have that

$\displaystyle~{}\mathsf{Pr}\Big{[}\frac{1}{2B\sigma}+\frac{j}{B\sigma}-b{\pmod{1/\sigma}}\in
I^{\prime}_{f_{j}}{\pmod{1/\sigma}}\Big{]}$ $\displaystyle=$
$\displaystyle~{}\mathsf{Pr}\Big{[}\frac{1}{2B}+\frac{j}{B}{\pmod{1}}\in\sigma
b+\sigma I^{\prime}_{f_{j}}{\pmod{1}}\Big{]}$ $\displaystyle=$
$\displaystyle~{}\mathsf{Pr}\Big{[}\sigma b+\sigma
f_{j}{\pmod{1}}\in\frac{1}{2B}+\frac{j}{B}+\sigma[-|I^{\prime}_{f_{j}}|/2,|I^{\prime}_{f_{j}}|/2]{\pmod{1}}\Big{]}$
$\displaystyle\leq$ $\displaystyle~{}\mathsf{Pr}\Big{[}\sigma b+\sigma
f_{j}{\pmod{1}}\in\frac{1}{2B}+\frac{j}{B}+\widehat{\sigma}[-|I^{\prime}_{f_{j}}|/2,|I^{\prime}_{f_{j}}|/2]{\pmod{1}}\Big{]}$
$\displaystyle\leq$
$\displaystyle~{}{\widehat{\sigma}|I^{\prime}_{f_{j}}|}+\frac{2\widehat{\sigma}|I^{\prime}_{f_{j}}|}{0.5\widehat{\sigma}b+0.5\widehat{\sigma}f_{j}}$
$\displaystyle\leq$ $\displaystyle~{}2{\widehat{\sigma}|I^{\prime}_{f_{j}}|}$
$\displaystyle\leq$ $\displaystyle~{}2{\widehat{\sigma}\cdot O(\Delta/B)}$
$\displaystyle\leq$ $\displaystyle~{}O(1/B)$ (9)

where the first steps are straightforward, the second step follows from the
center of $I^{\prime}_{f_{j}}$ is $f_{j}$, the length of the interval
$I^{\prime}_{f_{j}}$ is $|I^{\prime}_{f_{j}}|$, and $a\in[c-b,c+b]\Rightarrow
c\in[a-b,a+b]$, the third step follows from $\sigma\leq\widehat{\sigma}$, the
forth step follows by applying Lemma D.6 with the following parameters
setting:

$\displaystyle\widetilde{T}=$ $\displaystyle~{}1,$
$\displaystyle\widetilde{\delta}=$ $\displaystyle~{}\frac{1}{2B}+\frac{j}{B},$
$\displaystyle\widetilde{\varepsilon}=$
$\displaystyle~{}\widehat{\sigma}|I^{\prime}_{f_{j}}|/2,$ $\displaystyle A=$
$\displaystyle~{}0.5\widehat{\sigma}b+0.5\widehat{\sigma}f_{j},$
$\displaystyle\widetilde{\sigma}=$ $\displaystyle~{}\sigma b+\sigma f_{j},$

the fifth step follows from $0.5b\geq F\geq f_{j}$ and
$0.5b\widehat{\sigma}\geq 1$, the sixth step follows from Eq. (8), the last
step follows from the definition of $\widehat{\sigma}$.

Similarly, we have that

$\displaystyle\mathsf{Pr}[-\frac{1}{2B\sigma}+\frac{j}{B\sigma}-b{\pmod{1/\sigma}}\in
I^{\prime}_{f_{j}}{\pmod{1/\sigma}}]\leq$ $\displaystyle~{}O(1/B)$ (10)

Note that $I_{G}$ is the edge of filter $G^{(j)}_{\sigma,b}$, under the
meaning of module $1/\sigma$, the center of $G^{(j)}_{\sigma,b}$ is
$\frac{j}{B\sigma}-b$, the length of $G^{(j)}_{\sigma,b}$ is
$\frac{1}{B\sigma}$, the length of the edge is $s_{G}$. Moreover, $I_{f_{j}}$
is an interval center at $f_{j}$ and length $|\mathrm{supp}(\widehat{H})|$. We
can judge whether two interval have intersect $I_{f_{j}}\cap
I_{G}\neq\emptyset$ by moving the length of one interval to another and
judging whether $-\frac{1}{2B\sigma}+\frac{j}{B\sigma}-b{\pmod{1/\sigma}}$,
$\frac{1}{2B\sigma}+\frac{j}{B\sigma}-b{\pmod{1/\sigma}}$ (the end point of
$I_{G}$) contains in $I^{\prime}_{f_{j}}$. By combining Eq. (9) and Eq. (10),
we have that

$\displaystyle\mathsf{Pr}[I_{f_{j}}\cap I_{G}\neq\emptyset]\leq
O(1/B)+O(1/B)=O(1/B).$ (11)

Therefore, by a union bound over all $j\in[k]$, we get that

$\displaystyle\mathsf{Pr}[(\cup_{j=1}^{k}I_{f_{j}})\cap
I_{G}\neq\emptyset]\leq\sum_{j=1}^{k}\mathsf{Pr}[I_{f_{j}}\cap
I_{G}\neq\emptyset]\leq\sum_{j=1}^{k}O(1/B)\leq 0.01,$

where the first step is by union bound, the second step follows from Eq. (11),
and the last step follows from $B=O(k)$. By the definitions of $I_{f_{j}}$ and
$I_{G}$, it implies that with probability at least $0.99$, for any $j\in[k]$,
and any $f\in f_{j}+\mathrm{supp}(\widehat{H})$,
$\widehat{G}_{\sigma,b}^{(j)}(f)\notin[\delta/k,1-\delta/k]$.

The proof of the lemma is then completed. ∎

######  Lemma D.9.

For $x^{*}(t)$ be a $k$-Fourier-sparse signal. For frequency
$f^{*}\in\mathrm{supp}(\widehat{x}^{*})$, let $j=h_{\sigma,b}(f^{*})$ be the
bin that $f^{*}$ hashed into. If Large Offset event not happens, then for
$f\in\mathrm{supp}(\widehat{x}^{*}*\widehat{H})$,

$\displaystyle\widehat{G}^{(j)}_{\sigma,b}(f)\in[1-\delta/k,1]$

###### Proof.

Since Large Offset event not happens, for $f\in\mathbb{R}$,

$\displaystyle\widehat{G}^{(j)}_{\sigma,b}(f)\geq 1-\delta/k\text{ or
}\widehat{G}^{(j)}_{\sigma,b}(f)\leq\delta/k.$

Since Large Offset event not happens and $j=h_{\sigma,b}(f^{*})$, we have that
for $f\in\mathrm{supp}(\widehat{x}^{*}*\widehat{H})$,

$\displaystyle\widehat{G}^{(j)}_{\sigma,b}(f)\geq 1-\delta/k.$

By Lemma C.4 Property i@, ii@, and iii@, we have that

$\displaystyle\widehat{G}^{(j)}_{\sigma,b}(f)\in[1-\delta/k,1].$

∎

##  Appendix E Filter in Time Domain

Figure 10: The filter $H(t)$ of time domain. We use decay region to refer
$[0,a]$ and $[b,T]$. We use fluctuation region to refer $[a,b]$.

In this section, we discuss the filter $H(t)$ of time domain, which is an
analogous of the ideal filter $\mathrm{rect}_{T}(t)$. In the Fourier
interpolation problem, we only care about the time duration $[0,T]$. Thus,
applying the filter $\mathrm{rect}_{T}(t)$ to the observation signal $x(t)$
can cut-off the unobservable part and much simplify the analysis. Since
$\mathrm{rect}_{T}(t)$ have an infinite band width, for efficient computation,
we need to truncate $\mathrm{rect}_{T}(t)$’s frequency domain to a
$\mathrm{poly}(k)/T$-length interval. However, the frequency truncation loses
the high frequency components of the ideal filter $\mathrm{rect}_{T}(t)$, and
the resulting filter $H(t)$ is no longer sharp around the boundary of $[0,T]$.
More specifically, $H(t)$ is exponentially close to $1$ within
$[T/\mathrm{poly}(k),T(1-1/\mathrm{poly}(k))]$, and exponentially close to $0$
outside $[0,T]$.

We first provide the construction of $H(t)$ in [7] and review some known
properties (see Section E.1). Then, we discuss the normalization factor of the
filter and provide a polynomial upper bound of it (see Section E.2). This
bound is crucial for our fluctuation bound of the $H(t)$. Next, we bound the
fluctuation of $H(t)$ during a shrinking interval
$[T/\mathrm{poly}(k),T(1-1/\mathrm{poly}(k))]$ and prove that $H(t)$ is
exponentially close to $1$ in that range (see Section E.3). Furthermore, we
prove that $H(t)$ preserve the energy of Fourier sparse signal in the duration
$[0,T]$ (see Section E.4).

###  E.1 Time domain filter construction

We first introduce an growth rate bound from [7]. This theorem bound the
growth of Fourier sparse signal outside of the duration $[0,T]$ by an exponent
function of base $t$. This bound in this theorem is high related to the size
of the support set of $\widehat{H}(f)$.

######  Theorem E.1 ([7]).

There exists $S=O(k^{2}\log k)$ such that for any $|t|>T$ and
$g(t)=\sum_{j=1}^{k}v_{j}\cdot e^{2\pi\mathbf{i}f_{j}t}$,
$|g(t)|^{2}\leq\mathrm{poly}(k)\cdot\underset{x\in[-T,T]}{\operatorname*{{\mathbb{E}}}}[|g(x)|^{2}]\cdot|\frac{t}{T}|^{S}$.

The definition of the time domain filter $H(t)$ in [7] is given in below.
Intuitively, it uses some powers of $\operatorname{sinc}(t)$ to approximate
$\delta_{0}(t)*\mathrm{rect}_{1}(t)=\mathrm{rect}_{1}(t)$, thus one can get
finite band-limit and good approximation at the same time.

######  Definition E.2 (Definition 4.1 in [7]).

Given an energy bound $R$ satisfying

$\displaystyle|x(t)|^{2}\lesssim R\|x(t)\|_{T}^{2},~{}~{}~{}\forall
t\in[0,T]\text{ and $k$-Fourier sparse signal $x(t)$},$

the growth rate $S$ a power of two, $C\in 2\mathbb{Z}$, and
$C_{0}\in\pi\mathbb{Z}$,we define the filter function:

$\displaystyle H_{1}(t)=s_{0}\cdot\left(\operatorname{sinc}(C_{0}R\cdot
t)^{C\log R}\cdot\operatorname{sinc}\big{(}C_{0}\cdot S\cdot
t\big{)}^{C}\cdot\operatorname{sinc}\big{(}\frac{C_{0}\cdot S}{2}\cdot
t\big{)}^{2C}\cdots\operatorname{sinc}\big{(}C_{0}\cdot t\big{)}^{C\cdot
S}\right)*\mathrm{rect}_{1}(t),$

where $s_{0}\in\mathbb{R}^{+}$ is a parameter to normalize $H_{1}(0)=1$. Its
Fourier transform is as follows:

$\displaystyle\widehat{H}_{1}(f)=s_{0}\cdot\left(\mathrm{rect}_{C_{0}R}(f)^{*C\log
R}*\mathrm{rect}_{C_{0}\cdot S}(f)^{*C}*\mathrm{rect}_{\frac{C_{0}\cdot
S}{2}}(f)^{*2C}*\cdots*\mathrm{rect}_{C_{0}}(f)^{*CS}\right)\cdot\operatorname{sinc}(f/2).$

We then state some basic properties of the time domain filter in [7]. The
following lemma bounds the support size of $\widehat{H}_{1}(f)$:

######  Lemma E.3 ([7]).

Let $C_{0}=\Theta(C)$. we have that

$\displaystyle|\mathrm{supp}(\widehat{H}_{1}(f))|=O(C^{2}R\log R+C^{2}S\log
S).$

The following theorem shows some time domain properties of the filter:

######  Theorem E.4 (Theorem 4.2 in [7]).

Let $R,S>0$, let $C\in 2\mathbb{Z}$, $C_{0}\in\pi\mathbb{Z}$,
$C_{0}=\Theta(C)$, and define $\alpha=(\frac{1}{2}+\frac{1.2}{\pi C_{0}R})$.
Consider any function $x$ satisfying the following two conditions:

  1. 1.

$\underset{t\in[-1,1]}{\sup}\big{[}|x(t)|^{2}\big{]}\leq
R\cdot\underset{t\in[-1,1]}{\operatorname*{{\mathbb{E}}}}\big{[}|x(t)|^{2}\big{]}$,

  2. 2.

$\mathrm{poly}(R)\cdot\underset{t\in[-1,1]}{\operatorname*{{\mathbb{E}}}}\big{[}|x(t)|^{2}\big{]}\cdot|{t}|^{S}$
for $t\notin[-1,1]$,

Then, we have that the filter function $H(t)=H_{1}\big{(}\alpha t\big{)}$
satisfies

  * •

Part 1. $\int_{-1}^{1}|x(t)\cdot H\big{(}t\big{)}|^{2}\mathrm{d}t\geq
0.9\int_{-1}^{1}|x(t)|^{2}\mathrm{d}t$,

  * •

Part 2. $\int_{-1}^{1}|x(t)\cdot H\big{(}t\big{)}|^{2}\mathrm{d}t\geq
0.95\int_{-\infty}^{\infty}|x(t)\cdot H\big{(}t\big{)}|^{2}\mathrm{d}t$,

  * •

Part 3. $|H(t)|\leq 1.01$ for any $t$.

Throughout this paper, we denote $H(t)$ as the following re-scaling of
$H_{1}(t)$:

######  Definition E.5.

Let $\alpha=(\frac{1}{2}+\frac{1.2}{\pi C_{0}R})$. Let $H_{1}(t)$ be defined
as in Definition E.2. The filter $H(t)$ is defined as:

$\displaystyle H(t):=H_{1}(\alpha t).$

and setting $R=S=O(k^{2})$, $R=2^{s}$, where $s\in\mathbb{Z}_{+}$,
$C=O(\log(1/\delta_{1}))$, $C\in 2\mathbb{Z}$, $C_{0}=\Theta(C)$ and
$C_{0}\in\pi\mathbb{Z}$.

###  E.2 Normalization factor of the filter

The goal of this section is to prove Lemma E.6, an upper-bound for the
normalization factor $s_{0}$. This lemma will be used later to ensure that the
scaling factor will not break the exponential small fluctuation of Section
E.3. We note that the same result has been proved in [7], and we reprove it
below for completeness.

######  Lemma E.6 (Lemma 7.2 in [7]).

It holds that

$\displaystyle s_{0}\leq O({CR\sqrt{{C\log R}}}).$

###### Proof.

We first have that,

$\displaystyle H_{1}(t)$
$\displaystyle~{}=s_{0}\cdot(\operatorname{sinc}(C_{0}R\cdot t)^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot t\big{)}^{2^{i}\cdot C})*\mathrm{rect}_{1}(t)$
$\displaystyle~{}=s_{0}\cdot\int_{-\infty}^{\infty}\operatorname{sinc}(C_{0}R\cdot\tau)^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot\tau\big{)}^{2^{i}\cdot
C}\cdot\mathrm{rect}_{1}(t-\tau)\mathrm{d}\tau$
$\displaystyle~{}=s_{0}\cdot\int_{t-0.5}^{t+0.5}\operatorname{sinc}(C_{0}R\cdot\tau)^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot\tau\big{)}^{2^{i}\cdot C}\mathrm{d}\tau,$

where the first step follows from the definition of $H_{1}(t)$, the second
step follows from the definition of the convolution, the third step follows
from the definition of $\mathrm{rect}_{2}(t)$ function. Thus,

$\displaystyle
H_{1}(0)=s_{0}\cdot\int_{-0.5}^{+0.5}\operatorname{sinc}(C_{0}R\cdot\tau)^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot\tau\big{)}^{2^{i}\cdot C}\mathrm{d}\tau$

Let $U:=({2C_{0}\log R})^{-1/2}$. We have that

$\displaystyle~{}\int_{-0.5}^{+0.5}\operatorname{sinc}(C_{0}R\cdot\tau)^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot\tau\big{)}^{2^{i}\cdot C}\mathrm{d}\tau$ $\displaystyle\geq$
$\displaystyle~{}\int_{-\frac{1}{\pi C_{0}R}}^{+\frac{1}{\pi
C_{0}R}}\operatorname{sinc}(C_{0}R\cdot\tau)^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot\tau\big{)}^{2^{i}\cdot C}\mathrm{d}\tau$ $\displaystyle=$
$\displaystyle~{}\frac{1}{\pi
C_{0}R}\int_{-{1}}^{+{1}}\operatorname{sinc}(\frac{\upsilon}{\pi})^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{\upsilon}{2^{i}\pi}\big{)}^{2^{i}\cdot
C}\mathrm{d}\upsilon$ $\displaystyle\geq$ $\displaystyle~{}\frac{1}{\pi
C_{0}R}\int_{-U}^{+U}\operatorname{sinc}(\frac{\upsilon}{\pi})^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{\upsilon}{2^{i}\pi}\big{)}^{2^{i}\cdot
C}\mathrm{d}\upsilon$ $\displaystyle\geq$ $\displaystyle~{}\frac{1}{\pi
C_{0}R}\int_{-U}^{+U}(1-\frac{\upsilon^{2}}{6})^{C\log
R}\cdot\prod_{i=0}^{\log(S)}(1-\frac{\upsilon^{2}}{4^{i}6})^{2^{i}\cdot
C}\mathrm{d}\upsilon$ $\displaystyle\geq$ $\displaystyle~{}\frac{1}{\pi
C_{0}R}\int_{-U}^{+U}(1-{C\log
R}\cdot\frac{\upsilon^{2}}{6}-\sum_{i=0}^{\log(S)}C\cdot\frac{\upsilon^{2}}{2^{i}6})\mathrm{d}\upsilon$
$\displaystyle\geq$ $\displaystyle~{}\frac{1}{\pi
C_{0}R}\int_{-U}^{+U}(1-{C\log
R}\cdot\frac{\upsilon^{2}}{3})\mathrm{d}\upsilon$ $\displaystyle=$
$\displaystyle~{}\frac{1}{\pi C_{0}R}(2U-{2C\log R}\cdot\frac{U^{3}}{9})$
$\displaystyle\geq$ $\displaystyle~{}\frac{1}{\pi C_{0}R\sqrt{{2C_{0}\log
R}}},$ (12)

where the first step follows from $R=O(k^{2})$, $C_{0}=O(\log(1/\delta_{1}))$,
$0.5\geq\frac{1}{\pi C_{0}R}$, second step follows from changing the variable
$\nu=\pi CR\cdot\tau$, the third step follows from $U<1$, the forth step
follows from Fact E.7, the fifth step is follows from $(1-a)(1-b)\geq 1-a-b$,
the sixth step follows from $\log(R)>2$, the seventh step is straight forward,
the eighth step follows from setting $U=({2C_{0}\log R})^{-1/2}$ and
$C_{0}=\Theta(C)$.

As a result, we have that

$\displaystyle s_{0}\leq H_{1}(0)\cdot{\pi CR\sqrt{{2C\log R}}}={\pi
CR\sqrt{{2C\log R}}}$

where the first step follows from Eq. (12), the second step follows from
$H_{1}(0)=1$.

∎

######  Fact E.7.

For any $t\in\mathbb{R}$,

$\displaystyle 1-\frac{(\pi t)^{2}}{3!}\leq\operatorname{sinc}(t)\leq 1.$

###  E.3 Fluctuation bound

The idea filter $\mathrm{rect}_{T}(t)$ has a constant value $1$ in the
interval $[0,T]$. Due to the frequency domain truncation in $H(t)$, it
deviates from $\mathrm{rect}_{T}(t)$ with different magnitudes in different
regions. In this section, we prove the Lemma E.8, which shows that $H(t)$ is
fluctuating near $1$ in the “interior” of $[0,T]$ (i.e.,
$[0+\frac{T}{\mathrm{poly}(k)},T-\frac{T}{\mathrm{poly}(k)}]$). It serves as
an important tool for analyzing the error in our signal equivalent method.

######  Lemma E.8.

For filter $H_{1}(t)$ defined in Definition E.2 with the parameters
$C=\log(1/\delta_{1})$, $C_{0}=\Theta(C)$, $R=S$, and $S=2^{s}$ (where
$s\in\mathbb{Z}_{+}$), $C_{0}\in\pi\mathbb{Z}$, we have that

$\displaystyle H_{1}(t)\in[1-\delta_{1},1],\forall|t|<0.5-\frac{\pi}{C_{0}R}.$

Moreover, $H(t)\in[1-\delta_{1},1]$ for any
$t\in[\frac{T}{2}-\alpha^{-1}(\frac{1}{2}-\frac{\pi}{C_{0}R})\frac{T}{2},\frac{T}{2}+\alpha^{-1}(\frac{1}{2}-\frac{\pi}{C_{0}R})\frac{T}{2}]$.

###### Proof.

The proof consists of two parts: upper bound and lower bound. For the upper
bound, the idea is to compare the value of $H(t)$ with $H(0)$ by analyzing the
gradient of $H(t)$. And the lower bound follows from directly estimating the
integral of the product of $\operatorname{sinc}$ functions.

##### Upper bound:

We have that $H_{1}(0)=1$ by definition. We will show $H_{1}(t)\leq 1$ by
proving $H_{1}(t)$ is monotonically decreasing in $t$.

We have that,

$\displaystyle H_{1}(t)$
$\displaystyle~{}=s_{0}\cdot(\operatorname{sinc}(C_{0}R\cdot t)^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot t\big{)}^{2^{i}\cdot C})*\mathrm{rect}_{1}(t)$
$\displaystyle~{}=s_{0}\cdot\int_{-\infty}^{\infty}\operatorname{sinc}(C_{0}R\cdot\tau)^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot\tau\big{)}^{2^{i}\cdot
C}\cdot\mathrm{rect}_{1}(t-\tau)\mathrm{d}\tau$
$\displaystyle~{}=s_{0}\cdot\int_{t-0.5}^{t+0.5}\operatorname{sinc}(C_{0}R\cdot\tau)^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot\tau\big{)}^{2^{i}\cdot C}\mathrm{d}\tau,$ (13)

where the first step follows from the definition of $H_{1}(t)$, the second
step follows from the definition of the convolution, the third step follows
from the definition of $\mathrm{rect}_{1}(t)$ function.

Since $C\log R\in 2\mathbb{Z}$, $2^{i}\cdot C\in 2\mathbb{Z}$, we have that

$\displaystyle\operatorname{sinc}(C_{0}R\cdot\tau)^{C\log R}\geq 0,$

and

$\displaystyle\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot\tau\big{)}^{2^{i}\cdot C}\geq 0.$

Moreover, by setting $C_{0}=\pi\mathbb{Z}$, we have that

$\displaystyle 2\mod{\frac{2\pi}{C_{0}}}=0.$ (14)

By Eq. (14), we have that

$\displaystyle\sin\big{(}\frac{C_{0}\cdot S}{2^{i}}\cdot(t+0.5)\big{)}=$
$\displaystyle~{}\sin\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot(t-0.5)\big{)},~{}~{}~{}\forall
i\in\\{0,\cdots,\log(S)\\},~{}~{}\text{and}$
$\displaystyle\sin(C_{0}R\cdot(t+0.5))=$
$\displaystyle~{}\sin(C_{0}R\cdot(t-0.5)).$

Furthermore, for any $t>0$,

$\displaystyle\big{(}\frac{C_{0}\cdot S}{2^{i}}\cdot(t+0.5)\big{)}^{-1}\leq$
$\displaystyle~{}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot(t-0.5)\big{)}^{-1},\forall
i\in\\{0,\cdots,\log(S)\\},~{}~{}\text{and}$
$\displaystyle(C_{0}R\cdot(t+0.5))^{-1}\leq$
$\displaystyle~{}(C_{0}R\cdot(t-0.5))^{-1}.$

Thus,

$\displaystyle|\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot(t+0.5)\big{)}|\leq$
$\displaystyle~{}|\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot(t-0.5)\big{)}|,~{}~{}~{}\forall
i\in\\{0,\cdots,\log(S)\\},~{}~{}\text{and}$
$\displaystyle|\operatorname{sinc}(C_{0}R\cdot(t+0.5))|\leq$
$\displaystyle~{}|\operatorname{sinc}(C_{0}R\cdot(t-0.5))|.$ (15)

Then, we have that

$\displaystyle\frac{H_{1}^{\prime}(t)}{s_{0}}=$
$\displaystyle~{}\operatorname{sinc}(C_{0}R\cdot(t+0.5))^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot(t+0.5)\big{)}^{2^{i}\cdot C}$
$\displaystyle~{}\quad-\operatorname{sinc}(C_{0}R\cdot(t-0.5))^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot(t-0.5)\big{)}^{2^{i}\cdot C}$ $\displaystyle<$
$\displaystyle~{}0,$

where the first step is straight forward, the second step follows from Eq.
(15).

Thus, $H_{1}(t)<H_{1}(0)=1$ for any $t>0$.

Similarly, we also have that $H_{1}(t)<H_{1}(0)=1$ for any $t\leq 0$ since
$H_{1}(t)$ is symmetric with respect to $t$.

##### Lower bound:

We have that, for any $|t|<0.5-\frac{\pi}{C_{0}R}$,

$\displaystyle~{}\int_{-\infty}^{t-0.5}\operatorname{sinc}(C_{0}R\cdot\tau)^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot\tau\big{)}^{2^{i}\cdot C}\mathrm{d}\tau$ $\displaystyle=$
$\displaystyle~{}\int_{0.5-t}^{\infty}\operatorname{sinc}(C_{0}R\cdot\tau)^{C\log(R)}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot\tau\big{)}^{2^{i}\cdot C}\mathrm{d}\tau$ $\displaystyle\leq$
$\displaystyle~{}\int_{0.5-t}^{\infty}\operatorname{sinc}(C_{0}R\cdot\tau)^{C\log(R)}\mathrm{d}\tau$
$\displaystyle\leq$
$\displaystyle~{}\int_{0.5-t}^{\infty}(C_{0}R\cdot\tau)^{-C\log(R)}\mathrm{d}\tau$
$\displaystyle\leq$
$\displaystyle~{}\int_{\frac{\pi}{C_{0}R}}^{\infty}(C_{0}R\cdot\tau)^{-C\log(R)}\mathrm{d}\tau$
$\displaystyle=$
$\displaystyle~{}\frac{1}{C_{0}R}\int_{\pi}^{\infty}\upsilon^{-C\log(R)}\mathrm{d}\upsilon$
$\displaystyle=$
$\displaystyle~{}\frac{1}{C_{0}R}\frac{1}{C\log(R)-1}\pi^{-C\log(R)+1}$
$\displaystyle\lesssim$
$\displaystyle~{}\frac{1}{C_{0}^{2}R\log(R)}\delta_{1},$ (16)

where the first step is straight forward, the second step follows from
$\operatorname{sinc}(x)\leq 1$, the third step is follows from
$\operatorname{sinc}(x)\leq 1/x$, the forth step follows follows from
$0.5-t\geq\frac{\pi}{C_{0}R}$, the fifth step follows from $\upsilon:=CR\tau$,
the sixth step is straight forward, the seventh step follows from $\log(R)>1$,
$C\geq\log(1/\delta_{1})$.

Hence, for any $t>0$,

$\displaystyle H_{1}(t)=$
$\displaystyle~{}s_{0}\cdot\int_{t-0.5}^{t+0.5}\operatorname{sinc}(C_{0}R\cdot\tau)^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot\tau\big{)}^{2^{i}\cdot C}\mathrm{d}\tau$ $\displaystyle=$
$\displaystyle~{}H_{1}(0)+s_{0}\cdot\int_{1}^{t+0.5}\operatorname{sinc}(C_{0}R\cdot\tau)^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot\tau\big{)}^{2^{i}\cdot C}\mathrm{d}\tau$
$\displaystyle~{}\quad-
s_{0}\cdot\int_{-1}^{t-0.5}\operatorname{sinc}(C_{0}R\cdot\tau)^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot\tau\big{)}^{2^{i}\cdot C}\mathrm{d}\tau$ $\displaystyle\geq$
$\displaystyle~{}H_{1}(0)-s_{0}\cdot\int_{-\infty}^{t-0.5}\operatorname{sinc}(C_{0}R\cdot\tau)^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot\tau\big{)}^{2^{i}\cdot C}\mathrm{d}\tau$ $\displaystyle\geq$
$\displaystyle~{}H_{1}(0)-s_{0}O(\frac{1}{C_{0}^{2}R\log(R)})\delta_{1}$
$\displaystyle=$
$\displaystyle~{}1-s_{0}O(\frac{1}{C_{0}^{2}R\log(R)})\delta_{1}$
$\displaystyle\geq$ $\displaystyle~{}1-O(\delta_{1}),$

where the first step follows from Eq. (13), the second step is straight
forward, the third step follows from

$\displaystyle\operatorname{sinc}(C_{0}R\cdot\tau)^{C\log
R}\cdot\prod_{i=0}^{\log(S)}\operatorname{sinc}\big{(}\frac{C_{0}\cdot
S}{2^{i}}\cdot\tau\big{)}^{2^{i}\cdot C}\geq
0,~{}~{}~{}\forall\tau\in\mathbb{R}$

the forth step follows from Eq. (16), the fifth step follows from
$H_{1}(0)=1$, the sixth step follows from Lemma E.6.

By re-scaling $\delta_{1}$, we get that $H(t)\geq 1-\delta_{1}$ for any
$|t|<0.5-\frac{\pi}{C_{0}R}$.

The lemma then follows from the upper and lower bounds.

∎

###  E.4 Energy preserving of the time domain filter

In this section, we show the properties of $H(t)$ that we use in the rest of
the paper.

We first prove Lemma E.9, which summarizes the results in above sections and
prove the energy preserving property of $H(t)$.

######  Lemma E.9.

The filter function $(H(t),\widehat{H}(f))$ has the following properties:

$\displaystyle\mathrm{Property~{}\@slowromancap i@}:$ $\displaystyle|H(t)|\leq
1.01,~{}\forall t\in\mathbb{R}$
$\displaystyle\mathrm{Property~{}\@slowromancap ii@}:$ $\displaystyle
1-\delta_{1}\leq H(t)\leq
1,~{}\forall|t|<\alpha^{-1}(\frac{1}{2}-\frac{\pi}{CR})$
$\displaystyle\mathrm{Property~{}\@slowromancap iii@}:$
$\displaystyle|\mathrm{supp}(\widehat{H}(f))|\leq
O(k^{2}\log^{2}(k)\log^{2}(1/\delta_{1}))$
$\displaystyle\mathrm{Property~{}\@slowromancap iv@}:$
$\displaystyle\int_{-\infty}^{+\infty}\bigl{|}x^{*}(t)\cdot
H(t)\cdot(1-\mathrm{rect}_{2}(t))\bigr{|}^{2}\mathrm{d}t<0.1\int_{-\infty}^{+\infty}|x^{*}(t)\cdot\mathrm{rect}_{2}(t)|^{2}\mathrm{d}t$
$\displaystyle\mathrm{Property~{}\@slowromancap v@}:$
$\displaystyle\int_{-\infty}^{+\infty}|x^{*}(t)\cdot
H(t)\cdot\mathrm{rect}_{2}(t)|^{2}\mathrm{d}t\in[0.9,1.1]\cdot\int_{-\infty}^{+\infty}|x^{*}(t)\cdot\mathrm{rect}_{2}(t)|^{2}\mathrm{d}t$

###### Proof.

We prove each of the five properties in below.

##### Property I:

By Theorem E.4 Part 3, we have that

$\displaystyle|H(t)|\leq 1.01.$

##### Property II:

By Lemma E.8, we have that

$\displaystyle 1-\delta_{1}\leq H(t)\leq
1,~{}\forall|t|<\alpha^{-1}(\frac{1}{2}-\frac{\pi}{CR}).$

##### Property III:

By the $k$-Fourier-sparse signals’ energy bound (Theorem B.1), we have that

$\displaystyle R=O(k^{2}).$

By Theorem E.1, we have that

$\displaystyle S=O(k^{2}\log k).$

Then, by Lemma E.3, we have that

$\displaystyle|\mathrm{supp}(\widehat{H}(f))|=$ $\displaystyle~{}C^{2}R\log
R+C^{2}S\log S$ $\displaystyle=$
$\displaystyle~{}O(\log(1/\delta_{1}))^{2}\cdot O(k^{2}\log k\log(k^{2}\log
k))$ $\displaystyle=$
$\displaystyle~{}O(k^{2}\log^{2}k\log^{2}(1/\delta_{1})).$

##### Property IV:

We have that

$\displaystyle~{}\int_{-\infty}^{+\infty}\bigl{|}x^{*}(t)\cdot
H(t)\cdot(1-\mathrm{rect}_{1}(t))\bigr{|}^{2}\mathrm{d}t$ $\displaystyle=$
$\displaystyle~{}\int_{-\infty}^{+\infty}\bigl{|}x^{*}(t)\cdot
H(t)\bigr{|}^{2}\mathrm{d}t-\int_{-1}^{1}\bigl{|}x^{*}(t)\cdot
H(t)\bigr{|}^{2}\mathrm{d}t$ $\displaystyle\leq$
$\displaystyle~{}0.06\int_{-1}^{+1}\bigl{|}x^{*}(t)\cdot
H(t)\bigr{|}^{2}\mathrm{d}t$ $\displaystyle\leq$
$\displaystyle~{}0.1\int_{-1}^{+1}\bigl{|}x^{*}(t)\bigr{|}^{2}\mathrm{d}t$
$\displaystyle=$
$\displaystyle~{}0.1\int_{-\infty}^{+\infty}|x^{*}(t)\cdot\mathrm{rect}_{1}(t)|^{2}\mathrm{d}t,$

where the first step is straight forward, the second step follows from Theorem
E.4 Part 2, the third step follows from Theorem E.4 Part 3, the forth step is
straight forward.

##### Property V:

We first prove the upper bound:

$\displaystyle~{}\int_{-\infty}^{+\infty}|x^{*}(t)\cdot
H(t)\cdot\mathrm{rect}_{1}(t)|^{2}\mathrm{d}t$ $\displaystyle=$
$\displaystyle~{}\int_{-1}^{+1}|x^{*}(t)\cdot H(t)|^{2}\mathrm{d}t$
$\displaystyle\leq$
$\displaystyle~{}1.1\int_{-1}^{+1}|x^{*}(t)|^{2}\mathrm{d}t$ $\displaystyle=$
$\displaystyle~{}1.1\int_{-\infty}^{+\infty}|x^{*}(t)\cdot\mathrm{rect}_{1}(t)|^{2}\mathrm{d}t,$

where the first step is straight forward, the second step follows from Theorem
E.4 Part 3, the third step is straight forward.

Then, we prove the lower bound:

$\displaystyle~{}\int_{-\infty}^{+\infty}|x^{*}(t)\cdot
H(t)\cdot\mathrm{rect}_{1}(t)|^{2}\mathrm{d}t$ $\displaystyle=$
$\displaystyle~{}\int_{-1}^{+1}|x^{*}(t)\cdot H(t)|^{2}\mathrm{d}t$
$\displaystyle\geq$
$\displaystyle~{}0.9\cdot\int_{-1}^{+1}|x^{*}(t)|^{2}\mathrm{d}t$
$\displaystyle=$
$\displaystyle~{}0.9\cdot\int_{-\infty}^{+\infty}|x^{*}(t)\cdot\mathrm{rect}_{1}(t)|^{2}\mathrm{d}t$

where the first step is straight forward, the second step follows from Theorem
E.4 Part 1, the third step is straight forward.

∎

The following lemma bounds the length of the fluctuation region (where $H(t)$
is close to $1$) in the time domain.

######  Lemma E.10.

Let $\Delta=k|\mathrm{supp}(\widehat{H}(f))|$, $\beta=O(1/\Delta)$,
$L=\frac{T}{2}-\alpha^{-1}(\frac{1}{2}-\frac{\pi}{C_{0}R})\frac{T}{2},R=\frac{T}{2}+\alpha^{-1}(\frac{1}{2}-\frac{\pi}{C_{0}R})\frac{T}{2}-\beta$,
we have that

$\displaystyle T-k^{2}(T+L-R)\eqsim T,$

and

$\displaystyle R-L\eqsim T.$

###### Proof.

Let $U:=[L,R]$. By Lemma E.8, we have that for any $t_{0}\in U$,

$\displaystyle H(t)>1-\delta_{1},\forall t\in[t_{0},t_{0}+\beta].$

We have that

$\displaystyle R-L=$ $\displaystyle~{}|U|$ $\displaystyle=$
$\displaystyle~{}((\frac{1}{2}+\frac{1.2}{\pi
CR})^{-1}\cdot(\frac{1}{2}-\frac{\pi}{CR})-\beta)\cdot T$
$\displaystyle\eqsim$ $\displaystyle~{}T,$

where the first step follows from the definition of $L,R$, the second step
follows from Lemma E.9 Property ii@, the third step follows from $\Delta,CR\gg
1$.

We have that

$\displaystyle T+L-R=$ $\displaystyle~{}T-|U|$ $\displaystyle=$
$\displaystyle~{}(1-(\frac{1}{2}+\frac{1.2}{\pi
CR})^{-1}\cdot(\frac{1}{2}-\frac{\pi}{CR}))\cdot T+\beta T$ $\displaystyle=$
$\displaystyle~{}\frac{2\pi+{2.4}/{\pi}}{CR+{2.4}/{\pi}}\cdot T+\beta T,$ (17)

where the first step follows from the definition of $L,R$, the second step
follows from Lemma E.9 Property ii@, the third step is straight forward.

Then, we have that

$\displaystyle
T-k^{2}(T+L-R)=T-k^{2}\cdot(\frac{2\pi+{2.4}/{\pi}}{CR+{2.4}/{\pi}}+\beta)\cdot
T\eqsim T,$

where the first step follows from Eq. (17), the second step follows from
$C=O(\log(1/\delta_{1}))$, $R=k^{2}$, $k^{2}\beta<1/k$.

∎

##  Appendix F Ideal Filter Approximation

As we discussed in previous sections, the filtered signal $z^{(j)}(t)=(x\cdot
H)*G_{\sigma,b}^{(j)}(t)$ is the signal in the $j$-th bin by the HashToBins
procedure. In this section, we consider an approximation of the frequency
domain filter $G_{\sigma,b}^{(j)}$ by the _ideal filter_
$I_{\sigma,b}^{(j)}(t)$ defined by its Fourier transform:

$\displaystyle\widehat{I}_{\sigma,b}^{(j)}(f):=\begin{cases}1,&~{}\widehat{G}^{(j)}_{\sigma,b}(f)>1-\delta_{1}\\\
0,&~{}\text{otherwise}\end{cases}$ (18)

Intuitively, $I_{\sigma,b}^{(j)}$ is “denoising” the frequency domain filter
$\widehat{G}^{(j)}_{\sigma,b}$ in the sense that it rounds the heavy Fourier
coefficients of $\widehat{G}^{(j)}_{\sigma,b}$ to 1 and rounds the remaining
Fourier coefficients to 0. The main purpose of this section is to show that
$(x\cdot H)*I_{\sigma,b}^{(j)}$ is a good approximation of $z^{(j)}$. For
simplicity, we will use $I$ to denote $I_{\sigma,b}^{(j)}$ when $\sigma,b,j$
are clear from context.

We first show a commuting property of the ideal filter (see Section F.1).
Then, we derive the approximation error bound of the ideally filtered signals
(see Section F.2).

###  F.1 Swap the order of filtering

We first prove a good property of the ideal filter that $I_{\sigma,b}^{(j)}$
“commutes” with the time domain filter $H$ with high probability over the
random hashing function.

######  Lemma F.1.

Let $\delta_{1}$ be the $\delta$ defined in Lemma C.4.Let $H$ be defined as in
Definition E.5, ${G}^{(j)}_{\sigma,b}$ be defined as in Definition C.2. Let
the ideal filter $I=I_{\sigma,b}^{(j)}$ be defined as in Eq. (18).

Then, for any $x\in{\cal F}_{k,F}$, with probability $0.9$ over the choice of
$(\sigma,b)$, for any $j\in[B]$,

$\displaystyle(x\cdot H)*I(t)=(x*I)(t)\cdot H(t)~{}~{}~{}\forall
t\in\mathbb{R}.$

###### Proof.

By Fourier transformation, we have

$\displaystyle(x\cdot H)*I(t)=$
$\displaystyle~{}\int_{-\infty}^{\infty}(\widehat{x}*\widehat{H})(f)\cdot\widehat{I}(f)\cdot\exp(2\pi\mathbf{i}ft)\mathrm{d}f.$

We will show that
$(\widehat{x}*\widehat{H})(f)\cdot\widehat{I}(f)=((\widehat{x}\cdot\widehat{I})*\widehat{H})(f)$
with high probability.

On the one hand,

$\displaystyle(\widehat{x}*\widehat{H})(f)\cdot\widehat{I}(f)=$
$\displaystyle~{}\sum_{j=1}^{k}v_{j}\cdot(\delta_{f_{j}}*\widehat{H})(f)\cdot\widehat{I}(f)$
$\displaystyle=$
$\displaystyle~{}\sum_{j=1}^{k}v_{j}\cdot\widehat{H}(f-f_{j})\cdot\widehat{I}(f)$
$\displaystyle=$
$\displaystyle~{}\sum_{j=1}^{k}v_{j}\cdot\widehat{H}(f-f_{j})\cdot{\bf
1}_{f\in\mathrm{supp}(\widehat{I})},$

where the first step follows from
$\widehat{x}(f)=\sum_{j=1}^{k}v_{j}\cdot\delta_{f_{j}}(f)$, the second step
follows from the convolution property of Delta function. By Lemma D.8, we get
that with probability at least $0.9$, for any $j\in[k]$ and any
$f\in\mathrm{supp}(\widehat{H})+f_{j}$, either
$\widehat{G}_{\sigma,b}^{(j)}<\delta_{1}$ or
$\widehat{G}_{\sigma,b}^{(j)}>1-\delta_{1}$. In other words, either
$f_{j}+\mathrm{supp}(\widehat{H})\subseteq\mathrm{supp}(\widehat{I})$ or
$f_{j}+\mathrm{supp}(\widehat{H})\cap\mathrm{supp}(\widehat{I})=\emptyset$.
Since $0\in\mathrm{supp}(\widehat{H})$, we get that for any $f\in
f_{j}+\mathrm{supp}(\widehat{H})$,

$\displaystyle
f\in\mathrm{supp}(\widehat{I})~{}~{}\Longleftrightarrow~{}~{}f_{j}\in\mathrm{supp}(\widehat{I}).$

Hence, we have

$\displaystyle(\widehat{x}*\widehat{H})(f)\cdot\widehat{I}(f)=\sum_{j\in[k]:f_{j}\in\mathrm{supp}(\widehat{I})}v_{j}\cdot\widehat{H}(f-f_{j}).$

On the other hand,

$\displaystyle(\widehat{x}\cdot\widehat{I})*\widehat{H}(f)=$
$\displaystyle~{}\sum_{j\in[k]:f_{j}\in\mathrm{supp}(\widehat{I})}v_{j}\cdot\delta_{f_{j}}*\widehat{H}(f)$
$\displaystyle=$
$\displaystyle~{}\sum_{j\in[k]:f_{j}\in\mathrm{supp}(\widehat{I})}v_{j}\cdot\widehat{H}(f-f_{j})$
$\displaystyle=$
$\displaystyle~{}(\widehat{x}*\widehat{H})(f)\cdot\widehat{I}(f).$

Therefore,

$\displaystyle(x\cdot H)*I(t)=$
$\displaystyle~{}\int_{-\infty}^{\infty}(\widehat{x}*\widehat{H})(f)\cdot\widehat{I}(f)\cdot\exp(2\pi\mathbf{i}ft)\mathrm{d}f$
$\displaystyle=$
$\displaystyle~{}\int_{-\infty}^{\infty}(\widehat{x}\cdot\widehat{I})*\widehat{H}(f)\cdot\exp(2\pi\mathbf{i}ft)\mathrm{d}f$
$\displaystyle=$ $\displaystyle~{}(x*I)(t)\cdot H(t),$

where the last step follows from the definition of Fourier transform.

The lemma is then proved.

∎

###  F.2 Approximation error bounds

We analyze the approximation error due to replacing
$\widehat{G}_{\sigma,b}^{(j)}$ with the ideal filter $I_{\sigma,b}^{(j)}$
defined by Eq. (18). The following lemma gives a point-wise error bound.

######  Lemma F.2.

Let $\delta_{1}$ be defined as in Lemma C.4. Let $H$ be defined as in
Definition E.5, ${G}^{(j)}_{\sigma,b}$ be defined as in Definition C.2.

For any $x\in{\cal F}_{k,F}$, we have that with probability $0.9$, for any
$j\in[B]$,

$\displaystyle|(x\cdot H)*{G}^{(j)}_{\sigma,b}(t)-(x\cdot
H)*I(t)|\lesssim\delta_{1}\sqrt{T|S|}\cdot\|x(t)\|_{T}~{}~{}~{}\forall
t\in\mathbb{R}.$

###### Proof.

Let $S:=\mathrm{supp}(\widehat{x}*\widehat{H})$ be defined as the support set
of $\widehat{x}*\widehat{H}$. Then $|S|\leq\Delta$.

We have that

$\displaystyle~{}|(x\cdot H)*{G}^{(j)}_{\sigma,b}(t)-(x\cdot H)*I(t)|$ (19)
$\displaystyle=$ $\displaystyle~{}|(x\cdot H)*({G}^{(j)}_{\sigma,b}-I)(t)|$
$\displaystyle=$
$\displaystyle~{}\Big{|}\int_{-\infty}^{\infty}(\widehat{x}*\widehat{H})(f)\cdot(\widehat{G}^{(j)}_{\sigma,b}-\widehat{I})(f)\cdot
e^{2\pi\mathbf{i}ft}\mathrm{d}f\Big{|}$ $\displaystyle\leq$
$\displaystyle~{}\int_{-\infty}^{\infty}|(\widehat{x}*\widehat{H})(f)\cdot(\widehat{G}^{(j)}_{\sigma,b}-I)(f)|\mathrm{d}f$
$\displaystyle=$
$\displaystyle~{}\int_{S}|(\widehat{x}*\widehat{H})(f)\cdot(\widehat{G}^{(j)}_{\sigma,b}-I)(f)|\mathrm{d}f$
$\displaystyle\leq$
$\displaystyle~{}\int_{S}|(\widehat{x}*\widehat{H})(f)\cdot\delta_{1}|\mathrm{d}f$
$\displaystyle\leq$
$\displaystyle~{}\delta_{1}\sqrt{|S|}\cdot\sqrt{\int_{-\infty}^{\infty}|(\widehat{x}*\widehat{H})(f)|^{2}\mathrm{d}f}$
$\displaystyle=$
$\displaystyle~{}\delta_{1}\sqrt{|S|}\cdot\sqrt{\int_{-\infty}^{\infty}|(x\cdot
H)(t)|^{2}\mathrm{d}t}$ $\displaystyle\lesssim$
$\displaystyle~{}\delta_{1}\sqrt{T|S|}\cdot\|(x\cdot H)(t)\|_{T}$
$\displaystyle\lesssim$
$\displaystyle~{}\delta_{1}\sqrt{T|S|}\cdot\|x(t)\|_{T}$ (20)

where the first step is straight forward, the second step follows from the
definition of Fourier transform, the third step follows from triangle
equality, the forth step follows from the definition of $S$. For the fifth
step, by Lemma D.8 that with probability at least 0.9, the Large Offset event
does not happen (i.e., for any $f\in S$, either
$\widehat{G}^{(j)}_{\sigma,b}(f)<\delta_{1}$ or
$\widehat{G}^{(j)}_{\sigma,b}(f)>1-\delta_{1}$). Then, by Lemma C.4, we know
that $-\delta_{1}\leq\widehat{G}^{(j)}_{\sigma,b}(f)\leq 1$. Thus, we get that
$|(\widehat{G}^{(j)}_{\sigma,b}-\widehat{I})(f)|\leq\delta_{1}$. The sixth
step follows from Cauchy–Schwarz inequality, the seventh step follows from
Parseval’s theorem, the eighth step follows from Lemma E.9 Property iv@ and
v@, the last step follows from Lemma E.9 Property<EMAIL_ADDRESS>∎

The following lemma gives a $T$-norm bound for the approximation error.

######  Lemma F.3.

Let $\delta_{1}$ be defined as in Lemma C.4. Let $H$ be defined as in
Definition E.5, ${G}^{(j)}_{\sigma,b}$ be defined as in Definition C.2.

Then, for any $x\in{\cal F}_{k,F}$, with probability $0.9$, for any $j\in[B]$,

$\displaystyle\int_{-\infty}^{\infty}|(x\cdot H)*I(t)-(x\cdot
H)*G^{(j)}_{\sigma,b}(t)|^{2}\mathrm{d}t\lesssim\delta_{1}^{2}T\|x(t)\|_{T}^{2}.$

In particular,

$\displaystyle\|(x\cdot H)*I(t)-(x\cdot
H)*G^{(j)}_{\sigma,b}(t)\|_{T}\lesssim\delta_{1}\|x(t)\|_{T}.$

###### Proof.

Let $S:=\mathrm{supp}(\widehat{x}*\widehat{H})$ be defined as the support set
of $\widehat{x}*\widehat{H}$.

We have that

$\displaystyle~{}T\|(x\cdot H)*I(t)-(x\cdot
H)*G^{(j)}_{\sigma,b}(t)\|_{T}^{2}$ $\displaystyle=$
$\displaystyle~{}\int_{0}^{T}|(x\cdot H)*I(t)-(x\cdot
H)*G^{(j)}_{\sigma,b}(t)|^{2}\mathrm{d}t$ $\displaystyle\leq$
$\displaystyle~{}\int_{-\infty}^{\infty}|(x\cdot H)*I(t)-(x\cdot
H)*G^{(j)}_{\sigma,b}(t)|^{2}\mathrm{d}t$ $\displaystyle\leq$
$\displaystyle~{}\int_{-\infty}^{\infty}|(\widehat{x}*\widehat{H})(f)\cdot(\widehat{I}(f)-\widehat{G}^{(j)}_{\sigma,b}(f))|^{2}\mathrm{d}f$
$\displaystyle=$
$\displaystyle~{}\int_{S}|(\widehat{x}*\widehat{H})(f)\cdot(I(f)-\widehat{G}^{(j)}_{\sigma,b}(f))|^{2}\mathrm{d}f$
$\displaystyle\leq$
$\displaystyle~{}\int_{S}|(\widehat{x}*\widehat{H})(f)\cdot\delta_{1}|^{2}\mathrm{d}f$
$\displaystyle\leq$
$\displaystyle~{}\int_{-\infty}^{\infty}|(\widehat{x}*\widehat{H})(f)\cdot\delta_{1}|^{2}\mathrm{d}f$
$\displaystyle=$
$\displaystyle~{}\delta_{1}^{2}\int_{-\infty}^{\infty}|(x\cdot
H)(t)|^{2}\mathrm{d}t$ $\displaystyle\lesssim$
$\displaystyle~{}\delta_{1}^{2}T\|x(t)\|_{T}^{2}$

where the first step follows from the definition of the norm, the second step
is straight forward, the third step follows from Parseval’s theorem, the forth
step follows from the definition of $S$, the fifth step follows from Lemma D.8
and Lemma C.4, the sixth step is straight forward, the seventh step follows
from Parseval’s theorem, the eighth step follows from Lemma E.9 Property iv@
and Property<EMAIL_ADDRESS>
∎

##  Appendix G Concentration Property of the Filtered Signal

Recall that a frequency $f^{*}$ is _heavy_ if it satisfies the following
condition:

$\displaystyle\int_{f^{*}-\Delta_{h}}^{f^{*}+\Delta_{h}}|\widehat{x^{*}\cdot
H}(f)|^{2}\mathrm{d}f\geq T\mathcal{N}^{2}/k.$

In this section, we consider the filtered signal in a hashing bin that
contains a heavy frequency; that is, $z(t)=(x^{*}\cdot
H)*\widehat{G}_{\sigma,b}^{(j)}$ where $j=h_{\sigma,b}(f^{*})$ is the index of
the bin containing $f^{*}$. We will prove that $z(t)$ form a one-cluster
signal around $f^{*}$, which means that in the frequency domain most energy
are concentrated around $f^{*}$, and in the time domain, most energy are
contained in the observation window $[0,T]$. The formal definition are given
as follows:

######  Definition G.1 ($(\varepsilon,\Delta)$-one-cluster signal).

We say that a signal $z(t)$ is an $(\varepsilon,\Delta)$-one-cluster signal
around $f_{0}$ if and only if $z(t)$ and $\widehat{z}(f)$ satisfy the
following two properties:

$\displaystyle\mathrm{Property~{}\@slowromancap i@}$ $\displaystyle:$
$\displaystyle\int_{f_{0}-\Delta}^{f_{0}+\Delta}|\widehat{z}(f)|^{2}\mathrm{d}f\geq(1-\varepsilon)\int_{-\infty}^{+\infty}|\widehat{z}(f)|^{2}\mathrm{d}f$
$\displaystyle\mathrm{Property~{}\@slowromancap ii@}$ $\displaystyle:$
$\displaystyle\int_{0}^{T}|z(t)|^{2}\mathrm{d}t\geq(1-\varepsilon)\int_{-\infty}^{+\infty}|z(t)|^{2}\mathrm{d}t.$

We first prove the energy preservation in the time domain:

######  Lemma G.2 (Time domain energy preservation).

Let $\Delta_{h}=|\mathrm{supp}(\widehat{H})|$. Let $f^{*}$ satisfy

$\displaystyle\int_{f^{*}-\Delta_{h}}^{f^{*}+\Delta_{h}}|\widehat{x^{*}\cdot
H}(f)|^{2}\mathrm{d}f\geq T\mathcal{N}^{2}/k$

and $\widehat{z}=\widehat{x^{*}\cdot H}\cdot\widehat{G}^{(j)}_{\sigma,b}$
where $j=h_{\sigma,b}(f^{*})$. Suppose the Large Offset event does not happen.
Then, we have that,

$\displaystyle\int_{-\infty}^{+\infty}|z(t)|^{2}\mathrm{d}t\leq
1.35\int_{0}^{T}|z(t)|^{2}\mathrm{d}t.$

###### Proof.

Let $I(f)$ be the ideal filter defined by Eq. (18).

We first have

$\displaystyle\|z(t)\|_{L_{2}}=$ $\displaystyle~{}\|(x^{*}\cdot
H)(t)*G^{(j)}_{\sigma,b}(t)\|_{L_{2}}$ $\displaystyle\leq$
$\displaystyle~{}\|(x^{*}\cdot H)(t)*I(t)\|_{L_{2}}+\|(x^{*}\cdot
H)(t)*(I-G^{(j)}_{\sigma,b})(t)\|_{L_{2}},$

where the second step follows from triangle inequality.

Then, we bound the two terms separately.

For the first term, by Lemma F.1, if the Large Offset event does not happen,
we have that

$\displaystyle(x^{*}\cdot H)*I(t)=(x^{*}*I)(t)\cdot H(t).$ (21)

It implies that

$\displaystyle\|(x^{*}\cdot H)(t)*I(t)\|_{L_{2}}=$
$\displaystyle~{}\|(x^{*}*I)(t)\cdot H(t)\|_{L_{2}}$

Let $y(t):=(x^{*}*I)(t)$. It’s easy to see that $y(y)$ is $k$-Fourier-sparse.
Then, we have

$\displaystyle~{}\int_{-\infty}^{\infty}|y(t)\cdot H(t)|^{2}\mathrm{d}t$
$\displaystyle=$ $\displaystyle~{}\int_{0}^{T}|y(t)\cdot
H(t)|^{2}\mathrm{d}t+\int_{[-\infty,\infty]\backslash[0,T]}|y(t)\cdot
H(t)|^{2}\mathrm{d}t$ $\displaystyle\leq$
$\displaystyle~{}\int_{0}^{T}|y(t)\cdot
H(t)|^{2}\mathrm{d}t+0.1\int_{0}^{T}|y(t)|^{2}\mathrm{d}t$ $\displaystyle\leq$
$\displaystyle~{}1.1\int_{0}^{T}|y(t)|^{2}\mathrm{d}t$ $\displaystyle\leq$
$\displaystyle~{}1.3\int_{0}^{T}|y(t)\cdot H(t)|^{2}\mathrm{d}t,$ (22)

where the first step is straight forward, the second step follows from Lemma
E.9 Property iv@, the third step follows from Lemma E.9 Property v@, the forth
step follows from Lemma E.9 Property<EMAIL_ADDRESS>Hence,

$\displaystyle\|(x^{*}\cdot H)(t)*I(t)\|_{L_{2}}=\|y(t)\cdot
H(t)\|_{L_{2}}\leq\sqrt{1.3T}\cdot\|(x^{*}*I)(t)\cdot H(t)\|_{T}.$

By Eq. (21) again, we can swap the order of $I$ and $H$ and obtain:

$\displaystyle\|(x^{*}\cdot
H)(t)*I(t)\|_{L_{2}}\leq\sqrt{1.3T}\cdot\|(x^{*}\cdot H)(t)*I(t)\|_{T}.$

For the second term, by Lemma F.3, we have that

$\displaystyle\|(x^{*}\cdot H)*I(t)-(x^{*}\cdot
H)*G^{(j)}_{\sigma,b}(t)\|_{L_{2}}\lesssim\delta_{1}\sqrt{T}\|x^{*}(t)\|_{T}.$
(23)

Therefore, we get that

$\displaystyle\|z(t)\|_{L_{2}}\leq$
$\displaystyle~{}\sqrt{1.3T}\cdot\|(x^{*}\cdot
H)(t)*I(t)\|_{T}+O(\delta_{1}\sqrt{T}\|x^{*}(t)\|_{T})$ $\displaystyle\leq$
$\displaystyle~{}\sqrt{1.3T}\cdot\|(x^{*}\cdot
H)*G^{(j)}_{\sigma,b}(t)\|_{T}+\sqrt{1.3T}\cdot\|(x^{*}\cdot
H)*(I-G^{(j)}_{\sigma,b})(t)\|_{T}+O(\delta_{1}\sqrt{T}\|x^{*}(t)\|_{T})$
$\displaystyle\leq$
$\displaystyle~{}\sqrt{1.3T}\cdot\|z(t)\|_{T}+O(\delta_{1}\sqrt{T}\|x^{*}(t)\|_{T}),$

where the second step follows from triangle inequality, and the last step
follows from Lemma F.3 again.

We claim that the second term can be bounded by $o(1)\cdot\|z(t)\|_{T}$.
Indeed, we have

$\displaystyle~{}\int_{-\infty}^{\infty}|(x^{*}\cdot
H)*G^{(j)}_{\sigma,b}(t)|^{2}\mathrm{d}t$ $\displaystyle=$
$\displaystyle~{}\int_{-\infty}^{\infty}|(\widehat{x}^{*}*\widehat{H})\cdot\widehat{G}^{(j)}_{\sigma,b}(f)|^{2}\mathrm{d}f$
$\displaystyle\geq$
$\displaystyle~{}\int_{f^{*}-\Delta_{h}}^{f^{*}+\Delta_{h}}|(\widehat{x}^{*}*\widehat{H})\cdot\widehat{G}^{(j)}_{\sigma,b}(f)|^{2}\mathrm{d}f$
$\displaystyle\gtrsim$
$\displaystyle~{}\int_{f^{*}-\Delta_{h}}^{f^{*}+\Delta_{h}}|(\widehat{x}^{*}*\widehat{H})(f)|^{2}\mathrm{d}f$
$\displaystyle\gtrsim$
$\displaystyle~{}\int_{f^{*}-\Delta_{h}}^{f^{*}+\Delta_{h}}|(\widehat{x}^{*}*\widehat{H})(f)|^{2}\mathrm{d}f$
$\displaystyle\geq$ $\displaystyle~{}\frac{T\delta\|x^{*}\|_{T}^{2}}{k}$ (24)

where the first step follows from Parseval’s theorem, the second step is
straightforward, the third step follows from Lemma D.8 and Lemma C.4 Property
i@, the forth step follows from our assumption that there exists a heavy
frequency $f^{*}$ hashing into the $j$-th bin, the fifth step follows from
$f^{*}$ satisfying

$\displaystyle\int_{f^{*}-\Delta}^{f^{*}+\Delta}|\widehat{x^{*}\cdot
H}(f)|^{2}\mathrm{d}f\geq T\mathcal{N}^{2}/k.$

Thus, $\|x^{*}\|_{T}\leq O(\sqrt{k/(T\delta)})\|z(t)\|_{L_{2}}$ and we have

$\displaystyle
O(\delta_{1}\sqrt{T}\|x^{*}\|_{T})=O\Big{(}\delta_{1}\sqrt{\frac{k}{\delta}}\|z(t)\|_{L_{2}}\Big{)}\leq
O\Big{(}\sqrt{\frac{\delta}{k}}\Big{)}\|z(t)\|_{L_{2}}=o(1)\cdot\|z(t)\|_{L_{2}},$

where the second step follows from $\delta_{1}\leq\delta/k$.

Finally, we have

$\displaystyle\|z(t)\|_{L_{2}}\leq\sqrt{1.3T}\cdot\|z(t)\|_{T}+o(1)\cdot\|z(t)\|_{L_{2}},$

which implies that

$\displaystyle\int_{-\infty}^{+\infty}|z(t)|^{2}\mathrm{d}t\leq
1.35\int_{0}^{T}|z(t)|^{2}\mathrm{d}t.$

The lemma is then proved.

∎

We next show the frequency domain energy concentration in the following lemma.
Together with Lemma G.2, we conclude that $z(t)$ is a one-cluster signal.

######  Lemma G.3 (Frequency domain energy concentration).

Let $x^{*}$ be a $k$-Fourier-sparse signal. Let $f^{*}\in[-F,F]$ satisfy the
following property:

$\int_{f^{*}-\Delta_{h}}^{f^{*}+\Delta_{h}}|\widehat{x^{*}\cdot
H}(f)|^{2}\mathrm{d}f\geq T\mathcal{N}^{2}/k.$ (25)

Let $\sigma,b$ be the parameter of the hashing function. Suppose that Large
Offset event not happened and $f^{*}$ is well-isolated. Let
$j=h_{\sigma,b}(f^{*})$ be the bucket that $f^{*}$ maps to under the hash such
that $z=(x^{*}\cdot H)*G^{(j)}_{\sigma,b}$ and
$\widehat{z}=\widehat{x^{*}\cdot H}\cdot\widehat{G}^{(j)}_{\sigma,b}$. Then,
we have

$\displaystyle\int_{f^{*}-\Delta}^{f^{*}+\Delta}|\widehat{z}(f)|^{2}\mathrm{d}f\geq
0.7\int_{-\infty}^{+\infty}|\widehat{z}(f)|^{2}\mathrm{d}f.$

Furthermore, $z(t)$ is a $(0.3,\Delta)$-one-cluster signal around $f^{*}$.

###### Proof.

Define region $I_{f^{*}}=(f^{*}-\Delta,f^{*}+\Delta)$ with the complement
$\overline{I_{f^{*}}}=(-\infty,\infty)\setminus I_{f^{*}}$. We have that

$\displaystyle\int_{I_{f^{*}}}|\widehat{z}(f)|^{2}\mathrm{d}f\geq(1-\delta/k)\int_{I_{f^{*}}}|\widehat{x^{*}\cdot
H}(f)|^{2}\mathrm{d}f\geq(1-o(1))T\mathcal{N}^{2}/k$

where the first step follows from Lemma D.9, the second step follows from Eq.
(25).

On the other hand, $f^{*}$ is well-isolated. Thus, by the definition of well-
isolation (Definition D.4), we have that

$\int_{\overline{I_{f^{*}}}}|\widehat{z}(f)|^{2}\mathrm{d}f\lesssim\varepsilon\cdot
T\mathcal{N}^{2}/k\leq 0.1T\mathcal{N}^{2}/k.$

Combining them together, we get that

$\displaystyle\int_{f_{0}-\Delta}^{f_{0}+\Delta}|\widehat{z}(f)|^{2}\mathrm{d}f\geq
0.7\int_{-\infty}^{+\infty}|\widehat{z}(f)|^{2}\mathrm{d}f$

For the furthermore part, Lemma G.2 implies that

$\displaystyle\int_{0}^{T}|z(t)|^{2}\mathrm{d}t\geq(1-0.3)\int_{-\infty}^{+\infty}|z(t)|^{2}\mathrm{d}t.$

Hence, by Definition G.1, $z(t)$ is a $(0.3,\Delta)$-one-cluster. ∎

##  Appendix H Energy Bound for Filtered Fourier Sparse Signals

In this section, we prove an energy bound for the filtered signals $(x\cdot
H)*G_{\sigma,b}^{(j)}$, which upper bounds the magnitude of any such signal at
a point $t$ by its energy in the time duration $[0,T]$. We first prove an
energy bound for untruncated ideally filtered signals (see Section H.1). Then,
we prove an energy bound for filtered signals (see Section H.2). In addition,
we prove a technical claim (see Section H.3).

###  H.1 Energy bound for untruncated ideally filtered signals

In Section F, we show that the ideally filtered signal $(x\cdot
H)*I_{\sigma,b}^{(j)}$, where $I_{\sigma,b}^{(j)}$ defined as Eq. (18) is the
ideal filter, is close to the true filtered signal. Here, we further simplify
the signal by ignoring the truncation filter $H(t)$, and prove an energy bound
for the signals of the form $(x*I_{\sigma,b}^{(j)})(t)$:

######  Lemma H.1.

Let $H$ be defined as in Definition E.5, ${G}^{(j)}_{\sigma,b}$ be defined as
in Definition C.2 and the corresponding ideal filter $I=I_{\sigma,b}^{(b)}$ be
defined as in Eq. (18). Let $D(t):=\mathrm{Uniform}([-1,1])$.

For any $x\in{\cal F}_{k,F}$, we have that with probability $0.6$, for any
$t\in(-1,1)$

$\displaystyle|(x*I)(t)|^{2}\lesssim{\min}\Big{\\{}\frac{k}{1-|t|},k^{2}\Big{\\}}\cdot\|(x*I)(t)\|_{D}^{2}$

###### Proof.

Since $\widehat{(x*I)}(f)=\widehat{x}\cdot\widehat{I}(f)$ and $x$ is
$k$-Fourier-sparse, we know that $(x*\widehat{I})(t)$ is also a $k$-Fourier-
sparse signal.

On the one hand, by the $k$-Fourier-sparse signal’s location-dependent energy
bound (Theorem B.2), we have

$\displaystyle|(x*I)(t)|^{2}\lesssim$
$\displaystyle~{}\frac{k}{1-|t|}\|(x*I)(t)\|_{D}^{2}$ (26)

On the other hand, by the location-independent energy bound (Theorem B.1), we
have that

$\displaystyle|(x*I)(t)|^{2}\lesssim k^{2}\|(x*I)(t)\|_{D}^{2}$ (27)

Combine Eq. (26) and Eq. (27) together, we prove the lemma:

$\displaystyle|(x*I)(t)|^{2}\lesssim{\min}\Big{\\{}\frac{k}{1-|t|},k^{2}\Big{\\}}\cdot\|(x*I)(t)\|_{D}^{2}.$

∎

###  H.2 Energy bound for filtered signals

Based on Lemma H.1, we can relate the magnitude of the filtered signal with
its own energy plus the original Fourier-sparse signal’s energy.

######  Lemma H.2.

Let $H$ be defined as in Definition E.5, ${G}^{(j)}_{\sigma,b}$ be defined as
in Definition C.2 and the corresponding ideal filter $I=I_{\sigma,b}^{(b)}$ be
defined as in Eq. (18).

For any $x\in{\cal F}_{k,F}$, $j\in[B]$, and $(\sigma,b)$ such that Large
Offset event does not happen, let $z(t)=(x\cdot H)*{G}^{(j)}_{\sigma,b}(t)$.
It holds that:

$\displaystyle{|z(t)|^{2}}\lesssim{\min}\Big{\\{}\frac{k\cdot
H(t)}{1-|2t/T-1|},k^{2}\Big{\\}}\cdot{\|z(t)\|_{T}^{2}}+\delta_{1}\|x(t)\|_{T}^{2}~{}~{}~{}\forall
t\in(-1,1).$

###### Proof.

Let $S:=\mathrm{supp}(\widehat{x}*\widehat{H})$ be defined as the support set
of $\widehat{x}*\widehat{H}$. Then $|S|\leq\Delta$.

First, by the ideally untruncated filtered signal’s energy bound (Lemma H.1),
we have

$\displaystyle|(x*I)(t)\cdot H(t)|^{2}\lesssim$
$\displaystyle~{}H^{2}(t)\cdot{\min}\Big{\\{}\frac{k}{1-|2t/T-1|},k^{2}\Big{\\}}\cdot\|(x*I)(t)\|_{T}^{2}$
$\displaystyle\lesssim$ $\displaystyle~{}{\min}\Big{\\{}\frac{k\cdot
H(t)}{1-|2t/T-1|},k^{2}\Big{\\}}\cdot\|(x*I)(t)\|_{T}^{2},$ (28)

where the second step follows from $H(t)\lesssim 1$ (Lemma E.9 Property i@,
ii@).

Then, we bound the magnitude of the ideal filtered signal as follows:

$\displaystyle|(x\cdot H)*I(t)|^{2}=$ $\displaystyle~{}|(x*I)(t)\cdot
H(t)|^{2}$ $\displaystyle\lesssim$
$\displaystyle~{}{\min}\Big{\\{}\frac{k\cdot
H(t)}{1-|2t/T-1|},k^{2}\Big{\\}}\cdot\|(x*I)(t)\|_{T}^{2}$
$\displaystyle\lesssim$ $\displaystyle~{}{\min}\Big{\\{}\frac{k\cdot
H(t)}{1-|2t/T-1|},k^{2}\Big{\\}}\cdot(\|(x\cdot
H)*G^{(j)}_{\sigma,b}(t)\|_{T}^{2}+\delta_{1}^{2}\|x(t)\|_{T}^{2})$
$\displaystyle\lesssim$ $\displaystyle~{}{\min}\Big{\\{}\frac{k\cdot
H(t)}{1-|2t/T-1|},k^{2}\Big{\\}}\cdot\|(x\cdot
H)*G^{(j)}_{\sigma,b}(t)\|_{T}^{2}+\delta_{1}\|x(t)\|_{T}^{2}$ (29)

where the first step follows from Lemma F.1, the second step follows from Eq.
(28), the third step follows from Claim H.5, the forth step follows from
$k^{2}\delta_{1}\leq 1$.

Next, we consider the difference between the signals filtered by
${G}^{(j)}_{\sigma,b}(t)$ and $I(t)$:

$\displaystyle|(x\cdot H)*{G}^{(j)}_{\sigma,b}(t)-(x\cdot H)*I(t)|^{2}\leq$
$\displaystyle~{}\delta_{1}^{2}{T|S|}\cdot\|x(t)\|_{T}^{2}$
$\displaystyle\leq$ $\displaystyle~{}\delta_{1}\cdot\|x(t)\|_{T}^{2}$ (30)

where the first step follows from Lemma F.2, the second step follows from
$\delta_{1}T|S|\leq 1$.

Finally, we have that

$\displaystyle|(x\cdot H)*{G}^{(j)}_{\sigma,b}(t)|^{2}\leq$
$\displaystyle~{}2|(x\cdot H)*I(t)|^{2}+2|(x\cdot
H)*{G}^{(j)}_{\sigma,b}(t)-(x\cdot H)*I(t)|^{2}$ $\displaystyle\lesssim$
$\displaystyle~{}|(x\cdot H)*I(t)|^{2}+\delta_{1}\|x(t)\|_{T}^{2}$
$\displaystyle\lesssim$ $\displaystyle~{}{\min}\Big{\\{}\frac{k\cdot
H(t)}{1-|2t/T-1|},k^{2}\Big{\\}}\cdot\|(x\cdot
H)*\widehat{G}^{(j)}_{\sigma,b}(t)\|_{T}^{2}+\delta_{1}\|x(t)\|_{T}^{2},$

where the first step follows from $(a+b)^{2}\leq 2a^{2}+2b^{2}$, the second
step follows from Eq. (30), the third step follows from Eq. (29).

The lemma is then proved.

∎

The energy bound in Lemma H.2 not only depends on $\|z(t)\|_{T}$, but also on
$\|x(t)\|_{T}$. The following lemma show that assuming the filtered signal
contains a heavy frequency, $\|x(t)\|_{T}$ can be upper bounded by
$\|z(t)\|_{T}$.

######  Lemma H.3.

Given $k\in\mathbb{Z}_{+},F\in\mathbb{R}_{+}$. Let $H$ be defined as in
Definition E.5, ${G}^{(j)}_{\sigma,b}$ be defined as in Definition C.2. Let
$x\in{\cal F}_{k,F}$ be any $k$-Fourier sparse signal. For $j\in[B]$ such that
there exists a $f^{*}$ satisfying: $j=h_{\sigma,b}(f^{*})$ and

$\displaystyle\int_{f^{*}-\Delta_{h}}^{f^{*}+\Delta_{h}}|\widehat{x\cdot
H}(f)|^{2}\mathrm{d}f\geq T\mathcal{N}^{2}/k,$ (31)

where $\mathcal{N}^{2}\geq\delta\|x\|_{T}^{2}$ and
$\Delta_{h}=|\mathrm{supp}(\widehat{H})|$.

For any $(\sigma,b)$ that Large Offset event does not happen, we have that

$\displaystyle\|(x\cdot
H)*G^{(j)}_{\sigma,b}(t)\|^{2}_{T}\gtrsim\frac{\delta\|x\|_{T}^{2}}{k}.$

###### Proof.

We have that

$\displaystyle T\|(x\cdot H)*G^{(j)}_{\sigma,b}(t)\|^{2}_{T}=$
$\displaystyle~{}\int_{0}^{T}|(x\cdot
H)*G^{(j)}_{\sigma,b}(t)|^{2}\mathrm{d}t$ $\displaystyle\gtrsim$
$\displaystyle~{}\int_{-\infty}^{\infty}|(x\cdot
H)*G^{(j)}_{\sigma,b}(t)|^{2}\mathrm{d}t$ $\displaystyle=$
$\displaystyle~{}\int_{-\infty}^{\infty}|(\widehat{x}*\widehat{H})\cdot\widehat{G}^{(j)}_{\sigma,b}(f)|^{2}\mathrm{d}f$
$\displaystyle\geq$
$\displaystyle~{}\int_{f^{*}-\Delta_{h}}^{f^{*}+\Delta_{h}}|(\widehat{x}*\widehat{H})\cdot\widehat{G}^{(j)}_{\sigma,b}(f)|^{2}\mathrm{d}f$
$\displaystyle\gtrsim$
$\displaystyle~{}\int_{f^{*}-\Delta_{h}}^{f^{*}+\Delta_{h}}|(\widehat{x}*\widehat{H})(f)|^{2}\mathrm{d}f$
$\displaystyle\geq$ $\displaystyle~{}\frac{T\delta\|x\|_{T}^{2}}{k}$

where the first step follows from the definition of norm, the second step
follows from Lemma G.3, the third step follows from Parseval’s theorem, the
forth step is straight forward, the fifth step follows from Lemma D.9, the
sixth step follows from Eq. (31).

∎

Lemma H.2 and Lemma H.3 implies the following energy bound:

######  Corollary H.4 (Energy bound for filtered signals).

Given $k\in\mathbb{N}$ and $F\in\mathbb{R}_{+}$. Let $x\in{\cal F}_{k,F}$. Let
$H$ be defined as in Definition E.5, ${G}^{(j)}_{\sigma,b}$ be defined as in
Definition C.2 with $(\sigma,b)$ such that Large Offset event does not happen.

For any $j\in[B]$, suppose there exists an $f^{*}$ with
$j=h_{\sigma,b}(f^{*})$ satisfying:

$\displaystyle\int_{f^{*}-\Delta}^{f^{*}+\Delta}|\widehat{x\cdot
H}(f)|^{2}\mathrm{d}f\geq T\mathcal{N}^{2}/k,$

where $\mathcal{N}^{2}\geq\delta\|x\|_{T}^{2}$. Then, for $z(t)=(x\cdot
H)*{G}^{(j)}_{\sigma,b}(t)$, it holds that:

$\displaystyle{|z(t)|^{2}}\lesssim{\min}\Big{\\{}\frac{k\cdot
H(t)+\delta}{1-|2t/T-1|},k^{2}\Big{\\}}\cdot{\|z(t)\|_{D}^{2}}~{}~{}~{}\forall
t\in(0,T).$

###### Proof.

We have that

$\displaystyle|z(t)|^{2}\lesssim$ $\displaystyle~{}{\min}\Big{\\{}\frac{k\cdot
H(t)}{1-|2t/T-1|},k^{2}\Big{\\}}\cdot\|z(t)\|_{T}^{2}+\delta_{1}\|x(t)\|_{T}^{2}$
$\displaystyle\lesssim$ $\displaystyle~{}{\min}\Big{\\{}\frac{k\cdot
H(t)}{1-|2t/T-1|},k^{2}\Big{\\}}\cdot\|z(t)\|_{T}^{2}+\delta^{2}k^{-1}\|x(t)\|_{T}^{2}$
$\displaystyle\lesssim$ $\displaystyle~{}{\min}\Big{\\{}\frac{k\cdot
H(t)}{1-|2t/T-1|},k^{2}\Big{\\}}\cdot\|z(t)\|_{T}^{2}+\delta\|(x\cdot
H)*G^{(j)}_{\sigma,b}(t)\|_{T}^{2}$ $\displaystyle\lesssim$
$\displaystyle~{}{\min}\Big{\\{}\frac{k\cdot
H(t)+\delta}{1-|2t/T-1|},k^{2}\Big{\\}}\cdot\|z(t)\|_{T}^{2}$

where the first step follows from Lemma H.2, the second step follows from
$\delta_{1}\leq\delta^{2}k^{-1}$, the third step follows from Lemma H.3, the
forth step is straight forward.

∎

###  H.3 Technical claim

######  Claim H.5.

Given $k\in\mathbb{Z}_{+},F\in\mathbb{R}_{+}$. Let $\delta_{1}$ be defined as
the $\delta$ of Lemma C.4.Let $H$ be defined as in Definition E.5,
${G}^{(j)}_{\sigma,b}$ be defined as in Definition C.2, and
$I=I_{\sigma,b}^{(j)}$ be the ideal filter defined by Eq. (18).

Then, for any $x\in{\cal F}_{k,F}$ and $j\in[B]$, with probability $0.6$ over
$(\sigma,b)$, we have that

$\displaystyle\|(x*I)(t)\|_{T}^{2}\lesssim\|(x\cdot
H)*\widehat{G}^{(j)}_{\sigma,b}(t)\|_{T}^{2}+\delta_{1}^{2}\|x(t)\|_{T}^{2}.$

###### Proof.

We have that

$\displaystyle\|(x*I)(t)\|_{T}^{2}\lesssim$ $\displaystyle~{}\|(x*I)(t)\cdot
H\|_{T}^{2}$ $\displaystyle=$ $\displaystyle~{}\|(x\cdot H)*I(t)\|_{T}^{2}$
$\displaystyle\leq$ $\displaystyle~{}2\|(x\cdot
H)*G^{(j)}_{\sigma,b}(t)\|_{T}^{2}+2\|(x\cdot H)*G^{(j)}_{\sigma,b}(t)-(x\cdot
H)*I(t)\|_{T}^{2}$ $\displaystyle\lesssim$ $\displaystyle~{}\|(x\cdot
H)*G^{(j)}_{\sigma,b}(t)\|_{T}^{2}+\delta_{1}^{2}\|x(t)\|_{T}^{2}$

where the first step follows from $(x*I)(t)$ is a $k$-Fourier-sparse signal
and Lemma E.9 Property v@, the second step follows from Lemma F.1 conditioning
on Large Offset event not happening, the third step follows from
$(a+b)^{2}\leq 2a^{2}+2b^{2}$, the forth step follows from Lemma F.3. ∎

##  Appendix I Local-Test Signal

Recall that the filtered signal in the $j$-th bin of the HashToBins procedure
can be written as $z(t)=(x\cdot H)*G_{\sigma,b}^{(j)}(t)$. The next step of
the frequency estimation algorithm is to extract a significant frequency from
$z(t)$ by considering a so-called _local-test signal_ :

$\displaystyle d_{z}(t):=z(t)e^{2\pi f_{0}\beta}-z(t+\beta),$ (32)

where $f_{0}\in\mathrm{supp}(\widehat{x}^{*})$, and $j=h_{\sigma,b}(f_{0})$,
where $\beta\in\mathbb{R}_{+}$ is a parameter such that $\beta\leq
O(1/\Delta)$ with $\Delta=O(k\cdot|\mathrm{supp}(\widehat{H})|)$.

In this section, we will study some properties of $d_{z}(t)$ and its ideal
versions (see Section I.1 and Section I.2) and derive an energy bound for it
(See Section I.3).

###  I.1 Ideal local-test signal

In previous section, we’ve shown that ideal filter $I_{\sigma,b}^{(j)}$ can be
used to approximate $G_{\sigma,b}^{(j)}$ such that the ideally filtered signal
is close to the true filtered signal. We will show that under the ideal filter
approximation, the _ideal local-test signal_ is also close to the true local-
test signal. More formally, we define the ideal filtered signal and the ideal
local-test signal as follows:

$\displaystyle z_{I}(t):=$ $\displaystyle~{}(x\cdot H)*I(t),$ $\displaystyle
d_{I,z}(t):=$
$\displaystyle~{}z_{I}(t)e^{2\pi\mathbf{i}f_{0}\beta}-z_{I}(t+\beta),$ (33)

The following lemma bounds the point-wise distance between $d_{z}(t)$ and
$d_{I,z}(t)$.

######  Lemma I.1.

Let $\delta_{1}$ be defined as in Lemma C.4. Let $H$ be defined as in
Definition E.5, ${G}^{(j)}_{\sigma,b}$ be defined as in Definition C.2 and
$I=I_{\sigma,b}^{(j)}$ be the corresponding ideal filter as in Eq. (18).

For any $x\in{\cal F}_{k,F}$ and $(\sigma,b)$ such that Large Offset event
does not happen, for any $j\in[B]$, let $z(t)=(x\cdot
H)*G_{\sigma,b}^{(j)}(t)$, $d_{z}(t)$ be defined as Eq. (32), $z_{I}(t)$ and
$d_{z,I}(t)$ be defined as Eq. (I.1).

Then, we have

$\displaystyle|d_{z}(t)-d_{I,z}(t)|\lesssim\delta_{1}\sqrt{T|S|}\cdot\|x(t)\|_{T}~{}~{}~{}\forall
t\in\mathbb{R}.$

###### Proof.

$\displaystyle|d_{z}(t)-d_{I,z}(t)|=$
$\displaystyle~{}|z(t)e^{2\pi\mathbf{i}f_{0}\beta}-z_{I}(t)e^{2\pi\mathbf{i}f_{0}\beta}-(z(t+\beta)-z_{I}(t+\beta))|$
$\displaystyle\leq$
$\displaystyle~{}|z(t)e^{2\pi\mathbf{i}f_{0}\beta}-z_{I}(t)e^{2\pi\mathbf{i}f_{0}\beta}|+|z(t+\beta)-z_{I}(t+\beta)|$
$\displaystyle=$ $\displaystyle~{}|z(t)-z_{I}(t)|+|z(t+\beta)-z_{I}(t+\beta)|$
$\displaystyle\lesssim$
$\displaystyle~{}\delta_{1}\sqrt{T|S|}\cdot\|x(t)\|_{T},$

where the first step follows from the definition of $d_{z}(t)$ and
$d_{I,z}(t)$, the second step follows from triangle inequality, the third step
follows from $|e^{2\pi\mathbf{i}f_{0}\beta}|=1$, the forth step follows from
Lemma F.2. ∎

The following lemma bounds the $L_{2}$-distance between $d_{z}(t)$ and
$d_{z,I}(t)$.

######  Lemma I.2.

Let $\delta_{1}$ be defined as in Lemma C.4. Let $H$ be defined as in
Definition E.5, ${G}^{(j)}_{\sigma,b}$ be defined as in Definition C.2 and
$I=I_{\sigma,b}^{(j)}$ be the corresponding ideal filter as in Eq. (18).

For any $x\in{\cal F}_{k,F}$ and $(\sigma,b)$ such that Large Offset event
does not happen, for any $j\in[B]$, let $z(t)=(x\cdot
H)*G_{\sigma,b}^{(j)}(t)$, $d_{z}(t)$ be defined as Eq. (32), $z_{I}(t)$ and
$d_{z,I}(t)$ be defined as Eq. (I.1).Then,

$\displaystyle\int_{-\infty}^{\infty}|d_{I,z}(t)-d_{z}(t)|^{2}\mathrm{d}t\lesssim\delta_{1}^{2}T\|x(t)\|_{T}^{2}$

###### Proof.

We first have that,

$\displaystyle~{}\int_{-\infty}^{\infty}|z_{I}(t)e^{2\pi\mathbf{i}f_{0}\beta}-z(t)e^{2\pi\mathbf{i}f_{0}\beta}|^{2}\mathrm{d}t$
$\displaystyle=$
$\displaystyle~{}\int_{-\infty}^{\infty}|z_{I}(t)-z(t)|^{2}\mathrm{d}t$