$j\in[B]$,

$|\widehat{v}_{j}-\widehat{v}^{\prime}_{j}e^{2\pi\mathbf{i}f_{j}\beta}|\leq
0.08(|\widehat{v}_{j}|+|\widehat{v}^{\prime}_{j}|),$

holds with probability at least 0.6.

Using the definition of $z$ in Definition 7.18.

######  Claim 7.26.

Procedure GetEmpiricalKEnergy in Algorithm 7 runs Procedure HashTobins
$R_{\operatorname{est}}O((T\Delta)^{2})$ times to output a vector
$z_{\operatorname{emp}}\in\mathbb{R}^{B}$ such that, for each $j\in[B]$,

$z_{\operatorname{emp}}^{j}\in[0.8\|z^{(j)}\|_{T},1.2\|z^{(j)}\|_{T}],$

holds with probability at least 0.9.

######  Claim 7.27.

Algorithm LocateKSignal in Algorithm 6 uses
$O(\operatorname{poly}(k,\log(1/\delta))\cdot\log(FT))$, and runs in
$O(\operatorname{poly}(k,\log(1/\delta))\cdot\log^{2}(FT))$.

###### Proof.

We first calculate the number of samples. All the samples is basically all the
Fourier samples, each time needs $B\log(k/\delta)$. In total it calls
HashToBins
$O(R_{\operatorname{est}}+R_{\operatorname{repeat}}D_{\max}R_{\operatorname{loc}})$
times where $D_{\max}R_{\operatorname{loc}}=\Theta(\log(FT))$ by similar
analysis as one-cluster frequency recovery. Thus, the total number of samples
is

$\displaystyle(R_{\operatorname{est}}+R_{\operatorname{repeat}}D_{\max}R_{\operatorname{loc}})B\log(k/\delta)=\operatorname{poly}(k,\log(1/\delta))\cdot\log(FT).$

Then, we analyze the running time.

The expected running time includes the following parts: the first part is
running Procedure HashToBins
$O(R_{\operatorname{est}}+R_{\operatorname{repeat}}D_{\max}R_{loc})$ times,
each run takes $O(B\log(k/\delta)+B\log B)$ samples. For each such sample we
need $\operatorname{poly}(k,\log(1/\delta))$ time to compute $H(t)$ according
to Lemma C.8 and there are $\operatorname{poly}(k,\log(1/\delta))\log(FT))$
many samples; the second part is updating the counter $v$,which takes
$O(D_{\max}R_{loc}Bt)$ time. Thus, in total

$\displaystyle\operatorname{poly}(k,\log(1/\delta))\cdot
O(R_{\operatorname{est}}+R_{\operatorname{repeat}}D_{\max}R_{\operatorname{loc}})\cdot
O(B\log(k/\delta)+B\log B)+O(D_{\max}R_{loc}Bt)$ $\displaystyle=$
$\displaystyle\operatorname{poly}(k,\log(1/\delta))\cdot\log^{2}(FT),$

where by similar analysis as one-cluster recovery, $t=\Theta(\log(FT))$ and
$D_{\max}R_{\operatorname{loc}}=\Theta(\log(FT))$. ∎

To boost the success probability, Procedure MultipleStages reruns Procedure
LocateKSignal $O(k)$ times. At the end, Procedure FrequencyRecoveryKCluster
combining Procedure MultipleStages and MergedStages directly, and the running
time and sample complexity of MultipleStages are dominating MergedStages. Thus
we have

######  Lemma 7.28.

Procedure FrequencyRecoveryKCluster in Algorithm 8 uses
$O(\operatorname{poly}(k,\log(1/\delta))\cdot\log(FT))$, and runs in
$O(\operatorname{poly}(k,\log(1/\delta))\cdot\log^{2}(FT))$.

##  8 One-cluster Signal Recovery

###  8.1 Overview

In this section, we consider $x^{*}$ whose frequencies in $\widehat{x}^{*}$
are in the range $[f_{0}-\Delta^{\prime},f_{0}+\Delta^{\prime}]$ for some
frequency $f_{0}$ and $\Delta^{\prime}>0$ and provide an algorithm to
approximate it by a polynomial.

We fix $T$ in this section and recall that $\langle
f(t),g(t)\rangle_{T}:=\frac{1}{T}\int_{0}^{T}f(t)\overline{g}(t)\mathrm{d}t$
such that $\|e^{2\pi\mathbf{i}f_{i}t}\|_{T}=\sqrt{\langle
e^{2\pi\mathbf{i}f_{i}t},e^{2\pi\mathbf{i}f_{i}t}\rangle_{T}}=1$. For
convenience, given
$\overset{k}{\underset{j=1}{\sum}}v_{j}e^{2\pi\mathbf{i}f_{j}t}$, we say the
frequency gap of this signal is $\underset{i\neq j}{\min}|f_{i}-f_{j}|$.

For simplicity, we first consider frequencies clustered around 0. The main
technical lemma in this section is that any signal $x^{*}$ with bounded
frequencies in $\widehat{x}^{*}$ can be approximated by a low-degree
polynomial on $[0,T]$.

######  Lemma 2.3.

For any $\Delta>0$ and any $\delta>0$, let
$x^{*}(t)=\sum_{j\in[k]}v_{j}e^{2\pi\mathbf{i}f_{j}t}$ where
$|f_{j}|\leq\Delta$ for each $j\in[k]$. There exists a polynomial $P(t)$ of
degree at most

$d=O(T\Delta+k^{3}\log k+k\log 1/\delta)$

such that

$\|P(t)-x^{*}(t)\|^{2}_{T}\leq\delta\|x^{*}\|^{2}_{T}.$

One direct corollary is that when $\widehat{x}^{*}$ are in the range
$[f_{0}+\Delta^{\prime},f_{0}+\Delta^{\prime}]$, we can approximate $x^{*}$ by
$P(t)\cdot e^{2\pi\mathbf{i}f_{0}t}$ for some low degree polynomial $P$.

We give an overview of this section first. We first show some technical tools
in Section 8.2, 8.3. In Section 8.4, using those tools, we can show for any
$k$-Fourier-sparse signal, there exists another $k$-Fourier-sparse signal with
bounded frequency gap close to the original signal. In Section 8.5, we show
that for any $k$-Fourier-sparse signal with bounded frequency gap, then there
exists a low degree polynomial close to it. In Section 8.6, we show how to
transfer low degree polynomial back to a Fourier-sparse signal. Combining all
the above steps finishes the proof of Lemma 2.3.

We apply Theorem 7.5 of frequency estimation on $x^{*}$ to obtain an
estimation $\widetilde{f_{0}}$ of $f_{0}$ and use Theorem 4.5 on the
approximation $Q(t)e^{2\pi\mathbf{i}\widetilde{f_{0}}t}$ of $x^{*}$ to recover
the signal. We summarize this result as follows.

######  Theorem 8.1 (One-cluster Signal Recovery).

Let $x^{*}(t)=\overset{k}{\underset{j=1}{\sum}}v_{j}e^{2\pi\mathbf{i}f_{j}t}$
where $\forall j\in[k],|f_{j}-f_{0}|\leq\Delta$ and $x(t)=x^{*}(t)+g(t)$ be
our observable signal. For any $\delta>0$ and any $T>0$, let
$\mathcal{N}^{2}:=\|g\|^{2}_{T}+\delta\|x^{*}\|_{T}^{2}$. Procedure
CFT1Culster in Algorithm 5 finds a polynomial $P(t)$ of degree at most
$d=O\left((T\Delta_{h}+T\Delta)^{1.5}+k^{3}\log k+k\log 1/\delta\right)$ and a
frequency $\widetilde{f}_{0}$ such that

$\|P(t)\cdot
e^{2\pi\mathbf{i}\widetilde{f}_{0}t}-x^{*}(t)\|^{2}_{T}\lesssim\mathcal{N}^{2}$
(24)

The algorithm uses $O(kd)+\operatorname{poly}(k,\log(1/\delta))\log(FT)$
samples, run in
$O(kd^{\omega})+\operatorname{poly}(k,\log(1/\delta))\log^{2}(FT)$ time, and
succeeds with probability at least $1-2^{-\Omega(k)}$.

###### Proof.

We apply the algorithm in Theorem 7.5 to obtain an estimation
$\widetilde{f}_{0}$ with $\operatorname{poly}(k)\log(FT)$ samples and
$\operatorname{poly}(k)\log^{2}(FT)$ running time such that
$|\widetilde{f}_{0}-f_{0}|\lesssim(\Delta_{h}+\Delta)\sqrt{T(\Delta_{h}+\Delta)}$
holds with probability at least $1-2^{-\Omega(k)}$. Notice that
$|f_{j}-\widetilde{f}_{0}|\leq|f_{j}-f_{0}|+|\widetilde{f}_{0}-f_{0}|\lesssim(T(\Delta_{h}+\Delta))^{1.5}$.

We consider
$x^{\prime}(t)=e^{-2\pi\mathbf{i}\widetilde{f}_{0}t}x(t)=\overset{k}{\underset{j=1}{\sum}}v_{j}e^{2\pi\mathbf{i}(f_{j}-\widetilde{f}_{0})t}$
. By Lemma 2.3, there exists a polynomial $P(t)$ of degree at most

$d=O\left((T\Delta_{h}+T\Delta)^{1.5}+k^{3}\log k+k\log 1/\delta\right)$

such that it approximates $x^{\prime}$ by

$\|P(t)-x^{\prime}(t)\|_{T}\leq\frac{\delta}{4}\|x^{\prime}(t)\|_{T}=\frac{\delta}{4}\|x^{*}(t)\|_{T}.$

which indicates $\|Q(t)-e^{-2\pi\mathbf{i}\widetilde{f}_{0}t}\cdot
x^{*}(t)\|_{T}\leq\frac{\delta}{4}\|x^{*}(t)\|_{T}$.

Because we can sample $x(t)$, we can also sample
$e^{-2\pi\mathbf{i}\widetilde{f}_{0}t}\cdot x(t)=Q(t)+g^{\prime}(t)$ for
$g^{\prime}(t)=e^{-2\pi\mathbf{i}\widetilde{f}_{0}t}\cdot
g(t)+(e^{-2\pi\mathbf{i}\widetilde{f}_{0}t}\cdot x^{*}(t)-Q(t))$. Hence we
apply the algorithm in Theorem 4.5 and choose $R=O(k)$ in that proof. Then
Procedure RobustPolynomialLearning+ takes $O(kd)$ samples and $O(kd^{\omega})$
time to find a degree $d$ polynomial $P(t)$ approximating $Q(t)$ such that

$\|P(t)-Q(t)\|_{T}\lesssim\|g^{\prime}(t)\|_{T},$

holds with probability at least $1-2^{-\Omega(k)}$. It indicates

$\|P(t)-e^{-2\pi\mathbf{i}\widetilde{f}_{0}t}\cdot
x^{*}(t)\|_{T}\lesssim\|P(t)-Q(t)\|_{T}+\|Q(t)-x^{*}(t)\|\lesssim\delta\|x^{*}(t)\|_{T}+\|g(t)\|_{T}\eqsim\mathcal{N}.$

Therefore we know $\|e^{2\pi\mathbf{i}\widetilde{f}_{0}t}\cdot
P(t)-x^{*}(t)\|_{T}^{2}\lesssim\mathcal{N}^{2}$. ∎

###  8.2 Bounding the Gram matrix determinant

We define Gram matrix for
$e^{2\pi\mathbf{i}f_{1}t},e^{2\pi\mathbf{i}f_{2}t},\cdots,e^{2\pi\mathbf{i}f_{k}t}$
and provide lower/upper bounds for its determinant.

######  Definition 8.2 (Gram matrix).

We define $\operatorname{Gram}_{f_{1},\cdots,f_{k}}$ to be

$\begin{bmatrix}\langle
e^{2\pi\mathbf{i}f_{1}t},e^{2\pi\mathbf{i}f_{1}t}\rangle_{T}&\langle
e^{2\pi\mathbf{i}f_{1}t},e^{2\pi\mathbf{i}f_{2}t}\rangle_{T}&\cdots&\langle
e^{2\pi\mathbf{i}f_{1}t},e^{2\pi\mathbf{i}f_{k}t}\rangle_{T}\\\ \langle
e^{2\pi\mathbf{i}f_{2}t},e^{2\pi\mathbf{i}f_{1}t}\rangle_{T}&\langle
e^{2\pi\mathbf{i}f_{2}t},e^{2\pi\mathbf{i}f_{2}t}\rangle_{T}&\cdots&\langle
e^{2\pi\mathbf{i}f_{2}t},e^{2\pi\mathbf{i}f_{k}t}\rangle_{T}\\\
\cdots&\cdots&\cdots&\cdots\\\ \langle
e^{2\pi\mathbf{i}f_{k}t},e^{2\pi\mathbf{i}f_{1}t}\rangle_{T}&\langle
e^{2\pi\mathbf{i}f_{k}t},e^{2\pi\mathbf{i}f_{2}t}\rangle_{T}&\cdots&\langle
e^{2\pi\mathbf{i}f_{k}t},e^{2\pi\mathbf{i}f_{k}t}\rangle_{T}\\\ \end{bmatrix}$

Note that the above matrix is a Hermitian matrix with complex entries, thus
both its determinant and all eigenvalues are in $\mathbb{R}$.

We defer the proof of the following Theorem to Appendix A.1.

######  Theorem 8.3.

For real numbers $\xi_{1},\ldots,\xi_{k}$, let $G_{\xi_{1},\ldots,\xi_{k}}$ be
the matrix whose $(i,j)$-entry is

$\int_{-1}^{1}e^{2\pi\mathbf{i}(\xi_{i}-\xi_{j})t}dt.$

Then

$\det(G_{\xi_{1},\ldots,\xi_{k}})=2^{\tilde{O}(k^{2})}\prod_{i<j}\min(|\xi_{i}-\xi_{j}|^{2},1).$

We use the following corollary in this section.

######  Corollary 8.4.

There exists a universal constant $\alpha>0$ such that, for any $T>0$ and real
numbers $f_{1},\cdots,f_{k}$, the $k\times k$ Gram matrix of
$e^{2\pi\mathbf{i}f_{1}t},e^{2\pi\mathbf{i}f_{2}t},\cdots,e^{2\pi\mathbf{i}f_{k}t}$
whose $(i,j)$-entry is

$\operatorname{Gram}_{f_{1},\cdots,f_{k}}(i,j)=\langle
e^{2\pi\mathbf{i}f_{i}t},e^{2\pi\mathbf{i}f_{j}t}\rangle_{T}=\frac{1}{T}\int_{0}^{T}e^{2\pi\mathbf{i}(f_{i}-f_{j})t}\mathrm{d}t.$

satisfies

$k^{-\alpha
k^{2}}\prod_{i<j}\min((|f_{i}-f_{j}|T)^{2},1)\leq\det\left(\operatorname{Gram}_{f_{1},\cdots,f_{k}}\right)\leq
k^{\alpha k^{2}}\prod_{i<j}\min((|f_{i}-f_{j}|T)^{2},1).$

Based on Corollary 8.4, we show the coefficients of a $k$-Fourier-sparse
signal can be upper bounded by the energy $\|x\|^{2}_{T}$.

######  Lemma 2.2.

There exists a universal constant $c>0$ such that for any
$x(t)=\overset{k}{\underset{j=1}{\sum}}v_{j}e^{2\pi\mathbf{i}f_{j}t}$ with
frequency gap $\eta=\underset{i\neq j}{\min}|f_{i}-f_{j}|$,

$\|x(t)\|^{2}_{T}\geq k^{-ck^{2}}\min\left((\eta
T)^{2k},1\right)\sum_{j=1}^{k}|v_{j}|^{2}.$

###### Proof.

Let $\vec{v_{i}}$ denote the vector $e^{2\pi\mathbf{i}f_{i}t}$ and
$V=\\{\vec{v_{1}},\cdots,\vec{v_{k}}\\}$. Notice that
$\|\vec{v_{i}}\|_{T}^{2}=\langle\vec{v_{i}},\vec{v_{i}}\rangle=1$. For each
$\vec{v_{i}}$, we define $\vec{v}_{i}^{\parallel}$ to be the projection of
$\vec{v_{i}}$ into the linear subspace
$\mathrm{span}\\{V\setminus\vec{v_{i}}\\}=\mathrm{span}\\{\vec{v}_{1},\cdots,\vec{v}_{i-1},\vec{v}_{i+1},\cdots,\vec{v}_{k}\\}$
and $\vec{v}_{i}^{\perp}=\vec{v}_{i}-\vec{v}_{i}^{\parallel}$ which is
orthogonal to $\mathrm{span}\\{V\setminus\vec{v_{i}}\\}$ by the definition.

Therefore from the orthogonality,

$\|x(t)\|_{T}^{2}\geq\max_{j\in[k]}\\{|v_{j}|^{2}\cdot\|\vec{v}_{j}^{\perp}\|_{T}^{2}\\}\geq\frac{1}{k}\overset{k}{\underset{j=1}{\sum}}|v_{j}|^{2}\cdot\|\vec{v}_{j}^{\perp}\|_{T}^{2}.$

It is enough to estimate $\|\vec{v}_{j}^{\perp}\|_{T}^{2}$ from Claim 3.12:

$\|\vec{v}_{j}^{\perp}\|_{T}^{2}=\frac{\det(\operatorname{Gram}(V))}{\det(\operatorname{Gram}(V\setminus\vec{v}_{i}))}\geq
k^{-2\alpha k^{2}}\prod_{j\neq i}\min\left((f_{j}-f_{i})T,1\right)^{2}\geq
k^{-2\alpha k^{2}}(\eta T)^{2k-2},$

where we use Corollary 8.4 to lower bound it in the last step. ∎

###  8.3 Perturbing the frequencies does not change the subspace much

We show that for a $k$-Fourier-sparse signal with unboundedly close frequency
gap, there always exists another $k$-Fourier-sparse signal with slightly
separated gap.

######  Lemma 8.5 (Slightly Shifting one Frequency).

There is a universal constant $C_{0}>0$ such that for any
$x(t)=\overset{k}{\underset{j=1}{\sum}}v_{j}e^{2\pi\mathbf{i}f_{j}t}$ and any
frequency $f_{k+1}$, there always exists

$x^{\prime}(t)=\overset{k-1}{\underset{j=1}{\sum}}v^{\prime}_{j}e^{2\pi\mathbf{i}f_{j}t}+v^{\prime}_{k+1}e^{2\pi\mathbf{i}f_{k+1}t}$

with $k$ coefficients
$v^{\prime}_{1},v^{\prime}_{2},\cdots,v^{\prime}_{k-1},v_{k+1}^{\prime}$
satisfying

$\|x^{\prime}(t)-x(t)\|_{T}\leq
k^{C_{0}k^{2}}\cdot\left(|f_{k}-f_{k+1}|T\right)\cdot\|x(t)\|_{T}$

###### Proof.

We abuse the notation $e^{2\pi\mathbf{i}f_{j}t}$ to denote a vector in the
linear subspace. We plan to shift $f_{k}$ to $f_{k+1}$ and define

$\displaystyle V$ $\displaystyle=$
$\displaystyle\\{e^{2\pi\mathbf{i}f_{1}t},\cdots,e^{2\pi\mathbf{i}f_{k-1}t},e^{2\pi\mathbf{i}f_{k}t}\\}$
$\displaystyle V^{\prime}$ $\displaystyle=$
$\displaystyle\\{e^{2\pi\mathbf{i}f_{1}t},\cdots,e^{2\pi\mathbf{i}f_{k-1}t},e^{2\pi\mathbf{i}f_{k+1}t}\\}$
$\displaystyle U$ $\displaystyle=$
$\displaystyle\\{e^{2\pi\mathbf{i}f_{1}t},\cdots,e^{2\pi\mathbf{i}f_{k-1}t}\\}$
$\displaystyle W$ $\displaystyle=$
$\displaystyle\\{e^{2\pi\mathbf{i}f_{1}t},\cdots,e^{2\pi\mathbf{i}f_{k-1}t},e^{2\pi\mathbf{i}f_{k}t},e^{2\pi\mathbf{i}f_{k+1}t}\\}$

where $f_{1},f_{2},\cdots,f_{k}$ are original frequencies in $x$. The idea is
to show that any vector in the linear subspace $\mathrm{span}\\{V\\}$ is close
to some vector in the linear subspace $\mathrm{span}\\{V^{\prime}\\}$.

For convenience, we use $\vec{u}^{\parallel}$ to denote the projection of
vector $e^{2\pi\mathbf{i}f_{k}t}$ to the linear subspace
$\mathrm{span}\\{U\\}=\mathrm{span}\\{e^{2\pi\mathbf{i}f_{1}t},\cdots,e^{2\pi\mathbf{i}f_{k-1}t}\\}$
and $\vec{w}^{\parallel}$ denote the projection of vector
$e^{2\pi\mathbf{i}f_{k+1}t}$ to this linear subspace $\mathrm{span}\\{U\\}$.
Let $\vec{u}^{\perp}=e^{2\pi\mathbf{i}f_{k}t}-\vec{u}^{\parallel}$ and
$\vec{w}^{\perp}=e^{2\pi\mathbf{i}f_{k+1}t}-\vec{w}^{\parallel}$ be their
orthogonal part to $\mathrm{span}\\{U\\}$.

From the definition
$e^{2\pi\mathbf{i}f_{k}t}=\vec{u}^{\parallel}+\vec{u}^{\perp}$ and
$\vec{u}^{\parallel}\in\mathrm{span}\\{U\\}=\mathrm{span}\\{e^{2\pi\mathbf{i}f_{1}t},\cdots,e^{2\pi\mathbf{i}f_{k-1}t}\\}$,
we rewrite the linear combination

$x(t)=\sum_{j=1}^{k}v_{j}e^{2\pi\mathbf{i}f_{j}t}=\sum_{j=1}^{k-1}\alpha_{j}e^{2\pi\mathbf{i}f_{j}t}+v_{k}\cdot\vec{u}^{\perp}$

for some scalars $\alpha_{1},\cdots,\alpha_{k-1}$.

We will substitute $\vec{u}^{\perp}$ by $\vec{w}^{\perp}$ in the above linear
combination and find a set of new coefficients. Let
$\vec{w}^{\perp}=\vec{w}_{1}+\vec{w}_{2}$ where
$\vec{w}_{1}=\frac{\langle\vec{u}^{\perp},\vec{w}^{\perp}\rangle}{\|\vec{u}^{\perp}\|^{2}_{T}}\vec{u}^{\perp}$
is the projection of $\vec{w}^{\perp}$ to $\vec{u}^{\perp}$. Therefore
$\vec{w}_{2}$ is the orthogonal part of the vector
$e^{2\pi\mathbf{i}f_{k+1}t}$ to
$\mathrm{span}\\{V\\}=\mathrm{span}\\{e^{2\pi\mathbf{i}f_{1}t},\cdots,e^{2\pi\mathbf{i}f_{k-1}t},e^{2\pi\mathbf{i}f_{k}t}\\}$.
We use $\delta=\frac{\|\vec{w}_{2}\|_{T}}{\|\vec{w}^{\perp}\|_{T}}$ for
convenience.

Notice that the
$\underset{\beta\in\operatorname*{\mathbb{C}}}{\min}\frac{\|\vec{u}^{\perp}-\beta\cdot\vec{w}^{\perp}\|_{T}}{\|\vec{u}^{\perp}\|_{T}}=\delta$
and
$\beta^{*}=\frac{\langle\vec{u}^{\perp},\vec{w}^{\perp}\rangle}{\|\vec{w}^{\perp}\|^{2}_{T}}$
is the optimal choice. Therefore we set

