$\displaystyle\int_{C_{i}}|\widehat{H\cdot x_{S^{*}}}(f)|^{2}\mathrm{d}f\geq
T\mathcal{N}_{1}^{2}/k\geq\frac{1}{\varepsilon_{2}}\int_{C_{i}}|\widehat{H\cdot
x}(f)|^{2}\mathrm{d}f$ (48)

where the first steps follows from $C_{i}\subset\cup_{f_{j}\in S^{*}}C_{j}$,
the second step follows from $C_{i}\not\subset\cup_{f_{j}\in S}C_{j}$.

Thus,

$\displaystyle\int_{C_{i}}|\widehat{H\cdot g^{\prime}}(f)|^{2}\mathrm{d}f=$
$\displaystyle~{}\int_{C_{i}}|\widehat{H\cdot(x-x_{S^{*}})}(f)|^{2}\mathrm{d}f$
$\displaystyle\geq$ $\displaystyle~{}\left(\sqrt{\int_{C_{i}}|\widehat{H\cdot
x_{S^{*}}}(f)|^{2}\mathrm{d}f}-\sqrt{\int_{C_{i}}|\widehat{H\cdot
x}(f)|^{2}\mathrm{d}f}\right)^{2}$ $\displaystyle\geq$
$\displaystyle~{}(\frac{1}{\sqrt{\varepsilon_{2}}}-1)^{2}\int_{C_{i}}|\widehat{H\cdot
x}(f)|^{2}\mathrm{d}f$ $\displaystyle\geq$
$\displaystyle~{}\frac{1}{2{\varepsilon_{2}}}\int_{C_{i}}|\widehat{H\cdot
x}(f)|^{2}\mathrm{d}f,$ (49)

where the first step follows from the definition of $g^{\prime}$, the second
step follows from triangle inequality, the third step follows from Eq. (48),
the last step follows from $\varepsilon_{2}\leq 0.1$.

##### Bound $\|H\cdot x-H\cdot x_{S}\|_{T}$.

Let $I^{\prime}=\cup_{f_{j}\in S^{*}\backslash S}C_{j}$, then we have that,

$\displaystyle T\|H\cdot x-H\cdot x_{S}\|^{2}_{T}\leq$
$\displaystyle~{}\int_{-\infty}^{\infty}|H\cdot x(t)-H\cdot
x_{S}(t)|^{2}\mathrm{d}t$ $\displaystyle=$
$\displaystyle~{}\int_{-\infty}^{\infty}|(\widehat{H\cdot x}-\widehat{H\cdot
x_{S}})(f)|^{2}\mathrm{d}f$ $\displaystyle=$
$\displaystyle~{}\int_{I^{\prime}}|(\widehat{H\cdot x}-\widehat{H\cdot
x_{S}})(f)|^{2}\mathrm{d}f+\int_{\overline{I^{\prime}}}|(\widehat{H\cdot
x}-\widehat{H\cdot x_{S}})(f)|^{2}\mathrm{d}f$ (50)

where the first step follows from the definition of the norm, the second step
follows from Parseval’s theorem, the third step follows from
$I^{\prime}\cup\overline{I^{\prime}}=[-\infty,\infty]$.

##### Bound $\|H\cdot x_{S^{*}}-H\cdot x_{S}\|_{T}$

We can upper-bound it as follows:

$\displaystyle T\|H\cdot x_{S^{*}}-H\cdot x_{S}\|^{2}_{T}\leq$
$\displaystyle~{}\int_{-\infty}^{\infty}|H\cdot x_{S^{*}}(t)-H\cdot
x_{S}(t)|^{2}\mathrm{d}t$ $\displaystyle=$
$\displaystyle~{}\int_{-\infty}^{\infty}|(\widehat{H\cdot
x_{S^{*}}}-\widehat{H\cdot x_{S}})(f)|^{2}\mathrm{d}f$ $\displaystyle=$
$\displaystyle~{}\int_{I^{\prime}}|(\widehat{H\cdot x_{S^{*}}}-\widehat{H\cdot
x_{S}})(f)|^{2}\mathrm{d}f+\int_{\overline{I^{\prime}}}|(\widehat{H\cdot
x_{S^{*}}}-\widehat{H\cdot x_{S}})(f)|^{2}\mathrm{d}f$ $\displaystyle=$
$\displaystyle~{}\int_{I^{\prime}}|(\widehat{H\cdot x_{S^{*}}}-\widehat{H\cdot
x_{S}})(f)|^{2}\mathrm{d}f$ (51)

where the first step follows from the definition of the norm, the second step
follows from Parseval’s theorem, the third step follows from
$I^{\prime}\cup\overline{I^{\prime}}=[-\infty,\infty]$, the last step follows
from $(\cup_{f_{j}\in S^{*}/S}C_{j})\cap\overline{I^{\prime}}=\emptyset$.

##### Putting it all together.

By Eqs. (50) and (51), we get that

$\displaystyle~{}T\|H\cdot x_{S^{*}}-H\cdot x_{S}\|_{T}^{2}+T\|H\cdot x-H\cdot
x_{S}\|_{T}^{2}$ $\displaystyle\leq$
$\displaystyle~{}\int_{I^{\prime}}|(\widehat{H\cdot x_{S^{*}}}-\widehat{H\cdot
x_{S}})(f)|^{2}\mathrm{d}f+\int_{I^{\prime}}|(\widehat{H\cdot
x}-\widehat{H\cdot
x_{S}})(f)|^{2}\mathrm{d}f+\int_{\overline{I^{\prime}}}|(\widehat{H\cdot
x}-\widehat{H\cdot x_{S}})(f)|^{2}\mathrm{d}f.$

For the first integral, we have

$\displaystyle\sqrt{\int_{I^{\prime}}|(\widehat{H\cdot
x_{S^{*}}}-\widehat{H\cdot x_{S}})(f)|^{2}\mathrm{d}f}=$
$\displaystyle~{}\sqrt{\int_{I^{\prime}}|\widehat{H\cdot
x_{S^{*}}}(f)|^{2}\mathrm{d}f}$ $\displaystyle\leq$
$\displaystyle~{}\sqrt{\int_{I^{\prime}}|\widehat{H\cdot
x}(f)|^{2}\mathrm{d}f}+\sqrt{\int_{I^{\prime}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f}$ $\displaystyle\leq$
$\displaystyle~{}\sqrt{2\varepsilon_{2}\int_{I^{\prime}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f}+\sqrt{\int_{I^{\prime}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f}$ $\displaystyle\leq$
$\displaystyle~{}(1+\sqrt{2\varepsilon_{2}})\sqrt{\int_{I^{\prime}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f},$ (52)

where the first step follows from $(\cup_{f_{j}\in S}C_{j})\cap
I^{\prime}=\emptyset$, the second step follows from triangle inequality, the
third step follows from Eq. (49), the last step is straightforward.

For the second integral, we have

$\displaystyle\int_{I^{\prime}}|(\widehat{H\cdot x}-\widehat{H\cdot
x_{S}})(f)|^{2}\mathrm{d}f=$
$\displaystyle~{}\int_{I^{\prime}}|\widehat{H\cdot x}(f)|^{2}\mathrm{d}f$
$\displaystyle\leq$
$\displaystyle~{}2\varepsilon_{2}\int_{I^{\prime}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f,$ (53)

where the first step follows from $(\cup_{f_{j}\in S}C_{j})\cap
I^{\prime}=\emptyset$, the second step follows from Eq. (49).

For the third integral, together with the $\int_{I^{\prime}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f$ term in the first integral’s upper bound (Eq.
(52)), we have

$\displaystyle~{}\int_{\overline{I^{\prime}}}|(\widehat{H\cdot
x}-\widehat{H\cdot
x_{S}})(f)|^{2}\mathrm{d}f+\int_{I^{\prime}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f$ $\displaystyle=$
$\displaystyle~{}\int_{\overline{I^{\prime}}}|\widehat{H\cdot(x_{S^{*}}+g^{\prime}-x_{S})}(f)|^{2}\mathrm{d}f+\int_{I^{\prime}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f$ $\displaystyle=$
$\displaystyle~{}\int_{\overline{I^{\prime}}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f+\int_{I^{\prime}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f$ $\displaystyle=$
$\displaystyle~{}\int_{-\infty}^{\infty}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f$ $\displaystyle=$
$\displaystyle~{}\int_{-\infty}^{\infty}|H\cdot g^{\prime}(t)|^{2}\mathrm{d}t$
$\displaystyle=$ $\displaystyle~{}T\|H\cdot g^{\prime}(t)\|_{T}^{2}$
$\displaystyle\leq$ $\displaystyle~{}T\|g^{\prime}\|_{T}^{2},$ (54)

where the first step follows from the definition of $g^{\prime}$, the second
step follows from $(\cup_{f_{j}\in
S^{*}}C_{j})\cap\overline{I^{\prime}}=(\cup_{f_{j}\in S}C_{j})$, the third
step follows from $I^{\prime}\cup\overline{I^{\prime}}=[-\infty,\infty]$, the
forth step follows from Parseval’s theorem, the fifth step follows from
$g^{\prime}(t)=0,\forall t\not\in[0,T]$, the last step follows from $H(t)\leq
1$ by Remark 12.8.

Furthermore, we have that

$\displaystyle\int_{I^{\prime}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f\leq\int_{-\infty}^{\infty}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f\leq T\|g^{\prime}(t)\|_{T}^{2}.$ (55)

Therefore, we conclude that

$\displaystyle~{}T\|H\cdot x_{S^{*}}-H\cdot x_{S}\|^{2}_{T}+T\|H\cdot x-H\cdot
x_{S}\|^{2}_{T}$ $\displaystyle\leq$ $\displaystyle~{}T\|H\cdot
x_{S^{*}}-H\cdot x_{S}\|^{2}_{T}+\int_{I^{\prime}}|(\widehat{H\cdot
x}-\widehat{H\cdot
x_{S}})(f)|^{2}\mathrm{d}f+\int_{\overline{I^{\prime}}}|(\widehat{H\cdot
x}-\widehat{H\cdot x_{S}})(f)|^{2}\mathrm{d}f$ $\displaystyle\leq$
$\displaystyle~{}\int_{I^{\prime}}|(\widehat{H\cdot x_{S^{*}}}-\widehat{H\cdot
x_{S}})(f)|^{2}\mathrm{d}f+\int_{I^{\prime}}|(\widehat{H\cdot
x}-\widehat{H\cdot
x_{S}})(f)|^{2}\mathrm{d}f+\int_{\overline{I^{\prime}}}|(\widehat{H\cdot
x}-\widehat{H\cdot x_{S}})(f)|^{2}\mathrm{d}f$ $\displaystyle\leq$
$\displaystyle~{}(1+\sqrt{\varepsilon_{2}})^{2}{\int_{I^{\prime}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f}+\int_{I^{\prime}}|(\widehat{H\cdot
x}-\widehat{H\cdot
x_{S}})(f)|^{2}\mathrm{d}f+\int_{\overline{I^{\prime}}}|(\widehat{H\cdot
x}-\widehat{H\cdot x_{S}})(f)|^{2}\mathrm{d}f$ $\displaystyle\leq$
$\displaystyle~{}(1+\sqrt{\varepsilon_{2}})^{2}{\int_{I^{\prime}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f}+2\varepsilon_{2}\int_{I^{\prime}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f+\int_{\overline{I^{\prime}}}|(\widehat{H\cdot
x}-\widehat{H\cdot x_{S}})(f)|^{2}\mathrm{d}f$ $\displaystyle=$
$\displaystyle~{}O(\sqrt{\varepsilon_{2}})\int_{I^{\prime}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f+\int_{I^{\prime}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f+\int_{\overline{I^{\prime}}}|(\widehat{H\cdot
x}-\widehat{H\cdot x_{S}})(f)|^{2}\mathrm{d}f$ $\displaystyle\leq$
$\displaystyle~{}O(\sqrt{\varepsilon_{2}})T\|g^{\prime}\|_{T}^{2}+\int_{I^{\prime}}|\widehat{H\cdot
g^{\prime}}(f)|^{2}\mathrm{d}f+\int_{\overline{I^{\prime}}}|(\widehat{H\cdot
x}-\widehat{H\cdot x_{S}})(f)|^{2}\mathrm{d}f$ $\displaystyle\leq$
$\displaystyle~{}O(\sqrt{\varepsilon_{2}})T\|g^{\prime}\|_{T}^{2}+T\|g^{\prime}\|_{T}^{2}$
$\displaystyle=$
$\displaystyle~{}(1+O(\sqrt{\varepsilon_{2}}))T\|g^{\prime}\|_{T}^{2}$

where the first step follows from Eq. (50), the second step follows from Eq.
(51), the third step follows from Eq. (52), the forth step follows from Eq.
(53), the fifth step follows from $(1+\sqrt{2\varepsilon_{2}})^{2}\leq
1+O(\sqrt{\varepsilon_{2}})$, the sixth step follows from Eq. (55), the
seventh step follows from Eq. (54), the last step is straightforward.

The lemma is then proved. ∎

As a consequence, we can easily bound $\|x_{S^{*}}-x_{S}\|_{T}$ as follows.

######  Corollary 12.22.

Let $S^{*}$ and $S$ be defined as in Lemma 12.21. Then, we have that,

$\displaystyle\|x_{S^{*}}-x_{S}\|^{2}_{T}\leq(1+O(\sqrt{\varepsilon_{2}}))\|x-x_{S^{*}}\|_{T}^{2}$

###### Proof.

We have that,

$\displaystyle\|x_{S^{*}}-x_{S}\|^{2}_{T}\leq(1+2\varepsilon)\|H\cdot
x_{S^{*}}-H\cdot
x_{S}\|^{2}_{T}\leq(1+2\varepsilon)(1+O(\sqrt{\varepsilon_{2}}))\|x-x_{S^{*}}\|_{T}^{2}$

where the first step follows from Lemma 12.7 Property vi@, the second step
follows from Lemma 12.21 and $\varepsilon=\varepsilon_{2}$. ∎

In Lemma 12.21, we introduce an extra term $\|H\cdot x-H\cdot x_{S}\|_{T}$.
The following lemma shows that this term appears in the approximation error
$\|x-x_{S}\|_{T}$, which can be used to upper-bound the Signal Estimation’s
error.

######  Lemma 12.23 (Decomposing the approximation error of recoverable
signal).

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 observable signal. Let
$\mathcal{N}_{1}^{2}:=\|g(t)\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2}$. Let
$C_{1},\cdots,C_{l}$ are the $\mathcal{N}_{1}$-heavy clusters from Definition
12.11. Let $S^{*}$ denotes the set of frequencies
$f^{*}\in\\{f_{j}\\}_{j\in[k]}$ such that, $f^{*}\in C_{i}$ for some
$i\in[l]$, and

$\displaystyle\int_{C_{i}}|\widehat{x^{*}\cdot H}(f)|^{2}\mathrm{d}f\geq
T\mathcal{N}_{1}^{2}/k,$

Let $S$ denotes the set of frequencies $f^{*}\in S^{*}$ such that, $f^{*}\in
C_{j}$ for some $j\in[l]$, and

$\displaystyle\int_{C_{j}}|\widehat{x\cdot
H}(f)|^{2}\mathrm{d}f\geq\varepsilon_{2}T\mathcal{N}_{1}^{2}/k,$

Then we have that,

$\displaystyle\|x-x_{S}\|_{T}\leq\|H(x-x_{S})\|_{T}+\|g\|_{T}+O({\varepsilon})\|x^{*}-x_{S}\|_{T}.$

###### Proof.

We first decompose $\|x-x_{S}\|_{T}$ into the part that passes through the
filter $H$ and the part that does not pass through $H$:

$\displaystyle\|x-x_{S}\|^{2}_{T}\leq$
$\displaystyle~{}\|H(x-x_{S})\|^{2}_{T}+\|(1-H)(x-x_{S})\|^{2}_{T}$
$\displaystyle\leq$
$\displaystyle~{}\|H(x-x_{S})\|^{2}_{T}+\|(1-H)(x-x^{*})\|^{2}_{T}+\|(1-H)(x^{*}-x_{S})\|^{2}_{T}$
$\displaystyle\leq$
$\displaystyle~{}\|H(x-x_{S})\|^{2}_{T}+\|(1-H)g\|^{2}_{T}+\|(1-H)(x^{*}-x_{S})\|^{2}_{T},$

where the first step follows from triangle inequality, the second step follows
from triangle inequality, the last step follows from the definition of $g$.

For the second term, we have that

$\displaystyle\|(1-H)g\|^{2}_{T}\leq\|g\|^{2}_{T},$

by Remark 12.8.

For the third term, we have that,

$\displaystyle\|(1-H)(x^{*}-x_{S})\|^{2}_{T}=\|x^{*}-x_{S}\|^{2}_{T}-\|H(x^{*}-x_{S})\|^{2}_{T}\leq\varepsilon\|x^{*}-x_{S}\|^{2}_{T},$

where the first step follows from $1-H>0$, the second step follows from
$x^{*}-x_{S}$ is $k$-Fourier-sparse, thus combine Property vi@ of Lemma 12.7,
we have that
$\|H(x^{*}-x_{S})\|^{2}_{T}\geq(1-\varepsilon)\|x^{*}-x_{S}\|_{T}^{2}$.

Combining them together, we prove the lemma. ∎

###  12.6 Technical tools iii@: HashToBins

In this section, we provide some definitions and technical lemmas for the
HashToBins procedure, which will be very helpful for frequency estimation.

HashToBins partitions the frequency coordinates into $B=O(k)$ bins and
collects rotated magnitudes in each bins. Ideally, each bins only contains a
single ground-truth frequency, which allows us to recover its magnitude.

More specifically, HashToBins first randomly hashes the frequency coordinates
into the interval $[0,1]$. After equally dividing $[0,1]$ into $O(k)$ small
bins, each coordinate lays in a different bin. This step can be implemented by
multiplying the signal in the frequency domain with a _period pulse function_
$G^{(j)}_{\sigma,b}$. Then, even if the signal does not have frequency gap,
the HashToBins procedure can still partition it into several one-cluster
signals with high probability.

######  Definition 12.24 (Hash function, [CKPS16]).

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

######  Claim 12.25 (Collision probability, [CKPS16]).

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

  1. I.

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

  2. II.

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

######  Definition 12.26 (Filter for bins).

Given $B>1$, $\delta>0$, $\alpha>0$, let $G(t):=G_{B,\delta,\alpha}(2\pi t)$
where $G_{B,\delta,\alpha}$ is defined in Definition 12.9. For any
$\sigma>0,b\in\mathbb{R}$ and $j\in[B]$. define

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

and its Fourier transformation:

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

######  Definition 12.27 ($(\varepsilon_{0},\Delta_{0})$-one-cluster signal,
[CKPS16]).

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

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

######  Definition 12.28 (Well-isolation, [CKPS16]).

We say that a frequency $f^{*}$ is _well-isolated_ under the hashing
$(\sigma,b)$ if, for $j=h_{\sigma,b}(f^{*})$ and
$\overline{I_{f^{*}}}=(-\infty,\infty)\setminus(f^{*}-\Delta_{0},f^{*}+\Delta_{0})$,

$\int_{\overline{I_{f^{*}}}}\big{|}(\widehat{H\cdot
x}\cdot\widehat{G}_{\sigma,b}^{(j)})(f)\big{|}^{2}\mathrm{d}f\lesssim\varepsilon_{0}\cdot
T\mathcal{N}_{2}^{2}/k,$

where
$\mathcal{N}_{2}^{2}:=\varepsilon_{1}\varepsilon_{2}(\|g(t)\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2})$.

######  Lemma 12.29 (Well-isolation implies one-cluster signal, a variation of
Lemma 7.20 in [CKPS16]).

Let $f^{*}$ satisfy

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

where
$\mathcal{N}_{2}^{2}:=\varepsilon_{1}\varepsilon_{2}(\|g(t)\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2})$.
Let $\widehat{z}=\widehat{x^{*}\cdot H}\cdot\widehat{G}^{(j)}_{\sigma,b}$
where $j=h_{\sigma,b}(f^{*})$. If $f^{*}$ is well-isolated, then $z$ and
$\widehat{z}$ satisfying Property ii@ of one-cluster signal (Definition
12.27), i.e.,

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

######  Lemma 12.30 (Well-isolation by randomized hashing, [CKPS16]).

Given $B=\Theta(k/(\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}))$ and
$\sigma\in[\frac{1}{4B\Delta_{0}},\frac{1}{2B\Delta_{0}}]$ chosen uniformly at
random. Let $f^{*}$ be any frequency. Then $f^{*}$ is well-isolated by a
hashing $(\sigma,b)$ with probability at least $0.9$.

###### Proof.

Let $S^{\prime}=\\{f_{i}\\}_{i\in[k]}\cap\overline{I_{f^{*}}}$. By Claim
12.25, with probability at least $(1-1/B)^{k}\geq 1-k/B\geq
1-\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}\geq 0.99$, for all the
frequencies $f\in S^{\prime}$, we have that $h_{\sigma,b}(f^{*})\neq
h_{\sigma,b}(f)$.

Hence,

$\displaystyle\int_{\overline{I_{f^{*}}}}|\widehat{x^{*}\cdot
H}\cdot\widehat{G}^{(j)}_{\sigma,b}(f)|^{2}\mathrm{d}f\lesssim$
$\displaystyle~{}\frac{\delta^{2}}{k^{2}}\int_{\overline{I_{f^{*}}}}|\widehat{x^{*}\cdot
H}(f)|^{2}\mathrm{d}f$ $\displaystyle\leq$
$\displaystyle~{}\frac{\delta^{2}}{k^{2}}\int_{-\infty}^{\infty}|\widehat{x^{*}\cdot
H}(f)|^{2}\mathrm{d}f$ $\displaystyle=$
$\displaystyle~{}\frac{\delta^{2}}{k^{2}}\int_{-\infty}^{\infty}|{x^{*}\cdot
H}(t)|^{2}\mathrm{d}t$ $\displaystyle=$
$\displaystyle~{}\frac{\delta^{2}}{k^{2}}\int_{[-\infty,\infty]\backslash[0,T]}|{x^{*}\cdot
H}(t)|^{2}\mathrm{d}t+\frac{\delta^{2}}{k^{2}}\int_{[0,T]}|{x^{*}\cdot
H}(t)|^{2}\mathrm{d}t$ $\displaystyle\leq$
$\displaystyle~{}\frac{\delta^{2}}{k^{2}}\int_{[-\infty,\infty]\backslash[0,T]}|{x^{*}\cdot
H}(t)|^{2}\mathrm{d}t+\frac{\delta^{2}}{k^{2}}T\|{x^{*}}\|_{T}^{2}$
$\displaystyle\leq$
$\displaystyle~{}\frac{\delta^{2}(1+\delta)}{k^{2}}T\|{x^{*}}\|_{T}^{2}$ (56)

where the first step follows by the Property iii@ in the Lemma 12.10 that
$|\widehat{G}(f)|\leq\delta/k$, which implies that
$|\widehat{G}^{(j)}_{\sigma,b}(f)|\leq O(\delta/k)$ for $f\in S^{\prime}$, the
second step follows from $\overline{I_{f^{*}}}\subset[-\infty,\infty]$, the
third step follows from Parseval’s theorem, the forth step is straight
forward, the fifth step follows from the property vi@ of Lemma 12.7, the sixth
step follows from v@ of Lemma 12.7.

Moreover, let $I^{\prime}$ denote the set of frequencies that hash into the
same bin as $f^{*}$, then we have that,

$\displaystyle\int_{\overline{I_{f^{*}}}}|\widehat{g\cdot
H}\cdot\widehat{G}^{(j)}_{\sigma,b}(f)|^{2}\mathrm{d}f\leq$
$\displaystyle~{}\int_{I^{\prime}}|\widehat{g\cdot
H}\cdot\widehat{G}^{(j)}_{\sigma,b}(f)|^{2}\mathrm{d}f+\int_{\overline{I^{\prime}}}|\widehat{g\cdot
H}\cdot\widehat{G}^{(j)}_{\sigma,b}(f)|^{2}\mathrm{d}f$
$\displaystyle\lesssim$ $\displaystyle~{}\int_{I^{\prime}}|\widehat{g\cdot
H}(f)|^{2}\mathrm{d}f+\int_{\overline{I^{\prime}}}|\widehat{g\cdot
H}\cdot\widehat{G}^{(j)}_{\sigma,b}(f)|^{2}\mathrm{d}f$
$\displaystyle\lesssim$ $\displaystyle~{}\int_{I^{\prime}}|\widehat{g\cdot
H}(f)|^{2}\mathrm{d}f+\frac{\delta^{2}}{k^{2}}\int_{\overline{I^{\prime}}}|\widehat{g\cdot
H}(f)|^{2}\mathrm{d}f$ $\displaystyle\leq$
$\displaystyle~{}\int_{I^{\prime}}|\widehat{g\cdot
H}(f)|^{2}\mathrm{d}f+\frac{\delta^{2}T}{k^{2}}\|g\|_{T}^{2}$ (57)

where the first step follows from
$I^{\prime}\cup\overline{I^{\prime}}=[-\infty,\infty]$, the second step
follows from for any $f\in\mathbb{R}$,
$\widehat{G}^{(j)}_{\sigma,b}(f)\lesssim 1$, the third step follows from for
any $f\in\overline{I^{\prime}}$,
$\widehat{G}^{(j)}_{\sigma,b}(f)\lesssim\delta/k$, the last step follows from

$\int_{\overline{I^{\prime}}}|\widehat{g\cdot
H}(f)|^{2}\mathrm{d}f\leq\int_{-\infty}^{\infty}|\widehat{g\cdot
H}(f)|^{2}\mathrm{d}f=\int_{-\infty}^{\infty}|{g\cdot
H}(t)|^{2}\mathrm{d}t=T\|{g\cdot H}\|_{T}^{2}\leq T\|{g}\|_{T}^{2}.$

where the first step follows from $\overline{I^{\prime}}\in[-\infty,\infty]$,
the second step follows from Parseval’s theorem, the third step follows from
$g(t)=0,\forall t\not\in[0,T]$, the last step follows from Remark 12.8.

Next, we consider

$\displaystyle\operatorname*{{\mathbb{E}}}_{\sigma,b}\left[\int_{I^{\prime}}|\widehat{g\cdot
H}(f)|^{2}\mathrm{d}f\right]\eqsim$
$\displaystyle~{}\frac{1}{B}\int_{-\infty}^{\infty}|\widehat{g\cdot
H}(f)|^{2}\mathrm{d}f$ $\displaystyle\lesssim$
$\displaystyle~{}\frac{\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}}{k}T\|{g}\|_{T}^{2}$

where the first step follows from $\sigma,b$ are chosen randomly, the second
step follows from $\int_{-\infty}^{\infty}|\widehat{g\cdot
H}(f)|^{2}\mathrm{d}f\leq T\|{g}\|_{T}^{2}$.

Thus, by Markov inequality, with probability at least $0.99$,

$\displaystyle\int_{I^{\prime}}|\widehat{g\cdot
H}(f)|^{2}\mathrm{d}f\lesssim\frac{\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}}{k}T\|{g}\|_{T}^{2}.$
(58)

Finally, we can conclude that

$\displaystyle\int_{\overline{I_{f^{*}}}}|(\widehat{H\cdot
x}\cdot\widehat{G}_{\sigma,b}^{(j)})(f)|^{2}\mathrm{d}f=$
$\displaystyle~{}\int_{\overline{I_{f^{*}}}}|(\widehat{H\cdot(x^{*}+g)}\cdot\widehat{G}_{\sigma,b}^{(j)})(f)|^{2}\mathrm{d}f$
$\displaystyle\leq$
$\displaystyle~{}2\int_{\overline{I_{f^{*}}}}|\widehat{x^{*}\cdot
H}\cdot\widehat{G}^{(j)}_{\sigma,b}(f)|^{2}\mathrm{d}f+2\int_{\overline{I_{f^{*}}}}|\widehat{g\cdot
H}\cdot\widehat{G}^{(j)}_{\sigma,b}(f)|^{2}\mathrm{d}f$
$\displaystyle\lesssim$
$\displaystyle~{}\frac{\delta^{2}(1+\delta)}{k^{2}}T\|{x^{*}}\|_{T}^{2}+2\int_{\overline{I_{f^{*}}}}|\widehat{g\cdot
H}\cdot\widehat{G}^{(j)}_{\sigma,b}(f)|^{2}\mathrm{d}f$
$\displaystyle\lesssim$
$\displaystyle~{}\frac{\delta^{2}(1+\delta)}{k^{2}}T\|{x^{*}}\|_{T}^{2}+\frac{\delta^{2}T}{k^{2}}\|g\|_{T}^{2}+\int_{I^{\prime}}|\widehat{g\cdot
H}(f)|^{2}\mathrm{d}f$ $\displaystyle\lesssim$
$\displaystyle~{}\frac{\delta^{2}(1+\delta)}{k^{2}}T\|{x^{*}}\|_{T}^{2}+\frac{\delta^{2}T}{k^{2}}\|g\|_{T}^{2}+\frac{\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}}{k}T\|{g}\|_{T}^{2}$
$\displaystyle=$
$\displaystyle~{}\frac{\delta(1+\delta)}{\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}k}\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}T\delta\|{x^{*}}\|_{T}^{2}/k+(\frac{\delta^{2}}{\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}k}+1)\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}T\|{g}\|_{T}^{2}/k$
$\displaystyle\leq$
$\displaystyle~{}\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}T\delta\|{x^{*}}\|_{T}^{2}/k+2\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}T\|{g}\|_{T}^{2}/k$
$\displaystyle\lesssim$ $\displaystyle~{}\varepsilon_{0}\cdot
T\mathcal{N}_{2}^{2}/k,$

where the first step follows from the definition of $g$, the second step
follows from $(a+b)^{2}\leq 2a^{2}+2b^{2}$, the third step follows from Eq.
(56), the forth step follows from Eq. (57), the fifth step follows from Eq.
(58), the sixth step is straightforward, the seventh step follows from
$\frac{\delta(1+\delta)}{\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}k}\leq
1$ and
$(\frac{\delta^{2}}{\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}k}+1)\leq 2$,
the last step follows from the definition of $\mathcal{N}_{2}^{2}$.

∎

###  12.7 High signal-to-noise ratio (SNR) band approximation

In the this section, we will give the upper bound of
$\|x_{S_{f}}(t)-x_{S}(t)\|_{T}$.

######  Definition 12.31 (High SNR and Recoverable Set).

For $j\in[B]$, let $z^{*}_{j}(t):=(x^{*}\cdot H)\cdot G^{(j)}_{\sigma,b}$, we
define the set as follows

$\displaystyle
S_{g_{1}}:=\Big{\\{}j\in[B]~{}{|}~{}\|g_{j}(t)\|^{2}_{T}\leq(1-c\varepsilon)\cdot\|z_{j}^{*}(t)\|^{2}_{T}\Big{\\}}$

where $c$ is constant. And we also give the definition of recoverable set
which is the same with $s$ above

$\displaystyle S_{g_{2}}:=\Big{\\{}j\in[B]~{}{|}~{}\exists
f_{0},h_{\sigma,b}(f_{0})=j~{}{\text{and}}~{}\int_{f^{*}-\Delta}^{f^{*}+\Delta}|\widehat{x\cdot
H}(f)|^{2}\mathrm{d}f\geq T\mathcal{N}_{2}^{2}/k\Big{\\}}$

where
$\mathcal{N}_{2}^{2}:=\varepsilon_{1}\varepsilon_{2}(\|g(t)\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2}$.

And then we define a High SNR and recoverable set as follows

$\displaystyle S_{g}:=S_{g_{1}}\cap S_{g_{2}}$

Let $S_{f}:=\\{j\in[k]|h_{\sigma,b}(f_{g})\in S_{g}\\}\cap S$. We have
$x_{S_{f}}(t):=\sum_{j\in S_{f}}v_{j}e^{2\pi if_{j}t}$

######  Remark 12.32.

In the left part of the paper, we focus on the frequency in set $S_{f}$ which
is a subset of the recoverable frequency set $S$.

The following lemma shows that for any recoverable frequency (i.e., those
satisfy Eq. (59)), HashToBins will output a one-cluster and high signal-to-
noise ratio signal around it with high probability.

######  Lemma 12.33 (HashToBins for recoverable frequency).

Let $f^{*}\in[-F,F]$ satisfy:

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

where
$\mathcal{N}_{2}^{2}:=\varepsilon_{1}\varepsilon_{2}(\|g(t)\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2})$.

For a random hashing $(\sigma,b)$, let $j=h_{\sigma,b}(f^{*})$ be the bucket
that $f^{*}$ maps to under the hash such that $z=(x\cdot
H)*G^{(j)}_{\sigma,b}$ and $\widehat{z}=\widehat{x\cdot
H}\cdot\widehat{G}^{(j)}_{\sigma,b}$. With probability at least $0.9$, $z(t)$
is an $(\varepsilon_{0},\Delta_{0})$-one-cluster signal around $f^{*}$.

###### Proof.

The proof consists of two parts. In part 1, we prove that $z(t)$ satisfies
Property I of the one-cluster signal around $f^{*}$ (Definition 12.27). In
part 2, we prove that $z(t)$ satisfies Property II of Definition 12.27.

Part 1. Let region $I_{f^{*}}=(f^{*}-\Delta,f^{*}+\Delta)$ with complement
$\overline{I_{f^{*}}}=(-\infty,\infty)\setminus I_{f^{*}}$.

Next, with probability at least $0.99$, we have that

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

where the probability follows from $\Delta_{0}>1000\Delta$, the first step
follows from Property I of $G$ in Lemma 12.10, the second step follows from
Eq. (59).

On the other hand, $f^{*}$ is well-isolated with probability $0.9$, thus by
the definition of well-isolated, we have that

$\int_{\overline{I_{f^{*}}}}|\widehat{z}(f)|^{2}\mathrm{d}f\lesssim\varepsilon_{0}T\mathcal{N}_{2}^{2}/k.$

Hence, $\widehat{z}$ satisfies the Property I (in Definition 12.27) of one-
mountain recovery.

Part 2. By Lemma 12.29, we know that $(x^{*}\cdot H)*G^{(j)}_{\sigma,b}$
always satisfies Property ii@ (in Definition 12.27):

$\displaystyle\int_{0}^{T}|x^{*}(t)H(t)*G_{\sigma,b}^{(j)}(t)|^{2}\mathrm{d}t\geq(1-\varepsilon_{0})\int_{-\infty}^{+\infty}|x^{*}(t)H(t)*G_{\sigma,b}^{(j)}(t)|^{2}\mathrm{d}t$

As a result, by $[-\infty,\infty]=[-\infty,0]\cup[0,T]\cup[T,\infty]$,

$\displaystyle\varepsilon_{0}\int_{-\infty}^{+\infty}|x^{*}(t)H(t)*G_{\sigma,b}^{(j)}(t)|^{2}\mathrm{d}t\geq\int_{-\infty}^{0}|x^{*}(t)H(t)*G_{\sigma,b}^{(j)}(t)|^{2}\mathrm{d}t+\int_{T}^{\infty}|x^{*}(t)H(t)*G_{\sigma,b}^{(j)}(t)|^{2}\mathrm{d}t$
(60)

Then, we claim that

$\displaystyle\int_{-\infty}^{\infty}|x(t)\cdot
H(t)*G_{\sigma,b}^{(j)}(t)|^{2}\mathrm{d}t=$
$\displaystyle~{}\int_{-\infty}^{\infty}|\widehat{x\cdot
H}(f)\cdot\widehat{G}_{\sigma,b}^{(j)}(f)|^{2}\mathrm{d}f$ $\displaystyle\geq$
$\displaystyle~{}\int_{f^{*}-\Delta}^{f^{*}+\Delta}|\widehat{x\cdot
H}(f)\cdot\widehat{G}_{\sigma,b}^{(j)}(f)|^{2}\mathrm{d}f$
$\displaystyle\gtrsim$
$\displaystyle~{}\int_{f^{*}-\Delta}^{f^{*}+\Delta}|\widehat{x\cdot
H}(f)|^{2}\mathrm{d}f$ $\displaystyle\geq$
$\displaystyle~{}T\mathcal{N}_{2}^{2}/k,$ (61)

where the first step follows from Parseval’s theorem, the second step follows
from $[f^{*}-\Delta,f^{*}+\Delta]\subset[-\infty,\infty]$, the third step
holds with probability at least $0.99$ and follows from
$\Delta_{0}>1000\Delta$ and Property i@ of Lemma 12.10, the last step follows
from the definition of $f^{*}$.

By Definition 12.31, we have that

$\displaystyle\int_{-\infty}^{+\infty}|g(t)\cdot
H(t)*G_{\sigma,b}^{(j)}(t)|^{2}\mathrm{d}t=$
$\displaystyle~{}\int_{0}^{T}|g(t)\cdot
H(t)*G_{\sigma,b}^{(j)}(t)|^{2}\mathrm{d}t$ (62) $\displaystyle\leq$
$\displaystyle~{}(1-c\varepsilon)\int_{0}^{T}|z_{j}^{*}(t)|^{2}\mathrm{d}t$
$\displaystyle\leq$
$\displaystyle~{}(1-c\varepsilon)\int_{-\infty}^{+\infty}|z_{j}^{*}(t)|^{2}\mathrm{d}t$
$\displaystyle\leq$
$\displaystyle~{}\int_{-\infty}^{+\infty}(1-c\varepsilon)|x(t)\cdot
H(t)*G_{\sigma,b}^{(j)}(t)|^{2}\mathrm{d}t$

where the first step from $g(t)=0,\forall t\not\in[0,T]$, the second step
follows from Definition 12.31, the third step follows from simple algebra, the
last step is due to Definition of $z_{j}^{*}(t)$.

Then, we claim that

$\displaystyle\sqrt{\int_{-\infty}^{\infty}|x^{*}\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}\leq$
$\displaystyle~{}\sqrt{\int_{-\infty}^{\infty}|(x^{*}+g)\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}+\sqrt{\int_{-\infty}^{\infty}|g\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}$ $\displaystyle\leq$
$\displaystyle~{}(1+\sqrt{\varepsilon_{0}\varepsilon_{2}})\sqrt{\int_{-\infty}^{\infty}|(x^{*}+g)\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}$ $\displaystyle\lesssim$
$\displaystyle~{}\sqrt{\int_{-\infty}^{\infty}|(x^{*}+g)\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}$ (63)

where the first step follows from triangle inequality, the second step follows
from Eq. (62), the last step follows from $\varepsilon_{0},\varepsilon_{2}\leq
1$.

Next, we consider

$\displaystyle\sqrt{\int_{T}^{\infty}|(x^{*}+g)\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}\leq$
$\displaystyle~{}\sqrt{\int_{T}^{\infty}|x^{*}\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}+\sqrt{\int_{T}^{\infty}|g\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}$ $\displaystyle\leq$
$\displaystyle~{}\sqrt{\varepsilon_{0}\int_{-\infty}^{\infty}|x^{*}\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}+\sqrt{\int_{T}^{\infty}|g\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}$ $\displaystyle\leq$
$\displaystyle~{}\sqrt{\varepsilon_{0}\int_{-\infty}^{\infty}|x^{*}\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}+\sqrt{\varepsilon_{0}\int_{-\infty}^{\infty}|x\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}$ $\displaystyle\lesssim$
$\displaystyle~{}\sqrt{\varepsilon_{0}\int_{-\infty}^{\infty}|x\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t},$ (64)

where the first step follows from triangle inequality, the second step follows
from Eq. (60), the third step follows from Eq. (62), the forth step follows
from Eq. (63).

Similarly,

$\displaystyle\sqrt{\int_{-\infty}^{0}|(x^{*}+g)\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}\lesssim$
$\displaystyle~{}\sqrt{\varepsilon_{0}\int_{-\infty}^{\infty}|x\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}$ (65)

Combine equations above, we have that,

$\displaystyle~{}\sqrt{\int_{-\infty}^{0}|(x^{*}+g)\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t+\int_{T}^{\infty}|(x^{*}+g)\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}$ $\displaystyle\leq$
$\displaystyle~{}\sqrt{\int_{-\infty}^{0}|(x^{*}+g)\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}+\sqrt{\int_{T}^{\infty}|(x^{*}+g)\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}$ $\displaystyle\lesssim$
$\displaystyle~{}\sqrt{\varepsilon_{0}\int_{-\infty}^{\infty}|x\cdot
H*G^{(j)}_{\sigma,b}|^{2}\mathrm{d}t}$

where the first step follows from $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$, the
second step follows from Eq. (64) and Eq. (65).

Hence, we have that $z=(x^{*}+g)\cdot H*G^{(j)}_{\sigma,b}$ satisfies Property
ii@ (in Definition 12.27) with probability $0.95$.

∎

###  12.8 Ultra-high sensitivity frequency estimation

In this section, we improve the high sensitivity frequency estimation in
Section 12.3 with even higher sensitivity, using the results in previous
sections. More specifically, we show how to estimate the frequencies of the
signal $x_{S}$ whose frequencies are only $\varepsilon^{2}{\cal N}$-heavy,
while in section 12.3 the recoverable signal’s frequencies are ${\cal
N}$-heavy.

######  Lemma 12.34 (Frequency estimation for one-cluster signal, [CKPS16]).

For a sufficiently small constant $\varepsilon_{0}>0$, any $f_{0}\in[-F,F]$,
and $\Delta_{0}>0$, given an $(\varepsilon_{0},\Delta_{0})$-one-cluster signal
$z(t)$ around $f_{0}$, Procedure FrequencyRecovery1Cluster, returns
$\widetilde{f_{0}}$ with
$|\widetilde{f}_{0}-f_{0}|\lesssim\Delta_{0}\cdot\sqrt{\Delta_{0}T}$ with
probability at least $1-2^{-\Omega(k)}$.

The following theorem shows the algorithm for ultra-high sensitivity frequency
estimation.

######  Theorem 12.35 (Ultra-high sensitivity frequency estimation algorithm
with low success probability).

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 observable signal where $\|g(t)\|_{T}^{2}\leq
c\|x^{*}(t)\|_{T}^{2}$ for a sufficiently small constant $c$. Then Procedure
FrequencyRecoveryKCluster returns a set $L$ of
$O(k/(\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}))$ frequencies that cover
all $\mathcal{N}_{2}$-heavy clusters and have high SNR (See Definition 12.31)
of $x^{*}$, which uses
$\mathrm{poly}(k,\varepsilon^{-1},\varepsilon_{0}^{-1},\varepsilon_{1}^{-1},\varepsilon_{2}^{-1},\log(1/\delta))\log(FT)$
samples and
$\mathrm{poly}(k,\varepsilon^{-1},\varepsilon_{0}^{-1},\varepsilon_{1}^{-1},\varepsilon_{2}^{-1},\log(1/\delta))\log^{2}(FT)$
time.

In particular, for
$\Delta_{0}=\varepsilon^{-1}\mathrm{poly}(k,\log(1/\delta))/T$ and
$\mathcal{N}_{2}^{2}:=\varepsilon_{1}\varepsilon_{2}(\|g(t)\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2})$,
with probability $0.9$, for any $f^{*}$ with

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

there exists an $\widetilde{f}\in L$ satisfying

$|f^{*}-\widetilde{f}|\lesssim\Delta_{0}\sqrt{\Delta_{0}T}.$

###### Proof.

By Lemma 12.33 and Lemma 12.34, we prove the theorem. ∎

######  Theorem 12.36 (Ultra-high sensitivity frequency estimation algorithm
with high success probability).

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 observable signal where $\|g(t)\|_{T}^{2}\leq
c\|x^{*}(t)\|_{T}^{2}$ for a sufficiently small constant $c$. Then Procedure
FrequencyRecoveryKCluster returns a set $L$ of
$O(k/(\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}))$ frequencies that covers
all $\mathcal{N}_{2}$-heavy clusters of $x^{*}$, which uses
$\mathrm{poly}(k,\varepsilon^{-1},\varepsilon_{0}^{-1},\varepsilon_{1}^{-1},\varepsilon_{2}^{-1},\log(1/\delta))\log(FT)$
samples and
$\mathrm{poly}(k,\varepsilon^{-1},\varepsilon_{0}^{-1},\varepsilon_{1}^{-1},\varepsilon_{2}^{-1},\log(1/\delta))\log^{2}(FT)$
time.