$x^{\prime}(t)=\sum_{j=1}^{k-1}\beta_{j}e^{2\pi\mathbf{i}f_{j}t}+v_{k}\cdot\beta^{*}\cdot\vec{w}^{\perp}\in\mathrm{span}\\{e^{2\pi\mathbf{i}f_{1}t},\cdots,e^{2\pi\mathbf{i}f_{k-1}t},e^{2\pi\mathbf{i}f_{k+1}t}\\}$

where the coefficients $\beta_{1},\cdots,\beta_{k-1}$ guarantee that the
projection of $x^{\prime}$ onto $\mathrm{span}\\{U\\}$ is as same as the
projection of $x$ onto $\mathrm{span}\\{U\\}$. From the choice of $\beta^{*}$
and the definition of $x^{\prime}$,

$\|x(t)-x^{\prime}(t)\|_{T}^{2}=\delta^{2}\cdot|v_{k}|^{2}\cdot\|\vec{u}^{\perp}\|_{T}^{2}\leq\delta^{2}\cdot\|x(t)\|_{T}^{2}.$

Eventually, we show an upper bound for $\delta^{2}$ from Claim 3.12.

$\displaystyle\delta^{2}$ $\displaystyle=$
$\displaystyle\frac{\|\vec{w}_{2}\|_{T}^{2}}{\|\vec{w}^{\perp}\|_{T}^{2}}$
$\displaystyle=$
$\displaystyle\frac{\det(\operatorname{Gram}_{W})}{\det(\operatorname{Gram}_{V})}/\frac{\det(\operatorname{Gram}_{V^{\prime}})}{\det(\operatorname{Gram}_{U})}\text{\leavevmode\nobreak\
by\leavevmode\nobreak\ Claim\leavevmode\nobreak\
\ref{cla:orthogonal_distance}}$ $\displaystyle=$
$\displaystyle\frac{\det(\operatorname{Gram}_{W})}{\det(\operatorname{Gram}_{V})}\cdot\frac{\det(\operatorname{Gram}_{U})}{\det(\operatorname{Gram}_{V^{\prime}})}\text{\leavevmode\nobreak\
by\leavevmode\nobreak\ Corollary\leavevmode\nobreak\
\ref{cor:determinant_corollary} }$ $\displaystyle\leq$ $\displaystyle
k^{4\alpha
k^{2}}\cdot\frac{\overset{k+1}{\underset{i=1}{\prod}}\overset{k+1}{\underset{\begin{subarray}{c}j=1\\\
j\neq
i\end{subarray}}{\prod}}\min(|f_{i}-f_{j}|T,1)}{\overset{k}{\underset{i=1}{\prod}}\overset{k}{\underset{\begin{subarray}{c}j=1\\\
j\neq
i\end{subarray}}{\prod}}\min(|f_{i}-f_{j}|T,1)}\cdot\frac{\overset{k-1}{\underset{i=1}{\prod}}\overset{k-1}{\underset{\begin{subarray}{c}j=1\\\
j\neq
i\end{subarray}}{\prod}}\min(|f_{i}-f_{j}|T,1)}{\overset{k-1}{\underset{i=1}{\prod}}\overset{k-1}{\underset{\begin{subarray}{c}j=1\\\
j\neq
i\end{subarray}}{\prod}}\min(|f_{i}-f_{j}|T,1)\cdot\overset{k-1}{\underset{i=1}{\prod}}\min(|f_{i}-f_{k+1}|^{2}T^{2},1)}$
$\displaystyle=$ $\displaystyle k^{4\alpha k^{2}}|f_{k}-f_{k+1}|^{2}T^{2}$

∎

######  Lemma 8.6.

For any $k$ frequencies $f_{1}<f_{2}<\cdots<f_{k}$, there exists $k$
frequencies $f^{\prime}_{1},\cdots,f^{\prime}_{k}$ such that
$\underset{i\in[k-1]}{\min}f^{\prime}_{i+1}-f^{\prime}_{i}\geq\eta$ and for
all $i\in[k]$, $|f^{\prime}_{i}-f_{i}|\leq k\eta$.

###### Proof.

We define the new frequencies $f_{i}^{\prime}$ as follows:
$f_{1}^{\prime}=f_{1}$ and
$f_{i}^{\prime}=\max\\{f^{\prime}_{i-1}+\eta,f_{i}\\}$ for
$i\in\\{2,3,\cdots,k\\}$. ∎

###  8.4 Existence of nearby $k$-Fourier-sparse signal with frequency gap
bounded away from zero

We combine the results in the above section to finish the proof of Lemma 2.3.
We first prove that for any
$x^{*}(t)=\overset{k}{\underset{j=1}{\sum}}v_{j}e^{2\pi\mathbf{i}f_{j}t}$,
there always exists another $k$-Fourier-sparse signal $x^{\prime}$ close to
$x^{*}(t)=\overset{k}{\underset{j=1}{\sum}}v_{j}e^{2\pi\mathbf{i}f_{j}t}$ such
that the frequency gap in $x^{\prime}$ is at least $\eta\geq
2^{-\operatorname{poly}(k)}$. Then we show how to find a low degree polynomial
$P(t)$ approximating $x^{\prime}(t)$.

######  Lemma 2.1.

There is a universal constant $C_{1}>0$ such that, for any
$x^{*}(t)=\overset{k}{\underset{j=1}{\sum}}v_{j}e^{2\pi\mathbf{i}f_{j}t}$ and
any $\delta>0$ , there always exist $\eta\geq\frac{\delta}{T}\cdot
k^{-C_{1}k^{2}}$ and
$x^{\prime}(t)=\overset{k}{\underset{j=1}{\sum}}v^{\prime}_{j}e^{2\pi\mathbf{i}f^{\prime}_{j}t}$
satisfying

$\|x^{\prime}(t)-x^{*}(t)\|_{T}\leq\delta\|x^{*}(t)\|_{T}$

with $\underset{i\neq j}{\min}|f^{\prime}_{i}-f^{\prime}_{j}|\geq\eta$ and
$\underset{j\in[k]}{\max}\\{|f^{\prime}_{j}-f_{j}|\\}\leq k\eta$.

###### Proof.

Using Lemma 8.6 on frequencies $f_{1},\cdots,f_{k}$, we obtain $k$ new
frequencies $f^{\prime}_{1},\cdots,f^{\prime}_{k}$ such that their gap is at
least $\eta$ and $\max_{i}|f_{i}-f^{\prime}_{i}|\leq k\eta$. Next we use the
hybrid argument to find $x^{\prime}$.

Let $x^{(0)}(t)=x^{*}(t)$. For $i=1,\cdots,t,$ we apply Lemma 8.5 to shift
$f_{i}$ to $f^{\prime}_{i}$ and obtain

$x^{(i)}(t)=\overset{k}{\underset{j=i+1}{\sum}}v^{(i)}_{j}e^{2\pi\mathbf{i}f_{j}t}+\overset{i}{\underset{j=1}{\sum}}v^{(i)}_{j}e^{2\pi\mathbf{i}f^{\prime}_{j}t}.$

From Lemma 8.5, we know $\|x^{(i)}(t)-x^{(i-1)}(t)\|_{T}\leq
k^{C_{0}k^{2}}(|f_{i}-f^{\prime}_{i}|T)\|x^{(i-1)}\|_{T}$. Thus we obtain

$\left(1-k^{C_{0}k^{2}}(k\eta
T)\right)^{i}\|x^{(0)}(t)\|_{T}\leq\|x^{(i)}(t)\|_{T}\leq\left(1+k^{C_{0}k^{2}}(k\eta
T)\right)^{i}\|x^{(0)}(t)\|_{T},$

which is between $\left[\left(1-i\cdot k^{C_{0}k^{2}}(k\eta
T)\right)\|x^{(0)}(t)\|_{T},\left(1+2i\cdot k^{C_{0}k^{2}}(k\eta
T)\right)\|x^{(0)}(t)\|_{T}\right]$ for $\eta\leq\frac{1}{5T}\cdot
k^{-C_{1}k^{2}}$ with some $C_{1}>C_{0}$.

At last, we set $x^{\prime}(t)=x^{(k)}(t)$ and bound the distance between
$x^{\prime}(t)$ and $x^{*}(t)$ by

$\displaystyle\|x^{(k)}(t)-x^{(0)}(t)\|_{T}\leq$
$\displaystyle\leavevmode\nobreak\
\sum_{i=1}^{k}\|x^{(i)}(t)-x^{(i-1)}(t)\|_{T}$ by triangle inequality
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\sum_{i=1}^{k}k^{C_{0}k^{2}}(|f_{i}-f_{i}^{\prime}|T)\|x^{(i-1)}(t)\|_{T}$ by
Lemma 8.5 $\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\sum_{i=1}^{k}2k^{C_{0}k^{2}}(k\eta T)\|x^{(i-1)}(t)\|_{T}$ by
$\underset{i}{\max}|f_{i}-f_{i}^{\prime}|\leq k\eta$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ k\cdot 2k^{C_{0}k^{2}}(k\eta
T)\|x^{*}(t)\|_{T}$ $\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\delta\|x^{*}(t)\|_{T}$

where the last inequality follows by the sufficiently small $\eta$. ∎

###  8.5 Approximating $k$-Fourier-sparse signals by polynomials

For any $k$-Fourier-sparse signal with frequency gap bounded away from zero,
we show that there exists a low degree polynomial which is close to the
original $k$-Fourier-sparse signal in $\|\cdot\|_{T}$ distance.

######  Lemma 8.7 (Existence of low degree polynomial).

Let $x^{*}(t)=\overset{k}{\underset{j=1}{\sum}}v_{j}e^{2\pi\mathbf{i}f_{j}t}$,
where $\forall j\in[k],|f_{j}|\leq\Delta$ and $\underset{i\neq
j}{\min}|f_{i}-f_{j}|\geq\eta$. There exists a polynomial $Q(t)$ of degree

$d=O\left(T\Delta+k\log 1/(\eta T)+k^{2}\log k+k\log(1/\delta)\right)$

such that,

$\|Q(t)-x^{*}(t)\|_{T}^{2}\leq\delta\|x^{*}(t)\|_{T}^{2}$ (25)

###### Proof.

For each frequency $f_{j}$, let
$Q_{j}(t)=\overset{d-1}{\underset{k=0}{\sum}}\frac{(2\pi\mathbf{i}f_{j}t)^{k}}{k!}$
be the first $d$ terms in the Taylor Expansion of $e^{2\pi\mathbf{i}f_{j}t}$.
For any $t\in[0,T]$, we know the difference between $Q_{j}(t)$ and
$e^{2\pi\mathbf{i}f_{j}t}$ is at most

$|Q_{j}(t)-e^{2\pi\mathbf{i}f_{j}t}|\leq|\frac{(2\pi\mathbf{i}f_{j}T)^{d}}{d!}|\leq(\frac{2\pi
T\Delta\cdot e}{d})^{d}.$

We define

$Q(t)=\sum_{j=1}^{k}v_{j}Q_{j}(t)$

and bound the distance between $Q$ and $x^{*}$ from the above estimation:

$\displaystyle\|Q(t)-x^{*}(t)\|_{T}^{2}=$ $\displaystyle\leavevmode\nobreak\
\frac{1}{T}\int_{0}^{T}|Q(t)-x^{*}(t)|^{2}\mathrm{d}t$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
\frac{1}{T}\int_{0}^{T}|\sum_{j=1}^{k}v_{j}(Q_{j}(t)-e^{2\pi\mathbf{i}f_{j}t})|^{2}\mathrm{d}t$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
2k\sum_{j=1}^{k}\frac{1}{T}\int_{0}^{T}|v_{j}|^{2}\cdot|Q_{j}(t)-e^{2\pi\mathbf{i}f_{j}t}|^{2}\mathrm{d}t$
by triangle inequality $\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
k\sum_{j=1}^{k}|v_{j}|^{2}\cdot(\frac{2\pi T\Delta\cdot e}{d})^{2d}$ by Taylor
expansion

On the other hand, from Lemma 2.2, we know

$\|x^{*}(t)\|_{T}^{2}\geq(\eta T)^{2k}\cdot k^{-ck^{2}}\sum_{j}|v_{j}|^{2}.$

Because $d=10\cdot\pi e(T\Delta+k\log 1/(\eta T)+k^{2}\log k+k\log(1/\delta))$
is large enough, we have $k(\frac{2\pi T\Delta\cdot e}{d})^{2d}\leq\delta(\eta
T)^{2k}\cdot k^{-ck^{2}}$, which indicates that
$\|Q(t)-x^{*}(t)\|_{T}^{2}\leq\delta\|x^{*}\|_{T}^{2}$ from all discussion
above. ∎

###  8.6 Transferring degree-$d$ polynomial to ($d$+$1$)-Fourier-sparse signal

In this section, we show how to transfer a degree-$d$ polynomial to
($d$+$1$)-Fourier-sparse signal.

######  Lemma 8.8.

For any degree-$d$ polynomial
$Q(t)=\overset{d}{\underset{j=0}{\sum}}c_{j}t^{j}$, any $T>0$ and any
$\epsilon>0$, there always exist $\gamma>0$ and

$x^{*}(t)=\sum_{i=1}^{d+1}\alpha_{i}e^{2\pi\mathbf{i}(\gamma i)t}$

with some coefficients $\alpha_{0},\cdots,\alpha_{d}$ such that

$\forall t\in[0,T],|x^{*}(t)-Q(t)|\leq\epsilon.$

###### Proof.

We can rewrite $x^{*}(t)$,

$\displaystyle x^{*}(t)=\leavevmode\nobreak\ $
$\displaystyle\sum_{i=1}^{d+1}\alpha_{i}e^{2\pi\mathbf{i}\gamma it}$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\sum_{i=1}^{d+1}\alpha_{i}\sum_{j=0}^{\infty}\frac{(2\pi\mathbf{i}\gamma
it)^{j}}{j!}$ $\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\sum_{j=0}^{\infty}\frac{(2\pi\mathbf{i}\gamma
t)^{j}}{j!}\sum_{i=1}^{d+1}\alpha_{i}\cdot i^{j}$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\sum_{j=0}^{d}\frac{(2\pi\mathbf{i}\gamma
t)^{j}}{j!}\sum_{i=1}^{d+1}\alpha_{i}\cdot
i^{j}+\sum_{j=d+1}^{\infty}\frac{(2\pi\mathbf{i}\gamma
t)^{j}}{j!}\sum_{i=1}^{d+1}\alpha_{i}\cdot i^{j}$
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle
Q(t)+\underbrace{\left(\sum_{j=0}^{d}\frac{(2\pi\mathbf{i}\gamma
t)^{j}}{j!}\sum_{i=1}^{d+1}\alpha_{i}\cdot
i^{j}-Q(t)\right)}_{C_{1}}+\underbrace{\left(\sum_{j=d+1}^{\infty}\frac{(2\pi\mathbf{i}\gamma
t)^{j}}{j!}\sum_{i=1}^{d+1}\alpha_{i}\cdot i^{j}\right)}_{C_{2}}.$

Our goal is to show there exists some parameter $\gamma$ and coefficients
$\\{\alpha_{0},\alpha_{1},\cdots,\alpha_{d}\\}$ such that the term $C_{1}=0$
and $|C_{2}|\leq\epsilon$. Let’s consider $C_{1}$,

$\displaystyle
C_{1}=\sum_{j=0}^{d}(\frac{t}{T})^{j}\left(\frac{(2\pi\mathbf{i}\gamma
T)^{j}}{j!}\sum_{i=1}^{d+1}\alpha_{i}i^{j}-c_{j}\right)$

To guarantee $C_{1}=0$, we need to solve a linear system with $d+1$ unknown
variables and $d+1$ constraints,

Find $\displaystyle\leavevmode\nobreak\
\alpha_{1},\alpha_{2},\cdots\alpha_{d+1}$ s.t.
$\displaystyle\leavevmode\nobreak\ \frac{(2\pi\mathbf{i}\gamma
T)^{j}}{j!}\sum_{i=1}^{d+1}\alpha_{i}i^{j}-c_{j}=0,\forall
j\in\\{0,1,\cdots,d\\}$

Define $c^{\prime}_{j}=c_{j}j!/(2\pi\mathbf{i}\gamma)^{j}$, let $\alpha$ and
$c^{\prime}$ be the length-($d+1$) column vectors with $\alpha_{i}$ and
$c^{\prime}_{j}$. Let $A\in\mathbb{R}^{d+1\times d+1}$ denote the Vandermonde
matrix where $A_{i,j}=i^{j},\forall i,j\in[d+1]\times\\{0,1,\cdots,d\\}$. Then
we need to guarantee $A\alpha=c^{\prime}$. Using the definition of
determinant, $\det(A)=\underset{i<j}{\prod}|i-j|\leq 2^{O(d^{2}\log d)}$. Thus
$\sigma_{\max}(A)\leq 2^{O(d^{2}\log d)}$ and then

$\displaystyle\sigma_{\min}(A)=\frac{\det(A)}{\prod_{i=1}^{d-1}\sigma_{i}}\geq
2^{-O(d^{3}\log d)}.$

We show how to upper bound $|\alpha_{i}|$,

$\displaystyle\leavevmode\nobreak\
\max_{i\in[d+1]}|\alpha_{i}|\leq\|\alpha\|_{2}=\|A^{\dagger}c^{\prime}\|_{2}\leq\|A^{\dagger}\|_{2}\cdot\|c^{\prime}\|_{2}\leq\frac{1}{\sigma_{\min}(A)}\sqrt{d+1}\max_{0\leq
j\leq d}\frac{|c_{j}|j!}{(2\pi\gamma T)^{j}}$

Plugging the above equation into $C_{2}$, we have

$\displaystyle|C_{2}|$ $\displaystyle\leavevmode\nobreak\
=\left|\sum_{j=d+1}^{\infty}\frac{(2\pi\mathbf{i}\gamma
t)^{j}}{j!}\sum_{i=1}^{d+1}\alpha_{i}\cdot i^{j}\right|$
$\displaystyle\leavevmode\nobreak\ \leq\sum_{j=d+1}^{\infty}\frac{(2\pi\gamma
t)^{j}}{j!}\sum_{i=1}^{d+1}|\alpha_{i}|\cdot i^{j}$
$\displaystyle\leavevmode\nobreak\ \leq\sum_{j=d+1}^{\infty}\frac{(2\pi\gamma
t)^{j}}{j!}(d+1)^{d+1}\max_{i\in[d+1]}|\alpha_{i}|$
$\displaystyle\leavevmode\nobreak\ \leq\sum_{j=d+1}^{\infty}\frac{(2\pi\gamma
t)^{j}}{j!}(d+1)^{d+2}\frac{1}{\sigma_{\min}(A)}\frac{d!}{(2\pi\gamma
T)^{d}}\max_{0\leq j\leq d}|c_{j}|$ $\displaystyle\leavevmode\nobreak\
\leq\epsilon$

where the last step follows by choosing sufficiently small

$\displaystyle\gamma\lesssim\epsilon/\left(T2^{\Theta(d^{3}\log
d)}\underset{0\leq j\leq d}{\max}|c_{j}|\right).$

∎

##  9 $k$-cluster Signal Recovery

###  9.1 Overview

In this section, we prove Lemma 9.1 as the main technical lemma to finish the
proof of main Theorem 1.1, which shows how to learn
$x^{*}(t)=\sum_{j=1}^{k}v_{j}e^{2\pi\mathbf{i}f_{j}t}$ with noise.

######  Lemma 9.1.

Let $x^{*}(t)=\sum_{j=1}^{k}v_{j}e^{2\pi\mathbf{i}f_{j}t}$ and
$x(t)=x^{*}(t)+g(t)$ be our observation. For any $\delta>0$ and $T>0$, let
$\mathcal{N}^{2}:=\frac{1}{T}\int_{0}^{T}|g(t)|^{2}\mathrm{d}t+\delta\cdot\frac{1}{T}\int_{0}^{T}|x^{*}(t)|^{2}\mathrm{d}t$.
For $\Delta=\operatorname{poly}(k,\log(1/\delta))/T$, Procedure
SignalRecoveryKCluster+ in Algorithm 8 takes $l=O(k)$ frequencies
$\widetilde{f}_{1},\cdots,\widetilde{f}_{l}$ as input and finds $l$
polynomials $Q_{1},\cdots,Q_{l}$ of degree $d=O((T\Delta)^{1.5}+k^{3}\log
k+k\log 1/\delta)$ such that

$\widetilde{x}(t)=\sum_{j\in[l]}Q_{j}(t)e^{2\pi\mathbf{i}\widetilde{f}_{j}t}\mathrm{\leavevmode\nobreak\
satisfies\leavevmode\nobreak\
}\|\widetilde{x}(t)-x^{*}(t)\|_{T}^{2}\lesssim\mathcal{N}^{2}.$ (26)

The procedure succeeds with probability at least $1-2^{-\Omega(k)}$, uses
$\operatorname{poly}(k,\log(1/\delta))\cdot\log(FT)$ samples, and runs in
$\operatorname{poly}(k,\log(1/\delta))\cdot\log^{2}(FT)$ time.

For any set $W=\\{t_{1},\cdots,t_{m}\\}$ where each $t_{i}\in[0,T]$, we use

$\|\vec{v}\|_{W}=\sqrt{\frac{\sum_{i\in W}|\vec{v}(t_{i})|^{2}}{|W|}}\textit{
for any }\vec{v}:[0,T]\rightarrow\mathbb{C}$

in this section. We first show that Procedure SignalRecoveryKCluster succeeds
with constant probability, then prove that Procedure SignalRecoveryKCluster+
succeeds with probability at least $1-2^{-\Omega(k)}$.

###  9.2 Heavy clusters separation

Recall the definition of “heavy” clusters.

######  Definition 2.4.

Given
$x^{*}(t)=\overset{k}{\underset{j=1}{\sum}}v_{j}e^{2\pi\mathbf{i}f_{j}t}$, any
$\mathcal{N}>0$, and a filter function $(H,\widehat{H})$ with bounded support
in frequency domain. Let $L_{j}$ denote the interval of $\leavevmode\nobreak\
\operatorname{supp}(\widehat{e^{2\pi\mathbf{i}f_{j}t}\cdot H})$ for each
$j\in[k]$.

Define an equivalence relation $\sim$ on the frequencies $f_{i}$ by the
transitive closure of the relation $f_{i}\sim f_{j}$ if $L_{i}\cap
L_{j}\neq\emptyset$. Let $S_{1},\ldots,S_{n}$ be the equivalence classes under
this relation.

Define $C_{i}=\underset{f\in S_{i}}{\cup}L_{i}$ for each $i\in[n]$. We say
$C_{i}$ is a “heavy” cluster iff $\int_{C_{i}}|\widehat{H\cdot
x^{*}}(f)|^{2}\mathrm{d}f\geq T\cdot\mathcal{N}^{2}/k$.

By reordering $C_{i}$, we can assume $\\{C_{1},C_{2},\cdots,C_{l}\\}$ are
heavy clusters, where $l\leq n\leq k$.

######  Claim 2.5.

Given
$x^{*}(t)=\overset{k}{\underset{j=1}{\sum}}v_{j}e^{2\pi\mathbf{i}f_{j}t}$ and
any $\mathcal{N}>0$, let $H$ be the filter function defined in Appendix C.1
and $C_{1},\cdots,C_{l}$ be the heavy clusters from Definition 2.4. For

$S=\left\\{j\in[k]\bigg{|}f_{j}\in C_{1}\cup\cdots C_{l}\right\\},$

we have $x^{(S)}(t)=\underset{j\in S}{\sum}v_{j}e^{2\pi\mathbf{i}f_{j}t}$
approximating $x^{*}$ within distance
$\|x^{(S)}(t)-x^{*}(t)\|_{T}^{2}\lesssim\mathcal{N}^{2}.$

###### Proof.