In particular, for
$\Delta_{0}=\varepsilon^{-1}\mathrm{poly}(k,\log(1/\delta))/T$ and
$\mathcal{N}_{2}^{2}:=\varepsilon_{1}\varepsilon_{2}(\|g(t)\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2})$,
with probability $1-2^{-\Omega(k)}$, for any $f^{*}$ with

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

there exists an $\widetilde{f}\in L$ satisfying

$|f^{*}-\widetilde{f}|\lesssim\Delta_{0}\sqrt{\Delta_{0}T}.$

The following lemma shows the approximation error guarantee for the
recoverable signal $x_{S}$ of the ultra-high sensitivity frequency estimation
algorithm (Theorem 12.36).

######  Lemma 12.37 (Recoverable signal’s approximation error guarantee).

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 observable signal. Let
$\mathcal{N}_{1}^{2}:=\varepsilon_{1}(\|g(t)\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2})$.
Let $C_{1},\cdots,C_{l}$ are the $\mathcal{N}_{1}$-heavy clusters from
Definition 12.11. Let $S^{*}$ denotes the set of frequencies
$f^{*}\in\\{f_{j}\\}_{j\in[k]}$ such that, $f^{*}\in C_{i}$ for some
$i\in[l]$, and

$\displaystyle\int_{C_{i}}|\widehat{x^{*}\cdot H}(f)|^{2}\mathrm{d}f\geq
T\mathcal{N}_{1}^{2}/k,$

Let $S$ denotes the set of frequencies $f^{*}\in S^{*}$ such that, $f^{*}\in
C_{j}$ for some $j\in[l]$, and

$\displaystyle\int_{C_{j}}|\widehat{x\cdot
H}(f)|^{2}\mathrm{d}f\geq\varepsilon_{2}T\mathcal{N}_{1}^{2}/k,$

Then, we have that,

$\displaystyle\|x-x_{S}\|_{T}+\|x_{S}-x^{*}\|_{T}\leq(1+\sqrt{2}+O(\sqrt{\varepsilon}))\|g\|_{T}+O(\sqrt{\delta})\|x^{*}\|_{T}.$

###### Proof.

Following from the fact that $\sqrt{1+\varepsilon}=1+O(\varepsilon)$ for
$\varepsilon<1$, we have

$\mathcal{N}_{1}=\sqrt{\varepsilon_{1}(\|g\|_{T}^{2}+\delta\|x^{*}\|_{T}^{2})}\leq\sqrt{\varepsilon_{1}}\|g\|_{T}+\sqrt{\delta\varepsilon_{1}}\|x^{*}\|_{T}$

We have that

$\displaystyle\|x^{*}-x_{S}\|_{T}\leq$
$\displaystyle~{}\|x_{S^{*}}-x_{S}\|_{T}+\|x^{*}-x_{S^{*}}\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}(1+O(\sqrt{\varepsilon_{2}}))\|x-x_{S^{*}}\|_{T}+\|x^{*}-x_{S^{*}}\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}(1+O(\sqrt{\varepsilon_{2}}))\|x-x^{*}\|_{T}+(2+O(\sqrt{\varepsilon_{2}}))\|x^{*}-x_{S^{*}}\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}(1+O(\sqrt{\varepsilon_{2}}))\|g\|_{T}+(2+O(\sqrt{\varepsilon_{2}}+\varepsilon))\mathcal{N}_{1}$
(68)

where the first step follows from triangle inequality, the second step follows
from Corollary 12.22, the third step follows from triangle inequality, the
forth step follows from Claim 12.12.

Thus, we have that

$\displaystyle\|x-x_{S^{*}}\|_{T}\leq$
$\displaystyle~{}\|x-x^{*}\|_{T}+\|x^{*}-x_{S^{*}}\|_{T}$ $\displaystyle\leq$
$\displaystyle~{}\|g\|_{T}+\|x^{*}-x_{S^{*}}\|_{T}$ $\displaystyle\leq$
$\displaystyle~{}\|g\|_{T}+(1+\varepsilon)\mathcal{N}_{1}$ (69)

where the first step follows from triangle inequality, the second step follows
from the definition of $g$, the third step follows from Claim 12.12.

Therefore,

$\displaystyle~{}\|x-x_{S}\|_{T}+\|x_{S}-x^{*}\|_{T}$ $\displaystyle\leq$
$\displaystyle~{}(\|H(x-x_{S})\|_{T}+\|g\|_{T}+O(\varepsilon)\|x^{*}-x_{S}\|_{T})+\|x_{S}-x^{*}\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}(\|H(x-x_{S})\|_{T}+\|g\|_{T}+O(\varepsilon)\|x^{*}-x_{S}\|_{T})+\|x_{S}-x_{S^{*}}\|_{T}+\|x_{S^{*}}-x^{*}\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}(\|H(x-x_{S})\|_{T}+\|g\|_{T}+O(\varepsilon)\|x^{*}-x_{S}\|_{T})+(1+2\varepsilon)\|H(x_{S}-x_{S^{*}})\|_{T}+\|x_{S^{*}}-x^{*}\|_{T}$
$\displaystyle=$
$\displaystyle~{}\|g\|_{T}+O(\varepsilon)\|x^{*}-x_{S}\|_{T}+(1+O(\varepsilon))(\|H(x-x_{S})\|_{T}+\|H(x_{S}-x_{S^{*}})\|_{T})+\|x_{S^{*}}-x^{*}\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}\|g\|_{T}+O(\varepsilon)\|x^{*}-x_{S}\|_{T}+(1+O(\varepsilon))(\|H(x-x_{S})\|_{T}+\|H(x_{S}-x_{S^{*}})\|_{T})+(1+\varepsilon)\mathcal{N}_{1}$
$\displaystyle\leq$
$\displaystyle~{}\|g\|_{T}+O(\varepsilon)\|x^{*}-x_{S}\|_{T}+(1+O(\varepsilon))\sqrt{2}\sqrt{\|H(x-x_{S})\|^{2}_{T}+\|H(x_{S}-x_{S^{*}})\|^{2}_{T}}+(1+\varepsilon)\mathcal{N}_{1}$
$\displaystyle\leq$
$\displaystyle~{}\|g\|_{T}+O(\varepsilon)\|x^{*}-x_{S}\|_{T}+(1+O(\varepsilon))(1+O(\sqrt{\varepsilon_{2}}))\sqrt{2}\|x-x_{S^{*}}\|_{T}+(1+\varepsilon)\mathcal{N}_{1}$
$\displaystyle\leq$
$\displaystyle~{}\|g\|_{T}+O(\varepsilon)((1+O(\sqrt{\varepsilon_{2}}))\|g\|_{T}+(2+O(\sqrt{\varepsilon_{2}}+\varepsilon))\mathcal{N}_{1})$
$\displaystyle~{}+(1+O(\varepsilon))(1+O(\sqrt{\varepsilon_{2}}))\sqrt{2}\|x-x_{S^{*}}\|_{T}+(1+\varepsilon)\mathcal{N}_{1}$
$\displaystyle\leq$
$\displaystyle~{}\|g\|_{T}+O(\varepsilon)((1+O(\sqrt{\varepsilon_{2}}))\|g\|_{T}+(2+O(\sqrt{\varepsilon_{2}}+\varepsilon))\mathcal{N}_{1})$
$\displaystyle~{}+(\sqrt{2}+O(\varepsilon+\sqrt{\varepsilon_{2}}))(\|g\|_{T}+(1+\varepsilon)\mathcal{N}_{1})+(1+\varepsilon)\mathcal{N}_{1}$
$\displaystyle\leq$
$\displaystyle~{}(1+\sqrt{2}+O(\sqrt{\varepsilon}))\|g\|_{T}+O(\sqrt{\delta})\|x^{*}\|_{T},$

where the first step follows from Lemma 12.23, the second step follows from
triangle inequality, the third step follows from $x_{S}-x_{S^{*}}$ being
$k$-Fourier-sparse and Property vi@ of Lemma 12.7, the forth step change the
order of the terms, the fifth step follows from Claim 12.12, the sixth step
follows from
$\|H(x-x_{S})\|_{T}+\|H(x_{S}-x_{S^{*}})\|_{T}\leq\sqrt{2}\sqrt{\|H(x-x_{S})\|_{T}^{2}+\|H(x_{S}-x_{S^{*}})\|_{T}^{2}}$,
the seventh step follows from Lemma 12.21, the eighth step follows from Eq.
(68), the ninth step follows from Eq. (69), the last step follows from
$\varepsilon=\varepsilon_{0}=\varepsilon_{1}=\varepsilon_{2}$. ∎

The following lemma shows that the recoverable signal $x_{S}(t)$’s energy is
close to the observation signal $x(t)$.

######  Lemma 12.38 (Recoverable signal’s energy).

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 observable signal. Let
$\mathcal{N}_{1}^{2}:=\varepsilon_{1}(\|g(t)\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2})$.
Let $C_{1},\cdots,C_{l}$ are the $\mathcal{N}_{1}$-heavy clusters from
Definition 12.11. Let $S^{*}$ denotes the set of frequencies
$f^{*}\in\\{f_{j}\\}_{j\in[k]}$ such that, $f^{*}\in C_{i}$ for some
$i\in[l]$, and

$\displaystyle\int_{C_{i}}|\widehat{x^{*}\cdot H}(f)|^{2}\mathrm{d}f\geq
T\mathcal{N}_{1}^{2}/k,$

Let $S$ denotes the set of frequencies $f^{*}\in S^{*}$ such that, $f^{*}\in
C_{j}$ for some $j\in[l]$, and

$\displaystyle\int_{C_{j}}|\widehat{x\cdot
H}(f)|^{2}\mathrm{d}f\geq\varepsilon_{2}T\mathcal{N}_{1}^{2}/k,$

Then, we have that,

$\displaystyle\|x_{S}\|_{T}\lesssim\|g\|_{T}+\|x^{*}\|_{T}$

###### Proof.

We have that,

$\displaystyle\|x_{S}\|_{T}\leq$
$\displaystyle~{}\|x_{S^{*}}-x^{*}\|_{T}+\|x_{S}-x_{S^{*}}\|_{T}+\|x^{*}\|_{T}$
$\displaystyle\lesssim$
$\displaystyle~{}\|x_{S^{*}}-x^{*}\|_{T}+\|x-x_{S^{*}}\|_{T}+\|x^{*}\|_{T}$
$\displaystyle\lesssim$
$\displaystyle~{}\|x_{S^{*}}-x^{*}\|_{T}+\|x-x^{*}\|_{T}+\|x^{*}\|_{T}$
$\displaystyle\leq$ $\displaystyle~{}\|g\|_{T}+\|x^{*}\|_{T},$

where the first step follows from triangle inequality, the second step follows
from Corollary 12.22, the third step follows from triangle inequality, the
forth step follows from Claim 12.12. ∎

###  12.9 High SNR and Recoverable signals

######  Lemma 12.39 (High SNR and recoverable approximation error guarantee).

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 observable signal. Let
$\mathcal{N}_{1}^{2}:=\varepsilon_{1}(\|g(t)\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2})$.
Let $C_{1},\cdots,C_{l}$ are the $\mathcal{N}_{1}$-heavy clusters from
Definition 12.11. Let $S^{*}$ denotes the set of frequencies
$f^{*}\in\\{f_{j}\\}_{j\in[k]}$ such that, $f^{*}\in C_{i}$ for some
$i\in[l]$, and

$\displaystyle\int_{C_{i}}|\widehat{x^{*}\cdot H}(f)|^{2}\mathrm{d}f\geq
T\mathcal{N}_{1}^{2}/k,$

Let $S$ denotes the set of frequencies $f^{*}\in S^{*}$ such that, $f^{*}\in
C_{j}$ for some $j\in[l]$, and

$\displaystyle\int_{C_{j}}|\widehat{x\cdot
H}(f)|^{2}\mathrm{d}f\geq\varepsilon_{2}T\mathcal{N}_{1}^{2}/k,$

And $S_{f}$ is defined in Definition 12.31. Then, we have that,

$\displaystyle\|x_{S_{f}}-x_{S}\|_{T}\leq(1+O(\varepsilon))\cdot\|g(t)\|_{T}$
(70)

###### Proof.

By Definition 12.31, we have that

$\displaystyle S_{f}\subseteq S.$

And then for any $f\in S\setminus S_{f},j=h_{\sigma,b}(f)$, we have that

$\displaystyle\|(g\cdot H(t))*G^{(j)}_{\sigma,b}(t)\|^{2}_{T}\geq$
$\displaystyle(1-c\cdot\varepsilon)\|(x^{*}\cdot
H(t))*G^{(j)}_{\sigma,b}(t)\|^{2}_{T}$

where the first step follows from Definition 12.31, the second step is from
simple algebra.

Let $\mathcal{T}=S\setminus S_{f}$. And for any $j\in[B]$, if
$j\in[B]\setminus S_{g}$, $\mathcal{T}_{j}=\\{i\in
S|h_{\sigma,b}(f_{i})=j\\}$. Otherwise, $\mathcal{T}_{j}=\emptyset$. Moreover,
we have that for any
$f\in\mathrm{supp}(\widehat{x}_{\mathcal{T}_{j}}*\widehat{H})$,

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

From $\mathrm{Property~{}\@slowromancap vi@}$ of Lemma 12.7, we have that

$\displaystyle(1-\varepsilon)\cdot\int_{-\infty}^{+\infty}|x^{*}(t)|^{2}\mathrm{d}t\leq\int_{-\infty}^{+\infty}|x^{*}(t)\cdot
H(t)|^{2}\mathrm{d}t\leq\int_{-\infty}^{+\infty}|x^{*}(t)|^{2}\mathrm{d}t.$
(72)

By Lemma 12.29, we know that $(x^{*}\cdot H)*G^{(j)}_{\sigma,b}$ always
satisfies Property ii@ (in Definition 12.27):

$\displaystyle~{}T\|x^{*}(t)H(t)*G_{\sigma,b}^{(j)}(t)\|^{2}_{T}$
$\displaystyle=$
$\displaystyle~{}\int_{0}^{T}|x^{*}(t)H(t)*G_{\sigma,b}^{(j)}(t)|^{2}\mathrm{d}t$
$\displaystyle\geq$
$\displaystyle~{}(1-\varepsilon_{0})\int_{-\infty}^{+\infty}|x^{*}(t)H(t)*G_{\sigma,b}^{(j)}(t)|^{2}\mathrm{d}t$
$\displaystyle=$
$\displaystyle~{}(1-\varepsilon_{0})\int_{-\infty}^{+\infty}|(\widehat{x}^{*}(f)*\widehat{H}(f))*\widehat{G}_{\sigma,b}^{(j)}(f)|^{2}\mathrm{d}f$
$\displaystyle=$
$\displaystyle~{}(1-\varepsilon_{0})(\int_{-\infty}^{+\infty}|(\widehat{x}^{*}(f)*\widehat{H}(f))\cdot\widehat{G}_{\sigma,b}^{(j)}(f)|^{2}\mathrm{d}f+\int_{-\infty}^{+\infty}|(\widehat{x}^{*}(f)*\widehat{H}(f))\cdot\widehat{G}_{\sigma,b}^{(j)}(f)|^{2}\mathrm{d}f)$
$\displaystyle\geq$
$\displaystyle~{}(1-\varepsilon_{0})\cdot\int_{-\infty}^{+\infty}|(\widehat{x}^{*}(f)*\widehat{H}(f))\cdot\widehat{G}_{\sigma,b}^{(j)}(f)|^{2}\mathrm{d}f$
$\displaystyle\geq$
$\displaystyle~{}(1-\varepsilon_{0})\cdot\int_{-\infty}^{+\infty}|(\widehat{x}^{*}(f)*\widehat{H}(f))|^{2}\mathrm{d}f$
(73)

where the first step follows from the definition of the norm, the second step
is from Lemma 12.29, the third step is due to Parseval’s Theorem, the forth
step is based on the Large Offset event not happening, the fifth step is based
on simple algebra, the last step is because of Lemma 12.29.

We also have that

$\displaystyle~{}T\|x_{S_{f}}(t)-x_{S}(t)\|_{T}^{2}$ $\displaystyle=$
$\displaystyle~{}T\|x_{\mathcal{T}}\|_{T}^{2}$ $\displaystyle\leq$
$\displaystyle~{}(T/(1-\varepsilon)^{2})\cdot\|x_{\mathcal{T}}(t)\cdot
H(t)\|^{2}_{T}$ $\displaystyle=$
$\displaystyle~{}\frac{1}{1-\varepsilon^{2}}\cdot\int_{0}^{T}|x_{\mathcal{T}}(t)\cdot
H(t)|^{2}\mathrm{d}t$ $\displaystyle\leq$
$\displaystyle~{}\frac{1}{1-\varepsilon^{2}}\cdot\int_{-\infty}^{\infty}|x_{\mathcal{T}}(t)\cdot
H(t)|^{2}\mathrm{d}t$ $\displaystyle=$
$\displaystyle~{}\frac{1}{1-\varepsilon^{2}}\cdot\int_{-\infty}^{\infty}|\widehat{x}_{\mathcal{T}}(f)*\widehat{H}(f)|^{2}\mathrm{d}f$
$\displaystyle=$
$\displaystyle~{}\frac{1}{1-\varepsilon^{2}}\cdot\sum_{j=1}^{B}\int_{-\infty}^{\infty}|\widehat{x}_{\mathcal{T}_{j}}(f)*\widehat{H}(f)|^{2}\mathrm{d}f$
$\displaystyle\leq$
$\displaystyle~{}\frac{k^{2}}{(1-\varepsilon)^{2}(k-\delta)^{2}}\cdot\sum_{j\in
B\setminus S_{g}}T\|(x^{*}(t)\cdot H(t))*G^{(j)}_{\sigma,b}(t))\|^{2}_{T}$
$\displaystyle\leq$
$\displaystyle~{}\frac{k^{2}}{(1-c\varepsilon)(1-\varepsilon)^{2}(k-\delta)^{2}}\cdot\sum_{j\in
B\setminus S_{g}}T\|(g(t)\cdot H(t))*G^{(j)}_{\sigma,b}(t))\|^{2}_{T}$ (74)

where the first step follows from Definition of $\mathcal{T}$, the second step
follows from Eq. (72), the third step is based on definition of norm, the
forth step follows from simple algebra, the fifth step follows from Parseval’s
Theorem, the six step is due to Large Offset event not happening, the seventh
step is due to Lemma 12.29, the eighth step follows from Eq. (70).

In the following, we have that

$\displaystyle~{}\sum_{j\in[B]}T\cdot\|(g(t)\cdot
H(t))*G^{(j)}_{\sigma,b}(t)\|^{2}_{T}$ $\displaystyle\leq$
$\displaystyle~{}\sum_{j\in[B]}\int_{0}^{T}|(g^{*}(t)\cdot
H(t))*G^{(j)}_{\sigma,b}(t)|^{2}\mathrm{d}t$ $\displaystyle\leq$
$\displaystyle~{}\sum_{j\in[B]}\int_{-\infty}^{\infty}|(g^{*}(t)\cdot
H(t))*G^{(j)}_{\sigma,b}(t)|^{2}\mathrm{d}t$ $\displaystyle=$
$\displaystyle~{}\sum_{j\in[B]}\int_{-\infty}^{\infty}|(\widehat{g}(f)*\widehat{H}(f))\cdot\widehat{G}_{\sigma,b}^{(j)}(f)|^{2}\mathrm{d}f$
$\displaystyle\leq$
$\displaystyle~{}\frac{k^{2}}{(k-\delta)^{2}}\int_{-\infty}^{\infty}|\widehat{g}(f)*\widehat{H}(f)|^{2}\mathrm{d}f$
$\displaystyle=$
$\displaystyle~{}\frac{k^{2}}{(k-\delta)^{2}}\cdot\int_{-\infty}^{\infty}|g(t)\cdot
H(t)|^{2}\mathrm{d}t$ $\displaystyle=$
$\displaystyle~{}\frac{k^{2}}{(k-\delta)^{2}}\cdot\int_{0}^{T}|g(t)\cdot
H(t)|^{2}\mathrm{d}t$ $\displaystyle\leq$
$\displaystyle~{}\frac{k^{2}}{(k-\delta)^{2}}\cdot\int_{0}^{T}|g(t)|^{2}\mathrm{d}t$
$\displaystyle=$
$\displaystyle~{}T\frac{k^{2}}{(k-\delta)^{2}}\|g(t)\|^{2}_{T}$ (75)

where the first step is due to the definition of norm, the second step follows
from $g(t)=0$ when $t\notin[0,T]$, the third step follows from Parseval’s
Theorem, the forth step is because of Lemma 12.29, the fifth step is from
Parseval’s Theorem, the sixth step is based on $g(t)=0$ when $t\notin[0,T]$,
the seventh step is from $|H(t)|^{2}\leq 1$, the last step is from the
definition of norm. We have that

$\displaystyle~{}T\|x_{S_{f}}(t)-x_{S}(t)\|_{T}^{2}$ $\displaystyle\leq$
$\displaystyle~{}\frac{k^{2}}{(1-c\varepsilon)(1-\varepsilon)^{2}(k-\delta)^{2}}\cdot\sum_{j\in
B\setminus S_{g}}T\|(g^{*}(t)\cdot H(t))*G^{(j)}_{\sigma,b}(t))\|^{2}_{T}$
$\displaystyle\leq$
$\displaystyle~{}\frac{k^{2}}{(1-c\varepsilon)(1-\varepsilon)^{2}(k-\delta)^{2}}\sum_{j\in[B]}T\|(g^{*}(t)\cdot
H(t))*G^{(j)}_{\sigma,b}(t))\|^{2}_{T}$ $\displaystyle\leq$
$\displaystyle~{}\frac{k^{4}}{(1-c\varepsilon)(1-\varepsilon)^{2}(k-\delta)^{4}}T\|g(t)\|^{2}_{T}$
$\displaystyle\leq$ $\displaystyle~{}(1+O(\varepsilon))T\|g(t)\|^{2}_{T}$

where the first step follows from Eq. (12.9), the second step follows from
simple algebra, the third step is due to Eq.(12.9), the forth step is because
of the reason that $\delta$ is much smaller than $\varepsilon$ and
$\varepsilon<1$. ∎

######  Lemma 12.40 (High SNR signal’s energy).

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 observable signal. Let
$\mathcal{N}_{1}^{2}:=\varepsilon_{1}(\|g(t)\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2})$.
Let $C_{1},\cdots,C_{l}$ are the $\mathcal{N}_{1}$-heavy clusters from
Definition 12.11. Let $S^{*}$ denotes the set of frequencies
$f^{*}\in\\{f_{j}\\}_{j\in[k]}$ such that, $f^{*}\in C_{i}$ for some
$i\in[l]$, and

$\displaystyle\int_{C_{i}}|\widehat{x^{*}\cdot H}(f)|^{2}\mathrm{d}f\geq
T\mathcal{N}_{1}^{2}/k,$

Let $S$ denotes the set of frequencies $f^{*}\in S^{*}$ such that, $f^{*}\in
C_{j}$ for some $j\in[l]$, and

$\displaystyle\int_{C_{j}}|\widehat{x\cdot
H}(f)|^{2}\mathrm{d}f\geq\varepsilon_{2}T\mathcal{N}_{1}^{2}/k,$

Let $S_{f}$ be defined in Definition 12.31. Then, we have that,

$\displaystyle\|x_{S_{f}}\|_{T}\leq(1+O(\varepsilon))\|g\|_{T}+\|x^{*}\|_{T}$

###### Proof.

We have that,

$\displaystyle\|x_{S_{f}}\|_{T}\leq$
$\displaystyle~{}\|x_{S_{f}}-x_{S}\|_{T}+\|x_{S^{*}}-x^{*}\|_{T}+\|x_{S}-x_{S^{*}}\|_{T}+\|x^{*}\|_{T}$
$\displaystyle\lesssim$
$\displaystyle~{}\|x_{S_{f}}-x_{S}\|_{T}+\|x_{S^{*}}-x^{*}\|_{T}+\|x-x_{S^{*}}\|_{T}+\|x^{*}\|_{T}$
$\displaystyle\lesssim$
$\displaystyle~{}\|x_{S_{f}}-x_{S}\|_{T}+\|x_{S^{*}}-x^{*}\|_{T}+\|x-x^{*}\|_{T}+\|x^{*}\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}\|x_{S_{f}}-x_{S}\|_{T}+\|g\|_{T}+\|x^{*}\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}(1+O(\varepsilon))\|g\|_{T}+\|x^{*}\|_{T},$

where the first step follows from triangle inequality, the second step follows
from Corollary 12.22, the third step follows from triangle inequality, the
forth step follows from Claim 12.12, where the last step follows from Lemma
12.39. ∎

###  12.10 $(3+\sqrt{2}+\varepsilon)$-approximate algorithm

In this section, we prove the main result: a
$(3+\sqrt{2}+\varepsilon)$-approximate Fourier interpolation algorithm, which
significantly improves the accuracy of [CKPS16]’s result.

######  Theorem 12.41 (Fourier interpolation with
$(3+\sqrt{2}+\varepsilon)$-approximation error).

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
$y(t)$ such that with probability at least $1-2^{-\Omega(k)}$,

$\|y-x^{*}\|_{T}\leq(3+\sqrt{2}+\varepsilon)\|g\|_{T}+\delta\|x^{*}\|_{T}.$

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

###### Proof.

Let
$\mathcal{N}_{2}^{2}:=\varepsilon_{1}\varepsilon_{2}(\|g(t)\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2})$,
$\mathcal{N}_{1}^{2}:=\varepsilon_{1}(\|g(t)\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2})$
be the heavy cluster parameter.

First, by Lemma 12.12, there is a set of frequencies $S^{*}\subset[k]$ and
$x_{S^{*}}(t)=\underset{j\in S^{*}}{\sum}v_{j}e^{2\pi\mathbf{i}f_{j}t}$ such
that

$\displaystyle\|x_{S^{*}}-x^{*}\|_{T}^{2}\leq(1+\varepsilon)\mathcal{N}_{1}^{2}.$
(76)

Furthermore, each $f_{j}$ with $j\in S^{*}$ belongs to an
$\mathcal{N}_{1}$-heavy cluster $C_{j}$ with respect to the filter function
$H$ defined in Definition 12.6.

By Definition 12.11 of heavy cluster, it holds that

$\displaystyle\int_{C_{j}}|\widehat{H\cdot x^{*}}(f)|^{2}\mathrm{d}f\geq
T\mathcal{N}_{1}^{2}/k.$

By Definition 12.11, we also have $|C_{j}|\leq k\cdot\Delta_{h}$, where
$\Delta_{h}$ is the bandwidth of $\widehat{H}$.

Let $\Delta\in\mathbb{R}_{+}$, and $\Delta>k\cdot\Delta_{h}$, which implies
that $C_{j}\subseteq[f_{j}-\Delta,f_{j}+\Delta]$. Thus, we have

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

By Corollary 12.22, there is a set of frequencies $S\subset S^{*}$ and
$x_{S}(t)=\underset{j\in S}{\sum}v_{j}e^{2\pi\mathbf{i}f_{j}t}$ such that

$\displaystyle\|x_{S}-x_{S^{*}}\|_{T}^{2}\leq(1+O(\sqrt{\varepsilon_{2}}))\|x-x_{S^{*}}\|_{T}^{2}.$

Let $g^{\prime}=x-x_{S^{*}}$.

In the following part, we will only focus on recovering the high SNR
frequency. Let $S_{f}$ be defined in Definition 12.31. It’s to know
$S_{f}\subset S$ By applying Theorem 12.36, there is an algorithm that outputs
a set of frequencies $L\subset\mathbb{R}$ such that,
$|L|=O(k/(\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}))$, and with
probability at least $1-2^{-\Omega(k)}$, for any $f_{j}$ with $j\in S_{f}$,
there is a $\widetilde{f}\in L$ such that,

$\displaystyle|f_{j}-\widetilde{f}|\lesssim\Delta\sqrt{\Delta T}.$

We define a map $p:\mathbb{R}\rightarrow L$ as follows:

$\displaystyle p(f):=\arg\min_{\widetilde{f}\in
L}~{}|f-\widetilde{f}|~{}~{}~{}\forall f\in\mathbb{R}.$

Then, $x_{S}(t)$ can be expressed as

$\displaystyle x_{S_{f}}(t)=$ $\displaystyle~{}\sum_{j\in
S_{f}}v_{j}e^{2\pi\mathbf{i}f_{j}t}$ $\displaystyle=$
$\displaystyle~{}\sum_{j\in S_{f}}v_{j}e^{2\pi\mathbf{i}\cdot p(f_{j})t}\cdot
e^{2\pi\mathbf{i}\cdot(f_{j}-p(f_{j}))t}$ $\displaystyle=$
$\displaystyle~{}\sum_{\widetilde{f}\in
L}e^{2\pi\mathbf{i}\widetilde{f}t}\cdot\sum_{j\in
S_{f}:~{}p(f_{j})=\widetilde{f}}v_{j}e^{2\pi\mathbf{i}(f_{j}-\widetilde{f})t},$

where the first step follows from the definition of $x_{S}(t)$, the last step
follows from interchanging the summations.

For each $\widetilde{f}_{i}\in L$, by Corollary 12.2 with
$x^{*}=x_{S},\Delta=\Delta\sqrt{\Delta T}$, we have that there exist degree
$d=O(T\Delta\sqrt{\Delta T}+k^{3}\log k+k\log 1/\delta)$ polynomials
$P_{i}(t)$ corresponding to $\widetilde{f}_{i}\in L$ such that,

$\displaystyle\|x_{S_{f}}(t)-\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\|_{T}\leq\sqrt{\delta}\|x_{S_{f}}(t)\|_{T}$
(77)

Define the following function family:

$\displaystyle\mathcal{F}:=\mathrm{span}\Big{\\{}e^{2\pi\mathbf{i}\widetilde{f}t}\cdot
t^{j}~{}{|}~{}\forall\widetilde{f}\in L,j\in\\{0,1,\dots,d\\}\Big{\\}}.$

Note that $\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\in{\cal F}$.

By Claim 12.16, for function family $\cal F$,
$K_{\mathrm{Uniform[0,T]}}=O((|L|d)^{4}\log^{3}(|L|d))$.

By Lemma 12.18, we have that, choosing a set $W$ of
$O(\varepsilon^{-1}K_{\mathrm{Uniform[0,T]}}\log(|L|d/\rho))$ i.i.d. samples
uniformly at random over duration $[0,T]$ is a $(\varepsilon,\rho)$-WBSP.

By Lemma 12.19, there is an algorithm that runs in
$O(\varepsilon^{-1}|W|(|L|d)^{\omega-1}\log(1/\rho))$-time using samples in
$W$, and outputs $y^{\prime}(t)\in{\cal F}$ such that, with probability
$1-\rho$,

$\displaystyle\Big{\|}y^{\prime}(t)-\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\Big{\|}_{T}\leq(1+\varepsilon)\Big{\|}x(t)-\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\Big{\|}_{T}$ (78)

Then by Lemma 12.3, we have that there is a $(kd)$-Fourier-sparse signal
$y(t)$, such that

$\displaystyle\|y-y^{\prime}\|_{T}\leq\delta^{\prime}$ (79)

where $\delta^{\prime}>0$ is any positive real number, thus, $y$ can be
arbitrarily close to $y^{\prime}$.

Moreover, the sparsity of $y(t)$ is

$\displaystyle kd=kO(T\Delta\sqrt{\Delta T}+k^{3}\log k+k\log
1/\delta)=\mathrm{poly}(k,\varepsilon^{-1},\log(1/\delta)).$

Therefore, the total approximation error can be upper bounded as follows:

$\displaystyle~{}\|y-x^{*}\|_{T}$ $\displaystyle\leq$
$\displaystyle~{}\|y-y^{\prime}\|_{T}+\Big{\|}y^{\prime}-\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\Big{\|}_{T}+\Big{\|}\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)-x^{*}\Big{\|}_{T}$ (Triangle
inequality) $\displaystyle\leq$
$\displaystyle~{}(1+0.1\varepsilon)\Big{\|}y^{\prime}-\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\Big{\|}_{T}+\Big{\|}\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)-x^{*}\Big{\|}_{T}$ (Eq. (79))
$\displaystyle\leq$
$\displaystyle~{}(1+2\varepsilon)\Big{\|}x-\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\Big{\|}_{T}+\Big{\|}\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)-x^{*}\Big{\|}_{T}$ (Eq. (78))
$\displaystyle\leq$
$\displaystyle~{}(1+2\varepsilon)(\|x-x_{S_{f}}\|_{T}+\|x_{S_{f}}-x^{*}\|_{T})+2(1+2\varepsilon)\|\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)-x_{S_{f}}\|_{T}$ (Triangle
Inequality) $\displaystyle\leq$
$\displaystyle~{}(1+2\varepsilon)(\|x-x_{S}\|_{T}+2\|x_{S_{f}}-x_{S}\|_{T}+\|x_{S}-x^{*}\|_{T})+2(1+2\varepsilon)\|\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)-x_{S_{f}}\|_{T}$ (Triangle
Inequality) $\displaystyle\leq$
$\displaystyle~{}(1+2\varepsilon)(\|x-x_{S}\|_{T}+\|x_{S}-x^{*}\|_{T})+O(\sqrt{\delta})\|x_{S_{f}}(t)\|_{T}+2(1+2\varepsilon)\|x_{S_{f}}-x_{S}\|_{T}$
(Eq. (77)) $\displaystyle\leq$
$\displaystyle~{}(1+2\varepsilon)(1+\sqrt{2}+O(\sqrt{\varepsilon}))\|g\|_{T}+O(\sqrt{\delta})\|x^{*}\|_{T}+O(\sqrt{\delta})\|x_{S_{f}}(t)\|_{T}+2(1+2\varepsilon)\|x_{S_{f}}-x_{S}\|_{T}$
(Lemma 12.37) $\displaystyle\leq$
$\displaystyle~{}(1+2\varepsilon)(1+\sqrt{2}+O(\sqrt{\varepsilon}))\|g\|_{T}+O(\sqrt{\delta})\|x^{*}\|_{T}+O(\sqrt{\delta})(\|g\|_{T}+\|x^{*}\|_{T})+2(1+2\varepsilon)(1+O(\varepsilon))\|g(t)\|_{T}$
(Lemma 12.38) $\displaystyle\leq$
$\displaystyle~{}(3+\sqrt{2}+O(\sqrt{\varepsilon}))\|g\|_{T}+O(\sqrt{\delta})\|x^{*}\|_{T}$

By re-scaling $\varepsilon$ and $\delta$, we prove the theorem.

∎

## Acknowledgements

The authors would like to thank Michael Kapralov, Eric Price, Kshiteej Sheth,
and Lichen Zhang for their helpful discussions. OW’s research is supported by
NSF CAREER award CCF-1844887, an ISF grant #3011005535, and ERC Starting Grant
#101039914. Part of this research was performed while RZ was visiting the
Institute for Pure and Applied Mathematics (IPAM), which is supported by the
National Science Foundation (Grant No. DMS-1925919).

## Appendix

##  Appendix A High Dimensional Reduction Under Noiseless Assumption

This section is organized as follows:

  * •

Section A.1 shows that Fourier basis is linear independent.

  * •

Section A.2 shows that, there is straightforward algorithm for signal
estimation under noiseless setting.

###  A.1 Fourier basis is linear independent on randomly sampled points

######  Lemma A.1.

Given a basis $\mathcal{B}$ of $m$ known vectors $b_{1},b_{2},\cdots
b_{m}\in\mathbb{R}^{d}$, let $\Lambda(\mathcal{B})\subset\mathbb{R}^{d}$
denote the lattice

$\displaystyle\Lambda(\mathcal{B})=\Big{\\{}z\in\mathbb{R}^{d}:z=\sum_{i=1}^{m}c_{i}b_{i},c_{i}\in\mathbb{Z},\forall
i\in[m]\Big{\\}}$

Suppose that $f_{1},f_{2},\cdots,f_{k}\in\Lambda(\mathcal{B})$. Randomly
samples a vector $o\sim{\cal N}(0,I_{d})$. Let
$t=k^{-1}\cdot(T/2+o\cdot{\min}({\max}_{j\in[k]}|\langle
f_{j},o\rangle|^{-1},k^{-1}T))$. Let $t_{i}:=(i-1)\cdot t$ for $i\in[k]$.

Let $v_{j}=(\exp(2\pi\mathbf{i}\langle
f_{j},t_{1}\rangle),\exp(2\pi\mathbf{i}\langle
f_{j},t_{2}\rangle),\cdots,\exp(2\pi\mathbf{i}\langle f_{j},t_{k}\rangle))$
for $j\in[k]$. We have that $v_{1},v_{2},\cdots,v_{k}$ are linear independent
with probability $1$.

###### Proof.

We have that

$\displaystyle u_{j}:=\begin{bmatrix}e^{2\pi\mathbf{i}\langle f_{1},0\cdot
t\rangle}\\\ e^{2\pi\mathbf{i}\langle f_{1},1\cdot t\rangle}\\\ \vdots\\\
e^{2\pi\mathbf{i}\langle f_{1},(k-1)\cdot t\rangle}\\\
\end{bmatrix}=\begin{bmatrix}1\\\ e^{2\pi\mathbf{i}\langle f_{1},t\rangle}\\\
\vdots\\\ (e^{2\pi\mathbf{i}\langle
f_{1},t\rangle})^{k-1}\end{bmatrix}=\begin{bmatrix}1\\\ w_{1}\\\ \vdots\\\
w_{1}^{k-1}\end{bmatrix},$

where $w_{1}:=e^{2\pi\mathbf{i}\langle f_{1},t\rangle}$. Similarly, we can
define $w_{j}:=e^{2\pi\mathbf{i}\langle f_{j},t\rangle}$. And we have

$\displaystyle\begin{bmatrix}|&|&&|\\\ u_{1}&u_{2}&\cdots&u_{k}\\\
|&|&&|\end{bmatrix}=\begin{bmatrix}1&1&\cdots&1\\\ w_{1}&w_{2}&\cdots&w_{k}\\\
w_{1}^{2}&w_{2}^{2}&\cdots&w_{k}^{2}\\\ \vdots&\vdots&\ddots&\vdots\\\
w_{1}^{k-1}&w_{2}^{k-1}&\cdots&w_{k}^{k-1}\end{bmatrix},$

which is a Vandermonde matrix. Hence, they are linearly independent as long as
$w_{1},\dots,w_{k}$ are distinct. Or equivalently,

$\displaystyle\langle f_{1},t\rangle\mod{2\pi},\cdots,\langle
f_{k},t\rangle\mod{2\pi}$

are distinct.

Next, we will show that $w_{1},\dots,w_{k}$ are distinct with probability $1$.
We first show that:

$\displaystyle\langle f_{i},t\rangle\leq\langle
f_{i},o\rangle/{\max}_{j\in[k]}|\langle
f_{j},o\rangle|\in[-1,1]\subset[-\pi,\pi].$

Then, $\langle f_{i},t\rangle=\langle f_{j},t\rangle\mod{2\pi}$ is equivalent
to $\langle f_{i},t\rangle=\langle f_{j},t\rangle$, and is equivalent to
$\langle f_{i}-f_{j},t\rangle=0$, and is equivalent to $\langle
f_{i}-f_{j},o\rangle=0$. However, $\langle f_{i}-f_{j},o\rangle$ follows from
${\cal N}(0,\|f_{i}-f_{j}\|_{2}^{2})$. By our assumption,
$\|f_{i}-f_{j}\|_{2}^{2}\neq 0$. Thus,

$\displaystyle\Pr_{t\sim{\cal N}(0,I_{d})}[\langle f_{i}-f_{j},t\rangle=0]=0.$

Therefore, by union bound,

$\displaystyle\Pr_{t\sim{\cal N}(0,I_{d})}[\exists i\neq j\in[k]:\langle
f_{i}-f_{j},t\rangle=0]=0.$

∎

###  A.2 Reduction

######  Lemma A.2 (High Dimension Noiseless).

Given a basis $\mathcal{B}$ of $m$ known vectors $b_{1},b_{2},\cdots
b_{m}\in\mathbb{R}^{d}$, let $\Lambda(\mathcal{B})\subset\mathbb{R}^{d}$
denote the lattice

$\displaystyle\Lambda(\mathcal{B})=\Big{\\{}z\in\mathbb{R}^{d}:z=\sum_{i=1}^{m}c_{i}b_{i},c_{i}\in\mathbb{Z},\forall
i\in[m]\Big{\\}}$

Suppose that $f_{1},f_{2},\cdots,f_{k}\in\Lambda(\mathcal{B})$. Let
$x^{*}(t)=\sum_{j=1}^{k}v_{j}e^{2\pi\mathbf{i}\langle f_{j},t\rangle}$. Given
$x^{*}(t)$ is observable for $t\in[0,T]^{d}$. Let $\eta=\min_{i\neq
j}\|f_{j}-f_{i}\|_{\infty}$.

Given $D,\eta\in\mathbb{R}_{+}$. Suppose that there is an algorithm
$\textsc{FrequencyEstimation}(x^{*},k,\rho,d,F,T,\mathcal{B})$ that

  * •

takes $\mathcal{S}(k,\rho,d,F,T,\eta)$ samples,

  * •

runs $\mathcal{T}(k,\rho,d,F,T,\eta)$ time,

  * •

output a set $L$ of frequencies such that, for each $f_{i}$, there is
$f^{\prime}_{i}\in L$, $|f_{i}-f^{\prime}_{i}|\leq D/T$, holds with
probability $1-\rho$.

Let $C=|L|\cdot(D/T+\sqrt{m}\|{\cal
B}\|)^{m}\cdot\frac{\pi^{m/2}}{(m/2)!}\cdot\frac{1}{|\det({\cal B})|}$. If
$C\leq d$, then, there is an algorithm
($\textsc{SignalEstimation}(x,k,d,F,T,\mathcal{B})$ ) that

  * •

takes $O(\widetilde{k}+\mathcal{S}(k,d,F,T,\eta))$ samples,

  * •

runs $O(\widetilde{k}^{\omega}+\widetilde{k}^{2}d+\mathcal{T}(k,d,F,T,\eta))$
time,

  * •

output
$y(t)=\sum_{j=1}^{\widetilde{k}}v_{j}^{\prime}\cdot\exp(2\pi\mathbf{i}\langle
f_{j}^{\prime},t\rangle)$ such that

    * –

$\widetilde{k}\leq C$,

    * –

$y(t)=x(t)$, holds with probability $(1-\rho)^{2}$.

###### Proof.

First, we recover the frequencies by utilizing the algorithm
$\textsc{FrequencyEstimation}(x,k,d,T,F,\mathcal{B})$. Let $L$ be the set of
frequencies output by the algorithm
$\textsc{FrequencyEstimation}(x,k,d,T,F,\mathcal{B})$.

We define $\widetilde{L}$ as follows:

$\displaystyle\widetilde{L}:=\\{f\in\Lambda(\mathcal{B})~{}|~{}\exists
f^{\prime}\in L,~{}|f^{\prime}-f|<D/T\\}.$

We use $\widetilde{k}$ to denote the size of set $\widetilde{L}$. We use
$f^{\prime}_{1},f^{\prime}_{2},\cdots,f^{\prime}_{\widetilde{k}}$ to denote
the frequencies in the set $\widetilde{L}$.

By applying Lemma 10.2, we have that

$\displaystyle\widetilde{k}=|\widetilde{L}|\leq|L|\cdot(D/T+\sqrt{m}\|{\cal
B}\|)^{m}\cdot\frac{\pi^{m/2}}{(m/2)!}\cdot\frac{1}{|\det({\cal B})|}.$