Let $x^{(\overline{S})}(t)=\underset{j\in[k]\backslash
S}{\sum}v_{j}e^{2\pi\mathbf{i}f_{j}t}$. Notice that
$\|x^{*}-x^{(S)}\|_{T}^{2}=\|x^{(\overline{S})}\|^{2}_{T}$.

From the property vi@ of filter function $(H,\widehat{H})$ in Appendix C.1, we
have

$\int_{-\infty}^{+\infty}|x^{(\overline{S})}(t)\cdot H(t)|^{2}\mathrm{d}t\geq
0.9\int_{0}^{T}|x^{(\overline{S})}(t)|^{2}\mathrm{d}t=0.9\cdot
T\|x^{\overline{S}}\|_{T}^{2}.$

From Definition 2.4, we have

$\displaystyle\int_{-\infty}^{+\infty}|x^{(\overline{S})}(t)\cdot
H(t)|^{2}\mathrm{d}t=$ $\displaystyle\leavevmode\nobreak\
\int_{-\infty}^{+\infty}|\widehat{x^{(\overline{S})}\cdot
H}(f)|^{2}\mathrm{d}f$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\int_{[-\infty,+\infty]\setminus C_{1}\cup\cdots\cup
C_{l}}|\widehat{x^{*}\cdot H}(f)|^{2}\mathrm{d}f$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ k\cdot T\mathcal{N}^{2}/k.$

Overall, we have $\|x^{(\overline{S})}\|^{2}_{T}\lesssim\mathcal{N}^{2}.$ ∎

From the guarantee of Theorem 2.6, for any $j\in S$,
$\underset{i\in[l]}{\min}|f_{j}-\widetilde{f}_{i}|\leq\Delta\sqrt{\Delta T}$.
From now on, we focus on the recovery of $x^{(S)}$, which is enough to
approximate $x^{*}$ from the above claim. Because we are looking for
$\tilde{x}$ approximating $x^{(S)}$ within distance $O(\mathcal{N}^{2})$, from
Lemma 2.1, we can assume there is a frequency gap
$\eta\geq\frac{\delta}{10T}k^{-O(k^{2})}$ among $x^{(S)}$.

###  9.3 Approximating clusters by polynomials

In this section, we show how to approximate $x^{(S)}$ by
$x^{\prime}(t)=\sum_{i\in[l]}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)$
where $P_{1},\cdots,P_{l}$ are low degree polynomials.

######  Claim 9.2.

For any $x^{(S)}(t)=\sum_{j\in S}v_{j}e^{2\pi\mathbf{i}f_{j}t}$ with a
frequency gap $\eta=\underset{i\neq j}{\min}|f_{i}-f_{j}|$ and $l$ frequencies
$\widetilde{f}_{1},\cdots,\widetilde{f}_{l}$ with the property $\forall j\in
S,\min_{i\in[l]}|f_{j}-\widetilde{f}_{i}|\leq\Delta\sqrt{\Delta T}$, let

$d=5\pi\left((T\Delta)^{1.5}+k^{3}\log k+\log 1/\delta\right)\textit{ and
}V=\left\\{t^{j}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}|i\in[l],j\in\\{0,\cdots,d\\}\right\\}.$

There exists $x^{\prime}(t)\in\mathrm{span}\\{V\\}$ that approximates
$x^{(S)}(t)$ as follows:

$\forall t\in[0,T],|x^{\prime}(t)-x^{(S)}(t)|\leq\delta\|x^{(S)}\|_{T}.$

###### Proof.

From Lemma 2.2, we know

$\|x^{(S)}\|^{2}_{T}\geq(\eta T)^{2k}\cdot k^{-ck^{2}}\sum_{j\in
S}|v_{j}|^{2}.$

For each frequency $f_{j}$, we use $p_{j}$ to denote the index in $[l]$ such
that $|f_{j}-\widetilde{f}_{p_{j}}|\leq\Delta\sqrt{\Delta T}$. We rewrite

$x^{(S)}(t)=\sum_{i=1}^{l}e^{2\pi\mathbf{i}\widetilde{f}_{i}}\left(\sum_{j\in
S:p_{j}=i}v_{j}e^{2\pi\mathbf{i}(f_{j}-\widetilde{f}_{i})t}\right).$

For $d=5\pi((T\Delta)^{1.5}+k^{3}\log k+\log 1/\delta)$ and each
$e^{2\pi\mathbf{i}(f_{j}-\widetilde{f}_{p_{j}})t}$, let
$Q_{j}(t)=\sum_{i=0}^{d-1}\frac{\left(2\pi\mathbf{i}(f_{j}-\widetilde{f}_{p_{j}})t\right)^{i}}{i!}$
be the first $d$ terms in the Taylor Expansion of
$e^{2\pi\mathbf{i}(f_{j}-\widetilde{f}_{p_{j}})t}$. For any $t\in[0,T]$, we
know the difference between $Q_{j}(t)$ and
$e^{2\pi\mathbf{i}(f_{j}-\widetilde{f}_{p_{j}})t}$ is at most

$\forall
t\in[0,T],|Q_{j}(t)-e^{2\pi\mathbf{i}(f_{j}-\widetilde{f}_{p_{j}})t}|\leq|\frac{(2\pi\mathbf{i}(f_{j}-\widetilde{f}_{p_{j}})T)^{d}}{d!}|\leq(\frac{8\pi(\Delta
T)^{1.5}}{d})^{d}.$

Let
$x^{\prime}=\sum_{i=1}^{l}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}\left(\sum_{j\in
S:p_{j}=i}v_{j}Q_{j}(t)\right).$ From all discussion above, we know for any
$t\in[0,T]$,

$\displaystyle|x^{\prime}(t)-x^{(S)}(t)|^{2}\leq$
$\displaystyle\leavevmode\nobreak\ \left(\sum_{j\in
S}|v_{j}|(\frac{8\pi(T\Delta)^{1.5}}{d})^{d}\right)^{2}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
k(\frac{8\pi(T\Delta)^{1.5}}{d})^{2d}\sum_{j}|v_{j}|^{2}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
\frac{k(\frac{8\pi(T\Delta)^{1.5}}{d})^{2d}}{(\eta T)^{2k}\cdot
k^{-ck^{2}}}\|x^{(S)}\|_{T}^{2}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ \delta^{2}\|x^{(S)}\|_{T}^{2}.$

∎

We provide a property of functions in $\mathrm{span}\\{V\\}$ such that we can
use the Chernoff bound and the $\epsilon$-net argument on vectors in
$\mathrm{span}\\{V\\}$.

######  Claim 2.7.

For any
$\vec{u}\in\mathrm{span}\left\\{e^{2\pi\mathbf{i}\widetilde{f}_{i}t}\cdot
t^{j}\bigg{|}j\in\\{0,\cdots,d\\},i\in[l]\right\\}$, there exists some
universal constants $C_{1}\leq 4$ and $C_{2}\leq 3$ such that

$\max_{t\in[0,T]}\\{|\vec{u}(t)|^{2}\\}\lesssim(ld)^{C_{1}}\log^{C_{2}}(ld)\cdot\|\vec{u}\|^{2}_{T}$

###### Proof.

From Lemma 8.8, we can approximate each polynomial in $\vec{u}$ by a linear
combination of $\\{1,e^{2\pi\mathbf{i}\cdot\gamma
t},\cdots,e^{2\pi\mathbf{i}\cdot(\gamma d)t}\\}$ such that we obtain
$u^{*}\in\mathrm{span}\left\\{e^{2\pi\mathbf{i}\cdot(\gamma j)t}\cdot
e^{2\pi\mathbf{i}\tilde{f}_{i}t}|i\in[l],j\in\\{0,\cdots,d+1\\}\right\\}$ for
some small $\gamma$ such that $\forall t\in[0,T],|\vec{u}(t)-u^{*}(t)|\leq
0.01\|\vec{u}\|_{T}$.

From Lemma 5.1, we know

$\max_{t\in[0,T]}|u^{*}(t)|^{2}\leq
C\cdot\left((ld+1)^{4}\cdot\log^{3}(ld+1)\right)\|u^{*}\|_{T}^{2}.$

For some constant $C^{\prime}$, we have

$\max_{t\in[0,T]}|\vec{u}(t)|^{2}\leq
C^{\prime}\left((kd)^{C_{1}}\log^{C_{2}}d\right)\|\vec{u}\|_{T}^{2}.$

∎

###  9.4 Main result, with constant success probability

In this section, we show that the output $\widetilde{x}$ is close to
$x^{\prime}$ with high probability using the $\epsilon$-net argument, which is
enough to prove $\|\widetilde{x}-x\|_{T}\lesssim\mathcal{N}^{2}$ from all
discussion above. Because we can prove Lemma 9.6(which is the main goal of
this section), then combining
$\|x^{\prime}-x^{*}\|_{T}\leq\|x^{\prime}-x^{(S)}\|_{T}+\|x^{(S)}-x^{*}\|_{T}\lesssim\delta\|x^{*}\|_{T}$
and Lemma 9.6, we have
$\|x^{*}-\widetilde{x}\|_{T}\lesssim\|g\|_{T}+\delta\|x^{*}\|_{T}$, which
finishes the proof of Procedure SignalRecoveryKCluster in Algorithm 8
achieving the Equation (26) with constant success probability but not
$1-2^{-\Omega(k)}$. We will boost the success probability in Section 9.5.

We first provide an $\epsilon$-net $\mathcal{P}$ for the unit vectors
$\mathcal{Q}=\\{\vec{u}\in\mathrm{span}\\{V\\}\big{|}\|\vec{u}\|_{T}^{2}=1\\}$
in the linear subspace $\mathrm{span}\\{V\\}$ where $V=\left\\{t^{j}\cdot
e^{2\pi\mathbf{i}\widetilde{f}_{i}t}\big{|}j\in\\{0,1,\cdots,d\\},i\in[l]\right\\}$
from the above discussion. Notice that the dimension of $\mathrm{span}\\{V\\}$
is at most $l(d+1)$.

######  Claim 9.3.

There exists an $\epsilon$-net $\mathcal{P}\subset\mathrm{span}\\{V\\}$ such
that

  1. 1.

$\forall\vec{u}\in
Q,\exists\vec{w}\in\mathcal{P},\|\vec{u}-\vec{w}\|_{T}\leq\epsilon.$

  2. 2.

$|\mathcal{P}|\leq\left(5\frac{l(d+1)}{\epsilon}\right)^{2l(d+1)}.$

###### Proof.

Let $\mathcal{P^{\prime}}$ be an $\frac{\epsilon}{l(d+1)}$-net in the unit
circle of $\mathbb{C}$ with size at most $(4\frac{l(d+1)}{\epsilon}+1)^{2}$,
i.e.,

$\mathcal{P^{\prime}}=\left\\{\frac{\epsilon}{2l(d+1)}j_{1}+\mathbf{i}\frac{\epsilon}{2l(d+1)}j_{2}\bigg{|}j_{1},j_{2}\in\mathbb{Z},|j_{1}|\leq\frac{2l(d+1)}{\epsilon},|j_{2}|\leq\frac{2l(d+1)}{\epsilon}\right\\}.$

Observe that the dimension of $\mathrm{span}\\{V\\}$ is at most $l(d+1)$. Then
we take an orthogonal basis $\vec{w}_{1},\cdots,\vec{w}_{l(d+1)}$ in
$\mathrm{span}\\{V\\}$ and set

$P=\\{\sum_{i=1}^{l(d+1)}\alpha_{i}\vec{w}_{i}\big{|}\forall
i\in[l(d+1)],\alpha_{i}\in\mathcal{P^{\prime}}\\}.$

Therefore $\mathcal{P}$ is an $\epsilon$-net for $Q$ and
$|\mathcal{P}|\leq\left(5\frac{l(d+1)}{\epsilon}\right)^{2l(d+1)}$. ∎

We first prove that $W$ is a good estimation for all functions in the
$\epsilon$-net $\mathcal{P}$.

######  Claim 9.4.

For any $\epsilon>0$, there exists a universal constant $C_{3}\leq 5$ such
that for a set $S$ of i.i.d. samples chosen uniformly at random over $[0,T]$
of size $|S|\geq\frac{3(kd)^{C_{3}}\log^{C_{3}}d/\epsilon}{\epsilon^{2}}$,then
with probability at least $1-k^{-k}$, for all $\vec{w}\in\mathcal{P}$, we have

$\|\vec{w}\|_{W}\in\left[(1-\epsilon)\|\vec{w}\|_{T},(1+\epsilon)\|\vec{w}\|_{T}\right].$

###### Proof.

From Claim 2.7 and Lemma 3.5, for each $\vec{w}\in\mathcal{P}$,

$\mathsf{Pr}\left[\|\vec{w}(t)\|_{W}\notin\big{[}(1-\epsilon)\|\vec{w}\|_{T},(1+\epsilon)\|\vec{w}\|_{T}\big{]}\right]\leq
2^{-\frac{|W|\epsilon^{2}}{3(kd)^{C_{1}}\log^{C_{2}+0.5}d}}\leq
2^{-kd\log^{1.5}\frac{d}{\epsilon}}.$

From the union bound,
$\|\vec{w}\|_{W}\in[(1-\epsilon)\|\vec{w}\|_{T},(1+\epsilon)\|\vec{w}\|_{T}]$
for any $\vec{w}\in\mathcal{P}$ with probability at least
$1-(\frac{d}{\epsilon})^{-kd\log^{0.5}d}\cdot|\mathcal{P}|\geq 1-d^{-d}$. ∎

Then We prove that $W$ is a good estimation for all functions in
$\mathrm{span}\\{V\\}$ using the property of $\epsilon$-nets.

######  Claim 9.5.

For any $\epsilon>0$, there exists a universal constant $C_{3}\leq 5$ such
that for a set $W$ of i.i.d. samples chosen uniformly at random over $[0,T]$
of size $|W|\geq\frac{3(kd)^{C_{3}}\log^{C_{3}}d/\epsilon}{\epsilon^{2}}$,then
with probability at least $1-d^{-d}$, for all $u\in\mathrm{span}\\{V\\}$, we
have

$\|\vec{u}\|_{W}\in\left[(1-3\epsilon)\|\vec{u}\|_{T},(1+3\epsilon)\|\vec{u}\|_{T}\right]$

###### Proof.

We assume that the above claim is true for any $\vec{w}\in\mathcal{P}$.
Without loss of generality, we consider $\vec{u}\in\mathcal{Q}$ such that
$\|\vec{u}\|_{T}=1$.

Let $\vec{w}_{0}$ be the vector in $\mathcal{P}$ that minimizes
$\|\vec{w}-\vec{u}\|_{T}$ for all $\vec{w}\in\mathcal{P}$, i.e.,
$\vec{w}_{0}=\underset{\vec{w}\in\mathcal{P}}{\arg\min}\|\vec{w}-\vec{u}\|_{T}$.
Define $\vec{u}_{1}=\vec{u}-\vec{w}_{0}$ and notice that
$\|\vec{u}_{1}\|_{T}\leq\epsilon$ because $\mathcal{P}$ is a $\epsilon$-net.
If $\|\vec{u}_{1}\|_{T}=0$, then we skip the rest of this procedure.
Otherwise, we define $\alpha_{1}=\|\vec{u}_{1}\|_{T}$ and normalize
$\widetilde{u}_{1}=\vec{u}_{1}/\alpha_{1}$.

Then we choose $\vec{w}_{1}$ to be the vector in $\mathcal{P}$ that minimizes
$\|\vec{w}-\widetilde{u}_{1}\|_{T}$ for all $\vec{w}\in\mathcal{P}$.
Similarly, we set $\vec{u}_{2}=\widetilde{u}_{1}-\vec{w}_{1}$ and
$\alpha_{2}=\|\vec{u}_{2}\|_{T}$. Next we repeat this process for
$\widetilde{u}_{2}=\vec{u}_{2}/\alpha_{2}$ and so on. The recursive definition
can be summarized in the following sense,

initial : $\displaystyle\widetilde{u}_{0}=\vec{u}\text{ and
}m=10\log_{1/\epsilon}(ld)+1,$ $\displaystyle\text{For
}i\in\\{0,1,2,\cdots,m\\}\leavevmode\nobreak\ :$
$\displaystyle\vec{w}_{i}=\underset{\vec{w}\in\mathcal{P}}{\arg\min}\|\vec{w}-\widetilde{u}_{i}\|_{T},$
$\displaystyle\vec{u}_{i+1}=\widetilde{u}_{i}-\vec{w}_{i}\text{ and
}\alpha_{i+1}=\|\vec{u}_{i+1}\|_{T},$ $\displaystyle\text{if
}\alpha_{i+1}=0,\text{\leavevmode\nobreak\ stop.}$ $\displaystyle\text{if
}\alpha_{i+1}\neq
0,\widetilde{u}_{i+1}=\vec{u}_{i+1}/\alpha_{i+1}\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ continue},$

Eventually, we have
$\vec{u}=\vec{w}_{0}+\alpha_{1}\vec{w}_{1}+\alpha_{1}\alpha_{2}\vec{w}_{2}+\cdots+\prod_{j=1}^{m}\alpha_{j}(\vec{w}_{m}+\vec{u}_{m+1})$
where each $|\alpha_{i}|\leq\epsilon$ and each $\vec{w}_{i}$ is in the
$\epsilon$-net $\mathcal{P}$. Notice that $\|\vec{u}_{m+1}\|_{T}\leq 1$ and
$\|\vec{u}_{m+1}\|_{W}\leq(ld+1)^{3}\cdot\|\vec{u}_{m+1}\|_{T}$ from Claim
2.7. We prove a lower bound for $\|\vec{u}\|_{W}$,

$\displaystyle\|\vec{u}\|_{W}$ $\displaystyle=$
$\displaystyle\|\vec{w}_{0}+\alpha_{1}\vec{w}_{1}+\alpha_{1}\alpha_{2}\vec{w}_{2}+\cdots+\prod_{j=1}^{m}\alpha_{j}(\vec{w}_{m}+\vec{u}_{m+1})\|_{W}$
$\displaystyle\geq$
$\displaystyle\|\vec{w}_{0}\|_{W}-\|\alpha_{1}\vec{w}_{1}\|_{W}-\|\alpha_{1}\alpha_{2}\vec{w}_{2}\|_{W}-\cdots-\|\prod_{j=1}^{m}\alpha_{j}\vec{w}_{m}\|_{W}-\|\prod_{j=1}^{m}\alpha_{j}\vec{u}_{m+1}\|_{W}$
$\displaystyle\geq$
$\displaystyle(1-\epsilon)-\epsilon(1+\epsilon)-\epsilon^{2}(1+\epsilon)-\cdots-\epsilon^{m}(1+\epsilon)-\epsilon^{m}\|\vec{u}_{m+1}\|_{W}$
$\displaystyle\geq$ $\displaystyle
1-\epsilon-\frac{(1+\epsilon)\epsilon}{1-\epsilon}-\epsilon^{m}\cdot(ld+1)^{3}\geq
1-3\epsilon.$

Similarly, we have $\|\vec{u}\|_{W}\leq 1+3\epsilon$. ∎

######  Lemma 9.6.

With probability at least $0.99$ over the $m$ i.i.d samples in $W$,

$\|x^{\prime}(t)-\widetilde{x}(t)\|_{T}\leq
2200\left(\|g(t)\|_{T}+\|x^{(S)}(t)-x^{\prime}(t)\|_{T}\right).$

###### Proof.

Let $g^{\prime}(t)=g(t)+x^{*}(t)-x^{\prime}(t)$ such that
$x(t)=x^{\prime}(t)+g^{\prime}(t)$. Then we choose $\epsilon=0.03$ and bound:

$\displaystyle\leavevmode\nobreak\ \|x^{\prime}(t)-\widetilde{x}(t)\|_{T}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
(1+3\epsilon)\|x^{\prime}(t)-\widetilde{x}(t)\|_{W}\quad$
$\displaystyle\text{with\leavevmode\nobreak\ prob.\leavevmode\nobreak\
}1-2^{-\Omega(d\log d)}\leavevmode\nobreak\ \text{by\leavevmode\nobreak\
Claim\leavevmode\nobreak\ \ref{cla:concentration_for_any_polynomial_signal}}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
1.09\|x^{\prime}(t)-\widetilde{x}(t)\|_{W}$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\
}\epsilon=0.03$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
1.09\|x(t)-g^{\prime}(t)-\widetilde{x}(t)\|_{W}$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\
}x^{\prime}(t)=x(t)-g^{\prime}(t)$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
1.09\|x(t)-\widetilde{x}(t)\|_{W}+1.09\|g^{\prime}(t)\|_{W}\quad$ by triangle
inequality $\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
1.09\|x(t)-x^{\prime}(t)\|_{W}+1.09\|g^{\prime}(t)\|_{W}\quad$
$\displaystyle\text{by\leavevmode\nobreak\
}\widetilde{x}=\underset{y\in\mathrm{span}\\{V\\}}{\arg\min}\|x-y\|_{W}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
2.18\|g^{\prime}(t)\|_{W}.$ $\displaystyle\text{\leavevmode\nobreak\
by\leavevmode\nobreak\ }x(t)-x^{\prime}(t)=g(t)$

From the fact that
$\operatorname*{\mathbb{E}}_{W}[\|g^{\prime}\|_{W}]=\|g^{\prime}\|_{T}$,
$\|g^{\prime}\|_{W}\leq 1000\|g^{\prime}\|_{T}$ with probability at least
.999. It indicates $\|x^{\prime}(t)-\widetilde{x}(t)\|_{T}\leq
2200\|g^{\prime}\|_{T}$ with probability at least $0.99$ from all discussion
above. ∎

###  9.5 Boosting the success probability

In order to achieve $1-2^{-\Omega(k)}$ for the main theorem, we cannot combine
Procedure SignalRecoveryKCluster with FrequencyRecoveryKCluster directly.
However, using the similar proof technique in Theorem 4.5, we are able to
boost the success probability by using Procedure SignalRecoveryKCluster+ in
Algorithm 8. It runs Procedure SignalRecoveryKCluster $R=O(k)$ times in
parallel for independent fresh samples and report $R$ different $d$-Fourier-
sparse signals $\widetilde{x}_{i}(t)$. Then, taking $m=\operatorname{poly}(k)$
new locations $\\{t_{1},t_{2},\cdots,t_{m}\\}$, and computing $\widetilde{A}$
as before and $\widetilde{b}_{j}$ by taking the median of
$\\{\widetilde{x}_{1}(t_{j}),\cdots,\widetilde{x}_{R}(t_{j})\\}$. At the end,
solving the linear regression for matrix $\widetilde{A}$ and vector
$\widetilde{b}$. Thus, we complete the proof of Lemma 9.1.

Because we can transfer a degree-$d$ polynomial to a $d$-Fourier-sparse signal
by Lemma 8.8, the output of Procedure CFTKCluster in Algorithm 8 matches the
main theorem,

######  Theorem 1.1.

Let $x(t)=x^{*}(t)+g(t)$, where $x^{*}$ is $k$-Fourier-sparse signal with
frequencies in $[-F,F]$. Given samples of $x$ over $[0,T]$ we can output
$\widetilde{x}(t)$ such that with probability at least $1-2^{-\Omega(k)}$,

$\left\lVert\widetilde{x}-x^{*}\right\rVert_{T}\lesssim\left\lVert
g\right\rVert_{T}+\delta\left\lVert x^{*}\right\rVert_{T}.$

Our algorithm uses $\operatorname{poly}(k,\log(1/\delta))\cdot\log(FT)$
samples and $\operatorname{poly}(k,\log(1/\delta))\cdot\log^{2}(FT)$ time. The
output $\widetilde{x}$ is $\operatorname{poly}(k,\log(1/\delta))$-Fourier-
sparse signal.