Next, we focus on recovering magnitude
$v^{\prime}\in\mathbb{C}^{\widetilde{k}}$. Let $\rho_{1}:=\rho$. First, we
randomly samples a vector $o\sim{\cal N}(0,I_{d})$. Let
$t=k^{-1}\cdot(T/2+o\cdot{\min}({\max}_{j\in[k]}|\langle
f_{j},o\rangle|^{-1},\rho_{1}T))$. Let $t_{i}:=(i-1)\cdot t$ for $i\in[k]$. We
have that $|o\cdot{\min}({\max}_{j\in[k]}|\langle
f_{j},o\rangle|^{-1},\rho_{1}T)|\leq o\rho_{1}T$. Then with probability
$1-\rho_{1}$, $|o|\leq 1/(2\rho_{1})$, then $t_{i}\in[0,T]^{d},\forall
i\in[k]$.

Consider the matrix $A\in\mathbb{C}^{\widetilde{k}\times\widetilde{k}}$, where
the $(i,j)$-th entry in $A$ is $A_{i,j}=\exp(2\pi\mathbf{i}\langle
f^{\prime}_{j},t_{i}\rangle)$ for each $i\in[\widetilde{k}]$ and
$j\in[\widetilde{k}]$. Let
$b=(x^{*}(t_{1}),x^{*}(t_{2}),\cdots,x^{*}(t_{\widetilde{k}}))^{\top}\in\mathbb{C}^{\widetilde{k}}$.

Then, if the following linear system solvable, then we solve the following
linear system:

$\displaystyle Av^{\prime}=b.$ (80)

We output
$y(t)=\sum_{j=1}^{\widetilde{k}}v_{j}^{\prime}\cdot\exp(2\pi\mathbf{i}\langle
f_{j}^{\prime},t\rangle)$, and we have that $y(t)=x^{*}(t)$.

Finally, by Lemma A.1, we have that Eq. (80) is solvable with a large
probability.

∎

##  Appendix B Semi-continuous Approximation

In this section, we justify the usefulness of the semi-continuous setting by
showing that for any $k$-Fourier-sparse, it can be approximated by a
$k$-Fourier-sparse semi-continuous signal. This section is organized as
follows:

  * •

In Sections B.1 and B.2, we give some technical tools on the Gaussian
multiplier.

  * •

In Section B.3, we prove the main result of this section (Theorem B.8), which
is incomparable to the existence result in [CKPS16].

  * •

In Section B.4, we give a fast optimal-sparsity Fourier interpolation
algorithm with a different error guarantee.

  * •

In Section B.5, we also show that the frequency gap of the approximation can
be increased to $\Theta(1/T)$ if we slightly blow up the sparsity of the
approximation signal (Corollary B.12).

###  B.1 Properties related to Gaussians

######  Definition B.1 (Gaussian Multiplier).

For parameters $\mu,\sigma$, we define

$\displaystyle M_{\mu,\sigma^{2}}(x)=e^{-\frac{(x-\mu)^{2}}{2\sigma^{2}}}$

i.e. it is a Gaussian scaled so that its maximum value is $1$.

We stat a standard result for Gaussian multiplier (see [LLM21] for example).

######  Lemma B.2.

Let $0<\varepsilon<0.1$ be a parameter. Let $c$ be a real number such that
$0<c\leq(\log(1/\varepsilon))^{-1/2}$. Let $M$ be defined as in Definition
B.1. Define

$\displaystyle
f(x):=\sum_{j=-\infty}^{\infty}\frac{c}{\sqrt{2\pi}}M_{cj\sigma,\sigma^{2}}(x)\,.$

Then

$\displaystyle 1-\varepsilon^{10}\leq f(x)\leq 1+\varepsilon^{10}$

for all $x$. Furthermore, let $\alpha\leq 1$ be a parameter and
$c=\alpha(\log(1/\varepsilon))^{-1/2}$. Then

$\displaystyle 1-\varepsilon^{10/\alpha^{2}}\leq f(x)\leq
1+\varepsilon^{10/\alpha^{2}}$

for all $x$.

###### Proof.

Without loss of generality $\sigma=1$. Now the function $f$ is $c$-periodic
and even, so we may consider its Fourier expansion

$\displaystyle f(x)=$
$\displaystyle~{}a_{0}+2\sum_{j=1}^{\infty}a_{j}\cos(2j\pi x/c)$
$\displaystyle=$ $\displaystyle~{}a_{0}+2a_{1}\cos\left(\frac{2\pi
x}{c}\right)+2a_{2}\cos\left(\frac{4\pi x}{c}\right)+\dots$

and we will now compute the Fourier coefficients. First note that

$\displaystyle a_{0}=$
$\displaystyle~{}\frac{1}{c}\int_{0}^{c}f(x)\mathrm{d}x$ $\displaystyle=$
$\displaystyle~{}\frac{1}{\sqrt{2\pi}}\sum_{j=-\infty}^{\infty}\int_{c(j+1)}^{cj}M_{0,1}(x)\mathrm{d}x$
$\displaystyle=$ $\displaystyle~{}1.$

where the second step follows from the definition of $f$.

Next, for any $j\geq 1$,

$\displaystyle a_{j}=$
$\displaystyle~{}\frac{1}{c}\int_{0}^{c}f(x)\cos\left(\frac{2\pi
jx}{c}\right)\mathrm{d}x$ $\displaystyle=$
$\displaystyle~{}\frac{1}{c}\int_{0}^{c}\sum_{j=-\infty}^{\infty}\frac{c}{\sqrt{2\pi}}M_{cj,1}(x)\cos\left(\frac{2\pi
jx}{c}\right)\mathrm{d}x$ $\displaystyle=$
$\displaystyle~{}\frac{1}{\sqrt{2\pi}}\sum_{l=-\infty}^{\infty}\int_{c(l+1)}^{cl}M_{0,1}(x)\cos\left(\frac{2\pi
jx}{c}\right)\mathrm{d}x$ $\displaystyle=$
$\displaystyle~{}\frac{1}{\sqrt{2\pi}}\sum_{l=-\infty}^{\infty}\int_{c(l+1)}^{cl}\exp(-\frac{x^{2}}{2})\cos\left(\frac{2\pi
jx}{c}\right)\mathrm{d}x$ $\displaystyle=$
$\displaystyle~{}\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\frac{1}{2}\left(\exp(\frac{-x^{2}}{2}+\frac{2\pi\mathbf{i}jx}{c})+\exp(\frac{-x^{2}}{2}-\frac{2\pi\mathbf{i}jx}{c})\right)\mathrm{d}x$
$\displaystyle=$ $\displaystyle~{}\exp(-\frac{2\pi^{2}j^{2}}{c^{2}})\,.$

where the second step follows from the definition of $f$. The fourth step
follows from the definition of $M$.

Then we can claim that

$\displaystyle|f(x)-1|\leq$
$\displaystyle~{}2\sum_{j=1}^{\infty}\exp(-\frac{2\pi^{2}j^{2}}{c^{2}})$
$\displaystyle\leq$ $\displaystyle~{}2\sum_{j=1}^{\infty}\exp(-15j/c^{2})$
$\displaystyle=$ $\displaystyle~{}\frac{2\exp(-15/c^{2})}{1-\exp(-15/c^{2})}$
$\displaystyle\leq$
$\displaystyle~{}\frac{2\varepsilon^{15/\alpha^{2}}}{1-\varepsilon^{15}}$
$\displaystyle\leq$ $\displaystyle~{}\varepsilon^{10/\alpha^{2}}$
$\displaystyle\leq$ $\displaystyle~{}\varepsilon^{10}$

where the first step follows from $a_{0}=1$, the forth step follows from
$\alpha\leq 1$ and $c=\alpha(\log(1/\varepsilon))^{-1/2}$, the fifth step
follows from $\varepsilon\in(0,0.1)$, ∎

######  Claim B.3.

Let $\varepsilon\in(0,0.01)$ be a parameter. Let
$\varepsilon_{0}=2\varepsilon$, $c=0.01/\sqrt{\log(1/\varepsilon)}$,
$K=\lceil\frac{1+0.5\varepsilon}{c\varepsilon^{2}}\rceil$. Let
$M:\mathbb{R}\rightarrow\mathbb{R}$ be defined as in Definition B.1. Define
$f:\mathbb{R}\rightarrow\mathbb{R}$

$\displaystyle
f(x)=\sum_{j=-K}^{K}\frac{c}{\sqrt{2\pi}}M_{\mu_{j},\sigma^{2}}(x),\text{~{}~{}~{}where~{}~{}~{}}\mu_{j}={cj\varepsilon^{2}l},~{}~{}~{}\sigma^{2}=\varepsilon^{4}l^{2}\,.$

Then the following properties is satisfied

  * •

Part 1. $f(x)\in[0,1+\varepsilon_{0}]$, for all $x$

  * •

Part 2. $f(x)\in[1-\varepsilon_{0},1+\varepsilon_{0}]$, for all $x\in[-l,l]$

  * •

Part 3. $f(x)\in[0,\varepsilon_{0}]$, for all $|x|\geq(1+\varepsilon)l$

###### Proof.

Using Lemma B.2 with setting the following parameter choice
$\sigma=\varepsilon^{2}l$, $c=0.01(\log(1/\varepsilon))^{-1/2}$, we define

$\displaystyle
f_{0}(x)=\sum_{j=-\infty}^{\infty}\frac{c}{\sqrt{2\pi}}M_{\mu_{j},\sigma^{2}}\,.$

we can get that $1-\varepsilon\leq f_{0}(x)\leq 1+\varepsilon$.

We will then upper bound the perturbation between $f$ and $f_{0}$. Firstly, we
will provide a upper bound for $M$ when $x/(\varepsilon^{2}l)-cj\geq 10$

$\displaystyle\frac{c}{\sqrt{2\pi}}M_{\mu_{j},\sigma^{2}}(x)=$
$\displaystyle~{}\frac{c}{\sqrt{2\pi}}\exp(-(x-cj\varepsilon^{2}l)^{2}/(2\varepsilon^{4}l^{2}))$
$\displaystyle=$
$\displaystyle~{}\frac{c}{\sqrt{2\pi}}\exp(-(x/(\varepsilon^{2}l)-cj)^{2}/2)$
$\displaystyle\leq$ $\displaystyle~{}\exp(-|x/(\varepsilon^{2}l)-cj|)$ (81)

where the first step follows from the definition of $M$, the third step
follows from $x/(\varepsilon^{2}l)-cj\geq 10$.

Next we will claim that

$\displaystyle\sum_{j=0}^{\infty}\exp(-cj)=$
$\displaystyle~{}\frac{1}{1-\exp(-c)}$ $\displaystyle\leq$
$\displaystyle~{}\frac{2}{c}$ $\displaystyle\leq$
$\displaystyle~{}\frac{200}{\varepsilon}$ (82)

where the first step follows from $c>0$ and the sum of geometric sequence, the
second step follows from $1-\exp(-x)>x/2$ when $x<0.1$, the third step follows
from $c\geq 0.01\varepsilon$.

Because of the symmetry of $M$, We will also claim that

$\displaystyle M_{\mu,\sigma^{2}}(x)=M_{-\mu,\sigma^{2}}(-x)$ (83)

Part 1.

Because $M_{\mu,\sigma}=\exp(-(x-\mu)^{2}/\sigma^{2})\geq 0$, we can obtain
that $f(x)\geq 0$. Besides, we will claim that

$\displaystyle f(x)\leq$ $\displaystyle~{}f_{0}(x)$ $\displaystyle\leq$
$\displaystyle~{}1+\varepsilon$ $\displaystyle\leq$
$\displaystyle~{}\varepsilon_{0}$

where the first step follows from $M_{\mu,\sigma}\geq 0$.

Part 2.

Firstly, we upper bound $f$ when $x\in[-l,l]$. To bound
$\sum_{j=K+1}^{\infty}\frac{c}{\sqrt{2\pi}}M_{\mu_{j},\sigma^{2}}(x)$, we
obtain

$\displaystyle cj-x/(\varepsilon^{2}l)\geq$
$\displaystyle~{}cj-1/(\varepsilon^{2})$ $\displaystyle\geq$
$\displaystyle~{}c(K+1)-1/\varepsilon^{2}$ $\displaystyle\geq$
$\displaystyle~{}0.5/\varepsilon$ $\displaystyle\geq$ $\displaystyle~{}10$
(84)

where the first step follows from $x\in[-l,l]$, the second step follows from
$j\geq K+1$, the third step follows from
$K+1\geq(1+0.5\varepsilon)/(c\varepsilon^{2})$.

Then we can upper bound

$\displaystyle\sum_{j=K+1}^{\infty}\frac{c}{\sqrt{2\pi}}M_{\mu_{j},\sigma^{2}}(x)\leq$
$\displaystyle~{}\sum_{j=K+1}^{\infty}\exp(x/(\varepsilon^{2}l)-cj)$
$\displaystyle\leq$
$\displaystyle~{}\frac{200}{\varepsilon}\exp(x/(\varepsilon^{2}l)-c(K+1))$
$\displaystyle\leq$
$\displaystyle~{}\frac{200}{\varepsilon}\exp(-0.5/\varepsilon)$
$\displaystyle\leq$ $\displaystyle~{}0.1\varepsilon$ (85)

where the first step follows from Eq. (81) and Eq. (84), the second step
follows from Eq. (82), the third step follows from Eq. (84), the last step
follows from $\varepsilon\in(0,0.01)$.

We conclude

$\displaystyle|f(x)-1|=$
$\displaystyle~{}\Big{|}f_{0}(x)-1-\sum_{j=K+1}^{\infty}\frac{c}{\sqrt{2\pi}}M_{\mu_{j},\sigma^{2}}(x)-\sum_{j=-\infty}^{-K-1}\frac{c}{\sqrt{2\pi}}M_{\mu_{j},\sigma^{2}}(x)\Big{|}$
$\displaystyle\leq$
$\displaystyle~{}|f_{0}(x)-1|+\Big{|}\sum_{j=K+1}^{\infty}\frac{c}{\sqrt{2\pi}}M_{\mu_{j},\sigma^{2}}(x)\Big{|}+\Big{|}\sum_{j=-\infty}^{-K-1}\frac{c}{\sqrt{2\pi}}M_{\mu_{j},\sigma^{2}}(x)\Big{|}$
$\displaystyle\leq$
$\displaystyle~{}\varepsilon+0.1\varepsilon+0.1\varepsilon$
$\displaystyle\leq$ $\displaystyle~{}\varepsilon_{0}$

where the first step follows from the definition of $f$ and $f_{0}$, the
second step follows from the triangle inequality, the third step follows from
$|f_{0}(x)-1|\leq\varepsilon$, Eq.(85) and Eq. (83).

Part 3.

Secondly, we will provide the upper bound for $f$ when $|x|>(1+\varepsilon)l$.
Without loss of generality, we can only consider $x>(1+\varepsilon)l$ because
of Eq. (83). To bound
$\sum_{j=-K}^{K}\frac{c}{\sqrt{2\pi}}M_{\mu_{j},\sigma^{2}}(x)$. We obtain

$\displaystyle x/(\varepsilon^{2}l)-cj\geq$
$\displaystyle~{}x/(\varepsilon^{2}l)-cK$ $\displaystyle\geq$
$\displaystyle~{}(1+\varepsilon)/\varepsilon^{2}-cK$ $\displaystyle\geq$
$\displaystyle~{}0.25/\varepsilon$ $\displaystyle\geq$ $\displaystyle~{}10$
(86)

where the first step follows from $j\leq K$, the second step follows from
$x>(1+\varepsilon)l$, the third step follows from
$K\leq(1+0.5\varepsilon)/(c\varepsilon^{2})+1$ and $c\leq 0.01\leq
0.25/\varepsilon$.

Then we can upper bound

$\displaystyle\sum_{j=-K}^{K}\frac{c}{\sqrt{2\pi}}M_{\mu_{j},\sigma^{2}}(x)\leq$
$\displaystyle~{}\sum_{j=-K}^{K}\exp(cj-x/(\varepsilon^{2}l))$
$\displaystyle\leq$
$\displaystyle~{}\frac{200}{\varepsilon}\exp(cK-x/(\varepsilon^{2}l))$
$\displaystyle\leq$
$\displaystyle~{}\frac{200}{\varepsilon}\exp(-0.25/\varepsilon)$
$\displaystyle\leq$ $\displaystyle~{}\varepsilon$ $\displaystyle\leq$
$\displaystyle~{}\varepsilon_{0}$ (87)

where the first step follows from Eq. (81) and Eq. (86), the second step
follows from Eq. (82), the third step follows from Eq. (86), the fourth step
follows from $\varepsilon\in(0,0.01)$.

∎

######  Lemma B.4.

Given $c\in\mathbb{R},~{}\gamma,l,\sigma\in\mathbb{R}_{+}$,
$\mu\in\mathbb{R}$. Let $M:\mathbb{R}\rightarrow\mathbb{R}$ be defined as in
Definition B.1. For $|a-b|\leq\gamma$, We have that

$\displaystyle|{{M}_{\mu,\sigma^{2}}(a)\exp(c\mathbf{i}a)}-{{M}_{\mu,\sigma^{2}}(b)\exp(c\mathbf{i}b)}|\leq({\sigma}^{-1}+|c|)\gamma.$

###### Proof.

We have that

$\displaystyle~{}|{M}_{\mu,\sigma^{2}}(b)-{{M}_{\mu,\sigma^{2}}(a)}|$
$\displaystyle=$
$\displaystyle~{}|\exp(-(b-\mu)^{2}/(2\sigma^{2}))-\exp(-(a-\mu)^{2}/(2\sigma^{2}))|$
$\displaystyle=$
$\displaystyle~{}|b-a||(\xi-\mu)\exp(-(\xi-\mu)^{2}/(2\sigma^{2}))/(\sigma^{2})|$
$\displaystyle\leq$ $\displaystyle~{}\gamma/\sigma$ (88)

where the first step follows from the definition of $M$, the second step
defines $\xi\in[a,b]$ and follows from Lagrange’s Mean Value Theorem, the last
step follows from $|x\exp(-x^{2}/2)|\leq 1$. We have that

$\displaystyle~{}|{{M}_{\mu,\sigma^{2}}(a)\exp(c\mathbf{i}a)}-{{M}_{\mu,\sigma^{2}}(b)\exp(c\mathbf{i}b)}|$
$\displaystyle\leq$
$\displaystyle~{}|{{M}_{\mu,\sigma^{2}}(a)\exp(c\mathbf{i}a)}-{{M}_{\mu,\sigma^{2}}(b)\exp(c\mathbf{i}a)}|+|{{M}_{\mu,\sigma^{2}}(b)\exp(c\mathbf{i}a)}-{{M}_{\mu,\sigma^{2}}(b)\exp(c\mathbf{i}b)}|$
$\displaystyle\leq$
$\displaystyle~{}|{M}_{\mu,\sigma^{2}}(a)-{M}_{\mu,\sigma^{2}}(b)|+{M}_{\mu,\sigma^{2}}(b)\cdot|{\exp(c\mathbf{i}a)}-{\exp(c\mathbf{i}b)}|$
$\displaystyle\leq$
$\displaystyle~{}\frac{\gamma}{\sigma}+{M}_{\mu,\sigma^{2}}(b)\cdot|c(a-b)|$
$\displaystyle\leq$ $\displaystyle~{}\frac{\gamma}{\sigma}+|c|\gamma$
$\displaystyle\leq$ $\displaystyle~{}(\frac{1}{\sigma}+|c|)\gamma$

where the first follows from triangle inequality, the second follows from
$|\exp(\mathbf{i}\theta)|=1$, the third step follows from Eq. (88) and that
arc length is greater than chord length, the fourth step follows from $M\leq
1$ and the assume in the statement.

∎

###  B.2 Continuous Fourier transform

####  B.2.1 Bounding the tails

The goal of this section is to prove Lemma B.5,

######  Lemma B.5.

Let $\mu\in\mathbb{R},\alpha\in\mathbb{Z}_{+},\sigma$,
$F,F_{0},\varepsilon_{1}\in\mathbb{R}_{+}$. Let $\sigma\in(0,1)$,
$\varepsilon_{1}\in(0,0.1)$, $F>1$. Let $M:\mathbb{R}\rightarrow\mathbb{R}$ be
defined as in Definition B.1. Let $x:\mathbb{R}\rightarrow\mathbb{C}$ be a
function. Let $\mathrm{supp}(\widehat{x})\subseteq[-F,F]$. If

$\displaystyle F_{0}>{\sigma}^{-1}\cdot\log^{1/2}(4F/\varepsilon_{1})+F,$

then we have that,

$\displaystyle\Big{|}\int_{-\infty}^{\infty}(\widehat{M}_{\mu,\sigma^{2}}(f)*\widehat{x}(f))^{\alpha}\mathrm{d}f-\int_{-F_{0}}^{F_{0}}(\widehat{M}_{\mu,\sigma^{2}}(f)*\widehat{x}(f))^{\alpha}\mathrm{d}f\Big{|}\leq$
$\displaystyle~{}\|\widehat{x}\|^{\alpha}_{\infty}\varepsilon_{1}/{F^{\alpha}}.$

###### Proof.

First, we will calculate $\widehat{M}$. Then, we provide a bound on the tail
of $\widehat{M}$. Finally, we conclude our proof.

We can claim that

$\displaystyle\widehat{M}_{\mu,\sigma^{2}}(f)=\sqrt{2\pi\sigma^{2}}\cdot\exp(-2\pi\mathbf{i}\mu
f)\cdot M_{0,1/(4\pi^{2}\sigma^{2})}.$

Taking the $|\cdot|$ on both sides of the above equation, we get

$\displaystyle|\widehat{M}_{\mu,\sigma^{2}}(f)|=\sqrt{2\pi\sigma^{2}}\cdot|M_{0,1/(4\pi^{2}\sigma^{2})}|$

We start with