## References

  * [BCG+14] Petros Boufounos, Volkan Cevher, Anna C Gilbert, Yi Li, and Martin J Strauss.  What’s the frequency, Kenneth?: Sublinear Fourier sampling off the grid.  In Algorithmica(A preliminary version of this paper appeared in the Proceedings of RANDOM/APPROX 2012, LNCS 7408, pp. 61-72), pages 1–28. Springer, 2014.
  * [BM86] Y. Bresler and A. Macovski.  Exact maximum likelihood parameter estimation of superimposed exponential signals in noise.  IEEE Transactions on Acoustics, Speech, and Signal Processing, 34(5):1081–1089, Oct 1986.
  * [Bou14] Jean Bourgain.  An improved estimate in the restricted isometry problem.  In Geometric Aspects of Functional Analysis, pages 65–70. Springer, 2014.
  * [BS12] Markus Blaser and Chandan Saha.  Lecture 6: Multipoint evaluation of a polynomial.  Max-Planck-Institut für Informatik Class Notes, Computational Number Theory and Algebra, pages 1–4, 2012.
  * [CDL13] Albert Cohen, Mark A Davenport, and Dany Leviatan.  On the stability and accuracy of least squares approximations.  Foundations of computational mathematics, 13(5):819–834, 2013.
  * [CF14] Emmanuel J Candès and Carlos Fernandez-Granda.  Towards a mathematical theory of super-resolution.  Communications on Pure and Applied Mathematics, 67(6):906–956, 2014\.
  * [Che52] Herman Chernoff.  A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.  The Annals of Mathematical Statistics, 23:493–507, 1952.
  * [CNW15] Michael B Cohen, Jelani Nelson, and David P Woodruff.  Optimal approximate matrix product in terms of stable rank.  arXiv preprint arXiv:1507.02268, 2015.
  * [CRT06] Emmanuel J Candes, Justin K Romberg, and Terence Tao.  Stable signal recovery from incomplete and inaccurate measurements.  Communications on pure and applied mathematics, 59(8):1207–1223, 2006.
  * [CW87] Don Coppersmith and Shmuel Winograd.  Matrix multiplication via arithmetic progressions.  In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 1–6. ACM, 1987.
  * [CW13] Kenneth L. Clarkson and David P. Woodruff.  Low rank approximation and regression in input sparsity time.  In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 81–90, 2013.
  * [DB13] Marco F Duarte and Richard G Baraniuk.  Spectral compressive sensing.  Applied and Computational Harmonic Analysis, 35(1):111–129, 2013\.
  * [Dun10] Mark Dunster.  Legendre and Related Functions.  Handbook of Mathematical Functions, Cambridge University Press, 2010.
  * [FL12] Albert Fannjiang and Wenjing Liao.  Coherence pattern-guided compressive sensing with unresolved grids.  SIAM Journal on Imaging Sciences, 5(1):179–202, 2012.
  * [GGI+02] Anna C Gilbert, Sudipto Guha, Piotr Indyk, S Muthukrishnan, and Martin Strauss.  Near-optimal sparse Fourier representations via sampling.  In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 152–161. ACM, 2002.
  * [GMS05] Anna C Gilbert, S Muthukrishnan, and Martin Strauss.  Improved time bounds for near-optimal sparse Fourier representations.  In Optics & Photonics 2005, pages 59141A–59141A. International Society for Optics and Photonics, 2005.
  * [GZ16] Venkatesan Guruswami and David Zuckerman.  Robust Fourier and polynomial curve fitting.  In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on. IEEE, 2016.
  * [Haz01] Michiel Hazewinkel.  Gram matrix.  Encyclopedia of Mathematics, Springer, 2001.
  * [HIKP12a] Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price.  Nearly optimal sparse Fourier transform.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing. ACM, 2012.
  * [HIKP12b] Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price.  Simple and practical algorithm for sparse Fourier transform.  In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1183–1194. SIAM, 2012.
  * [HK15] Qingqing Huang and Sham M Kakade.  Super-resolution off the grid.  In Advances in Neural Information Processing Systems, pages 2647–2655, 2015.
  * [HR15] Ishay Haviv and Oded Regev.  The restricted isometry property of subsampled Fourier matrices.  arXiv preprint arXiv:1507.01768, 2015.
  * [IK14] Piotr Indyk and Michael Kapralov.  Sample-optimal Fourier sampling in any constant dimension.  In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 514–523. IEEE, 2014.
  * [IKP14] Piotr Indyk, Michael Kapralov, and Eric Price.  (Nearly) Sample-optimal sparse Fourier transform.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 480–499. SIAM, 2014.
  * [Iwe13] Mark A Iwen.  Improved approximation guarantees for sublinear-time Fourier algorithms.  Applied And Computational Harmonic Analysis, 34(1):57–82, 2013\.
  * [Kap16] Michael Kapralov.  Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time.  In Symposium on Theory of Computing Conference, STOC’16, Cambridge, MA, USA, June 19-21, 2016, 2016.
  * [Mas69] James L Massey.  Shift-register synthesis and BCH decoding.  Information Theory, IEEE Transactions on, 15(1):122–127, 1969.
  * [Moi15] Ankur Moitra.  The threshold for super-resolution via extremal functions.  In STOC, 2015.
  * [MP14] Gregory T Minton and Eric Price.  Improved concentration bounds for count-sketch.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 669–686. Society for Industrial and Applied Mathematics, 2014.
  * [NN13] Jelani Nelson and Huy L Nguyên.  OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings.  In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 117–126. IEEE, 2013.
  * [PS15] Eric Price and Zhao Song.  A robust sparse Fourier transform in the continuous setting.  In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 583–600. IEEE, 2015.
  * [RPK86] Robert Roy, Arogyaswami Paulraj, and Thomas Kailath.  Esprit–a subspace rotation approach to estimation of parameters of cisoids in noise.  Acoustics, Speech and Signal Processing, IEEE Transactions on, 34(5):1340–1342, 1986.
  * [RV08] Mark Rudelson and Roman Vershynin.  On sparse reconstruction from fourier and gaussian measurements.  Communications on Pure and Applied Mathematics, 61(8):1025–1045, 2008.
  * [Sch81] Ralph Otto Schmidt.  A signal subspace approach to multiple emitter location spectral estimation.  Ph. D. Thesis, Stanford University, 1981.
  * [Str69] Volker Strassen.  Gaussian elimination is not optimal.  Numerische Mathematik, 13(4):354–356, 1969.
  * [Tar09] Robert E. Tarjan.  Lecture 10: More chernoff bounds, sampling, and the chernoff + union bound.  Princeton Class Notes, Probability and Computing, pages 1–9, 2009\.
  * [TBR15] Gongguo Tang, Badri Narayan Bhaskar, and Benjamin Recht.  Near minimax line spectral estimation.  Information Theory, IEEE Transactions on, 61(1):499–512, 2015.
  * [TBSR13] Gongguo Tang, Badri Narayan Bhaskar, Parikshit Shah, and Benjamin Recht.  Compressed sensing off the grid.  Information Theory, IEEE Transactions on, 59(11):7465–7490, 2013\.
  * [Wil12] Virginia Vassilevska Williams.  Multiplying matrices faster than coppersmith-winograd.  In STOC, pages 887–898. ACM, 2012.
  * [Woo14] David P Woodruff.  Sketching as a tool for numerical linear algebra.  arXiv preprint arXiv:1411.4357, 2014.
  * [YX15] Zai Yang and Lihua Xie.  Achieving high resolution for super-resolution via reweighted atomic norm minimization.  In Acoustics, Speech and Signal Processing (ICASSP), 2015 IEEE International Conference on, pages 3646–3650. IEEE, 2015.

##  Appendix A Technical Proofs

###  A.1 Proof of Theorem 8.3

We prove the following Theorem

######  Theorem 8.3.

For real numbers $\xi_{1},\ldots,\xi_{k}$, let $G_{\xi_{1},\ldots,\xi_{k}}$ be
the matrix whose $(i,j)$-entry is

$\int_{-1}^{1}e^{2\pi\mathbf{i}(\xi_{i}-\xi_{j})t}dt.$

Then

$\det(G_{\xi_{1},\ldots,\xi_{k}})=2^{\tilde{O}(k^{2})}\prod_{i<j}\min(|\xi_{i}-\xi_{j}|^{2},1).$

First, we note by the Cauchy-Binet formula that the determinant in question is
equal to

$\int_{-1}^{1}\int_{-1}^{1}\ldots\int_{-1}^{1}\left|\det([e^{2\pi
i\xi_{i}t_{j}}]_{i,j})\right|^{2}dt_{1}dt_{2}\ldots dt_{k}.$ (27)

We next need to consider the integrand in the special case when
$\sum|\xi_{i}|\leq 1/8$.

######  Lemma A.1.

If $\xi_{i}\in R$ and $t_{j}\in\mathbb{R}$,
$\sum_{i}|\xi_{i}|(\max_{i}|t_{i}|)\leq 1/8$ then

$|\det([e^{2\pi
i\xi_{i}t_{j}}]_{i,j})|=\Theta\left(\frac{(2\pi)^{\binom{k}{2}}\prod_{i<j}|t_{i}-t_{j}||\xi_{i}-\xi_{j}|}{1!2!\cdots
k!}\right).$

###### Proof.

Firstly, by adding a constant to all the $t_{j}$ we can make them non-
negative. This multiplies the determinant by a root of unity, and at most
doubles $\sum_{i}|\xi_{i}|(\max_{i}|t_{i}|)$.

By continuity, it suffices to consider the $t_{i}$ to all be multiples of
$1/N$ for some large integer $N$. By multiplying all the $t_{j}$ by $N$ and
all $\xi_{i}$ by $1/N$, we may assume that all of the $t_{j}$ are non-negative
integers with $t_{1}\leq t_{2}\leq\ldots\leq t_{k}$.

Let $z_{i}=\exp(2\pi i\xi_{i})$. Then our determinant is

$\det\left(\left[z_{i}^{t_{j}}\right]_{i,j}\right),$

which is equal to the Vandermonde determinant times the Schur polynomial
$s_{\lambda}(z_{i})$ where $\lambda$ is the partition
$\lambda_{j}=t_{j}-(j-1)$.

Therefore, this determinant equals

$\prod_{i<j}(z_{i}-z_{j})s_{\lambda}(z_{1},z_{2},\ldots,z_{k}).$

The absolute value of

$\prod_{i<j}(z_{i}-z_{j})$

is approximately $\prod_{i<j}(2\pi i)(\xi_{i}-\xi_{j})$, which has absolute
value $(2\pi)^{\binom{k}{2}}\prod_{i<j}|\xi_{i}-\xi_{j}|$. We have left to
evaluate the size of the Schur polynomial.

By standard results, $s_{\lambda}$ is a polynomial in the $z_{i}$ with non-
negative coefficients, and all exponents at most $\max_{j}|t_{j}|$ in each
variable. Therefore, the monomials with non-zero coefficients will all have
real part at least $1/2$ and absolute value $1$ when evaluated at the $z_{i}$.
Therefore,

$|s_{\lambda}(z_{1},\ldots,z_{k})|=\Theta(|s_{\lambda}(1,1,\ldots,1)|).$

On the other hand, by the Weyl character formula

$s_{\lambda}(1,1,\ldots,1)=\prod_{i<j}\frac{t_{j}-t_{i}}{j-i}=\frac{\prod_{i<j}|t_{i}-t_{j}|}{1!2!\ldots
k!}.$

This completes the proof. ∎

Next we prove our Theorem when the $\xi$ have small total variation.

######  Lemma A.2.

If there exists a $\xi_{0}$ so that $\sum|\xi_{i}-\xi_{0}|<1/8$, then

$\det(G_{\xi_{1},\ldots,\xi_{k}})=\Theta\left(\frac{2^{3k(k-1)/2}\pi^{k(k-1)}\prod_{i<j}|\xi_{i}-\xi_{j}|^{2}}{(k!)^{3}\prod_{n=0}^{k-1}(2n)!}\right).$

###### Proof.

By translating the $\xi_{i}$ we can assume that $\xi_{0}=0$.

By the above we have

$\Theta(\frac{(2\pi)^{k(k-1)}\prod_{i<j}|\xi_{i}-\xi_{j}|^{2}}{(1!2!\cdots
k!)^{2}})\int_{-1}^{1}\ldots\int_{-1}^{1}\prod_{i<j}|t_{i}-t_{j}|^{2}dt_{1}\ldots
dt_{k}.$

We note that by the Cauchy-Binet formula the latter term is the determinant of
the matrix $M$ with $M_{i,j}=\int_{-1}^{1}t^{i+j}dt$. This is the Graham
matrix associated to the polynomials $t^{i}$ for $0\leq i\leq k-1$. Applying
Graham-Schmidt (without the renormalization step) to this set yields the basis
$P_{n}\alpha_{n}$ where $\alpha_{n}=\frac{2^{n}(n!)^{2}}{(2n)!}$ is the
inverse of the leading term of $P_{n}$. This polynomial has norm
$\alpha_{n}^{2}2/(2n+1)$. Therefore, the integral over the $t_{i}$ yields

$\prod_{n=0}^{k-1}\frac{2^{n+1}(n!)^{2}}{(n+1)(2n)!}.$

This completes the proof. ∎

Next we extend this result to the case that all the $\xi$ are within
$\operatorname{poly}(k)$ of each other.

######  Proposition A.3.

If there exists a $\xi_{0}$ so that $|\xi_{i}-\xi_{0}|=\operatorname{poly}(k)$
for all $i$, then

$\det(G_{\xi_{1},\ldots,\xi_{k}})=2^{\tilde{O}(k^{2})}\prod_{i<j}\min(|\xi_{i}-\xi_{j}|^{2},1).$

###### Proof.

We begin by proving the lower bound. We note that for $0<x<1$,

$\det(G_{\xi_{1},\ldots,\xi_{k}})\geq\int_{-x}^{x}\int_{-x}^{x}\ldots\int_{-1}^{1}\left|\det([e^{2\pi
i\xi_{i}t_{j}}]_{i,j})\right|^{2}dt_{1}dt_{2}\ldots
dt_{k}=x^{k}\det(G_{\xi_{1}/x,\xi_{2}/x,\ldots,\xi_{k}/k}).$

Taking $x=1/\operatorname{poly}(k)$, we may apply the above Lemma to compute
the determinant on the right hand side, yielding an appropriate lower bound.

To prove the lower bound, we note that we can divide our $\xi_{i}$ into
clusters, $\mathcal{C}_{i}$, where for any $i,j$ in the same cluster
$|\xi_{i}-\xi_{j}|<1/k$ and for $i$ and $j$ in different clusters
$|\xi_{i}-\xi_{j}|\geq 1/k^{2}$. We then note as a property of Graham matrices
that

$\det(G_{\xi_{1},\ldots,\xi_{k}})\leq\prod_{\mathcal{C}_{i}}\det(G_{\\{\xi_{j}\in\mathcal{C}_{i}\\}})=2^{\tilde{O}(k^{2})}\prod_{i<j,\textrm{
in same
cluster}}|\xi_{i}-\xi_{j}|^{2}=2^{\tilde{O}(k^{2})}\prod_{i<j}|\xi_{i}-\xi_{j}|^{2}.$

This completes the proof. ∎

Finally, we are ready to prove our Theorem.

###### Proof.

Let $I(t)$ be the indicator function of the interval $[-1,1]$.

Recall that there is a function $h(t)$ so that for any function $f$ that is a
linear combination of at most $k$ complex exponentials that
$|h(t)f(t)|_{2}=\Theta(|I(t)f(t)|_{2})$ and so that $\hat{h}$ is supported on
an interval of length $\operatorname{poly}(k)<k^{C}$ about the origin.

Note that we can divide our $\xi_{i}$ into clusters, $\mathcal{C_{i}}$, so
that for $i$ and $j$ in a cluster $|\xi_{i}-\xi_{j}|<k^{C+1}$ and for $i$ and
$j$ in different clusters $|\xi_{i}-\xi_{j}|>k^{C}$.

Let $\tilde{G}_{\xi_{1},\xi_{2},\ldots,\xi_{k}^{\prime}}$ be the matrix with
$(i,j)$-entry $\int_{\mathbb{R}}|h(t)|^{2}e^{(2\pi i)(\xi_{i}-\xi_{j})t}dt.$

We claim that for any $k^{\prime}\leq k$ that

$\det(\tilde{G}_{\xi_{1},\xi_{2},\ldots,\xi_{k}^{\prime}})=2^{O(k^{\prime})}\det(G_{\xi_{1},\xi_{2},\ldots,\xi_{k}^{\prime}}).$

This is because both are Graham determinants, one for the set of functions
$I(t)\exp((2\pi i)\xi_{j}t)$ and the other for $h(t)\exp((2\pi i)\xi_{j}t)$.
However since any linear combination of the former has $L^{2}$ norm a constant
multiple of that the same linear combination of the latter, we have that

$\tilde{G}_{\xi_{1},\xi_{2},\ldots,\xi_{k}^{\prime}}=\Theta(G_{\xi_{1},\xi_{2},\ldots,\xi_{k}^{\prime}})$

as self-adjoint matrices. This implies the appropriate bound.

Therefore, we have that

$\det(G_{\xi_{1},\ldots,\xi_{k}})=2^{O(k)}\det(\tilde{G}_{\xi_{1},\ldots,\xi_{k}}).$

However, note that by the Fourier support of $h$ that

$\int_{\mathbb{R}}|h(t)|^{2}e^{(2\pi i)(\xi_{i}-\xi_{j})t}dt=0$

if $|\xi_{i}-\xi_{j}|>k^{C}$, which happens if $i$ and $j$ are in different
clusters. Therefore $\tilde{G}$ is block diagonal and hence its determinant
equals

$\det(\tilde{G}_{\xi_{1},\ldots,\xi_{k}})=\prod_{\mathcal{C_{i}}}\det(\tilde{G}_{\\{\xi_{j}\in\mathcal{C}_{i}\\}})=2^{O(k)}\prod_{\mathcal{C_{i}}}\det(G_{\\{\xi_{j}\in\mathcal{C}_{i}\\}}).$

However the Proposition above shows that

$\prod_{\mathcal{C_{i}}}\det(G_{\\{\xi_{j}\in\mathcal{C}_{i}\\}})=2^{\tilde{O}(k^{2})}\prod_{i<j}\min(1,|\xi_{i}-\xi_{j}|^{2}).$

This completes the proof. ∎

###  A.2 Proofs of Lemma 5.3 and Lemma 5.4

We fix $z_{1},\cdots,z_{k}$ to be complex numbers on the unit circle and use
$Q(z)$ to denote the degree-$k$ polynomial
$\overset{k}{\underset{i=1}{\prod}}(z-z_{i})$.

######  Lemma 5.3.

Let $Q(z)$ be a degree $k$ polynomial, all of whose roots are complex numbers
with absolute value $1$. For any integer $n$, let
$r_{n,k}(z)=\sum_{l=0}^{k-1}r_{n,k}^{(l)}\cdot z^{l}$ denote the residual
polynomial of

$r_{n,k}(z)\equiv z^{n}\pmod{Q(z)}.$

Then, each coefficient of $r_{n,k}$ is bounded: $|r_{n,k}^{(l)}|\leq
2^{k}n^{k-1}$ for any $l$.

###### Proof.

By definition, $r_{n,k}(z_{i})=z_{i}^{n}$. From the polynomial interpolation,
we have

$r_{n,k}(z)=\sum_{i=1}^{k}\frac{\underset{j\in[k]\backslash
i}{\prod}(z-z_{j})z_{i}^{n}}{\underset{j\in[k]\backslash
i}{\prod}(z_{i}-z_{j})}.$

Let $\operatorname{Sym}_{S,i}$ be the symmetry polynomial of
$z_{1},\cdots,z_{k}$ with degree $i$ among subset $S\subseteq[k]$, i.e.,
$\operatorname{Sym}_{S,i}=\underset{S^{\prime}\subseteq\binom{S}{i}}{\sum}\underset{j\in
S^{\prime}}{\prod}z_{j}$. Then

$r_{n,k}^{(l)}=(-1)^{k-1-l}\sum_{i=1}^{k}\frac{\operatorname{Sym}_{[k]\setminus
i,k-1-l}\cdot z_{i}^{n}}{\underset{j\in[k]\backslash i}{\prod}(z_{i}-z_{j})}.$

We omit $(-1)^{k-1-l}$ in the rest of proof and use induction on $n,k,$ and
$l$ to prove $|r_{n,k}^{(l)}|\leq\binom{k-1}{l}\binom{n}{k-1}$.

Base Case of $n$: For any $n<k$, from the definition, $r(z)=z^{n}$ and
$|r_{n,k}^{(l)}|\leq 1$.

Suppose it is true for any $n<n_{0}$. We consider $r_{n_{0},k}^{l}$ from now
on. When $k=1$, $r_{n,0}=z_{1}^{n}$ is bounded by $1$ because $z_{1}$ is on
the unit circle of $\mathbb{C}$.

Given $n_{0}$, suppose the induction hypothesis is true for any $k<k_{0}$ and
any $l<k$. For $k=k_{0}$, we first prove that
$|r_{n_{0},k_{0}}^{(k_{0}-1)}|\leq\binom{n_{0}}{k_{0}-1}$ then prove that
$|r_{n_{0},k_{0}}^{(l)}|\leq\binom{k_{0}-1}{l}\binom{n_{0}}{k_{0}-1}$ for
$l=k_{0}-2,\cdots,0$.

$\displaystyle r_{n_{0},k_{0}}^{(k_{0}-1)}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{k_{0}}\frac{z_{i}^{n_{0}}}{\underset{j\in[k_{0}]\backslash
i}{\prod}(z_{i}-z_{j})}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{k_{0}-1}\frac{z_{i}^{n_{0}}}{\underset{j\in[k_{0}]\backslash
i}{\prod}(z_{i}-z_{j})}+\frac{z_{k_{0}}^{n_{0}}}{\underset{j\in[k_{0}]\backslash{k_{0}}}{\prod}(z_{k_{0}}-z_{j})}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{k_{0}-1}\frac{z_{i}^{n_{0}}-z_{i}^{n_{0}-1}z_{k_{0}}+z_{i}^{n_{0}-1}z_{k_{0}}}{\underset{j\in[k_{0}]\backslash
i}{\prod}(z_{i}-z_{j})}+\frac{z_{k_{0}}^{n_{0}}}{\underset{j\in
k_{0}\backslash{k_{0}}}{\prod}(z_{k_{0}}-z_{j})}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{k_{0}-1}\left(\frac{z_{i}^{n_{0}-1}}{\underset{j\in[k_{0}-1]\backslash
i}{\prod}(z_{i}-z_{j})}+\frac{z_{i}^{n_{0}-1}z_{k_{0}}}{\underset{j\in
k_{0}\backslash
i}{\prod}(z_{i}-z_{j})}\right)+\frac{z_{k_{0}}^{n_{0}}}{\underset{j\in
k_{0}\backslash{k_{0}}}{\prod}(z_{k_{0}}-z_{j})}$ $\displaystyle=$
$\displaystyle\left(\sum_{i=1}^{k_{0}-1}\frac{z_{i}^{n_{0}-1}}{\underset{j\in[k_{0}-1]\backslash
i}{\prod}(z_{i}-z_{j})}\right)+\left(z_{k_{0}}\sum_{i=1}^{k_{0}}\frac{z_{i}^{n_{0}-1}}{\underset{j\in
k_{0}\backslash i}{\prod}(z_{i}-z_{j})}\right)$ $\displaystyle=$
$\displaystyle r_{n_{0}-1,k_{0}-1}^{(k_{0}-2)}+z_{k_{0}}\cdot
r_{n_{0}-1,k_{0}}^{(k_{0}-1)}$