$\displaystyle\int_{F_{0}-F}^{\infty}|\widehat{M}_{\mu,\sigma^{2}}(f)|^{\alpha}\mathrm{d}f=$
$\displaystyle~{}\sqrt{2\pi\sigma^{2}}\cdot\int_{F_{0}-F}^{\infty}|M_{0,1/(4\pi^{2}\sigma^{2})}|^{\alpha}\mathrm{d}f$
$\displaystyle=$
$\displaystyle~{}\sqrt{2\pi\sigma^{2}}\cdot\int_{F_{0}-F}^{\infty}\exp(-2\alpha\pi^{2}\sigma^{2}f^{2})\mathrm{d}f$
$\displaystyle=$
$\displaystyle~{}\frac{1}{\sqrt{\alpha\pi}}\cdot\int_{\sqrt{2\alpha}\pi\sigma(F_{0}-F)}^{\infty}\exp(-\xi^{2})\mathrm{d}\xi$
$\displaystyle\leq$
$\displaystyle~{}\frac{1}{\sqrt{\alpha\pi}}\cdot\int_{\sqrt{2\alpha}\pi\sigma(F_{0}-F)}^{\infty}\exp(-\sqrt{2\alpha}\pi\sigma(F_{0}-F)\xi)\mathrm{d}\xi$
$\displaystyle=$
$\displaystyle~{}\frac{1}{\sqrt{\alpha\pi}}\cdot\frac{1}{\sqrt{2\alpha}\pi\sigma(F_{0}-F)}\exp(-2\alpha\pi^{2}\sigma^{2}(F_{0}-F)^{2})$
$\displaystyle\leq$ $\displaystyle~{}\varepsilon_{1}/(4F)^{2\alpha}.$ (89)

where the second step follows definition of $M$, the third step follows from
$\xi=\sqrt{2\alpha}\pi\sigma f$, the forth step follows from
$\xi\leq\sqrt{2\alpha}\pi\sigma(F_{0}-F)$, the last step follows from lower
bound on $F_{0}$ in the Lemma statement.

Finally, we can bound LHS in the statement as follows

$\displaystyle~{}\Big{|}\int_{-\infty}^{\infty}(\widehat{M}_{\mu,\sigma^{2}}(f)*\widehat{x}(f))^{\alpha}\mathrm{d}f-\int_{-F_{0}}^{F_{0}}(\widehat{M}_{\mu,\sigma^{2}}(f)*\widehat{x}(f))^{\alpha}\mathrm{d}f\Big{|}$
$\displaystyle=$
$\displaystyle~{}\Big{|}\int_{-\infty}^{F_{0}}(\widehat{M}_{\mu,\sigma^{2}}(f)*\widehat{x}(f))^{\alpha}\mathrm{d}f+\int_{F_{0}}^{\infty}(\widehat{M}_{\mu,\sigma^{2}}(f)*\widehat{x}(f))^{\alpha}\mathrm{d}f\Big{|}$
$\displaystyle=$
$\displaystyle~{}\Big{|}\int_{-\infty}^{F_{0}}(\int_{-F}^{F}\widehat{M}_{\mu,\sigma^{2}}(f-\xi)\cdot\widehat{x}(\xi)\mathrm{d}\xi)^{\alpha}\mathrm{d}f+\int_{F_{0}}^{\infty}(\int_{-F}^{F}\widehat{M}_{\mu,\sigma^{2}}(f-\xi)\cdot\widehat{x}(\xi)\mathrm{d}\xi)^{\alpha}\mathrm{d}f\Big{|}$
$\displaystyle\leq$
$\displaystyle~{}\Big{|}\int_{F_{0}}^{\infty}(\int_{-F}^{F}\widehat{M}_{\mu,\sigma^{2}}(f-\xi)\cdot\widehat{x}(\xi)\mathrm{d}\xi)^{\alpha}\mathrm{d}f\Big{|}+\Big{|}\int_{-\infty}^{-F_{0}}(\int_{-F}^{F}\widehat{M}_{\mu,\sigma^{2}}(f-\xi)\cdot\widehat{x}(\xi)\mathrm{d}\xi)^{\alpha}\mathrm{d}f\Big{|}$
$\displaystyle\leq$
$\displaystyle~{}\int_{F_{0}}^{\infty}(\int_{-F}^{F}|\widehat{M}_{\mu,\sigma^{2}}(f-\xi)\cdot\widehat{x}(\xi)|\mathrm{d}\xi)^{\alpha}\mathrm{d}f+\int_{-\infty}^{-F_{0}}(\int_{-F}^{F}|\widehat{M}_{\mu,\sigma^{2}}(f-\xi)\cdot\widehat{x}(\xi)|\mathrm{d}\xi)^{\alpha}\mathrm{d}f$
$\displaystyle=$
$\displaystyle~{}\|\widehat{x}\|^{\alpha}_{\infty}\cdot(\int_{F_{0}}^{\infty}(\int_{-F}^{F}|\widehat{M}_{\mu,\sigma^{2}}(f-\xi)|\mathrm{d}\xi)^{\alpha}\mathrm{d}f+\int_{-\infty}^{-F_{0}}(\int_{-F}^{F}|\widehat{M}_{\mu,\sigma^{2}}(f-\xi)|\mathrm{d}\xi)^{\alpha}\mathrm{d}f)$
(90)

where the third step follows from triangle inequality, the fourth step follows
from triangle inequality.

For the second term in the above Eq. (B.2.1)

$\displaystyle\int_{F_{0}}^{\infty}(\int_{-F}^{F}|\widehat{M}_{\mu,\sigma^{2}}(f-\xi)|\mathrm{d}\xi)^{\alpha}\mathrm{d}f\leq$
$\displaystyle~{}\int_{F_{0}}^{\infty}(\int_{-F}^{F}|\widehat{M}_{\mu,\sigma^{2}}(f-F)|\mathrm{d}\xi)^{\alpha}\mathrm{d}f$
$\displaystyle=$
$\displaystyle~{}\int_{F_{0}}^{\infty}|2F\widehat{M}_{\mu,\sigma^{2}}(f-F)|^{\alpha}\mathrm{d}f$
$\displaystyle=$
$\displaystyle~{}(2F)^{\alpha}\cdot\int_{F_{0}}^{\infty}|\widehat{M}_{\mu,\sigma^{2}}(f-F)|^{\alpha}\mathrm{d}f$
$\displaystyle=$
$\displaystyle~{}(2F)^{\alpha}\cdot\int_{F_{0}-F}^{\infty}|\widehat{M}_{\mu,\sigma^{2}}(\xi)|^{\alpha}\mathrm{d}\xi$
$\displaystyle\leq$
$\displaystyle~{}(2F)^{\alpha}\cdot\varepsilon_{1}/(4F)^{2\alpha}$
$\displaystyle\leq$ $\displaystyle~{}\varepsilon_{1}/(2F^{\alpha})$ (91)

where the first step follows from what
$\widehat{M}_{\mu,\sigma^{2}}(f-\xi)\leq\widehat{M}_{\mu,\sigma^{2}}(f-F)$
because $f-\xi\geq f-F\geq F_{0}-F>0$, the forth step follows from $f-F=\xi$,
second last step follows from Eq. (B.2.1).

Similarly, we have that

$\displaystyle\int_{-\infty}^{-F_{0}}(\int_{-F}^{F}|\widehat{M}_{\mu,\sigma^{2}}(f-\xi)|\mathrm{d}\xi)^{\alpha}\mathrm{d}f\leq\varepsilon_{1}/2.$
(92)

Combining Eq. (B.2.1), (B.2.1) and (92) completes the proof. ∎

####  B.2.2 Bounding the convolution

The goal of this section is to prove Lemma B.6.

######  Lemma B.6.

Given $\mu^{\prime},F,\sigma^{\prime},\gamma\in\mathbb{R}_{+}$. Let
$M:\mathbb{R}\rightarrow\mathbb{R}$ be defined as in Definition B.1. Let
$x:\mathbb{R}\rightarrow\mathbb{C}$ be a function. For simplicity, let
$M=M_{\mu^{\prime},\sigma^{\prime 2}}$. We have that for $\forall
f\in\mathbb{R}$,

$\displaystyle|\widehat{M}*\widehat{x}(f)-\sum_{\mu\in\mathbb{Z}\gamma}\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(\xi)\mathrm{d}\xi\cdot\widehat{M}(f)*\delta(f-\mu)|\leq(\sigma^{\prime
2}+\sigma^{\prime}|\mu^{\prime}|)\gamma^{2}\cdot\|\widehat{x}\|_{1}.$

###### Proof.

We will separate $\widehat{M}*\widehat{x}(f)$ into
$\widehat{M}(f)*(\widehat{x}(f)\cdot\mathrm{rect}_{\gamma/2}(f-\mu))$ where
$\mu\in\gamma\mathbb{Z}$. This decomposes $\widehat{x}$ into different
intervals. Then, we get a bound for each interval.

We can rewrite $\widehat{M}_{\mu^{\prime},\sigma^{\prime 2}}(f)$ in the
following sense,

$\displaystyle\widehat{M}_{\mu^{\prime},\sigma^{\prime 2}}(f)=$
$\displaystyle~{}\sqrt{2\pi\sigma^{\prime 2}}\cdot\exp(-2\pi^{2}\sigma^{\prime
2}f^{2})\cdot\exp(-2\pi\mathbf{i}\mu^{\prime}f)$ $\displaystyle=$
$\displaystyle~{}\sqrt{2\pi\sigma^{\prime 2}}\cdot
M_{0,1/(4\pi^{2}\sigma^{\prime 2})}(f)\cdot\exp(-2\pi\mathbf{i}\mu^{\prime}f)$

where the second step follows from the definition of $M$.

First, we consider the first term in the LHS of our statement

$\displaystyle\widehat{M}(f)*(\widehat{x}(f)\cdot\mathrm{rect}_{\gamma/2}(f-\mu))=$
$\displaystyle~{}\widehat{M}(f)*\Big{(}\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(\xi)\delta(f-\xi)\mathrm{d}\xi\Big{)}$
$\displaystyle=$
$\displaystyle~{}\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(\xi)\cdot\widehat{M}(f)*\delta(f-\xi)\mathrm{d}\xi$
$\displaystyle=$
$\displaystyle~{}\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(\xi)\cdot\widehat{M}(f-\xi)\mathrm{d}\xi$
(93)

where the first step follows from definition of $\mathrm{rect}$ function, the
last step follows from $\widehat{M}(f)*\delta(f-\xi)=\widehat{M}(f-\xi)$.

Now, we consider the second term in the LHS of our statement

$\displaystyle\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(\xi)\mathrm{d}\xi\cdot\widehat{M}(f)*\delta(f-\mu)=$
$\displaystyle~{}\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(\xi)\cdot\widehat{M}(f)*\delta(f-\mu)\mathrm{d}\xi$
$\displaystyle=$
$\displaystyle~{}\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(\xi)\cdot\widehat{M}(f-\mu)\mathrm{d}\xi.$
(94)

where the last step follows from
$\widehat{M}(f)*\delta(f-\mu)=\widehat{M}(f-\mu)$.

By Lemma B.4 (with $\gamma=\gamma/2$, $\sigma=1/(2\pi\sigma^{\prime})$,
$\mu=0$, $c=-2\pi\mu^{\prime}$), we have that

$\displaystyle~{}|\widehat{M}(f-\xi)-\widehat{M}(f-\mu)|$ $\displaystyle=$
$\displaystyle~{}\sqrt{2\pi\sigma^{\prime 2}}|M_{0,1/(4\pi^{2}\sigma^{\prime
2})}(f-\xi)\exp(-2\pi\mathbf{i}\mu^{\prime}(f-\xi))-M_{0,1/(4\pi^{2}\sigma^{\prime
2})}(f-\mu)\exp(-2\pi\mathbf{i}\mu^{\prime}(f-\mu))|$ $\displaystyle\leq$
$\displaystyle~{}\sqrt{2\pi\sigma^{\prime
2}}(2\pi\sigma^{\prime}+2\pi|\mu^{\prime}|)\gamma$ $\displaystyle\lesssim$
$\displaystyle~{}(\sigma^{\prime 2}+\sigma^{\prime}|\mu^{\prime}|)\gamma$ (95)

where the first step from the calculation of $\widehat{M}$, the second step
follows from Lemma B.4.

Thus, we can claim that $\forall f\in\mathbb{R}$,

$\displaystyle~{}|\widehat{M}(f)*(\widehat{x}(f)\cdot\mathrm{rect}_{\gamma/2}(f-\mu))-\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(f)\mathrm{d}f\cdot\widehat{M}(f)*\delta(f-\mu)|$
$\displaystyle=$
$\displaystyle~{}|\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(\xi)\cdot\widehat{M}(f-\xi)\mathrm{d}\xi-\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(\xi)\cdot\widehat{M}(f-\mu)\mathrm{d}\xi|$
$\displaystyle=$
$\displaystyle~{}|\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(\xi)\cdot(\widehat{M}(f-\xi)-\widehat{M}(f-\mu))\mathrm{d}\xi|$
$\displaystyle\leq$
$\displaystyle~{}\int_{\mu-\gamma/2}^{\mu+\gamma/2}|\widehat{x}(\xi)|\cdot|\widehat{M}(f-\xi)-\widehat{M}(f-\mu)|\mathrm{d}\xi$
$\displaystyle\leq$
$\displaystyle~{}\underset{\xi\in[\mu-\gamma/2,\mu+\gamma/2]}{\max}\\{|\widehat{M}(f-\xi)-\widehat{M}(f-\mu)|\\}\cdot\int_{\mu-\gamma/2}^{\mu+\gamma/2}|\widehat{x}(\xi)|\mathrm{d}\xi$
$\displaystyle\lesssim$ $\displaystyle~{}(\sigma^{\prime
2}+\sigma^{\prime}|\mu^{\prime}|)\gamma\cdot\int_{\mu-\gamma/2}^{\mu+\gamma/2}|\widehat{x}(\xi)|\mathrm{d}\xi.$
(96)

where the first step follows from from Eq. (93), Eq. (94), the third step
follows from triangle inequality, and the last step follows from Eq. (95).

As a result, we have that for $f$

$\displaystyle~{}|\widehat{M}*\widehat{x}(f)-\sum_{\mu\in\mathbb{Z}\gamma}\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(\xi)\mathrm{d}\xi\cdot\widehat{M}(f)*\delta(f-\mu)|$
$\displaystyle\leq$
$\displaystyle~{}|\sum_{\mu\in\mathbb{Z}\gamma}\widehat{M}(f)*(\widehat{x}(f)\cdot\mathrm{rect}_{\gamma/2}(f-\mu))-\sum_{\mu\in\mathbb{Z}\gamma}\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(\xi)\mathrm{d}\xi\cdot\widehat{M}(f)*\delta(f-\mu)|$
$\displaystyle\leq$
$\displaystyle~{}\sum_{\mu\in\mathbb{Z}\gamma}|\widehat{M}(f)*(\widehat{x}(f)\cdot\mathrm{rect}_{\gamma/2}(f-\mu))-\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(f)\mathrm{d}f\cdot\widehat{M}(f)*\delta(f-\mu)|$
$\displaystyle\lesssim$ $\displaystyle~{}(\sigma^{\prime
2}+\sigma^{\prime}|\mu^{\prime}|)\gamma\cdot\sum_{\mu\in\mathbb{Z}\gamma}\int_{\mu-\gamma/2}^{\mu+\gamma/2}|\widehat{x}(\xi)|\mathrm{d}\xi$
$\displaystyle\leq$ $\displaystyle~{}(\sigma^{\prime
2}+\sigma^{\prime}|\mu^{\prime}|)\gamma\cdot\|\widehat{x}\|_{1}$

where the first step follows from
$\sum_{\mu\in\mathbb{Z}\gamma}\mathrm{rect}_{\gamma/2}(f-\mu)=1$, the second
step follows from triangle inequality, the third step follows from Eq. (96),
the last step follows from the definition of $\ell_{1}$ norm.

Thus we complete proof. ∎

##### Choice of parameters

The following lemma shows how to take the parameters in this section.

######  Lemma B.7.

Let
$\varepsilon_{0},\varepsilon,F,c_{0},\sigma^{\prime},T,F_{0},K,\varepsilon_{1}\in\mathbb{R}_{+}$
such that

  * •

$\varepsilon_{0}=0.01$

  * •

$\varepsilon_{1}\leq\varepsilon^{2}/T$

  * •

$\sigma^{\prime}=\sqrt{2}\varepsilon_{0}^{2}T$

  * •

$c_{0}=0.01/\sqrt{\log(1/\varepsilon_{0})}$

  * •

$K=\lceil\frac{1+0.5\varepsilon_{0}}{c_{0}\varepsilon_{0}^{2}}\rceil\leq
2/(c_{0}\varepsilon_{0}^{2})$

  * •

$F_{0}={\sigma^{\prime}}^{-1}\cdot\log^{1/2}(4F/\varepsilon_{1})+F$

We have that

  * •

Part 1. $c_{0}K\lesssim 1$

  * •

Part 2. $F_{0}\lesssim(1/T)\cdot\log^{1/2}(FT/\varepsilon)+F$

###### Proof.

We will prove them separately.

Part 1.

We can show

$\displaystyle c_{0}K=$
$\displaystyle~{}c_{0}\lceil\frac{1+0.5\varepsilon_{0}}{c_{0}\varepsilon_{0}^{2}}\rceil\leq~{}\frac{2c_{0}}{c_{0}\varepsilon_{0}^{2}}\lesssim~{}1.$

where the first step follows from the definition of $K$, the third step
follows from the definition of $\varepsilon_{0}$.

Part 2.

We have that

$\displaystyle F_{0}=$
$\displaystyle~{}{\sigma^{\prime}}^{-1}\cdot\log^{1/2}(4F/\varepsilon_{1})+F$
$\displaystyle\lesssim$
$\displaystyle~{}1/(\varepsilon_{0}^{2}T)\cdot\log^{1/2}(F/\varepsilon_{1})+F$
$\displaystyle\lesssim$
$\displaystyle~{}1/T\cdot\log^{1/2}(F/\varepsilon_{1})+F$
$\displaystyle\lesssim$
$\displaystyle~{}1/T\cdot\log^{1/2}(FT/\varepsilon^{2})+F$
$\displaystyle\lesssim$ $\displaystyle~{}1/T\cdot\log^{1/2}(FT/\varepsilon)+F$

where the second step follows from the definition of $\sigma^{\prime}$, the
third step follows from the definition of $\varepsilon_{0}$, the fourth step
follows from the definition of $\varepsilon_{1}\geq\varepsilon^{2}/T$.

∎

###  B.3 Semi-continuouse approximation of Fourier-sparse signals

The main theorem of this section is stated and proved below.

######  Theorem B.8 (Sparse Signal is Semi-continuous).

Given $\gamma,\varepsilon\in(0,0.1),F,T\in\mathbb{R}_{+}$. Let
$x:\mathbb{R}\rightarrow\mathbb{C}$ be a function that such that $x$ is
$k$-Fourier-sparse and $\mathrm{supp}(\widehat{x})\subseteq[-F,F]$. Let
$\gamma>0$ and $\varepsilon_{1}>0$. Then there is an algorithm output a
$k^{\prime}$-Fourier-sparse signal ($k^{\prime}\leq k$),

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

such that

$\displaystyle\|x^{\prime}-x\|_{T}^{2}\lesssim(F_{0}T^{3}\gamma^{2}+\varepsilon_{1}/(F^{2}T))\cdot\|\widehat{x}\|_{1}^{2}$

where $\gamma=\underset{i\neq j}{\min}|f_{i}-f_{j}|$,
$f_{i}\in[-F,F],~{}f_{i}\in\gamma\mathbb{Z},~{}\forall i\in[k^{\prime}]$ and
$F_{0}=\Omega(T^{-1}\log^{1/2}(F/\varepsilon_{1})+F)$.

Further, if $\varepsilon_{1}\leq\varepsilon^{2}/T$ and
$\gamma\leq\varepsilon/\sqrt{F_{0}T^{3}}$, then we have

$\displaystyle\|x^{\prime}-x\|_{T}^{2}\lesssim\varepsilon^{2}\|\widehat{x}\|_{1}^{2}$

###### Proof.

First, we will introduce our choice for $x^{\prime}$. Then, we bound
$|\widehat{M}_{j}*\widehat{x}-\widehat{M}_{j}*\widehat{x}^{\prime}|$. Finally,
show the relationship between
$|\widehat{M}_{j}*\widehat{x}-\widehat{M}_{j}*\widehat{x}^{\prime}|$ and the
LHS in our statement by utilizing $M$ to bridge the integral calculated in the
time domain $\|x^{\prime}-x\|_{T}$ and the integral calculated in the
frequency domain $\|\widehat{x}\|_{1}$.

Let $x^{\prime}$ be chosen as

$\displaystyle
x^{\prime}(t)=\sum_{\mu\in\mathbb{Z}\gamma}\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(f)\mathrm{d}f\cdot\exp(2\pi\mathbf{i}\mu
t).$

Then,

$\displaystyle\|\widehat{x^{\prime}}\|_{1}=\sum_{\mu\in\mathbb{Z}\gamma}\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(f)\mathrm{d}f=\int_{-\infty}^{\infty}\widehat{x}(f)\mathrm{d}f=\|\widehat{x}\|_{1}.$
(97)

Let $c_{0},\varepsilon_{0}\in\mathbb{R}_{+}$, $K\in\mathbb{Z}_{+}$ such that
$\varepsilon_{0}=0.01\in(0,0.1),~{}c_{0}=0.01/\sqrt{\log(1/\varepsilon_{0})},~{}K=\lceil\frac{1+0.5\varepsilon_{0}}{c_{0}\varepsilon_{0}^{2}}\rceil\leq
2/(c_{0}\varepsilon_{0}^{2})$.

For simplicity, let $M_{j}(t)=M_{\mu_{j}^{\prime},\sigma^{\prime
2}}(t)=M_{c_{0}j\varepsilon_{0}^{2}T,2\varepsilon_{0}^{4}T^{2}}(t)$, then

$\displaystyle\widehat{M}_{j}(f)=\sqrt{2\pi\sigma^{\prime
2}}\exp(-2\pi^{2}\sigma^{\prime
2}f^{2})\exp(-2\pi\mathbf{i}\mu^{\prime}_{j}f).$

and

$\displaystyle\mu^{\prime}_{j}\leq$
$\displaystyle~{}c_{0}K\varepsilon_{0}^{2}T$ $\displaystyle\leq$
$\displaystyle~{}c_{0}(\frac{2}{c_{0}\varepsilon_{0}^{2}})\varepsilon_{0}^{2}T$
$\displaystyle=$ $\displaystyle~{}2T.$

where the second step follows from upper bound on $K$.

We have that