Hence
$|r_{n_{0},k_{0}}^{(k_{0}-1)}|\leq|r_{n_{0}-1,[k_{0}-1]}^{(k_{0}-2)}|+|r_{n_{0}-1,k_{0}}^{(k_{0}-1)}|\leq\binom{n_{0}-2}{k_{0}-2}+\binom{n_{0}-2}{k_{0}-1}=\binom{n_{0}-1}{k_{0}-1}$.
For $l<k_{0}-1$, we have

$\displaystyle r_{n_{0},k_{0}}^{(l)}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{k_{0}}\frac{\operatorname{Sym}_{[k_{0}]\setminus
i,k_{0}-1-l}\cdot z_{i}^{n_{0}}}{\underset{j\in[k_{0}]\backslash
i}{\prod}(z_{i}-z_{j})}\quad\text{let\leavevmode\nobreak\
}l^{\prime}=k_{0}-1-l$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{k_{0}-1}\frac{\left(\operatorname{Sym}_{[k_{0}-1]\setminus
i,l^{\prime}}+\operatorname{Sym}_{[k_{0}-1]\setminus i,l^{\prime}-1}\cdot
z_{k_{0}}\right)z_{i}^{n_{0}}}{\underset{j\in[k_{0}]\backslash
i}{\prod}(z_{i}-z_{j})}+\frac{\operatorname{Sym}_{[k_{0}-1],l^{\prime}}\cdot
z_{k_{0}}^{n_{0}}}{\underset{j<k_{0}}{\prod}(z_{k_{0}}-z_{j})}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{k_{0}-1}\frac{\operatorname{Sym}_{[k_{0}-1]\setminus
i,l^{\prime}}\cdot(z_{i}-z_{k_{0}})z_{i}^{n_{0}-1}+\operatorname{Sym}_{[k_{0}-1]\setminus
i,l^{\prime}}\cdot
z_{k_{0}}z_{i}^{n_{0}-1}+\operatorname{Sym}_{[k_{0}-1]\setminus
i,l^{\prime}-1}\cdot z_{k_{0}}z_{i}^{n_{0}}}{\underset{j\in[k_{0}]\backslash
i}{\prod}(z_{i}-z_{j})}$
$\displaystyle+\frac{\operatorname{Sym}_{[k_{0}-1],l^{\prime}}\cdot
z_{k_{0}}^{n_{0}}}{\underset{j<k_{0}}{\prod}(z_{k_{0}}-z_{j})}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{k_{0}-1}\frac{\operatorname{Sym}_{[k_{0}-1]\setminus
i,l^{\prime}}\cdot(z_{i}-z_{k_{0}})z_{i}^{n_{0}-1}+\operatorname{Sym}_{[k_{0}-1],l^{\prime}}\cdot
z_{k_{0}}z_{i}^{n_{0}-1}}{\underset{j\in[k_{0}]\backslash
i}{\prod}(z_{i}-z_{j})}+\frac{\operatorname{Sym}_{[k_{0}-1],l^{\prime}}\cdot
z_{k_{0}}^{n_{0}}}{\underset{j<k_{0}}{\prod}(z_{k_{0}}-z_{j})}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{k_{0}-1}\frac{\operatorname{Sym}_{[k_{0}-1]\setminus
i,l^{\prime}}z_{i}^{n_{0}-1}}{\underset{j\in[k_{0}-1]\backslash
i}{\prod}(z_{i}-z_{j})}+\sum_{i=1}^{k_{0}-1}\frac{\operatorname{Sym}_{[k_{0}-1],l^{\prime}}\cdot
z_{k_{0}}z_{i}^{n_{0}-1}}{\underset{j\in[k_{0}]\backslash
i}{\prod}(z_{i}-z_{j})}+\frac{\operatorname{Sym}_{[k_{0}-1],l^{\prime}}\cdot
z_{k_{0}}^{n_{0}}}{\underset{j<k_{0}}{\prod}(z_{k_{0}}-z_{j})}$
$\displaystyle=$ $\displaystyle
r_{n_{0}-1,k_{0}-1}^{(l-1)}+\operatorname{Sym}_{[k_{0}-1],k_{0}-1-l}\cdot
z_{k_{0}}\cdot r_{n_{0}-1,k_{0}}^{(k_{0}-1)}$

By induction hypothesis,
$|r_{n_{0},k_{0}}^{(l)}|\leq\binom{k_{0}-2}{l-1}\binom{n_{0}-1}{k_{0}-2}+\binom{k_{0}-1}{l}\binom{n_{0}-1}{k_{0}-1}\leq\binom{k_{0}-1}{l}\binom{n_{0}}{k_{0}-1}.$
∎

Now we finish the proof of Lemma 5.4.

######  Lemma 5.4.

For any $k\in\mathbb{Z}$ and any $z_{1},\cdots,z_{k}$ on the unit circle of
$\mathbb{C}$, there always exists a degree $m=O(k^{2}\log k)$ polynomial
$P(z)=\overset{m}{\underset{j=0}{\sum}}c_{j}z^{j}$ with the following
properties:

$\displaystyle\mathrm{Property\leavevmode\nobreak\ \@slowromancap i@}$
$\displaystyle P(z_{i})=0,\forall i\in\\{1,\cdots,k\\},$
$\displaystyle\mathrm{Property\leavevmode\nobreak\ \@slowromancap ii@}$
$\displaystyle c_{0}=1,$ $\displaystyle\mathrm{Property\leavevmode\nobreak\
\@slowromancap iii@}$ $\displaystyle|c_{j}|\leq 11,\forall
j\in\\{1,\cdots,m\\}.$

Let $m=10k^{2}\log k$ and $\mathcal{P}$ denote a set of polynomials that has
degree at most $m$, and all the coefficients are integers chosen from
$\\{-5,\cdots,-1,0,1,\cdots,5\\}$, i.e.,

$\mathcal{P}:=\left\\{P(z)=\sum_{i=0}^{m}\alpha_{i}z^{i}\leavevmode\nobreak\
|\leavevmode\nobreak\ \forall i\in\\{0,1,\cdots,m\\},|\alpha_{i}|\leq
2\right\\}.$

######  Claim A.4.

There exists $P^{*}(z)=\overset{m}{\underset{i=0}{\sum}}\alpha_{i}z^{i}$ with
coefficient $|\alpha_{i}|\leq 10$ for any $i\in\\{0,1,\cdots,m\\}$, such that
every coefficient of $P^{*}(z)\mod Q(z)$ is bounded by $2^{-m}$.

###### Proof.

For $P(z)=\overset{m}{\underset{i=0}{\sum}}\alpha_{i}z^{i}\in\mathcal{P}$,
$P(z)\mod Q(z)\equiv\overset{m}{\underset{i=0}{\sum}}\alpha_{i}r_{n,k}(z)$
from the definition $r_{n,k}(z)$. Hence

$P(z)\mod
Q(z)=\sum_{i=0}^{m}\alpha_{i}\sum_{l=0}^{k-1}r_{i,k}^{(l)}z^{l}=\sum_{l=0}^{k-1}z^{l}\sum_{i=0}^{m}\alpha_{i}r_{i,k}^{(l)}.$

Each coefficient in $P(z)\mod Q(z)$ is bounded by
$|\overset{m}{\underset{i=0}{\sum}}\alpha_{i}r_{i,k}^{(l)}|\leq
5\overset{m}{\underset{i=0}{\sum}}2^{k}i^{k-1}\leq 2^{k}m^{k}.$

At the same time, $|\mathcal{P}|=11^{m}$. From the pigeonhole principle and
$\left(\frac{2^{k}m^{k}}{(2^{-m})^{2}}\right)^{k}<11^{m}$, there exists
$P_{1},P_{2}\in\mathcal{P}$ such that for $P^{*}(z)=P_{1}(z)-P_{2}(z)$,
$P^{*}(z)\mod Q(z)=\overset{k-1}{\underset{i=0}{\sum}}\gamma_{i}z^{i}$ where
each coefficient $|\gamma_{i}|\leq 2^{-m}$. ∎

Let $r(z)=\overset{k-1}{\underset{i=0}{\sum}}\gamma_{i}z^{i}=P^{*}(z)\mod
Q(z)$ for convenience. If $P^{*}(0)$ (the constant term of $P^{*}$) is
nonzero, then $|P^{*}(0)-r(0)|\geq 0.99$ from the above lemma. Therefore the
polynomial $\frac{P^{*}(z)-r(z)}{P^{*}(0)-r(0)}$ satisfies the three
properties in Lemma 5.4.

Otherwise, we assume $z^{l}$ is the first term in $P^{*}(z)$ with a non-zero
coefficient. Let

$r_{-l,k}(z)=z^{-l}\mod Q(z)=\sum_{i=1}^{k}\frac{\underset{j\in[k]\backslash
i}{\prod}(z-z_{j})z_{i}^{-l}}{\underset{j\in[k]\backslash
i}{\prod}(z_{i}-z_{j})}.$

For convenience, we use $z_{S}=\underset{i\in S}{\prod}z_{i}$ for any subset
$S\subseteq[k]$. Notice that $z_{i}^{-l}=\frac{z^{l}_{[k]\setminus
i}}{z_{[k]}^{l}}$. Hence $r_{-l,k}(z)=r^{\prime}_{l,k}(z)/z_{[k]}^{l}$ where
$r^{\prime}$ is the polynomial for $k$ units roots $z_{[k]\setminus
1},\cdots,z_{[k]\setminus k}$. So each coefficients of $r$ is still bounded by
$2^{k}l^{k}$, which is less than $2^{-m/2}$.

Eventually we choose $P^{*}(z)/z^{l}-r(z)\cdot r_{-l,k}(z)$ and renormalize it
to satisfy the three properties in Lemma 5.4.

###  A.3 Proof of Lemma 4.3

######  Lemma 4.3.

For any degree $d$ polynomial $P(t):\mathbb{R}\rightarrow\mathbb{C}$ with
derivative $P^{\prime}(t)$, we have,

$\int_{-1}^{1}(1-t^{2})|P^{\prime}(t)|^{2}\mathrm{d}t\leq
2d^{2}\int_{-1}^{1}|P(t)|^{2}\mathrm{d}t.$ (28)

Given a degree $d$ polynomial $P(x)$, we rewrite $P(x)$ as a linear
combination of the Legendre polynomials:

$P(x)=\sum_{i=0}^{d}\alpha_{i}L_{i}(x).$

We use $F_{i}(x)=(1-x^{2})L^{\prime}_{i}(x)$ for convenience. From the
definition of the Legendre polynomials in the Equation (3),
$F^{\prime}_{i}(x)=-i(i+1)\cdot L_{i}(x)$ and
$F^{\prime\prime}_{i}(x)=-i(i+1)\cdot L^{\prime}_{i}(x)$.

Hence we have

$\displaystyle\int_{1}^{-1}(1-x^{2})|P^{\prime}(x)|^{2}\mathrm{d}x=\quad$
$\displaystyle\int_{1}^{-1}(1-x^{2})P^{\prime}(x)\cdot\overline{P^{\prime}}(x)\mathrm{d}x$
$\displaystyle=\quad$
$\displaystyle\int_{1}^{-1}\left(\sum_{i\in[d]}\alpha_{i}F_{i}(x)\right)\cdot\left(\sum_{i\in[d]}\overline{\alpha_{i}}\frac{-F^{\prime\prime}_{i}(x)}{i(i+1)}\right)\mathrm{d}x$
$\displaystyle=\quad$
$\displaystyle\left(\sum_{i\in[d]}\alpha_{i}F_{i}(x)\right)\cdot\left(\sum_{i\in[d]}\overline{\alpha_{i}}\frac{-F^{\prime}_{i}(x)}{i(i+1)}\right)\bigg{|}_{-1}^{1}$
$\displaystyle+\quad$
$\displaystyle\int_{1}^{-1}\left(\sum_{i\in[d]}\alpha_{i}F^{\prime}_{i}(x)\right)\cdot\left(\sum_{i\in[d]}\overline{\alpha_{i}}\frac{F^{\prime}_{i}(x)}{i(i+1)}\right)\mathrm{d}x$
$\displaystyle=\quad$
$\displaystyle\int_{1}^{-1}\left(\sum_{i\in[d]}\alpha_{i}\cdot i(i+1)\cdot
L_{i}(x)\right)\cdot\left(\sum_{i\in[d]}\overline{\alpha_{i}}\frac{i(i+1)\cdot
L_{i}(x)}{i(i+1)}\right)\mathrm{d}x$ $\displaystyle=\quad$
$\displaystyle\sum_{i\in[d]}|\alpha_{i}|^{2}i(i+1)\|L_{i}\|_{T}^{2}$
$\displaystyle\leq\quad$ $\displaystyle d(d+1)\|P\|^{2}_{T}$

###  A.4 Proof of Lemma 6.2

######  Lemma 6.2.

$\widehat{P_{\sigma,a,b}x}(\sigma(f-b))=\frac{1}{\sigma}e^{-2\pi\mathbf{i}\sigma
af}\widehat{x}(f)$ and
$\widehat{P_{\sigma,a,b}x}(f)=\frac{1}{\sigma}e^{-2\pi\mathbf{i}\sigma
a(f/\sigma+b)}\widehat{x}(f/\sigma+b)$

###### Proof.

Let’s compute the Fourier Transform of $(P_{\sigma,a,b}x)(t)$,

$\displaystyle\widehat{P_{\sigma,a,b}x}(f)$ $\displaystyle=$
$\displaystyle\int_{-\infty}^{+\infty}(P_{\sigma,a,b}(x))(t)e^{-2\pi\mathbf{i}ft}\mathrm{d}t$
$\displaystyle=$
$\displaystyle\int_{-\infty}^{+\infty}x(\sigma(t-a))e^{-2\pi\mathbf{i}\sigma
bt}e^{-2\pi\mathbf{i}ft}\mathrm{d}t$ $\displaystyle=$ $\displaystyle
e^{-2\pi\mathbf{i}(\sigma
ab+fa)}\int_{-\infty}^{+\infty}x(\sigma(t-a))e^{-2\pi\mathbf{i}\sigma
b(t-a)}e^{-2\pi\mathbf{i}f(t-a)}\mathrm{d}t$ by shifting $t$ by $a$
$\displaystyle=$ $\displaystyle e^{-2\pi\mathbf{i}(\sigma
ab+fa)}\int_{-\infty}^{+\infty}x(\sigma t)e^{-2\pi\mathbf{i}\sigma
bt}e^{-2\pi\mathbf{i}ft}\mathrm{d}t$ by replacing $t-a$ by $t$
$\displaystyle=$ $\displaystyle\frac{1}{\sigma}e^{-2\pi\mathbf{i}(\sigma
ab+fa)}\int_{-\infty}^{+\infty}x(\sigma t)e^{-2\pi\mathbf{i}b\sigma
t}e^{-2\pi\mathbf{i}f\sigma t/\sigma}\mathrm{d}\sigma t$ $\displaystyle=$
$\displaystyle\frac{1}{\sigma}e^{-2\pi\mathbf{i}(\sigma
ab+fa)}\int_{-\infty}^{+\infty}x(t)e^{-2\pi\mathbf{i}(b+f/\sigma)t}\mathrm{d}t$
by replacing $t\sigma$ by $t$ $\displaystyle=$
$\displaystyle\frac{1}{\sigma}e^{-2\pi\mathbf{i}a\sigma(f/\sigma+b)}\widehat{x}(f/\sigma+b)$
by definition of FT

The first result follows immediately by replacing $f/\sigma+b$ by
$f^{\prime}$, which gives

$\widehat{P_{\sigma,a,b}x}(\sigma(f^{\prime}-b))=\frac{1}{\sigma}e^{-2\pi\mathbf{i}a\sigma
f^{\prime}}\widehat{x}(f^{\prime}).$

Thus, we complete the proof of this Lemma. ∎

###  A.5 Proof of Lemma 3.5

######  Lemma 3.5.

Given any function $x(t):\mathbb{R}\rightarrow\mathbb{C}$ with
$\underset{t\in[0,T]}{\max}|x(t)|^{2}\leq d\|x(t)\|_{T}^{2}$. Let $S$ denote a
set of points from $0$ to $T$. If each point of $S$ is chosen uniformly at
random from $[0,T]$, we have

$\displaystyle\mathsf{Pr}\left[\left|\frac{1}{|S|}\sum_{i\in
S}|x(t_{i})|^{2}-\|x(t)\|_{T}^{2}]\right|\geq\epsilon\|x(t)\|_{T}^{2}\right]$
$\displaystyle\leq$ $\displaystyle e^{-\Omega(\epsilon^{2}|S|/d)}$

###### Proof.

Let $M$ denote $\underset{t\in[0,T]}{\max}|x(t)|^{2}$. Replacing $X_{i}$ by
$\frac{|x(t_{i})|^{2}}{M}$ and $n$ by $|S|$ in Lemma B.2, we obtain that

$\displaystyle\mathsf{Pr}[|X-\mu|>\epsilon\mu]\leq
2\exp(-\frac{\epsilon^{2}}{3}\mu)$ $\displaystyle\implies$
$\displaystyle\mathsf{Pr}\left[\left|\sum_{i\in
S}\frac{|x(t_{i})|^{2}}{M}-|S|\frac{\|x(t)\|_{T}^{2}}{M}\right|>\epsilon|S|\frac{\|x(t)\|_{T}^{2}}{M}\right]\leq
2\exp(-\frac{\epsilon^{2}}{3}\mu)$ $\displaystyle\implies$
$\displaystyle\mathsf{Pr}\left[\left|\frac{1}{|S|}\sum_{i\in
S}|x(t_{i})|^{2}-\|x(t)\|_{T}^{2}\right|\geq\epsilon\|x(t)\|_{T}^{2}\right]\leq
2\exp(-\frac{\epsilon^{2}}{3}\mu)$ $\displaystyle\implies$
$\displaystyle\mathsf{Pr}\left[\left|\frac{1}{|S|}\sum_{i\in
S}|x(t_{i})|^{2}-\|x(t)\|_{T}^{2}\right|\geq\epsilon\|x(t)\|_{T}^{2}\right]\leq
2\exp(-\frac{\epsilon^{2}}{3}|S|\frac{\|x(t)\|_{T}^{2}}{M})$

which is less than $2\exp(-\frac{\epsilon^{2}}{3}|S|/d)$, thus completes the
proof. ∎

###  A.6 Proof of Lemma 3.10

######  Lemma 3.10.

For any polynomial $P(t)$ of degree at most $d$ from $R$ to $\mathbb{C}$, for
any interval $[S,T]$,

$\max_{t\in[S,T]}|P(t)|^{2}\leq(d+1)^{2}\cdot\frac{1}{T-S}\int_{S}^{T}|P(t)|^{2}\mathrm{d}x.$

###### Proof.

Let $t^{*}=\underset{t\in[S,T]}{\arg\max}|P(t)|^{2}$. If $t^{*}\in(S,T)$, then
it is enough to prove that

$|P(t^{*})|^{2}\leq(d+1)^{2}\frac{1}{t^{*}-S}\int_{S}^{t^{*}}|P(x)|^{2}\mathrm{d}x\text{
and
}|P(t^{*})|^{2}\leq(d+1)^{2}\frac{1}{T-t^{*}}\int_{t^{*}}^{T}|P(x)|^{2}\mathrm{d}x$

on the two intervals $[S,t^{*}]$ and $[t^{*},T]$ separately.

Without loss of generality, we will prove the inequality for $S=-1$ and
$t^{*}=T=1$. We find the minimum $\|P(x)\|^{2}_{T}$ assuming $|P(1)|^{2}=1$.
Because the first $(d+1)$ Legendre polynomials provide a basis of polynomials
of degree at most $d$ and their evaluation $L_{n}(1)=1$ for any $n$, we
consider:

$\displaystyle\underset{\alpha_{0},\alpha_{1},\cdots,\alpha_{d}\in\mathbb{C}}{\min}$
$\displaystyle\int_{-1}^{1}|P(x)|^{2}\mathrm{d}x$ s.t. $\displaystyle
P(x)=\sum_{i=0}^{d}\alpha_{i}L_{i}(x)$
$\displaystyle|P(1)|=|\sum_{i=0}^{d}\alpha_{i}|=1.$

We simplify the integration of $P(x)^{2}$ over $[-1,1]$ by the orthogonality
of Legendre polynomials:

$\displaystyle\int_{-1}^{1}|P(x)|^{2}\mathrm{d}x$ $\displaystyle=$
$\displaystyle\int_{-1}^{1}\left(\sum_{i=0}^{d}\alpha_{i}L_{i}(x)\right)\cdot\left(\sum_{j=0}^{d}\overline{\alpha_{j}}\overline{L_{j}}(x)\right)\mathrm{d}x$
$\displaystyle=$
$\displaystyle\int_{-1}^{1}\sum_{i=0}^{d}|\alpha_{i}|^{2}L_{i}(x)^{2}+\sum_{i\neq
j}\alpha_{i}\overline{\alpha_{j}}L_{i}(x)\overline{L_{j}}(x)\mathrm{d}x$
$\displaystyle=$
$\displaystyle\sum_{i=0}^{d}|\alpha_{i}|^{2}\frac{2}{2i+1}\text{\leavevmode\nobreak\
by\leavevmode\nobreak\ Fact\leavevmode\nobreak\
\ref{fac:legendre_inner_product}}$

Using
$\int_{-1}^{1}|P(x)|^{2}\mathrm{d}x=\overset{d}{\underset{i=0}{\sum}}|\alpha_{i}|^{2}\frac{2}{2i+1}$,
we simplify the optimization problem to

$\displaystyle\underset{\alpha_{0},\alpha_{1},\cdots,\alpha_{d}\in\operatorname*{\mathbb{C}}}{\min}$
$\displaystyle\sum_{i=0}^{d}|\alpha_{i}|^{2}\frac{2}{2i+1}$ s.t.
$\displaystyle\left|\sum_{i=0}^{d}\alpha_{i}\right|=1$

From the Cauchy-Schwarz inequality, we have

$\left|\sum_{i=0}^{d}\alpha_{i}\right|^{2}\leq\left(\sum_{i=0}^{d}|\alpha_{i}|^{2}\frac{2}{2i+1}\right)\left(\sum_{i=0}^{d}\frac{2i+1}{2}\right).$

Therefore
$\overset{d}{\underset{i=0}{\sum}}|\alpha_{i}|^{2}\frac{2}{2i+1}\geq\frac{2}{(d+1)^{2}}$
and
$|P(1)|^{2}\leq(d+1)^{2}\cdot\frac{1}{2}\int_{-1}^{1}|P(x)|^{2}\mathrm{d}x$. ∎

##  Appendix B Known Facts

This section provides a list of well-known facts existing in literature.

###  B.1 Inequalities

We state the Hölder’s inequality for complex numbers. We will use the
corresponding version $p=q=2$ of Cauchy-Schwarz inequality for complex
numbers.

######  Lemma B.1 (Hölder’s inequality).

If $S$ is a measurable subset of $\mathbb{R}^{n}$ with the Lebesgue measure,
and $f$ and $g$ are measurable complex-valued functions on $S$, then

$\int_{S}|f(x)g(x)|\mathrm{d}x\leq(\int_{S}|f(x)|^{p}\mathrm{d}x)^{\frac{1}{p}}(\int_{S}|g(x)|^{q}\mathrm{d}x)^{\frac{1}{q}}$

######  Lemma B.2 (Chernoff Bound [Tar09],[Che52] ).

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 $\epsilon>0$,

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

###  B.2 Linear regression

Given a linear subspace $\mathrm{span}\\{\vec{v}_{1},\cdots,\vec{v}_{d}\\}$
and $n$ points, we always use $\ell_{2}$-regression to find a vector as the
linear combination of $\vec{v}_{1},\cdots,\vec{v}_{d}$ that minimizes the
distance of this vector to those $n$ points.

######  Fact B.3.

Given an $n\times d$ matrix $A$ and an $n\times 1$ column vector $b$ , it
takes $O(nd^{\omega-1})$ time to output an $x^{\prime}$ such that

$x^{\prime}=\underset{x}{\arg\min}\|Ax-b\|_{2}.$

where $\omega$ is the exponent of matrix multiplication[Wil12].

Notice that weighted linear regression can be solved by linear regression
solver as a black-box.

Algorithm 1 Linear regression algorithms

1:procedure LinearRegression($A,b,$) — Fact B.3

2: $x^{\prime}\leftarrow\underset{x}{\arg\min}\|Ax-b\|_{2}$.

3: return $x^{\prime}$

4:end procedure

5:procedure LinearRegressionW($A,b,w$) — Fact B.3

6:
$x^{\prime}\leftarrow\underset{x}{\arg\min}\overset{d}{\underset{i=1}{\sum}}w_{i}|(Ax)_{i}-b_{i}|^{2}$.

7: return $x^{\prime}$

8:end procedure

Algorithm 2 Multipoint evaluation of a polynomial

1:procedure MultipointEvaluation($P,\\{t_{1},t_{2},\cdots,t_{d}\\}$) — Fact
B.4

2: return $P(t_{1}),P(t_{2}),\cdots,P(t_{d})$

3:end procedure

###  B.3 Multipoint evaluation of a polynomial

Given a degree-$d$ polynomial, and $n$ locations. The naive algorithm of
computing the evaluations at those $n$ locations takes $O(nd)$. However, the
running time can be improved to $O(n\operatorname{poly}(\log d))$ by using
this well-known result,

######  Fact B.4 ([BS12]).

Given a degree-$d$ polynomial $P(t)$, and a set of $d$ locations
$\\{t_{1},t_{2},\cdots,t_{d}\\}$. There exists an algorithm that takes
$O(d\log^{c}d)$ time to output the evaluations
$\\{P(t_{1}),P(t_{2}),\cdots,P(t_{d})\\}$, for some constant $c$.

##  Appendix C Analysis of Hash Functions and Filter Functions

###  C.1 Analysis of filter function $(H(t),\widehat{H}(f))$

We construct the Filter function $(H(t),\widehat{H}(f))$ in this section.

We fix the interval to be
$\operatorname{supp}(\operatorname{rect}_{1})=[-1/2,1/2]$ instead of $[0,T]$
for convenience. We first define the filter function $H_{1}(t)$ which
preserves the energy of a $k$-Fourier-sparse signal $x^{*}$ on $[-1/2,1/2]$ to
the signal $H_{1}\cdot x^{*}$ on $[-\infty,+\infty]$.

######  Definition C.1.

Let $s_{1}=\Theta(k^{4}\log^{4}k)$, $\ell=\Omega(k\log k/\delta)$ be a even
number, and $s_{0}=C_{0}s_{1}\sqrt{\ell}$ for some constant $C_{0}$ that will
normalize $H_{1}(0)=1$. Recall that $\operatorname{rect}_{s}(t)=1$ iff
$|t|\leq s/2$ and
$\widehat{\operatorname{rect}_{s}(f)}=\operatorname{sinc}(fs)=\frac{\sin(\pi
fs)}{\pi fs}$.

We define the filter function $H_{1}(t)$ and its Fourier transform
$\widehat{H}_{1}(f)$ as follows:

$\displaystyle\widehat{H}_{1}(f)$ $\displaystyle=$ $\displaystyle
s_{0}\cdot\left(\operatorname{rect}_{s_{1}}(f)\right)^{*\ell}\cdot\operatorname{sinc}\left(fs_{2}\right),$
$\displaystyle=$ $\displaystyle
s_{0}\cdot\bigl{(}{\vbox{\hbox{\includegraphics[width=86.72267pt]{rect_s1}}}}\bigr{)}^{*\ell}\cdot{\vbox{\hbox{\includegraphics[width=173.44534pt]{sinc_s2}}}}$
$\displaystyle H_{1}(t)$ $\displaystyle=$ $\displaystyle
s_{0}\cdot\left(\operatorname{sinc}(s_{1}t)\right)^{\cdot\ell}*\operatorname{rect}_{s_{2}}(t)$
$\displaystyle=$ $\displaystyle
s_{0}\cdot\bigl{(}{\vbox{\hbox{\includegraphics[width=173.44534pt]{sinc_s1}}}}\bigr{)}^{\cdot\ell}*{\vbox{\hbox{\includegraphics[width=86.72267pt]{rect_s2}}}}$

where $s_{0}$ is a fixed parameter s.t. $H_{1}(0)=1$.

We provide some basic properties about our filter function. Notice that
$\operatorname{sinc}(t)=\frac{\sin(\pi t)}{\pi t}$ ( $\operatorname{sinc}(0)$
is defined to be $1$ ) has the following properties (shown in Figure 4):

  1. 1.

$\forall t\in\mathbb{R},1-\frac{(\pi t)^{2}}{3!}\leq\operatorname{sinc}(t)\leq
1$.

  2. 2.

$\forall|t|\leq 1.2/\pi,\operatorname{sinc}(t)\leq 1-\frac{t^{2}}{8}$.

  3. 3.

$\forall|t|>1.2/\pi,|\operatorname{sinc}(t)|\leq\frac{1}{\pi|t|}$.

Figure 4: The Property of $\operatorname{sinc}(t)$.

######  Claim C.2.

$\int_{-\frac{1.2}{\pi s_{1}}}^{\frac{1.2}{\pi
s_{1}}}(\operatorname{sinc}(s_{1}t))^{\ell}\mathrm{d}t\eqsim\frac{1}{s_{1}\sqrt{\ell}}$.

###### Proof.

We use the above properties for the sinc function to prove the upper bound:

$\displaystyle\int_{-\frac{1.2}{\pi s_{1}}}^{+\frac{1.2}{\pi
s_{1}}}(\operatorname{sinc}(s_{1}t))^{\ell}\mathrm{d}t$
$\displaystyle=\frac{1}{s_{1}}\int_{-1.2/\pi}^{+1.2/\pi}(\operatorname{sinc}(t))^{\ell}\mathrm{d}t$
$\displaystyle=\frac{2}{s_{1}}\left(\int_{0}^{\sqrt{8/\ell}}(\operatorname{sinc}{t})^{\ell}\mathrm{d}t+\int_{\sqrt{8/\ell}}^{1.2/\pi}(\operatorname{sinc}(t))^{\ell}\mathrm{d}t\right)$
$\displaystyle\leq\frac{2}{s_{1}}\left(\sqrt{8/\ell}+\sum_{i=1}^{\frac{1.2/\pi}{\sqrt{8/\ell}}-1}\int_{i\sqrt{8/\ell}}^{(i+1)\sqrt{8/\ell}}(1-x^{2}/8)^{\ell}\mathrm{d}x\right)$
$\displaystyle\leq\frac{2}{s_{1}}\left(\sqrt{8/\ell}+\sum_{i=1}^{\frac{1.2/\pi}{\sqrt{8/\ell}}-1}\sqrt{8/\ell}\cdot
2^{-i^{2}}\right)$ $\displaystyle\lesssim\frac{1}{s_{1}\sqrt{\ell}}.$

We prove the lower bound:

$\displaystyle\int_{-\frac{1.2}{\pi s_{1}}}^{\frac{1.2}{\pi
s_{1}}}(\operatorname{sinc}(s_{1}t))^{\ell}\mathrm{d}t$
$\displaystyle=\frac{2}{s_{1}}\left(\int_{0}^{\sqrt{8/\ell}}(\operatorname{sinc}{t})^{\ell}\mathrm{d}t+\int_{\sqrt{8/\ell}}^{1.2/\pi}(\operatorname{sinc}(t))^{\ell}\mathrm{d}t\right)$
$\displaystyle\geq\frac{2}{s_{1}}\left(\int_{0}^{\sqrt{8/\ell}}(1-\frac{\pi^{2}t^{2}}{6})^{\ell}\mathrm{d}t\right)$
$\displaystyle\gtrsim\frac{1}{s_{1}\sqrt{\ell}}.$

∎

We bound the integration outside $[-\frac{1.2}{\pi s_{1}},\frac{1.2}{\pi
s_{1}}]$ from the last property of the sinc function.

######  Claim C.3.

$\int_{\frac{1.2}{\pi
s_{1}}}^{+\infty}(\operatorname{sinc}(s_{1}t))^{\ell}\mathrm{d}t=O(1.2^{-\ell})$.

From these two claims, we have the existence of $s_{0}$.

######  Claim C.4.

There exists a universal constant $C_{0}$ and $s_{0}=C_{0}s_{1}\sqrt{\ell}$
such that $H_{1}(0)=1$.

###### Proof.

Because $\ell$ is a large even number,
$\int_{\operatorname{rect}_{1-2/s_{1}}}\operatorname{sinc}(s_{1}t)^{\ell}\mathrm{d}t\eqsim\frac{1}{s_{1}\sqrt{\ell}}$
from all discussion above. ∎

We show several useful properties about the Filter functions
$\big{(}H_{1}(t),\widehat{H_{1}}(f)\big{)}$.

######  Lemma C.5.

Given $s_{0},s_{1},s_{2},\ell$, where $\frac{s_{2}}{2}+\frac{1}{s_{1}}\leq
1/2$ and $s_{0}=C_{0}s_{1}\sqrt{\ell}$ for some constant $C_{0}$. The filter
function $(H_{1}(t),\widehat{H}_{1}(f))[s_{0},s_{1},s_{2},\ell]$ has the
following properties,

$\displaystyle\mathrm{Property\leavevmode\nobreak\ \@slowromancap i@}:$
$\displaystyle
H_{1}(t)\in[1-\frac{s_{0}}{s_{1}}\cdot\frac{2\pi^{-\ell}}{\ell-1},1],\text{\leavevmode\nobreak\
if\leavevmode\nobreak\ }|t|\leq\frac{s_{2}}{2}-\frac{1}{s_{1}}.$
$\displaystyle\mathrm{Property\leavevmode\nobreak\ \@slowromancap ii@}:$
$\displaystyle H_{1}(t)\in[0,1],\text{\leavevmode\nobreak\
if\leavevmode\nobreak\ }\frac{s_{2}}{2}-\frac{1}{s_{1}}\leq|t|\leq\frac{1}{2}$
$\displaystyle\mathrm{Property\leavevmode\nobreak\ \@slowromancap iii@}:$
$\displaystyle H_{1}(t)\leq
s_{0}s_{2}\left((s_{1}|t|-s_{1}+2)^{2}+1\right)^{-\ell},\forall|t|>\frac{1}{2}$
$\displaystyle\mathrm{Property\leavevmode\nobreak\ \@slowromancap iv@}:$
$\displaystyle\operatorname{supp}(\widehat{H}_{1}(f))\subseteq[-\frac{s_{1}\ell}{2},\frac{s_{1}\ell}{2}]$

Figure 5: The light red area represents
$\int_{(1/2-2/s_{1})}^{(1/2-2/s_{1})-t}s_{0}\cdot\operatorname{sinc}\left(s_{1}(\tau)\right)^{\ell}\mathrm{d}\tau$
and the light green area represents
$\int_{1/2-2/s_{1}}^{1/2-2/s_{1}+t}s_{0}\cdot\operatorname{sinc}\left(s_{1}(\tau)\right)^{\ell}\mathrm{d}\tau$.

Proof of Property<EMAIL_ADDRESS>First, $H_{1}(0)=1$ follows by definition of $s_{0}$,
then we can prove the upper bound for $H_{1}(t)$ by showing for any $t>0$,
$H_{1}(0)-H_{1}(t)>0$ always holds ,

By definition of sinc function, we know that
$\operatorname{sinc}(s_{1}t)^{\ell}$ reaches $0$ at all the points
$\\{\frac{1}{s_{1}}+i\frac{2}{s_{1}}|i\in\mathbb{N}\\}$. By definition of
$s_{1}$, we know that $\frac{1}{s_{1}}\ll\frac{1}{2}-\frac{1}{s_{1}}$. For any
$t>0$,

$\displaystyle H_{1}(0)-H_{1}(t)$ $\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\int
s_{0}\cdot\operatorname{sinc}\left(s_{1}(\tau)\right)^{\ell}\cdot\operatorname{rect}_{1-2/s_{1}}(0-\tau)\mathrm{d}\tau-\int
s_{0}\cdot\operatorname{sinc}\left(s_{1}(\tau)\right)^{\ell}\cdot\operatorname{rect}_{1-2/s_{1}}(t-\tau)\mathrm{d}\tau$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\int_{-(1/2-2/s_{1})}^{1/2-2/s_{1}}s_{0}\cdot\operatorname{sinc}\left(s_{1}(\tau)\right)^{\ell}\mathrm{d}\tau-\int_{-(1/2-2/s_{1})+t}^{1/2-2/s_{1}+t}s_{0}\cdot\operatorname{sinc}\left(s_{1}(\tau)\right)^{\ell}\mathrm{d}\tau$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\int_{-(1/2-2/s_{1})}^{-(1/2-2/s_{1})+t}s_{0}\cdot\operatorname{sinc}\left(s_{1}(\tau)\right)^{\ell}\mathrm{d}\tau-\int_{1/2-2/s_{1}}^{1/2-2/s_{1}+t}s_{0}\cdot\operatorname{sinc}\left(s_{1}(\tau)\right)^{\ell}\mathrm{d}\tau$
shown in Figure 5 $\displaystyle\geq\leavevmode\nobreak\ $ $\displaystyle 0,$

where the last inequality follows by choosing $s_{1}$ to be an integer. Thus,
we prove an upper bound for $H_{1}(t)$. Third, we show the lower bound for
$H_{1}(t)$,

$\displaystyle H_{1}(t)$ $\displaystyle=$
$\displaystyle\int_{-\infty}^{+\infty}s_{0}\cdot\operatorname{sinc}(s_{1}\tau)^{\cdot\ell}\operatorname{rect}_{s_{2}}(t-\tau)\mathrm{d}\tau$
$\displaystyle=$
$\displaystyle\int_{t-\frac{s_{2}}{2}}^{t+\frac{s_{2}}{2}}s_{0}\cdot\operatorname{sinc}(s_{1}\tau)^{\cdot\ell}\mathrm{d}\tau$
$\displaystyle=$ $\displaystyle
1-\underbrace{\int_{t+\frac{s_{2}}{2}}^{+\infty}s_{0}\cdot\operatorname{sinc}(s_{1}\tau)^{\cdot\ell}\mathrm{d}\tau}_{A}-\underbrace{\int_{-\infty}^{t-\frac{s_{2}}{2}}s_{0}\cdot\operatorname{sinc}(s_{1}\tau)^{\cdot\ell}\mathrm{d}\tau}_{B}$

Thus, as long as we can upper bound the term $A$ and $B$, then we will have a
lower bound for the $H_{1}(t)$, for any
$|t|\leq\frac{s_{2}}{2}-\frac{1}{s_{1}}$.

$\displaystyle A$ $\displaystyle=$
$\displaystyle\int_{t+\frac{s_{2}}{2}}^{+\infty}s_{0}\cdot\operatorname{sinc}(s_{1}\tau)^{\cdot\ell}\mathrm{d}\tau$
$\displaystyle\leq$
$\displaystyle\int_{\frac{1}{s_{1}}}^{+\infty}s_{0}\cdot\operatorname{sinc}(s_{1}\tau)^{\cdot\ell}\mathrm{d}\tau$
$\displaystyle\leq$
$\displaystyle\int_{\frac{1}{s_{1}}}^{+\infty}s_{0}\cdot(s_{1}\pi\tau)^{-\ell}\mathrm{d}\tau$
$\displaystyle=$ $\displaystyle
s_{0}\cdot(s_{1}\pi)^{-\ell}\frac{1}{\ell-1}(1/s_{1})^{-\ell+1}$
$\displaystyle=$
$\displaystyle\frac{s_{0}}{s_{1}}\cdot(\pi)^{-\ell}\frac{1}{\ell-1}$

Similarly, we can bound the term $B$ in the same way. ∎

Proof of Property<EMAIL_ADDRESS>In the proof of Property i@, we already show that
$\forall t$, $H_{1}(t)\leq 1$. Thus, the upper bound of Property ii@ is also
holding. The lower bound follows by both
$\operatorname{sinc}(s_{1}t)^{\cdot\ell}$ and $\operatorname{rect}_{s_{2}}(t)$
are always nonnegative, thus the convolution of these two functions has to be
nonnegative. ∎

Proof of Property<EMAIL_ADDRESS>Let’s prove the case when $t>1$, since $H_{1}(t)$ is
symmetric, then the case $t<-1$ will also hold. By definition of
$(H_{1}(t),\widehat{H}_{1}(f))$, we have

$\displaystyle H_{1}(t)$ $\displaystyle=$ $\displaystyle
s_{0}\cdot\int_{-\infty}^{+\infty}\operatorname{sinc}(s_{1}(t-\tau))^{\cdot\ell}\operatorname{rect}_{s_{2}}(\tau)\mathrm{d}\tau$
$\displaystyle=$ $\displaystyle
s_{0}\cdot\int_{-\frac{s_{2}}{2}}^{\frac{s_{2}}{2}}\operatorname{sinc}(s_{1}(t-\tau))^{\cdot\ell}\mathrm{d}\tau$
$\displaystyle=$ $\displaystyle
s_{0}\cdot\int_{-\frac{s_{2}}{2}}^{\frac{s_{2}}{2}}\operatorname{sinc}(s_{1}(\tau-t))^{\cdot\ell}\mathrm{d}\tau$

We’d like to choose a middle point $\tau_{0}$, and then separated the interval
into two parts, one is $[-\frac{s_{2}}{2},\tau_{0}]$ and the other is
$[\tau_{0},\frac{s_{2}}{2}]$. To choose a reasonable $\tau_{0}$, we need to
use the following simple facts,

$\displaystyle(\frac{\sin(x)}{x})^{\ell}$ $\displaystyle\leq$ $\displaystyle
x^{-\ell}\text{\leavevmode\nobreak\ if\leavevmode\nobreak\ }x\geq 1.2$
$\displaystyle(\frac{\sin(x)}{x})^{\ell}$ $\displaystyle\leq$
$\displaystyle(1-\frac{x^{2}}{8})^{\ell}\text{\leavevmode\nobreak\
if\leavevmode\nobreak\ }x<1.2$

Thus, $|\pi s_{1}(\tau_{0}-t)|=1.2$, which implies that
$\tau_{0}^{+}=t+\frac{1.2}{\pi s_{1}}$ or $\tau_{0}^{-}=t-\frac{1.2}{\pi
s_{1}}$. By relationship between $s_{1}$ and $s_{2}$, we know
$\tau_{0}^{-}>\frac{1}{2}-\frac{1.2}{\pi
s_{1}}>\frac{1}{2}-\frac{1}{s_{1}}\geq\frac{s_{2}}{2}$. Thus, we can use the
case $x<1.2$ to upper bound the $H_{1}(t)$,

$\displaystyle\leavevmode\nobreak\ H_{1}(t)$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle s_{0}\cdot
s_{2}\cdot\underset{\tau\in[-s_{2}/2,s_{2}/2]}{\max}\operatorname{sinc}(s_{1}(\tau-t))^{\cdot\ell}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle s_{0}\cdot
s_{2}\underset{\tau\in[-s_{2}/2,s_{2}/2]}{\max}(1-\frac{(s_{1}\pi(\tau-t))^{2}}{8})^{\ell}$
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle s_{0}\cdot
s_{2}(1-\frac{(s_{1}\pi(\frac{s_{2}}{2}-t))^{2}}{8})^{\ell}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle s_{0}\cdot
s_{2}\cdot(e^{-\frac{(s_{1}\pi(\frac{s_{2}}{2}-t))^{2}}{8}})^{\ell}$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\ }1-x\leq
e^{-x}$ $\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle s_{0}\cdot
s_{2}\cdot(e^{(s_{1}(t-s_{2}/2))^{2}})^{-\ell}$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\ }1<\pi^{2}/8$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle s_{0}\cdot
s_{2}\cdot(1+(s_{1}(t-s_{2}/2))^{2})^{-\ell}$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\ }1+x\leq
e^{x}$ $\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
s_{0}\cdot(1+(s_{1}(t-s_{2}/2))^{2})^{-\ell}$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\ }s_{1}\leq 1.$

Thus, we complete the proof. ∎

Proof of Property<EMAIL_ADDRESS>Because of the support of
$\operatorname{rect}_{s_{1}}(f)$ is $s_{1}$, then the support of
$(\operatorname{rect}_{s_{1}}(f))^{*\ell}=s_{1}\ell$. Since
$\widehat{H}_{1}(f)$ is defined to be the
$(\operatorname{rect}_{s_{1}}(f))^{*\ell}$ multiplied by
$\operatorname{sinc}(fs_{2})$, thus
$\operatorname{supp}(\widehat{H}_{1}(f))\subseteq[-\frac{s_{1}\ell}{2},\frac{s_{1}\ell}{2}]$.
∎

######  Definition C.6.

Given any $0<s_{3}<1$, $0<\delta<1$, we define $(H(t),\widehat{H}(f))$ to be
the filter function $(H_{1}(t),\widehat{H_{1}}(f))$ by doing the following
operations

  * •

Setting $\ell=\Theta(k\log(k/\delta))$,

  * •

Setting $s_{2}=1-\frac{2}{s_{1}}$,

  * •

Shrinking by a factor $s_{3}$ in time domain,

$\displaystyle H(t)$ $\displaystyle=$ $\displaystyle H_{1}(t/s_{3})$ (29)
$\displaystyle\widehat{H}(f)$ $\displaystyle=$ $\displaystyle
s_{3}\widehat{H_{1}}(s_{3}f)$ (30)

We call the “heavy cluster" around a frequency $f_{0}$ to be the support of
$\delta_{f_{0}}(f)*\widehat{H}(f)$ in the frequency domain and use

$\Delta_{h}=|\operatorname{supp}(\widehat{H}(f))|=\frac{s_{1}\cdot\ell}{s_{3}}$
(31)

to denote the width of the cluster.

We show several useful properties about the Filter functions
$\big{(}H(t),\widehat{H}(f)\big{)}$.

######  Lemma 6.6.

Given $s_{0},s_{1},0<s_{3}<1,\ell>1,0<\delta<1$, where
$\ell=\Theta(k\log(k/\delta))$.The filter function $(H(t),\widehat{H}(f))$ has
the following properties,

$\displaystyle\mathrm{Property\leavevmode\nobreak\ \@slowromancap i@}:$
$\displaystyle H(t)\in[1-\delta,1],\text{\leavevmode\nobreak\
when\leavevmode\nobreak\ }|t|\leq(\frac{1}{2}-\frac{2}{s_{1}})s_{3}.$
$\displaystyle\mathrm{Property\leavevmode\nobreak\ \@slowromancap ii@}:$
$\displaystyle H(t)\in[0,1],\text{\leavevmode\nobreak\
when\leavevmode\nobreak\
}(\frac{1}{2}-\frac{2}{s_{1}})s_{3}\leq|t|\leq\frac{1}{2}s_{3}.$
$\displaystyle\mathrm{Property\leavevmode\nobreak\ \@slowromancap iii@}:$
$\displaystyle H(t)\leq
s_{0}\cdot(s_{1}(\frac{|t|}{s_{3}}-\frac{1}{2})+2)^{-\ell},\forall|t|>\frac{1}{2}s_{3}.$
$\displaystyle\mathrm{Property\leavevmode\nobreak\ \@slowromancap iv@}:$
$\displaystyle\operatorname{supp}(\widehat{H}(f))\subseteq[-\frac{s_{1}\ell}{2s_{3}},\frac{s_{1}\ell}{2s_{3}}].$