$\displaystyle\widehat{x}^{\prime}(f)=\sum_{\mu\in\mathbb{Z}\gamma}\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(f)\mathrm{d}f\cdot\delta(f-\mu).$

So, we can convolute $\widehat{M}$ at the both sides and get

$\displaystyle\widehat{M}_{j}(f)*\widehat{x}^{\prime}(f)=\sum_{\mu\in\mathbb{Z}\gamma}\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(f)\mathrm{d}f\cdot\widehat{M}_{j}(f)*\delta(f-\mu).$
(98)

By Lemma B.6, we have that for $\forall f\in\mathbb{R}$,

$\displaystyle~{}|\widehat{M}_{j}*\widehat{x}-\widehat{M}_{j}*\widehat{x}^{\prime}|$
$\displaystyle=$
$\displaystyle~{}\Big{|}\widehat{M}_{j}*\widehat{x}-\sum_{\mu\in\mathbb{Z}\gamma}\int_{\mu-\gamma/2}^{\mu+\gamma/2}\widehat{x}(f)\mathrm{d}f(\widehat{M}_{j}(f)*\delta(f-\mu))\Big{|}$
$\displaystyle\leq$ $\displaystyle~{}(\sigma^{\prime
2}+\sigma^{\prime}|\mu^{\prime}_{j}|)\gamma\cdot\|\widehat{x}\|_{1}$
$\displaystyle\lesssim$ $\displaystyle~{}T^{2}\gamma\cdot\|\widehat{x}\|_{1}.$
(99)

where the first step follows from Eq. (98), the second step follows from Lemma
B.6, the third step follows the choice of $\mu^{\prime}_{j}$ and $\sigma$ and
that $\varepsilon_{0}$ is a constant.

Let $F_{0}$ be defined as

$\displaystyle
F_{0}>{\sigma^{\prime}}^{-1}\cdot\log^{1/2}(4F/\varepsilon_{1})+F.$

Next, we can bound $|x^{\prime}(t)-x(t)|^{2}$,

$\displaystyle\int_{-\infty}^{\infty}{M}_{j}^{2}(t)\cdot|x^{\prime}(t)-x(t)|^{2}\mathrm{d}t=$
$\displaystyle~{}\int_{-\infty}^{\infty}|\widehat{M}_{j}*\widehat{x}^{\prime}(f)-\widehat{M}_{j}*\widehat{x}(f)|^{2}\mathrm{d}f$
$\displaystyle\leq$
$\displaystyle~{}\int_{-F_{0}}^{F_{0}}|\widehat{M}_{j}*\widehat{x}^{\prime}(f)-\widehat{M}_{j}*\widehat{x}(f)|^{2}\mathrm{d}f+\varepsilon_{1}\|\widehat{x}^{\prime}(f)-\widehat{x}(f)\|^{2}_{\infty}$
$\displaystyle\leq$
$\displaystyle~{}\int_{-F_{0}}^{F_{0}}|\widehat{M}_{j}*\widehat{x}^{\prime}(f)-\widehat{M}_{j}*\widehat{x}(f)|^{2}\mathrm{d}f+4\varepsilon_{1}\|\widehat{x}\|^{2}_{\infty}$
$\displaystyle\lesssim$
$\displaystyle~{}2F_{0}T^{4}\gamma^{2}\cdot\|\widehat{x}\|_{1}^{2}+4\varepsilon_{1}\|\widehat{x}\|^{2}_{\infty}$
$\displaystyle\lesssim$
$\displaystyle~{}\underbrace{(F_{0}T^{4}\gamma^{2}+\varepsilon_{1}/F^{2})\cdot\|\widehat{x}\|_{1}^{2}}_{\mathrm{err}}$
(100)

where the second step follows from Lemma B.5, the third step follows from
$\|\widehat{x}^{\prime}(f)-\widehat{x}(f)\|^{2}_{\infty}\leq(\|\widehat{x}^{\prime}(f)\|_{\infty}+\|\widehat{x}(f)\|_{\infty})^{2}=(2\|\widehat{x}(f)\|_{\infty})^{2}=4\|\widehat{x}\|^{2}_{\infty}$
due to Eq. (97), the forth step follows from Eq. (99), the fifth step follows
from $\|\widehat{x}\|_{\infty}\leq\|\widehat{x}\|_{1}$.

Then we can upper bound the LHS
$\int_{0}^{T}|x^{\prime}(t)-x(t)|^{2}\mathrm{d}t$ as follows:

$\displaystyle~{}\int_{0}^{T}|x^{\prime}(t)-x(t)|^{2}\mathrm{d}t$
$\displaystyle=$
$\displaystyle~{}\int_{0}^{T}\mathrm{rect}_{T}(t)|x^{\prime}(t)-x(t)|^{2}\mathrm{d}t$
$\displaystyle\leq$
$\displaystyle~{}\int_{0}^{T}\sum_{j=-K}^{K}(\frac{c_{0}}{(1-2\varepsilon_{0})\sqrt{2\pi}}){M}_{j}^{2}(t)\cdot|x^{\prime}(t)-x(t)|^{2}\mathrm{d}t$
$\displaystyle\leq$
$\displaystyle~{}\int_{0}^{T}\sum_{j=-K}^{K}c_{0}{M}_{j}^{2}(t)\cdot|x^{\prime}(t)-x(t)|^{2}\mathrm{d}t$
$\displaystyle\leq$
$\displaystyle~{}c_{0}\cdot\sum_{j=-K}^{K}\int_{-\infty}^{\infty}{M}_{j}^{2}(t)\cdot|x^{\prime}(t)-x(t)|^{2}\mathrm{d}t$
$\displaystyle\lesssim$ $\displaystyle~{}c_{0}K\cdot\mathrm{err}$
$\displaystyle\lesssim$ $\displaystyle~{}\mathrm{err}$

where the second step follows from Claim B.3 and
${M}_{j}^{2}(t)={M}_{c_{0}j\varepsilon_{0}^{2}T,\varepsilon_{0}^{4}T^{2}}(t)$,
the third step follows from $\varepsilon_{0}=0.01$, the forth step follows
from relaxing integral range, the fifth step follows from Eq. (100), the last
step follows from $c_{0}K\lesssim 1$ due to Lemma B.7.

∎

###  B.4 Fast optimal-sparsity Fourier sparse recovery

######  Corollary B.9 (Our result).

For any $F>0,T>0,\varepsilon>0$. Let
$x^{*}(t)=\sum_{j=1}^{k}v_{j}\exp({2\pi\mathbf{i}f_{j}t})$ with $|f_{j}|\leq
F$ for $j\in[k]$. For observation $x(t)=x^{*}(t)+g(t)$, there exists an
algorithm that takes

$m=O(\varepsilon^{-1}k^{2}\log^{3}(k)\log(FT/(\delta\rho)))$

random samples $t_{1},\dotsc,t_{m}\in[0,T]$, runs in
$({\varepsilon}^{-1}FT)^{O(k)}$ time, and outputs
$y(t)=\sum_{j=1}^{k}\widetilde{v}_{j}\exp({2\pi\mathbf{i}\widetilde{f}_{j}t})$
such that

$\displaystyle\|y(t)-x^{*}(t)\|_{T}\leq(1+\varepsilon)\|g(t)\|_{T}+\delta\|\widehat{x}^{*}(f)\|_{1},$

holds with probability $1-\rho$.

###### Proof.

Let
$N_{f}=O(\frac{\delta}{T\sqrt{FT\log(1/\delta)}})\cdot\mathbb{Z}\cap[-F,F]$
denote a net of frequencies. Because

$\displaystyle\frac{\delta}{T\sqrt{F_{0}T}}\gtrsim$
$\displaystyle~{}\frac{\delta}{T\sqrt{\log^{1/2}(F/\varepsilon_{1})+FT}}$
$\displaystyle\geq$
$\displaystyle~{}\frac{\delta}{T\sqrt{\log^{1/2}(FT/\delta^{2})+FT}}$
$\displaystyle\geq$
$\displaystyle~{}\frac{\delta}{T\sqrt{\log(FT)+\log(1/\delta)+FT}}$
$\displaystyle\geq$ $\displaystyle~{}\frac{\delta}{T\sqrt{FT\log(1/\delta)}}$

where the first step follows from
$F_{0}=\Omega(T^{-1}\log^{1/2}(F/\varepsilon_{1})+F)$, the second step follows
from setting $\varepsilon_{1}=\delta^{2}/T$.

By Theorem B.8, for any signal
$x^{*}(t)=\sum_{j=1}^{k}v_{j}\exp({2\pi\mathbf{i}f_{j}t})$, there exists a
$k$-Fourier-sparse signal
$\widetilde{x}(t)=\sum_{j=1}^{k}v^{\prime}_{j}\exp({2\pi\mathbf{i}f^{\prime}_{j}t})$
such that,

$\|x^{*}(t)-\widetilde{x}(t)\|_{T}\leq\delta\|\widehat{x}^{*}(f)\|_{1}$

and $f^{\prime}_{1},\cdots,f^{\prime}_{k}\subseteq N_{f}$.

Because we have that

$\displaystyle\|y(t)-x^{*}(t)\|_{T}\leq$
$\displaystyle~{}\|y(t)-\widetilde{x}(t)\|_{T}+\|\widetilde{x}(t)-x^{*}(t)\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}\|y(t)-\widetilde{x}(t)\|_{T}+\delta\|\widehat{x}^{*}(f)\|_{1}.$

Let $S$ be the set of i.i.d samples from $D(t)$ of size
$O(\varepsilon^{-1}k\log^{3}(k)\log(1/\rho_{0}))$, $w$ be the corresponding
weight in Algorithm 13 Procedure SparseFT line 3. By Lemma 6.5, we have that,
for any $\cal F$, with probability at least $1-\rho_{0}$,

$\displaystyle(1-\sqrt{\varepsilon})\|x\|_{T}\leq\|x\|_{S,w}\leq(1+\sqrt{\varepsilon})\|x\|_{T}.$

In total, we enumerate $({\delta}^{-1}FT)^{O(k)}$ function family ${\cal F}$
in Algorithm 13 Procedure SparseFT line 6. By taking
$\rho_{0}=\rho{({\delta}(FT)^{-1})^{O(k)}}$, we have that the total success
probability is at least

$\displaystyle(1-\rho_{0})^{({\delta}^{-1}FT)^{O(k)}}\geq
1-{({\delta}^{-1}FT)^{O(k)}}\cdot\rho_{0}\geq 1-\rho$

Thus, by Lemma 9.11, with probability at least $1-\rho$, sampling $S$ and $w$
forms a $\varepsilon$-WBSP for every $\cal F$.

Finally, we bound $\|y(t)-\widetilde{x}(t)\|_{T}$ as follows,

$\displaystyle\|y(t)-\widetilde{x}(t)\|_{T}\leq$
$\displaystyle~{}(1+O(\varepsilon))\|x(t)-\widetilde{x}(t)\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}(1+O(\varepsilon))(\|x(t)-x^{*}(t)\|_{T}+\|x^{*}(t)-\widetilde{x}(t)\|_{T})$
$\displaystyle\leq$
$\displaystyle~{}(1+O(\varepsilon))(\|g(t)\|_{T}+\delta\|\widehat{x}^{*}(f)\|_{1})$

where the first step follows from the proof of Theorem 9.4.

Combine the results above we have that

$\displaystyle\|y(t)-x^{*}(t)\|_{T}\leq$
$\displaystyle~{}\|y(t)-\widetilde{x}(t)\|_{T}+\delta\|\widehat{x}^{*}(f)\|_{1}$
$\displaystyle\leq$
$\displaystyle~{}(1+O(\varepsilon))\|g(t)\|_{T}+O(\delta)\|\widehat{x}^{*}(f)\|_{1}.$

Note that our sample complexity is
$|S|=O(\varepsilon^{-1}k\log^{3}(k)\log(1/\rho_{0}))=O(\varepsilon^{-1}k^{2}\log^{3}(k)\log(FT/(\delta\rho)))$.

∎

Algorithm 13 Recover $k$-sparse FT

1:procedure SparseFT($x,k,F,T,\varepsilon,\delta,\rho$) $\triangleright$
Corollary B.9

2: $m\leftarrow O(\varepsilon^{-1}k^{2}\log^{3}(k)\log(FT/(\delta\rho)))$

3: $S,w\leftarrow\textsc{WeightedSketch}(m,k,T)$$\triangleright$ Algorithm 7

4: We observe the signal $x(t)$ for each $t\in S$

5: $N_{f}\leftarrow
O(\frac{\varepsilon}{T\sqrt{FT\log(1/\varepsilon)}})\cdot\mathbb{Z}\cap[-F,F]$

6: for $\\{f^{\prime}_{1},\dotsc,f^{\prime}_{k}\\}\in\binom{N_{f}}{[k]}$ do

7: Let ${\cal
F}={\text{span}\\{\exp({2\pi\mathbf{i}f^{\prime}_{1}t}),\cdots,\exp({2\pi\mathbf{i}f^{\prime}_{k}t})\\}}$

8: $h(t)\leftarrow{\mathrm{argmin}}_{h\in{\cal F}}\|h(t)-x(t)\|_{S,w}$

9: if $\|h(t)-x(t)\|_{S,w}\leq\|\widetilde{f}(t)-x(t)\|_{S,w}$ then

10: $\widetilde{f}(t)\leftarrow h(t)$

11: end if

12: end for

13: return $\widetilde{f}(t)$

14:end procedure

######  Lemma B.10 (Running time of Lemma B.9).

Procedure SparseFT in Algorithm 13 runs in
$O(({\delta}^{-1}{FT})^{O(k)}\log(1/\rho))$ times.

###### Proof.

In each call of the Procedure SparseFT in Algorithm 13,

  * •

In the for loop, it repeats the line 8 for
$({\delta}^{-1}{\log^{0.5}(1/\delta)(FT)^{1.5}})^{k}$ times.

  * •

Note that each 8 of Procedure SparseFT in Algorithm 13 is solving linear
regression. This part takes
$O(\varepsilon^{-1}k^{\omega+1}\log^{3}(k)\log(FT/(\delta\rho)))$ time.

So, the time complexity of Procedure SparseFT in Algorithm 13 is

$\displaystyle O(({\delta}^{-1}{\log^{0.5}(1/\delta)(FT)^{1.5}})^{k})\cdot
O(\varepsilon^{-1}k^{\omega+1}\log^{3}(k)\log(FT/(\delta\rho)))=O(({\varepsilon}^{-1}{FT})^{O(k)}\log(1/\rho)).$

∎

###  B.5 Semi-continuous approximation with a constant frequency gap

In this section, we show that the semi-continuous approximation result in
previous section can be further improved in terms of the frequency gap.

We first consider the one-sparse case in the following lemma.

######  Lemma B.11.

Let $0<\delta<0.1$ be a parameter. Let $x^{*}=v^{*}\exp(2\pi\mathbf{i}f^{*}t)$
be a function such that $f^{*}\in[-c/T,c/T]$. Then, there exists
$k>\log(1/\delta)$, $F\lesssim k/T$, $f_{1},\dots,f_{k}\in
c/T\mathbb{Z}\cap[-F,F]$, and $v_{1},\dots,v_{k}\in\mathbb{C}$ and for the
function

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

we have that

$\displaystyle\|x^{*}-\widetilde{x}\|_{T}\lesssim\delta|v^{*}|$

###### Proof.

Note that $x^{*}(t)$ can be written as

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

Now consider the Taylor expansion of

$\displaystyle\exp(2\pi\mathbf{i}ft)=\sum_{j=0}^{\infty}\frac{(2\pi\mathbf{i}ft)^{j}}{j!}$

Note that since $f\in[-F,F]$, $t\in[0,T]$, $FT\lesssim k$, we have

$\displaystyle\sum_{j=k+1}^{\infty}\lvert\frac{(2\pi\mathbf{i}ft)^{j}}{j!}\rvert\leq$
$\displaystyle~{}\sum_{j=k+1}^{\infty}\lvert\frac{(2e\pi\mathbf{i}ft)^{j}}{j^{j}}\rvert$
$\displaystyle\leq$ $\displaystyle~{}\sum_{j=k+1}^{\infty}\frac{1}{\exp(j)}$
$\displaystyle\leq$ $\displaystyle~{}\frac{1}{\exp(k)}\cdot\frac{1}{1-1/e}$
$\displaystyle\lesssim$ $\displaystyle~{}\delta_{1}$ (101)

where the first step follows from Stirling’s formula
$n!\geq\sqrt{2\pi}n^{n+0.5}\exp(-n)$, the second step follows from $2e^{2}\pi
f\geq j$, the last step follows from $k\geq\log(1/\delta_{1})$.

In particular, if we define the approximator of exponential function

$\displaystyle g_{f}(x)=\sum_{j=0}^{k}\frac{(2\pi\mathbf{i}ft)^{j}}{j!}$

then over the interval $t\in[0,T]$, $f\in[-F,F]$, $FT\lesssim k$,

$\displaystyle|\exp(2\pi\mathbf{i}ft)-g_{f}(t)|=$
$\displaystyle~{}|\sum_{j=k+1}^{\infty}\frac{(2\pi\mathbf{i}ft)^{j}}{j!}|$
$\displaystyle\leq$
$\displaystyle~{}\sum_{j=k+1}^{\infty}\lvert\frac{(2\pi\mathbf{i}ft)^{j}}{j!}\rvert$
$\displaystyle\leq$ $\displaystyle~{}\delta_{1}.$ (102)

where the first step follows from the definition of $g_{f}(x)$, the second
step follows from the triangle inequality, the last step follows from Eq.
(101).

Next, let ${\cal V}_{k}(f)=(1,f,\cdots,f^{k})$. For $f^{*}\in[-c/T,c/T]$, we
can write the vector

$\displaystyle{\cal V}_{k}(f^{*})=w_{1}{\cal V}_{k}(f_{1})+\dots+w_{k}{\cal
V}_{k}(f_{k})$

for some real numbers (depending on $f^{*}$) $w_{1},\dots,w_{k}$, because
${\cal V}_{k}(f_{1}),\cdots,{\cal V}_{k}(f_{k})$ is linear independence. Thus,

$\displaystyle g_{f^{*}}(t)=w_{1}g_{f_{1}}(t)+\dots+w_{k}g_{f_{k}}(t)$ (103)

for the same weights. Now note that by (B.5), for all $t\in[0,T]$,

$\displaystyle\lvert x^{*}(t)-v^{*}g_{f^{*}}(t)\rvert=$
$\displaystyle~{}\lvert v^{*}(g_{f^{*}}(t)-\exp(2\pi\mathbf{i}f^{*}t))\rvert$
$\displaystyle\leq$ $\displaystyle~{}|v^{*}|\delta_{1}.$

Then, because $g_{f}(t)$ can be expressed by $g_{f_{j}}(t),j\in[k]$, we have
that

$\displaystyle\lvert
x^{*}(t)-\sum_{j=0}^{k}v^{*}g_{f_{j}}(t)w_{j}\rvert=\lvert
x^{*}(t)-v^{*}g_{f^{*}}(t)\rvert$

which is follows from Eq. (103).

Note that

$\displaystyle\sum_{j=1}^{k}\lvert w_{j}\rvert\leq C_{1}$

So by Eq. (B.5), we will transform the approximator of exponential function
back to exponential function. For $\forall t\in[0,T]$,

$\displaystyle\lvert\sum_{j=1}^{k}(g_{f_{j}}(t)-\exp(2\pi\mathbf{i}f_{j}t))(v^{*}w_{j})\rvert\leq
C_{1}|v^{*}|\delta_{1}$

Therefore, we can conclude that for $\forall t\in[0,T]$

$\displaystyle\lvert
x^{*}(t)-\sum_{j=1}^{k}(v^{*}w_{j})\exp(2\pi\mathbf{i}f_{j}t)\rvert\leq
C_{1}|v^{*}|\delta_{1}$

and setting

$\displaystyle h(x)=\sum_{j=1}^{k}(v^{*}w_{j})\exp(2\pi\mathbf{i}f_{j}t)$

immediately leads to the desired conclusion. ∎

Lemma B.11 immediately gives the following corollary by taking linear
summation over $k$ frequencies.

######  Corollary B.12.

Let $0<\delta<0.1$ be a parameter. Let $x^{*}$ be any $k$-Fourier-sparse
signal. Then, there exists $\widetilde{k}\lesssim k\log(k/\delta)$, universal
constant $c\in(0,1)$, $f_{1},\cdots,f_{k}\in c/T\mathbb{Z}$, and
$v_{1},\dots,v_{k}\in\mathbb{C}$ and for the function

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

we have that

$\displaystyle\|x^{*}-\widetilde{x}\|_{T}\lesssim\delta\|\widehat{x}^{*}(f)\|_{1}$

##  Appendix C Improving Fourier Interpolation Precision in a Smaller Range

In this section, we show that the approximation error of the Fourier
interpolation algorithm developed in Section 12 can be further improved, if we
only care about the signal in a shorter time duration $[0,(1-c)T]$ for
$c\in(0,1)$. The main result of this section is Theorem C.4.

###  C.1 Control noise

######  Lemma C.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 observable signal. Let
$\mathcal{N}_{1}^{2}:=\varepsilon_{1}(\|g(t)\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2})$.
Let $C_{1},\cdots,C_{l}$ are the $\mathcal{N}_{1}$-heavy clusters from
Definition 12.11. Let $S^{*}$ denotes the set of frequencies
$f^{*}\in\\{f_{j}\\}_{j\in[k]}$ such that, $f^{*}\in C_{i}$ for some
$i\in[l]$, and

$\displaystyle\int_{C_{i}}|\widehat{x^{*}\cdot H}(f)|^{2}\mathrm{d}f\geq
T\mathcal{N}_{1}^{2}/k,$

Let $S$ denotes the set of frequencies $f^{*}\in S^{*}$ such that, $f^{*}\in
C_{j}$ for some $j\in[l]$, and

$\displaystyle\int_{C_{j}}|\widehat{x\cdot
H}(f)|^{2}\mathrm{d}f\geq\varepsilon_{2}T\mathcal{N}_{1}^{2}/k,$

Then, we have that,

$\displaystyle\|x-x_{S}\|_{T^{\prime}}+\|x_{S}-x^{*}\|_{T^{\prime}}\leq(\sqrt{2}+O(\sqrt{\varepsilon}+c))\|g\|_{T}+O(\sqrt{\delta})\|x^{*}\|_{T}.$

###### Proof.

Following from the fact that $\sqrt{1+\varepsilon}=1+O(\varepsilon)$ for
$\varepsilon<1$, we have

$\mathcal{N}_{1}=\sqrt{\varepsilon_{1}(\|g\|_{T}^{2}+\delta\|x^{*}\|_{T}^{2})}\leq\sqrt{\varepsilon_{1}}\|g\|_{T}+\sqrt{\delta\varepsilon_{1}}\|x^{*}\|_{T}.$

We have that

$\displaystyle\|x-x_{S^{*}}\|_{T}\leq$
$\displaystyle~{}\|x-x^{*}\|_{T}+\|x^{*}-x_{S^{*}}\|_{T}$ $\displaystyle\leq$
$\displaystyle~{}\|g\|_{T}+\|x^{*}-x_{S^{*}}\|_{T}$ $\displaystyle\leq$
$\displaystyle~{}\|g\|_{T}+(1+\varepsilon)\mathcal{N}_{1},$ (104)

where the first step follows from triangle inequality, the second step follows
the definition of $g$, the third step follows from Claim 12.12.

Therefore,

$\displaystyle~{}\|x-x_{S}\|_{T^{\prime}}+\|x_{S}-x^{*}\|_{T^{\prime}}$
$\displaystyle\leq$
$\displaystyle~{}\|x-x_{S}\|_{T^{\prime}}+\|x_{S}-x_{S^{*}}\|_{T^{\prime}}+\|x_{S^{*}}-x^{*}\|_{T^{\prime}}$
$\displaystyle\leq$
$\displaystyle~{}\|x-x_{S}\|_{T^{\prime}}+\|x_{S}-x_{S^{*}}\|_{T^{\prime}}+(1+2c)\|x_{S^{*}}-x^{*}\|_{T^{\prime}}$
$\displaystyle\leq$
$\displaystyle~{}(1+2\delta)\|H(x-x_{S})\|_{T^{\prime}}+(1+2\delta)\|H(x_{S}-x_{S^{*}})\|_{T^{\prime}}+(1+2c)\|x_{S^{*}}-x^{*}\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}(1+O(\delta))(1+2c)(\|H(x-x_{S})\|_{T}+\|H(x_{S}-x_{S^{*}})\|_{T})+(1+\varepsilon)(1+O(c))\mathcal{N}_{1}$
$\displaystyle\leq$
$\displaystyle~{}(1+O(\delta))(1+2c)\sqrt{2}\sqrt{\|H(x-x_{S})\|^{2}_{T}+\|H(x_{S}-x_{S^{*}})\|^{2}_{T}}+(1+\varepsilon)(1+O(c))\mathcal{N}_{1}$
$\displaystyle\leq$
$\displaystyle~{}(1+O(\delta))(1+O(\sqrt{\varepsilon_{2}}))(1+O(c))\sqrt{2}\|x-x_{S^{*}}\|_{T}+(1+\varepsilon)(1+O(c))\mathcal{N}_{1}$
$\displaystyle\leq$
$\displaystyle~{}(\sqrt{2}+O(\delta+\sqrt{\varepsilon_{2}}+c))(\|g\|_{T}+(1+\varepsilon)\mathcal{N}_{1})+(1+\varepsilon)(1+O(c))\mathcal{N}_{1}$
$\displaystyle\leq$
$\displaystyle~{}(\sqrt{2}+O(\sqrt{\varepsilon}+c))\|g\|_{T}+O(\sqrt{\delta})\|x^{*}\|_{T},$

where the first step follows from triangle inequality, the second step follows
from for any function $x:\mathbb{R}\rightarrow\mathbb{C}$,
$(1-c)\|x\|_{T^{\prime}}\leq\|x\|_{T}$, the third step follows from Property
i@ of Lemma 12.7 and $(1-c)/2<(\frac{1}{2}-\frac{2}{s_{1}})s_{3}$, the forth
step follows from Claim 12.12, the fifth step follows from
$\|H(x-x_{S})\|_{T}+\|H(x_{S}-x_{S^{*}})\|_{T}\leq\sqrt{2}\sqrt{\|H(x-x_{S})\|_{T}^{2}+\|H(x_{S}-x_{S^{*}})\|_{T}^{2}}$,
the sixth step follows from Lemma 12.21, the seventh step follows from Eq.
(68), the last step follows from
$\varepsilon=\varepsilon_{0}=\varepsilon_{1}=\varepsilon_{2}$. ∎

##### Parameters setting

By Section C.3 in [CKPS16], we choose parameters for filter function
$(H(t),\widehat{H}(f))$ as follows:

  * •

By Eq. (12.2) in the proof of Property vi@ of filter function
$(H(t),\widehat{H}(f))$, we need
$(1-s_{3}(1-\frac{2}{s_{1}}))\cdot\widetilde{O}(k^{4})\leq\varepsilon$, thus
we have that
$\min(\frac{1}{1-s_{3}},s_{1})\geq\widetilde{O}(k^{4})/\varepsilon$.

  * •

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

  * •

In the proof of Lemma C.1, we set
$(1-c)/2<(\frac{1}{2}-\frac{2}{s_{1}})s_{3}$. Thus, we have that
$\min(s_{3},1-\frac{4}{s_{1}})\geq 1-\frac{c}{2}$ or equivalently
$\min(\frac{1}{1-s_{3}},s_{1}/4)\geq\frac{2}{c}$.

  * •

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

###  C.2 $(\sqrt{2}+\varepsilon)$-approximation ratio

######  Corollary C.2 (Corollary of Theorem 12.36).

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 observable signal where $\|g(t)\|_{T}^{2}\leq
c_{0}\|x^{*}(t)\|_{T}^{2}$ for a sufficiently small constant $c_{0}$. Then
Procedure FrequencyRecoveryKCluster returns a set $L$ of
$O(k/(\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}))$ frequencies that covers
all $\mathcal{N}_{2}$-heavy clusters of $x^{*}$, which uses
$\mathrm{poly}(k,c^{-1},\varepsilon^{-1},\varepsilon_{0}^{-1},\varepsilon_{1}^{-1},\varepsilon_{2}^{-1},\log(1/\delta))\log(FT)$
samples and
$\mathrm{poly}(k,c^{-1},\varepsilon^{-1},\varepsilon_{0}^{-1},\varepsilon_{1}^{-1},\varepsilon_{2}^{-1},\log(1/\delta))\log^{2}(FT)$
time.

In particular, for
$\Delta_{0}=c^{-1}\varepsilon^{-1}\mathrm{poly}(k,\log(1/\delta))/T$ and
$\mathcal{N}_{2}^{2}:=\varepsilon_{1}\varepsilon_{2}(\|g(t)\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2})$,
with probability $1-2^{-\Omega(k)}$, for any $f^{*}$ with

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

there exists an $\widetilde{f}\in L$ satisfying

$|f^{*}-\widetilde{f}|\lesssim\Delta_{0}\sqrt{\Delta_{0}T}.$

######  Remark C.3.

The proof is similar with the proof of Theorem 12.36.

######  Theorem C.4 ($(\sqrt{2}+\varepsilon)$-approximate Fourier
interpolation algorithm with shrinking range).

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

$\|y-x^{*}\|_{T^{\prime}}\leq(\sqrt{2}+\varepsilon+c)\|g\|_{T}+\delta\|x^{*}\|_{T}.$

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

######  Remark C.5.

[LLM21] considers the following guarantee: for parameter $\delta>0$,
$\|y(t)-x^{*}(t)\|_{(1-c)T}\leq\alpha\|g(t)\|_{T}+\delta\|\widehat{x}^{*}(f)\|_{1}$,
where $\alpha$ is the approximation ratio, $c$ is the shrinking factor.
[LLM21] uses $\mathrm{poly}(k,\log(1/\delta))\log(FT)$ samples and
$\mathrm{poly}(k,c^{-1},\log(1/\delta))\cdot\log^{2}(FT)$ time, and recovers a
$k\mathrm{poly}(1/c,\log(k/\delta))$-Fourier-sparse signal but only guarantee
for $c\in(0,1)$ and $\alpha=\mathrm{poly}(\log(k/(\delta c)))$.

###### Proof.

Let
$\mathcal{N}_{1}^{2}:=\varepsilon_{1}(\|g(t)\|_{T}^{2}+\delta\|x^{*}(t)\|_{T}^{2})$
be the heavy cluster parameter.

First, by Lemma 12.12, there is a set of frequencies $S^{*}\subset[k]$ and
$x_{S^{*}}(t)=\underset{j\in S^{*}}{\sum}v_{j}e^{2\pi\mathbf{i}f_{j}t}$ such
that

$\displaystyle\|x_{S^{*}}-x^{*}\|_{T}^{2}\leq(1+\varepsilon)\mathcal{N}_{1}^{2}.$
(106)

Furthermore, each $f_{j}$ with $j\in S$ belongs to an $\mathcal{N}_{1}$-heavy
cluster $C_{j}$ with respect to the filter function $H$ defined in Definition
12.6.

By Definition 12.11 of heavy cluster, it holds that

$\displaystyle\int_{C_{j}}|\widehat{H\cdot x^{*}}(f)|^{2}\mathrm{d}f\geq
T\mathcal{N}_{1}^{2}/k.$

By Definition 12.11, we also have $|C_{j}|\leq k\cdot\Delta_{h}$, where
$\Delta_{h}$ is the bandwidth of $\widehat{H}$.

Let $\Delta\in\mathbb{R}_{+}$, and $\Delta>k\cdot\Delta_{h}$, which implies
that $C_{j}\subseteq[f_{j}-\Delta,f_{j}+\Delta]$. Thus, we have

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

By Corollary 12.22, there is a set of frequencies $S\subset S^{*}$ and
$x_{S}(t)=\underset{j\in S}{\sum}v_{j}e^{2\pi\mathbf{i}f_{j}t}$ such that

$\displaystyle\|x_{S}-x_{S^{*}}\|_{T}^{2}\leq(1+O(\sqrt{\varepsilon_{2}}))\|x-x_{S^{*}}\|_{T}^{2}.$

Let $g^{\prime}=x-x_{S^{*}}$.

Now it is enough to recover only $x_{S}$, instead of $x^{*}$.

By applying Theorem C.2, there is an algorithm that outputs a set of
frequencies $L\subset\mathbb{R}$ such that,
$|L|=O(k/(\varepsilon_{0}\varepsilon_{1}\varepsilon_{2}))$, and with
probability at least $1-2^{-\Omega(k)}$, for any $f_{j}$ with $j\in S$, there
is a $\widetilde{f}\in L$ such that,

$\displaystyle|f_{j}-\widetilde{f}|\lesssim\Delta\sqrt{\Delta T}.$

We define a map $p:\mathbb{R}\rightarrow L$ as follows:

$\displaystyle p(f):=\arg\min_{\widetilde{f}\in
L}~{}|f-\widetilde{f}|~{}~{}~{}\forall f\in\mathbb{R}.$

Then, $x_{S}(t)$ can be expressed as

$\displaystyle x_{S}(t)=$ $\displaystyle~{}\sum_{j\in
S}v_{j}e^{2\pi\mathbf{i}f_{j}t}$ $\displaystyle=$ $\displaystyle~{}\sum_{j\in
S}v_{j}e^{2\pi\mathbf{i}\cdot p(f_{j})t}\cdot
e^{2\pi\mathbf{i}\cdot(f_{j}-p(f_{j}))t}$ $\displaystyle=$
$\displaystyle~{}\sum_{\widetilde{f}\in
L}e^{2\pi\mathbf{i}\widetilde{f}t}\cdot\sum_{j\in
S:~{}p(f_{j})=\widetilde{f}}v_{j}e^{2\pi\mathbf{i}(f_{j}-\widetilde{f})t},$

where the first step follows from the definition of $x_{S}(t)$, the last step
follows from interchanging the summations.

For each $\widetilde{f}_{i}\in L$, by Corollary 12.2 with
$x^{*}=x_{S},\Delta=\Delta\sqrt{\Delta T}$, we have that there exist degree
$d=O(T\Delta\sqrt{\Delta T}+k^{3}\log k+k\log 1/\delta)$ polynomials
$P_{i}(t)$ corresponding to $\widetilde{f}_{i}\in L$ such that,

$\displaystyle\|x_{S}(t)-\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\|_{T}\leq\delta\|x_{S}(t)\|_{T}$
(107)

Define the following function family:

$\displaystyle\mathcal{F}:=\mathrm{span}\Big{\\{}e^{2\pi\mathbf{i}\widetilde{f}t}\cdot
t^{j}~{}{|}~{}\forall\widetilde{f}\in L,j\in\\{0,1,\dots,d\\}\Big{\\}}.$

Note that $\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\in{\cal F}$.

By Claim 12.16, for function family $\cal F$,
$K_{\mathrm{Uniform[cT/2,T(1-c/2)]}}=O((|L|d)^{4}\log^{3}(|L|d))$.

By Lemma 12.18, we have that, choosing a set $W$ of
$O(\varepsilon^{-1}K_{\mathrm{Uniform[cT/2,T(1-c/2)]}}\log(|L|d/\rho))$ i.i.d.
samples uniformly at random over duration $[0,T]$ is a
$(\varepsilon,\rho)$-WBSP.

By Lemma 12.19, there is an algorithm that runs in
$O(\varepsilon^{-1}|W|(|L|d)^{\omega-1}\log(1/\rho))$-time using samples in
$W$, and outputs $y^{\prime}(t)\in{\cal F}$ such that, with probability
$1-\rho$,

$\displaystyle\|y^{\prime}(t)-\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\|_{T^{\prime}}\leq(1+\varepsilon)\|x(t)-\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\|_{T^{\prime}}$ (108)

Then by Lemma 12.3, we have that there is a $O(kd)$-Fourier-sparse signal
$y(t)$, such that

$\displaystyle\|y(t)-y^{\prime}(t)\|_{T^{\prime}}\leq\delta^{\prime}$ (109)

where $\delta^{\prime}>0$ is any positive real number. Thus, $y$ can be
arbitrarily close to $y^{\prime}$.

Moreover, the sparsity of $y(t)$ is $kd=kO(T\Delta\sqrt{\Delta T}+k^{3}\log
k+k\log 1/\delta)=\mathrm{poly}(k,\varepsilon^{-1},c^{-1},\log(1/\delta))$.

Therefore, the total approximation error can be upper bounded as follows:

$\displaystyle~{}\|y-x^{*}\|_{T^{\prime}}$ $\displaystyle\leq$
$\displaystyle~{}\|y-y^{\prime}\|_{T^{\prime}}+\Big{\|}y-\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\Big{\|}_{T^{\prime}}+\Big{\|}\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)-x^{*}\Big{\|}_{T^{\prime}}$
$\displaystyle\leq$
$\displaystyle~{}(1+0.1\varepsilon)\Big{\|}y-\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\Big{\|}_{T^{\prime}}+\Big{\|}\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)-x^{*}\Big{\|}_{T^{\prime}}$
$\displaystyle\leq$
$\displaystyle~{}(1+2\varepsilon)\Big{\|}x-\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\Big{\|}_{T^{\prime}}+\Big{\|}\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)-x^{*}\Big{\|}_{T^{\prime}}$
$\displaystyle\leq$
$\displaystyle~{}(1+2\varepsilon)(\Big{\|}x-x_{S}\Big{\|}_{T^{\prime}}+\Big{\|}x_{S}-x^{*}\Big{\|}_{T^{\prime}})+2(1+\varepsilon)\|x_{S}-\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\|_{T^{\prime}}$
$\displaystyle\leq$
$\displaystyle~{}(1+2\varepsilon)(\Big{\|}x-x_{S}\Big{\|}_{T^{\prime}}+\Big{\|}x_{S}-x^{*}\Big{\|}_{T^{\prime}})+O(\delta)\|x_{S}(t)\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}(1+2\varepsilon)(\sqrt{2}+O(\sqrt{\varepsilon}+c))\|g\|_{T}+O(\sqrt{\delta})\|x^{*}\|_{T}+O(\delta)\|x_{S}(t)\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}(1+2\varepsilon)(\sqrt{2}+O(\sqrt{\varepsilon}+c))\|g\|_{T}+O(\sqrt{\delta})\|x^{*}\|_{T}+O(\delta)(\|g\|_{T}+\|x^{*}\|_{T})$
$\displaystyle\leq$
$\displaystyle~{}(\sqrt{2}+O(\sqrt{\varepsilon}+c))\|g\|_{T}+O(\sqrt{\delta})\|x^{*}\|_{T},$

where the first step follows from triangle inequality, the second step follows
from Eq. (109), the third step follows from Eq. (108), the forth step follows
from Triangle Inequality again, the fifth step follows from Eq. (107), the
sixth step follows from Lemma C.1, the seventh step follows from Lemma 12.38,
and the last step is straightforward.

By re-scaling $\varepsilon$ and $\delta$, we prove the theorem.

∎

## References

  * [ASSN08] Abiodun M Aibinu, Momoh-Jimoh E Salami, Amir A Shafie, and Athaur R Najeeb.  Mri reconstruction using discrete fourier transform: a tutorial.  2008\.
  * [AW21] Josh Alman and Virginia Vassilevska Williams.  A refined laser method and faster matrix multiplication.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522–539. SIAM, 2021.
  * [BE06] Peter Borwein and Tamás Erdélyi.  Nikolskii-type inequalities for shift invariant function spaces.  Proceedings of the American Mathematical Society, 134(11):3243–3246, 2006.
  * [Boa15] Boualem Boashash.  Time-frequency signal analysis and processing: a comprehensive reference.  Academic press, 2015.
  * [BSS12] Joshua Batson, Daniel A Spielman, and Nikhil Srivastava.  Twice-ramanujan sparsifiers.  SIAM Journal on Computing, 41(6):1704–1721, 2012.
  * [Che52] Herman Chernoff.  A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.  The Annals of Mathematical Statistics, pages 493–507, 1952.
  * [CKPS16] Xue Chen, Daniel M Kane, Eric Price, and Zhao Song.  Fourier-sparse interpolation without a frequency gap.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 741–750. IEEE, 2016.
  * [CP19a] Xue Chen and Eric Price.  Active regression via linear-sample sparsification.  In Conference on Learning Theory (COLT), pages 663–695. PMLR, 2019\.
  * [CP19b] Xue Chen and Eric Price.  Estimating the frequency of a clustered signal.  In ICALP, 2019.
  * [CT65] James W Cooley and John W Tukey.  An algorithm for the machine calculation of complex fourier series.  Mathematics of computation, 19(90):297–301, 1965.
  * [Don06] D.L. Donoho.  Compressed sensing.  IEEE Transactions on Information Theory, 52(4):1289–1306, 2006\.
  * [GHI+13] Badih Ghazi, Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price, and Lixin Shi.  Sample-optimal average-case sparse fourier transform in two dimensions.  In 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1258–1265. IEEE, 2013.
  * [GIIS14] Anna C. Gilbert, Piotr Indyk, Mark A. Iwen, and Ludwig Schmidt.  Recent developments in the sparse fourier transform: A compressed fourier transform for big data.  IEEE Signal Process. Mag., 31(5):91–100, 2014.
  * [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, pages 563–578, 2012.
  * [HIKP12b] 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, pages 563–578, 2012.
  * [IK14] Piotr Indyk and Michael Kapralov.  Sample-optimal Fourier sampling in any constant dimension.  In IEEE 55th Annual Symposium onFoundations of Computer Science (FOCS), 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.
  * [JLS23] Yaonan Jin, Daogao Liu, and Zhao Song.  A robust multi-dimensional sparse fourier transform in the continuous setting.  In SODA, 2023.
  * [Kap16] Michael Kapralov.  Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 264–277, 2016.
  * [Kap17] Michael Kapralov.  Sample efficient estimation and recovery in sparse FFT via isolation on average.  In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 651–662. IEEE Computer Society, 2017.
  * [Kós08] Géza Kós.  Two turán type inequalities.  Acta Mathematica Hungarica, 119(3):219–226, 2008.
  * [KVZ19] Michael Kapralov, Ameya Velingker, and Amir Zandieh.  Dimension-independent sparse Fourier transform.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2709–2728. SIAM, https://arxiv.org/pdf/1902.10633.pdf, 2019.
  * [LG14] François Le Gall.  Powers of tensors and fast matrix multiplication.  In Proceedings of the 39th international symposium on symbolic and algebraic computation (ISSAC), pages 296–303. ACM, 2014.
  * [LLM21] Jerry Li, Allen Liu, and Ankur Moitra.  Sparsification for sums of exponentials and its algorithmic applications.  arXiv preprint arXiv:2106.02774, 2021.
  * [LS15] Yin Tat Lee and He Sun.  Constructing linear-sized spectral sparsification in almost-linear time.  In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 250–269. IEEE Computer Society, 2015.
  * [MMM21] Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  Learning with invariances in random features and kernel models.  In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 3351–3418. PMLR, 2021.
  * [Moi15] Ankur Moitra.  The threshold for super-resolution via extremal functions.  In STOC. arXiv preprint arXiv:1408.1681, 2015.
  * [NSW19] Vasileios Nakos, Zhao Song, and Zhengyu Wang.  (nearly) sample-optimal sparse fourier transform in any dimension; ripless and filterless.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1568–1577. IEEE, 2019.
  * [Opp11] Alan V. Oppenheim.  Lecture notes: Fourier transform properties.  https://ocw.aprende.org/resources/res-6-007-signals-and-systems-spring-2011/lecture-notes/MITRES_6_007S11_lec09.pdf, 2011\.
  * [Osg02] Brad Osgood.  Lecture notes for ee 261 the fourier transform and its applications.  2002\.
  * [OWN+97] Alan V Oppenheim, Alan S Willsky, Syed Hamid Nawab, Gloria Mata Hernández, et al.  Signals & systems.  Pearson Educación, 1997.
  * [Pri11] Eric Price.  Efficient sketches for the set query problem.  In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 41–56. SIAM, 2011.
  * [PS15] Eric Price and Zhao Song.  A robust sparse Fourier transform in the continuous setting.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 583–600. IEEE, 2015.