For any exact $k$-Fourier-sparse signal $x^{*}(t)$, we shift the interval from
$[0,T]$ to $[-1/2,1/2]$ and consider $x^{*}(t)$ for $t\in[-1/2,1/2]$ to be our
observation, which is also $x^{*}(t)\cdot\operatorname{rect}_{1}(t)$.

$\displaystyle\mathrm{Property\leavevmode\nobreak\ \@slowromancap v@}:$
$\displaystyle\int_{-\infty}^{+\infty}\bigl{|}x^{*}(t)\cdot
H(t)\cdot(1-\operatorname{rect}_{1}(t))\bigr{|}^{2}\mathrm{d}t<\delta\int_{-\infty}^{+\infty}|x^{*}(t)\cdot\operatorname{rect}_{1}(t)|^{2}\mathrm{d}t.$
$\displaystyle\mathrm{Property\leavevmode\nobreak\ \@slowromancap vi@}:$
$\displaystyle\int_{-\infty}^{+\infty}|x^{*}(t)\cdot
H(t)\cdot\operatorname{rect}_{1}(t)|^{2}\mathrm{d}t\in[1-\epsilon,1]\cdot\int_{-\infty}^{+\infty}|x^{*}(t)\cdot\operatorname{rect}_{1}(t)|^{2}\mathrm{d}t.$

for arbitrarily small constant $\epsilon$.

The Property i@, ii@, iii@ and iv@ follow by filter function
$H(t),\widehat{H}(f)$ inheriting $H_{1}(t),\widehat{H}_{1}(f)$.

Figure 6: $\widehat{H\cdot x^{*}}(f)$ and $H\cdot x^{*}(t)$.

Proof of Property<EMAIL_ADDRESS>$\forall t\notin[-1/2,1/2]$, we have,

$\displaystyle|x^{*}(t)\cdot H(t)|^{2}$ $\displaystyle\leq\leavevmode\nobreak\
$ $\displaystyle|x^{*}(t)|^{2}\cdot|H(t)|^{2}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle|x^{*}(t)|^{2}\cdot(s_{1}(|t|-1/2)+2)^{-\ell}$ by Property iii@
of $H_{1}(t)$ $\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
k^{7}\cdot(2kt)^{2.5k}\cdot\int_{-\infty}^{+\infty}|x^{*}(t)\cdot\operatorname{rect}_{1}(t)|^{2}\mathrm{d}t\cdot(s_{1}(\frac{|t|}{s_{3}}-\frac{1}{2})+2)^{-\ell}\leavevmode\nobreak\
$ by Lemma 5.5 $\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
t^{O(k\log
k)}\cdot\int_{-\infty}^{+\infty}|x^{*}(t)\cdot\operatorname{rect}_{1}(t)|^{2}\mathrm{d}t\cdot(s_{1}(\frac{|t|}{s_{3}}-\frac{1}{2})+2)^{-\ell/2}.$
(32)

Thus taking the integral finishes the proof because $\ell\gtrsim
k\log(k/\delta)$. ∎

Proof of Property<EMAIL_ADDRESS>First, because of for any $t$, $|H_{1}(t)|\leq 1$, thus
we prove the upper bound for LHS,

$\int_{-\infty}^{+\infty}|x^{*}(t)\cdot
H(t)\cdot\operatorname{rect}_{1}(t)|^{2}\mathrm{d}t\leq\int_{-\infty}^{+\infty}|x^{*}(t)\cdot
1\cdot\operatorname{rect}_{1}(t)|^{2}\mathrm{d}t.$

Second, as mentioned early, we need to prove the general case when
$s_{3}=1-1/\operatorname{poly}(k)$. Define interval
$S=[-s_{3}(\frac{1}{2}-\frac{1}{s_{1}}),s_{3}(\frac{1}{2}-\frac{1}{s_{1}})]$,
by definition, $S\subset[-1/2,1/2]$. Then define
$\overline{S}=[-1/2,1/2]\setminus S$, which is
$[-1/2,-s_{3}(\frac{1}{2}-\frac{1}{s_{1}}))\cup(s_{3}(\frac{1}{2}-\frac{1}{s_{1}}),1/2]$.
By Property i@, we have

$\int_{S}|x^{*}(t)\cdot
H(t)|^{2}\mathrm{d}t\geq(1-\delta)^{2}\int_{S}|x^{*}(t)|^{2}\mathrm{d}t$ (33)

Then we can show

$\displaystyle\int_{\overline{S}}|x^{*}(t)|^{2}\mathrm{d}t$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle|\overline{S}|\cdot\underset{t\in[-1/2,1/2]}{\max}|x^{*}(t)|^{2}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle(1-s_{3}(1-\frac{2}{s_{1}}))\cdot\widetilde{O}(k^{4})\int_{-\frac{1}{2}}^{\frac{1}{2}}|x^{*}(t)|^{2}\mathrm{d}t$
by Lemma 5.1 $\displaystyle\lesssim\leavevmode\nobreak\ $
$\displaystyle\int_{-\frac{1}{2}}^{\frac{1}{2}}|x^{*}(t)|^{2}\mathrm{d}t$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\
}\min(\frac{1}{1-s_{3}},s_{1})\geq\widetilde{O}(k^{4})$ (34)

Combining Equations (33) and (C.1) gives a lower bound for LHS,

$\displaystyle\int_{-\infty}^{+\infty}|x^{*}(t)\cdot
H(t)\cdot\operatorname{rect}_{1}(t)|^{2}\mathrm{d}t$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\int_{S}|x^{*}(t)H(t)|^{2}\mathrm{d}t$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle(1-2\delta)\int_{S}|x^{*}(t)|^{2}\mathrm{d}t$ by Equation (33)
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle(1-2\delta)\int_{S\cup\overline{S}}|x^{*}(t)|^{2}\mathrm{d}t-(1-2\delta)\int_{\overline{S}}|x^{*}(t)|^{2}\mathrm{d}t$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle(1-2\delta)\int_{S\cup\overline{S}}|x^{*}(t)|^{2}\mathrm{d}t-(1-2\delta)\epsilon\int_{S\cup\overline{S}}|x^{*}(t)|^{2}\mathrm{d}t$
by Equation (C.1) $\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle(1-2\delta-\epsilon)\int_{-\frac{1}{2}}^{\frac{1}{2}}|x^{*}(t)|^{2}\mathrm{d}t$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle(1-2\epsilon)\int_{-\infty}^{+\infty}|x^{*}(t)\cdot\operatorname{rect}_{1}(t)|^{2}\mathrm{d}t$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\
}\epsilon\gg\delta$

∎

Figure 7: Property vi@ of filter function $H(t)$, the light green area
represents $\mathrm{RHS}$(without scalar) of Property vi@ of filter $H$, the
light red area represents $\mathrm{LHS}$ of Property vi@ of filter $H$, the
light yellow area represents the difference. Property vi@ says the light
yellow area is only a small constant fraction of the light green area.

######  Remark C.7.

To match $(H(t),\widehat{H}(f))$ on $[-1/2,1/2]$ with signal $x(t)$ on
$[0,T]$, we will scale the time domain from $[-1/2,1/2]$ to $[-T/2,T/2]$ and
shift it to $[0,T]$. For example, the rectangle function in Property v@ and
vi@ will be replaced by $\operatorname{rect}_{T}(t-T/2)$. For the parameters
$s_{0},s_{1},s_{3},\delta,\ell$ in the definition of $H$, we always treat them
as numbers. We assume $T$ has seconds as unit and $\Delta_{h}$ has Hz as unit
. For example, in time domain, the Property i@ becomes that given $T>0$,

$H(t)\in[1-\delta,1]\text{\leavevmode\nobreak\ if\leavevmode\nobreak\
}|t-\frac{T}{2}|\leq(\frac{1}{2}-\frac{1}{s_{1}})s_{3}\cdot T$

In frequency domain, the Property iv@ becomes

$\operatorname{supp}(\widehat{H}(f))\subseteq[-\frac{\Delta_{h}}{2},\frac{\Delta_{h}}{2}],\text{\leavevmode\nobreak\
where\leavevmode\nobreak\ }\Delta_{h}=\frac{s_{1}\ell}{s_{3}T}.$ (35)

######  Lemma C.8.

Let $H(t)$ denote the function defined in Definition C.6. For any
$t\in[-\frac{1}{2},\frac{1}{2}]$, there exists an algorithm that takes
$O(s_{1}+\ell\log(s_{1})+\log(1/\epsilon))$ time to output a value
$\widetilde{H}(t)$ such that

$(1-\epsilon)H(t)\leq\widetilde{H}(t)\leq(1+\epsilon)H(t).$

###### Proof.

We will show that using a low degree polynomial with sufficiently large degree
is able to approximate the sinc function. By definition of filter function,

$\displaystyle H(t)$
$\displaystyle=s_{0}\cdot\int_{-\infty}^{+\infty}\operatorname{sinc}(s_{1}\tau)^{\cdot\ell}\operatorname{rect}_{s_{2}}(t-\tau)\mathrm{d}\tau$
$\displaystyle=s_{0}\cdot\int_{t-\frac{s_{2}}{2}}^{t+\frac{s_{2}}{2}}(\frac{\sin(\pi
s_{1}\tau)}{\pi s_{1}\tau})^{\ell}\mathrm{d}\tau$
$\displaystyle=\frac{s_{0}}{\pi s_{1}}\int_{(t-\frac{s_{2}}{2})\pi
s_{1}}^{(t+\frac{s_{2}}{2})\pi
s_{1}}(\frac{\sin(\tau)}{\tau})^{\ell}\mathrm{d}\tau$
$\displaystyle=\frac{s_{0}}{\pi s_{1}}\int_{(t-\frac{s_{2}}{2})\pi
s_{1}}^{(t+\frac{s_{2}}{2})\pi
s_{1}}\left(\sum_{i=0}^{\infty}(-1)^{i}\frac{\tau^{2i}}{(2i+1)!}\right)^{\ell}\mathrm{d}\tau$
by Taylor expansion $\displaystyle=\frac{s_{0}}{\pi
s_{1}}\int_{(t-\frac{s_{2}}{2})\pi s_{1}}^{(t+\frac{s_{2}}{2})\pi
s_{1}}(A+B)^{\ell}\mathrm{d}\tau$

where the last step follows by setting
$A=\sum_{i=0}^{d}(-1)^{i}\frac{\tau^{2i}}{(2i+1)!}$, and
$B=\sum_{i=d+1}^{\infty}(-1)^{i}\frac{\tau^{2i}}{(2i+1)!}$.

Denote $I^{+}=(t+\frac{s_{2}}{2})\pi s_{1}$ and $I^{-}=(t-\frac{s_{2}}{2})\pi
s_{1}$. Because of $t\in[-1/2,1/2]$, then $\max(|I^{+}|,|I^{-}|)=O(s_{1})$.
The goal is to show that

$(1-\epsilon)\int_{I^{-}}^{I^{+}}(A+B)^{\ell}\mathrm{d}\tau\leq\int_{I^{-}}^{I^{+}}A^{\ell}\mathrm{d}\tau\leq(1+\epsilon)\int_{I^{-}}^{I^{+}}(A+B)^{\ell}\mathrm{d}\tau$

Let’s prove an upper first,

$\displaystyle\int_{I^{-}}^{I^{+}}(A+B-B)^{\ell}\mathrm{d}\tau$
$\displaystyle=$
$\displaystyle\int_{I^{-}}^{I^{+}}(A+B)^{\ell}\mathrm{d}\tau+\sum_{j=1}^{\ell}\int_{I^{-}}^{I^{+}}{\ell\choose
j}(A+B)^{\ell-j}(-B)^{j}\mathrm{d}\tau$ $\displaystyle\leq$
$\displaystyle\int_{I^{-}}^{I^{+}}(A+B)^{\ell}\mathrm{d}\tau+\sum_{j=1}^{\ell}\int_{I^{-}}^{I^{+}}{\ell\choose
j}|A+B|^{\ell-j}|B|^{j}\mathrm{d}\tau$ $\displaystyle\leq$
$\displaystyle\int_{I^{-}}^{I^{+}}(A+B)^{\ell}\mathrm{d}\tau+\sum_{j=1}^{\ell}\int_{I^{-}}^{I^{+}}{\ell\choose
j}|A+B|^{\ell-j}\mathrm{d}\tau\cdot\max_{\tau\in[I^{-},I^{+}]}|B|^{j}$
$\displaystyle\leq$
$\displaystyle\int_{I^{-}}^{I^{+}}(A+B)^{\ell}\mathrm{d}\tau+\ell
2^{\ell}\cdot\max_{\tau\in[I^{-},I^{+}]}|B|$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\ }|H(t)|\leq
1\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }|B|^{j}\leq|B|$
$\displaystyle\leq$
$\displaystyle\int_{I^{-}}^{I^{+}}(A+B)^{\ell}\mathrm{d}\tau+\epsilon\cdot(s_{1})^{-\Theta(\ell)}$
by Claim C.9 $\displaystyle\leq$
$\displaystyle(1+\epsilon)\int_{I^{-}}^{I^{+}}(A+B)^{\ell}\mathrm{d}\tau$ by
Claim C.10

where all the steps by setting $d\gtrsim
s_{1}+\ell\log(s_{1})+\log(1/\epsilon)$. Similarly, we can prove a lower
bound. ∎

######  Claim C.9.

Let $B(\tau)=\sum_{i=d+1}^{+\infty}(-1)\frac{\tau^{2i}}{(2i+1)!}$, if
$d\gtrsim\tau+\ell\log(s_{1})+\log(1/\epsilon)$ then
$|B(\tau)|\leq\epsilon(1/s_{1})^{O(\ell)}$.

###### Proof.

We first show, for any $i\geq d+1$,

$\displaystyle\frac{\tau^{2i}}{(2i+1)!}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\frac{\tau^{2i}}{e((2i+1)/e)^{2i+1}}$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\
}e(n/e)^{n}\leq n!$ $\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
2^{-2i}$ $\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\
}i\gtrsim\tau$ $\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\epsilon(1/s_{1})^{O(\ell)}$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\
}i\gtrsim\ell\log(s_{1})+\log(1/\epsilon)$

Second, we can show that

$\sum_{i=d+1}^{+\infty}(-1)\frac{\tau^{2i}}{(2i+1)!}\lesssim\frac{\tau^{2(d+1)}}{(2(d+1)+1)!}\leq\epsilon(1/s_{1})^{O(\ell)}$

Thus, we complete the proof. ∎

######  Claim C.10.

$\min_{t\in[-1/2,1/2]}|H(t)|\geq(s_{1})^{-\Omega(\ell)}$.

###### Proof.

By the property of $H(t)$,

$\min_{\frac{1}{2}s_{3}<|t|\leq\frac{1}{2}}H(t)=\min_{|t|\leq\frac{1}{2}}H(t)$

Thus, it suffices to prove a lower bound on $H(t)$ for any $t$ such that
$\frac{1}{2}s_{3}<|t|\leq\frac{1}{2}$. Because of symmetric property, we only
need to prove a lower bound for one side. Let’s consider
$t\in[\frac{1}{2}s_{3},1/2]$,

$\displaystyle H(t)$ $\displaystyle\leavevmode\nobreak\ \geq\frac{s_{0}}{\pi
s_{1}}\int_{(t-\frac{s_{2}}{2})\pi s_{1}}^{(t+\frac{s_{2}}{2})\pi
s_{1}}(\frac{\sin(\tau)}{\tau})^{\ell}\mathrm{d}\tau$
$\displaystyle\leavevmode\nobreak\ \geq\frac{s_{0}}{\pi
s_{1}}\int_{(t+\frac{s_{2}}{4})\pi s_{1}}^{(t+\frac{s_{2}}{2})\pi
s_{1}}(\frac{\sin(\tau)}{\tau})^{\ell}\mathrm{d}\tau$
$\displaystyle\leavevmode\nobreak\ \geq\frac{s_{0}}{\pi
s_{1}}\cdot\Theta((t+\frac{s_{2}}{2})s_{1})\cdot\frac{1}{2}\cdot\pi\cdot\Theta((t+\frac{s_{2}}{2})\pi
s_{1})^{-\ell}$ $\displaystyle\leavevmode\nobreak\
\geq(s_{1})^{-\Omega(\ell)}$

∎

###  C.2 Analysis of filter function $(G(t),\widehat{G}(f))$

We construct $(G(t),\widehat{G}(f))$ in a similar way of
$(H_{1}(t),\widehat{H_{1}}(f))$ by switching the time domain and the frequency
domain of $(H_{1}(t),\widehat{H_{1}}(f))$ and modify the parameters for the
permutation hashing $P_{\sigma,a,b}$.

######  Definition C.11.

Given $B>1$, $\delta>0$, $\alpha>0$, we construct $G(t),\widehat{G}(f)$ by
doing the following operations,

  * •

$s_{2}=\frac{\pi}{2B}$,

  * •

$s_{1}=\frac{B}{\alpha\pi}$,

  * •

$\ell=l=\Theta(\log(k/\delta))$.

Then $G(t),\widehat{G}(f)$ becomes

$\displaystyle G(t)$ $\displaystyle=$ $\displaystyle
b_{0}\cdot(\operatorname{rect}_{s_{1}}(t))^{*l}\cdot\operatorname{sinc}(ts_{2})$
$\displaystyle=$ $\displaystyle
b_{0}\cdot(\operatorname{rect}_{\frac{B}{(\alpha\pi)}}(t))^{*l}\cdot\operatorname{sinc}(t\frac{\pi}{2B}),$
$\displaystyle\widehat{G}(f)$ $\displaystyle=$ $\displaystyle
b_{0}\cdot(\operatorname{sinc}(s_{1}f))^{\cdot
l}*\operatorname{rect}_{s_{2}}(f)$ $\displaystyle=$ $\displaystyle
b_{0}\cdot(\operatorname{sinc}(\frac{B}{\alpha\pi}f))^{\cdot
l}*\operatorname{rect}_{\frac{\pi}{2B}}(f).$

where the scalar $b_{0}=\Theta(s_{1}\sqrt{l})=\Theta(B\sqrt{l}/\alpha)$
satisfying $\widehat{G}(0)=1$.

######  Lemma 6.7.

Given $B>1$, $\delta>0$, $\alpha>0$, we set $l=\Omega(\log(\delta/k))$. The
filter function $(G(t),\widehat{G}(f))[B,\delta,\alpha,l]$ satisfies the
following properties,

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

###### Proof.

The first five Properties follows from Lemma 6.6 directly.

∎

###  C.3 Parameters setting for filters

#### One-cluster Recovery.

Figure 8: Parameters for $s_{1},s_{3}$ and $\ell$.

In one-cluster, we donot need filter function $(G(t),\widehat{G}(f))$.

In section C.1, by Equation (C.1) in the proof of Property vi@ of filter
function $(H(t),\widehat{H}(f))$, we need
$\min(\frac{1}{1-s_{3}},s_{1})\geq\widetilde{O}(k^{4})$.

In section C.1, by Equation (C.1) in the proof of Property v@ of filter
function $(H(t),\widehat{H}(f))$, we set $\ell\gtrsim k\log(k/\delta)$.

$\Delta_{h}$ is determined by the parameters of filter $(H(t),\widehat{H}(f))$
in Equation (35): $\Delta_{h}\eqsim\frac{s_{1}\ell}{s_{3}T}$ in section C.1.
Combining the setting of $s_{1}$, $s_{3}$ $\ell$, we should set
$\Delta_{h}\geq\widetilde{O}(k^{5}\log(1/\delta))/T$.

####  $k$-cluster Recovery.

Note that in the $k$-cluster recovery, we need to use filter function
$(G(t),\widehat{G}(f))$. We choose $l=\log(k/\delta)$, $\alpha\eqsim 1$,
$B\eqsim k$ , and $D=l/\alpha$.

By proof of Property ii@ of $z$ in Lemma 7.20 from section 7.6, we need
$T(1-s_{3})>\sigma Bl$. By the same reason in one-cluster recovery,
$1-s_{3}\leq\frac{1}{\widetilde{O}(k^{4})}$. Combining $T(1-s_{3})>\sigma Bl$
and $1-s_{3}\leq\frac{1}{\widetilde{O}(k^{4})}$, we obtain

$\frac{T}{\widetilde{O}(k^{4})}>\sigma Bl$ (36)

Because in our algorithm, we will sample $\sigma$ from
$[\frac{1}{B\Delta_{h}},\frac{2}{B\Delta_{h}}]$. Thus, plugging
$\sigma=\Theta(\frac{1}{B\Delta_{h}})$ in Equation (36) we have

$\frac{T}{\widetilde{O}(k^{4})}>\frac{l}{\Delta_{h}}$

which implies another lower bound for $\Delta_{h}$,

$\Delta_{h}\geq\widetilde{O}(k^{4})l/T$

Combining the above bound with previous lower bound in one-cluster recovery,
we get

$\Delta_{h}\geq\widetilde{O}(k^{4}\log(1/\delta))/T+\widetilde{O}(k^{5}\log(1/\delta))/T=\widetilde{O}(k^{5}\log(1/\delta))/T$

For $s_{1}$ and $\ell$, we still choose the same setting as before,
$s_{1}\eqsim\widetilde{O}(k^{4})$ and $\ell\eqsim O(k\log(k/\delta))$.

###  C.4 Analysis of HashToBins

In this section, we explain the correctness of Procedure HashToBins in
Algorithm 6. Before giving the proof of that algorithm, we show how to connect
$\mathrm{CFT}$, $\mathrm{DTFT}$ and $\mathrm{DFT}$.

######  Lemma C.12.

For any signal $W:\mathbb{R}\rightarrow\mathbb{C}$, let
$A:\mathbb{Z}\rightarrow\mathbb{C}$ and $B:[n]\rightarrow\mathbb{C}$ be
defined as follows:

$\displaystyle A[i]=W(i),\forall i\in\mathbb{Z}\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }B[i]=\sum_{j\in\mathbb{Z}}A[i+jn],\forall i\in[n].$

Then we consider the Fourier transform on $W,A,$ and $B$:

$\displaystyle\mathrm{CFT}\quad$
$\displaystyle\quad\widehat{W}:\mathbb{R}\rightarrow\mathbb{C},$
$\displaystyle\mathrm{DTFT}\quad$
$\displaystyle\quad\widehat{A}:[0,1]\rightarrow\mathbb{C},$
$\displaystyle\mathrm{DFT}\quad$
$\displaystyle\quad\widehat{B}:[n]\rightarrow\mathbb{C}.$

We have:

$\forall
f\in[0,1),\widehat{A}(f)=\sum_{j\in\mathbb{Z}}\widehat{W}(f+j);\quad\forall
i\in[n],\widehat{B}[i]=\sum_{j\in\mathbb{Z}}\widehat{W}(i/n+j).$

###### Proof.

Recall that $\operatorname{Comb}_{s}(t)=\sum_{j\in\mathbb{Z}}\delta_{js}(t)$.
First, we show
$\widehat{A}(f)=\sum_{j\in\operatorname*{\mathbb{Z}}}e^{2\pi\mathbf{i}jf}A[j]$
equals to $\underset{j\in\operatorname*{\mathbb{Z}}}{\sum}\widehat{W}(f+j)$:

$\displaystyle\widehat{A}(f)=\quad$
$\displaystyle\sum_{j\in\operatorname*{\mathbb{Z}}}e^{2\pi\mathbf{i}jf}W[j]$
by $A[j]=W(j)$ $\displaystyle=\quad$
$\displaystyle\int_{-\infty}^{+\infty}e^{2\pi\mathbf{i}fj}W(j)\cdot\operatorname{Comb}_{1}(j)\mathrm{d}j$
$\displaystyle=\quad$
$\displaystyle\widehat{W\cdot\operatorname{Comb}_{1}}(f)$
$\displaystyle=\quad$
$\displaystyle(\widehat{W}*\widehat{\operatorname{Comb}}_{1})(f)$
$\displaystyle=\quad$
$\displaystyle\sum_{j\in\operatorname*{\mathbb{Z}}}\widehat{W}(f+j).$ (37)

Next, we prove that $\forall i\in[n],\widehat{B}[i]=\widehat{A}(i/n)$,

$\displaystyle\widehat{B}[i]=\quad$
$\displaystyle\sum_{j=1}^{n}B[j]e^{\frac{2\pi\mathbf{i}}{n}ij}$ by
$\mathrm{DFT}$ $\displaystyle=\quad$
$\displaystyle\sum_{j=1}^{n}(\sum_{k\in\operatorname*{\mathbb{Z}}}A[j+kn])e^{\frac{2\pi\mathbf{i}}{n}ij}$
by $B[j]=\sum_{k\in\operatorname*{\mathbb{Z}}}A[j+kn]$ $\displaystyle=\quad$
$\displaystyle\sum_{j=1}^{n}\sum_{k\in\operatorname*{\mathbb{Z}}}A[j+kn]e^{\frac{2\pi\mathbf{i}}{n}i(j+kn)}$
by $e^{\frac{2\pi\mathbf{i}}{n}\cdot ikn}=1$ $\displaystyle=\quad$
$\displaystyle\sum_{j\in\operatorname*{\mathbb{Z}}}A[j]e^{2\pi\mathbf{i}j\frac{i}{n}}=\widehat{A}(i/n)$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\ DTFT}.$ (38)

Combining Equation (C.4) and Equation (C.4), we obtain that
$\widehat{B}[j]=\widehat{A}(j/n)=\sum_{i\in\operatorname*{\mathbb{Z}}}\widehat{W}(j/n+i)$
for all $j\in[n]$. ∎

######  Claim C.13.

Let $u\in\operatorname*{\mathbb{C}}^{B}$ and
$V\in\operatorname*{\mathbb{C}}^{BD}$ such that for any $j\in B$,
$u[j]=\underset{i\in[D]}{\sum}V[j+(i-1)B]$. Then

$\widehat{u}[j]=\widehat{V}[jD],\forall j\in[B].$

###### Proof.

We prove it through the definition of the Fourier transform:

$\displaystyle\widehat{V}[jD]=\quad$ $\displaystyle\sum_{i=1}^{BD}V[i]\cdot
e^{\frac{2\pi\mathbf{i}}{BD}\cdot i\cdot(jD)}$ by definition of DFT
$\displaystyle=\quad$
$\displaystyle\sum_{i=1}^{B}\sum_{k=1}^{D}V[i+kB]e^{\frac{2\pi\mathbf{i}}{B}\cdot(i+kB)\cdot
j}$ by replacing $i$ by $i+kB$ $\displaystyle=\quad$
$\displaystyle\sum_{i=1}^{B}e^{\frac{2\pi\mathbf{i}}{B}\cdot j\cdot
i}\sum_{k=1}^{D}V[i+(k-1)B]$ by $e^{2\pi\mathbf{i}jk}=1$ $\displaystyle=\quad$
$\displaystyle\sum_{i=1}^{B}e^{\frac{2\pi\mathbf{i}}{B}\cdot j\cdot
i}u[i]=\widehat{u}[j]$ by definition of DFT on $u$

∎

We use Definition 6.1 and Lemma 6.2 to generalize Lemma C.12,

######  Corollary C.14.

If for all $j\in[n]$,
$B[j]=\underset{i\in\operatorname*{\mathbb{Z}}}{\sum}W\big{(}(j+in)\sigma-\sigma
a\big{)}$, then $\forall j\in[n]$,

$\widehat{B}[j]=\sum_{i\in\operatorname*{\mathbb{Z}}}\widehat{W}\left((\frac{j}{n}+i)/\sigma\right)\cdot\frac{1}{\sigma}e^{-2\pi\mathbf{i}(\frac{j}{n}+i)a}.$

If for all $j\in[n]$,
$B[j]=\underset{i\in\operatorname*{\mathbb{Z}}}{\sum}W\big{(}(j+in)\sigma-\sigma
a\big{)}e^{-2\pi\mathbf{i}\sigma b(j+in)}$, then $\forall j\in[n]$,

$\widehat{B}[j]=\sum_{i\in\operatorname*{\mathbb{Z}}}\widehat{W}\left((\frac{j}{n}+i)/\sigma+b\right)\cdot\frac{1}{\sigma}e^{-2\pi\mathbf{i}(\frac{j}{n}+i)a-2\pi\mathbf{i}\sigma
ab}.$

######  Remark C.15 (Samples of HashToBins).

Procedure HashToBins in Algorithm 6 takes $BD$ samples in $x(t)$:

$x(\sigma(1-a)),x(\sigma(2-a)),\cdots,x(\sigma(BD-a)).$

Figure 9: $\widehat{G}_{\sigma,b}^{(j)}(f)$ where the top one is $j=0$ and the
bottom one is $j=1$, ${\cal
A}_{i,j}=[\frac{1}{\sigma}(2\pi(i+\frac{j}{B})-\frac{2\pi}{2B}),\frac{1}{\sigma}(2\pi(i+\frac{j}{B})+\frac{2\pi}{2B})]$,
${\cal
B}_{i,j}=[\frac{1}{\sigma}(2\pi(i+\frac{j}{B})-\frac{2\pi(1-\alpha)}{2B}),\frac{1}{\sigma}(2\pi(i+\frac{j}{B})+\frac{2\pi(1-\alpha)}{2B})]$

To analyze our algorithm, we use filter function $(G(t),\widehat{G}(f))$ and
$\operatorname{Comb}_{s}(t)=\underset{j\in\operatorname*{\mathbb{Z}}}{\sum}\delta_{sj}(t)$
to define the discretization of $G$.

######  Definition C.16.

Define the discretization of $G(t)$ and $\widehat{G}(f)$,

$\displaystyle G^{\operatorname{dis}}(t)$ $\displaystyle=$ $\displaystyle
G(t)\cdot\operatorname{Comb}_{s}(t)$
$\displaystyle\widehat{G}^{\operatorname{dis}}(f)$ $\displaystyle=$
$\displaystyle\frac{1}{s}(\widehat{G}*\operatorname{Comb}_{1/s})(f)$
$\displaystyle=$ $\displaystyle(\widehat{G}*\operatorname{Comb}_{1})(f)$
$\displaystyle=$
$\displaystyle\bigl{(}{\vbox{\hbox{\includegraphics[width=108.405pt]{hatG}}}}\bigr{)}*{\vbox{\hbox{\includegraphics[width=130.08731pt]{comb_1}}}}$

where $|\operatorname{supp}(G(t))|=\frac{lB}{\pi\alpha}$,
$D=\frac{l}{\pi\alpha}$, $s=|\operatorname{supp}(G(t))|/(BD)=l/(\pi\alpha
D)=1$.

######  Definition 6.8.

$\forall\sigma>0,b$ and $j\in[B]$. Define,

$\displaystyle G^{(j)}_{\sigma,b}(t)$ $\displaystyle=$
$\displaystyle\frac{1}{\sigma}G(t/\sigma)e^{2\pi\mathbf{i}t(j/B-\sigma
b)/\sigma}$ $\displaystyle\widehat{G}^{(j)}_{\sigma,b}(f)$ $\displaystyle=$
$\displaystyle\widehat{G}^{\operatorname{dis}}(\frac{j}{B}-\sigma f-\sigma
b)=\sum_{i\in\operatorname*{\mathbb{Z}}}\widehat{G}(i+\frac{j}{B}-\sigma
f-\sigma b)$

######  Lemma 6.9.

Let $u\in\operatorname*{\mathbb{C}}^{B}$ be the result of HashToBins under
permutation $P_{\sigma,a,b}$, and let $j\in[B]$. Define

$\widehat{z}=\widehat{x\cdot H}\cdot\widehat{G}^{(j)}_{\sigma,b},$

so

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

Let vector $\widehat{u}\in\operatorname*{\mathbb{C}}^{B}$ denote the
$B$-dimensional DFT of $u$, then $\forall j\in[B]$,

$\widehat{u}[j]=z_{\sigma a}.$

###### Proof.

Recall $B$ is the number of hash bins. $B\cdot D$ is the number of samples in
time signal. Let $W(t)=x\cdot H(t)$, define vector
$y\in\operatorname*{\mathbb{C}}^{BD}$, then $\forall j\in[BD]$, define

$y[j]=W(\sigma(j-a))e^{2\pi\mathbf{i}\sigma bj}$

Recall $G(t)$ denote the
$\operatorname{rect}^{*l}_{B/\alpha}(t)\cdot\operatorname{sinc}(t/B)$, then
$|\operatorname{supp}(G(t))|=\frac{lB}{\alpha}$. Let vector
$G^{\prime}\in\mathbb{C}^{BD}$ is the discretization of $G(t)$, where
$G^{\prime}[i]=G(i)$. Then, $\forall j\in[B]$,

$u[j]=\sum_{i\in[D]}V[j+iB]$

where $V[j]=y[j]\cdot G^{\prime}[j]$ and $G^{\prime}[j]$ is the value at the
$j$th nonzero point of $G^{\operatorname{dis}}(t)$. Applying Claim C.13 with
the definition of $u[j]$ and $V[j+iB]$, gives
$\widehat{u}[j]=\widehat{V}[jD],\forall j\in[B]$.

Because of $u$ is the result of $\textsc{HashToBins}(x\cdot
H,P_{\sigma,a,b},G)$ and $|\operatorname{supp}(G(t))|=BD$(choosing
$D=l/\alpha$), then

$u[j]=\sum_{i\in\operatorname*{\mathbb{Z}}}W(\sigma(j+iB-a))e^{-2\pi\mathbf{i}\sigma
b(j+iB)}G(j+iB)$

Then we define
$G^{\prime\prime}(t)=G(t/\sigma+a)e^{-2\pi\mathbf{i}b\sigma(t/\sigma+a)}$ and
$Y(t)=W(t)\cdot G^{\prime\prime}(t)$, then immediately, we have

$\widehat{G}^{\prime\prime}(f)=\sigma\widehat{G}(\sigma(f-b))e^{2\pi\mathbf{i}a\sigma
f}\quad\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}\quad\widehat{Y}(f)=\widehat{W}(f)*\widehat{G}^{\prime\prime}(f)$

Thus, we can rewrite $u[j]$ in the following sense,

$\displaystyle u[j]$ $\displaystyle=\quad$
$\displaystyle\sum_{i\in\operatorname*{\mathbb{Z}}}W(\sigma(j+iB-a))e^{-2\pi\mathbf{i}\sigma
b(j+iB)}G(j+iB)$ $\displaystyle=\quad$
$\displaystyle\sum_{i\in\operatorname*{\mathbb{Z}}}W(\sigma(j+iB-a))G^{\prime\prime}(\sigma(j+iB-a))$
by $G^{\prime\prime}(t)=G(t/\sigma+a)e^{-2\pi\mathbf{i}b\sigma(t/\sigma+a)}$
$\displaystyle=\quad$
$\displaystyle\sum_{i\in\operatorname*{\mathbb{Z}}}Y(\sigma(j+iB-a))$ by
$Y(t)=W(t)\cdot G^{\prime\prime}(t)$

Then

$\displaystyle\widehat{u}[j]$ $\displaystyle=\quad$
$\displaystyle\sum_{i\in\operatorname*{\mathbb{Z}}}\widehat{Y}((\frac{j}{B}+i)/\sigma)\cdot\frac{1}{\sigma}\cdot
e^{-2\pi\mathbf{i}(\frac{j}{B}+i)a}$ by Corollary C.14 $\displaystyle=\quad$
$\displaystyle\sum_{i\in\operatorname*{\mathbb{Z}}}\int_{-\infty}^{+\infty}\widehat{W}(s)\cdot\widehat{G}^{\prime\prime}(\frac{j/B+i}{\sigma}-s)\cdot\frac{1}{\sigma}\cdot
e^{-2\pi\mathbf{i}\cdot(j/B+i)a}\mathrm{d}s$ by
$\widehat{Y}(f)=\widehat{W}(f)*\widehat{G}^{\prime\prime}(f)$
$\displaystyle=\quad$
$\displaystyle\sum_{i\in\operatorname*{\mathbb{Z}}}\int_{-\infty}^{+\infty}\widehat{W}(s)\cdot\widehat{G}(j/B+i-\sigma
s-\sigma b)\cdot e^{-2\pi\mathbf{i}\cdot(-\sigma s)a}\mathrm{d}s$ by
$\widehat{G}^{\prime\prime}(f)=\sigma\widehat{G}(\sigma(f-b))e^{2\pi\mathbf{i}a\sigma
f}$ $\displaystyle=\quad$
$\displaystyle\int_{-\infty}^{+\infty}\widehat{W}(s)\cdot\sum_{i\in\operatorname*{\mathbb{Z}}}\widehat{G}((j/B+i)-\sigma
s-\sigma b)e^{2\pi\mathbf{i}a\sigma s}\mathrm{d}s$ $\displaystyle=\quad$
$\displaystyle\int_{-\infty}^{+\infty}\widehat{W}(s)\cdot\widehat{G}^{\operatorname{dis}}(\frac{j}{B}-\sigma
s-\sigma b)e^{-2\pi\mathbf{i}a\sigma s}\mathrm{d}s$ by
$\widehat{G}^{\operatorname{dis}}(f)=\sum_{i\in\operatorname*{\mathbb{Z}}}\widehat{G}(f+i)$

By definition C.16,

$\widehat{G}^{(j)}_{\sigma,b}=\widehat{G}^{\operatorname{dis}}(\frac{j}{B}-\sigma
s-\sigma
b)=\sum_{i\in\operatorname*{\mathbb{Z}}}\widehat{G}(i+\frac{j}{B}-\sigma
s-\sigma b)$

By definition of $\widehat{z}$, we have

$\widehat{z}(s)=\widehat{x\cdot
H}(s)\cdot\widehat{G}^{(j)}(s)=\widehat{W}(s)\cdot\widehat{G}^{(j)}(s)$

Then $\widehat{u}[j]$ is the $(a\sigma)^{th}$ inverse Fourier coefficients of
$\widehat{z}$, basically,

$\widehat{u}[j]=z_{a\sigma}=z(a\sigma)$

Thus, we can conclude first computing vector $u\in\mathbb{C}^{B}$. Getting
vector $\widehat{u}\in\mathbb{C}^{B}$ by using the Discrete Fourier transform
$\widehat{u}=\mathrm{DFT}(u)$. This procedure allows us to sample from time
domain to implicitly access the time signal’s Fourier transform $\widehat{z}$.
If $z$ is one-cluster in frequency domain, then apply one-cluster recovery
algorithm.

∎

##  Appendix D Acknowledgments

The authors would to like thank Aaron Sidford and David Woodruff for useful
discussions.

##  Appendix E Algorithm

This section lists the pseudocode of our algorithms.

Algorithm 3

1:procedure GetEmpirical1Energy($z,T,\Delta$) — Claim 7.11

2: $R_{\operatorname{est}}\leftarrow(T\Delta)^{2}$

3: for $i=1\to R_{\operatorname{est}}$ do

4: Choose $\alpha_{i}\in[0,T]$ uniformly at random

5: $z_{\operatorname{emp}}\leftarrow
z_{\operatorname{emp}}+|z(\alpha_{i})|^{2}$

6: end for

7:
$z_{\operatorname{emp}}\leftarrow\sqrt{z_{\operatorname{emp}}/R_{\operatorname{est}}}$

8: return $z_{\operatorname{emp}}$

9:end procedure

10:procedure GetLegal1Sample($z,\Delta,T,\beta,z_{\operatorname{emp}}$) —
Lemma 7.2

11:
$R_{\operatorname{repeat}}\leftarrow(T\Delta)^{3},S_{\operatorname{heavy}}\leftarrow\emptyset$

12: for $i=1\to R_{\operatorname{repeat}}$ do

13: Choose $\alpha_{i}\in[0,T]$ uniformly at random

14: if $|z(\alpha_{i})|\geq 0.5\cdot z_{\operatorname{emp}}$ then

15: $S_{\operatorname{heavy}}\leftarrow S_{\operatorname{heavy}}\cup i$

16: end if

17: end for

18: for $i\in S_{\operatorname{heavy}}$ do

19: $w(i)\leftarrow|z(\alpha_{i})|^{2}+|z(\alpha_{i}+\beta)|^{2}$

20: end for

21: $\alpha\leftarrow\alpha_{i}$ with probability $w(i)/\sum_{j\in
S_{\operatorname{heavy}}}w(j)$ for $i\in S_{\operatorname{heavy}}$

22: return $\alpha$

23:end procedure

Algorithm 4

1:procedure Locate1Signal($z,T,F,\Delta,z_{\operatorname{emp}}$) — Lemma 7.15

2: Set $t\eqsim\log(FT)$, $t^{\prime}=t/4$,
$D_{\max}\eqsim\log_{t^{\prime}}(FT)$,
$R_{\operatorname{loc}}\eqsim\log_{1/c}(tc)$, $L^{(1)}=2F$

3: for $i\in[D_{\max}]$ do

4: $l\eqsim 2F/(t^{\prime})^{i-1}\Delta$, $s\eqsim c$,
$\widehat{\beta}=\frac{ts}{2\Delta l}$

5: if $\widehat{\beta}\gtrsim T/(T\Delta)^{3/2}$ then

6: break

7: else

8:
$L^{(i)}\leftarrow\textsc{Locate1Inner}$($z,\Delta,T,\widehat{\beta},z_{\operatorname{emp}},L^{(i-1)}$)

9: end if

10: end for

11: return $L^{(i)}$

12:end procedure

13:procedure
Locate1Inner($z,\Delta,T,\widehat{\beta},z_{\operatorname{emp}},\widetilde{L}$)

14: Let $v_{q}\leftarrow 0$ for $q\in[t]$

15: while $r=1\to R_{\operatorname{loc}}$ do

16: Choose $\beta\in[\frac{1}{2}\widehat{\beta},\widehat{\beta}]$ uniformly at
random

17:
$\gamma\leftarrow\textsc{GetLegal1Sample}(z,\Delta,T,\beta,z_{\operatorname{emp}})$

18: for $i\in[m]$ do

19: $s_{i}\in[\beta(\widetilde{L}-\Delta l/2),\beta(\widetilde{L}+\Delta
l/2)]\cap\mathbb{Z}_{+},\theta_{i}=\frac{1}{2\pi\sigma\beta}(\phi(x(\gamma)/x(\gamma+\beta))+2\pi
s_{i})$

20: Let $\theta_{i}$ belong to $\text{region}(q)$

21: Then add a vote to region($q$) and its two neighbors, i.e., region($q-1$)
and region($q+1$)

22: end for

23: end while

24: $q_{j}^{*}\leftarrow\\{q|v_{q}>\frac{R_{\operatorname{loc}}}{2}\\}$

25: return $L\leftarrow\mathrm{center\leavevmode\nobreak\
of\leavevmode\nobreak\ region}(q_{j}^{*})$

26:end procedure

27:procedure FrequencyRecovery1Cluster($z,T,F,\Delta$) — Theorem 7.5

28: $z_{\operatorname{emp}}\leftarrow$ GetEmpirical1Energy($z,T,\Delta$)

29: for $r=1\to O(k)$ do

30:
$L_{r}\leftarrow\textsc{Locate1Signal}$($z,T,F,\Delta,z_{\operatorname{emp}}$)

31: end for

32: return
$L^{*}\leftarrow\underset{r\in[O(k)]}{\operatorname*{median}}\leavevmode\nobreak\
L_{r}$

33:end procedure

Algorithm 5 Main algorithm for one-cluster recovery

1:procedure CFT1Culster($x,H,T,F$) — Theorem 8.1

2: $\widetilde{f_{0}}\leftarrow\textsc{FrequencyRecovery1Cluster}$($x,H,T,F$)

3:
$\widetilde{x}\leftarrow\textsc{SignalRecovery1Cluster}$($\widetilde{f}_{0},\operatorname{poly}(k)\Delta_{h}$)

4: return $\widetilde{x}$

5:end procedure

6:procedure GenerateIntervals($d$)

7: $n\leftarrow y_{0}\leftarrow i\leftarrow 0$, $m\leftarrow\Theta(d)$

8: while $y_{i}\leq 1-\frac{9}{m^{2}}$ do

9: $y_{i+1}\leftarrow y_{i}+\frac{\sqrt{1-y_{i}^{2}}}{m}$,
$I_{n+1}\leftarrow[y_{i},y_{i+1}],I_{n+2}\leftarrow[-y_{i+1},-y_{i}]$

10: $i\leftarrow i+1,n\leftarrow n+2$

11: end while

12: $I_{n+1}\leftarrow[y_{i},1],I_{n+2}\leftarrow[-y_{i},-1]$, $n\leftarrow
n+2$

13: return $n,I$

14:end procedure

15:procedure RobustPolynomialLearning($x,d,T$) — Theorem 1.2

16: $(n,I)\leftarrow\textsc{GenerateIntervals}$($d$)

17: for $j=1\to n$ do

18: $w_{j}\leftarrow|I_{j}|/2$

19: Choose $t_{j}$ from $I_{j}$ uniformly at random

20: $z_{j}\leftarrow x(T\cdot\frac{t_{j}+1}{2})$

21: end for

22: $\widetilde{A}_{j,i}\leftarrow t_{j}^{i}$, for each
$(j,i)\in[n]\times\\{0,1,\cdots,d\\}$

23: $\alpha\leftarrow$ LinearRegressionW($\widetilde{A},\widetilde{b}=z,w$)

24: $Q(t)\leftarrow\sum_{i=0}^{d}\alpha_{i}t^{i}$

25: return $\widetilde{Q}(t)=Q(T\cdot\frac{t+1}{2})$

26:end procedure

27:procedure RobustPolynomialLearning+($x,d,T$) — Theorem 4.5 — a.k.a.
SignalRecovery1Cluster

28: $R\leftarrow\Theta(d)$

29: $(n,I)\leftarrow\textsc{GenerateIntervals}$($d$)

30: $w_{j}\leftarrow|I_{j}|/2$, for each $j\in[n]$

31: for $i=1\to R$ do

32: $Q_{i}\leftarrow\textsc{RobustPolynomialLearning}$($x,d,T$)

33: end for

34: Choose $t_{j}$ from $I_{j}$ uniformly at random, for each $j\in[n]$

35: for $i=1\to R$ do

36: $Q_{i}(t_{1}),Q_{i}(t_{2}),\cdots,Q_{i}(t_{n})\leftarrow$
MultipointEvaluation($Q_{i},\\{t_{1},t_{2},\cdots,t_{n}\\}$)

37: end for

38:
$\widetilde{Q}_{j}\leftarrow\underset{i\in[R]}{\operatorname*{median}}\leavevmode\nobreak\
Q_{i}(t_{j})$, for each $j\in[n]$

39: $\widetilde{A}_{j,i}\leftarrow t_{j}^{i}$, for each
$(j,i)\in[n]\times\\{0,1,\cdots,d\\}$

40: $\alpha\leftarrow$
LinearRegressionW($\widetilde{A},\widetilde{b}=\widetilde{Q},w$)

41: return $Q(t)\leftarrow\sum_{i=0}^{d}\alpha_{i}t^{i}$

42:end procedure

Algorithm 6

1:procedure LocateKSignal($x,H,G,T,\Delta,\sigma,b,z_{\operatorname{emp}}$) —
Clain 7.27