29:end data structure

######  Lemma 7.9 (Time and space complexities of Algorithms 5 and 6).

The Init procedure takes $O(nd^{\omega-1})$-time. The Query procedure takes
$O(d^{2}\log(n/d)+d^{\omega})$-time. The data structure uses $O(nd)$-space.

###### Proof.

We prove the space and time complexities of the data structure as follows:
Space complexity:  Let $m=n/d$. It is easy to see that there are $O(m)$ nodes
in the data structure. And each node has two $d$-by-$d$ matrices. Hence, the
total space used by the data structure is $O(n/d)\cdot O(d^{2})=O(nd)$.

##### Time complexity:

In the preprocessing stage, the time-consuming step is the call of BuildTree.
There are $O(m)$ internal nodes and $O(m)$ leaf nodes. Each internal node
takes $O(d^{2})$-time to construct the matrix $V_{1}$ (Line 22). For each leaf
node, it takes $O(d^{2})$-time to form the matrix $V_{2}$ (Line 15). And it
takes $O(d^{\omega})$-time to compute the matrix $V_{1}$ (Line 16). Hence, the
total running time of BuildTree is $O(md^{\omega})=O(nd^{\omega-1})$.

In the query stage, the While loop in the Query procedure (Line 17) is the
same as in Algorithm 4. Since there are $O(m)$ nodes in the tree, it takes
$O(d^{2}\log m)$-time. Then, in the BlockSampling procedure, it takes
$O(d^{\omega})$-time to compute the matrix $U$ (Line 9), and it takes
$O(d)$-time to sample an index from the distribution ${\cal D}_{l}$ (Line 11).
Hence, the total running time for each query is $O(d^{2}\log
m+d^{\omega})=O(d^{2}\log(n/d)+d^{\omega})$.

The proof of the lemma is then completed. ∎

######  Lemma 7.10 (Correctness of Algorithm 6).

The distribution of the output of the Query($A$) is ${\cal D}_{A}$ defined by
Eq. (16).

###### Proof.

For simplicity, we assume that all the coefficients $\alpha_{i}=1$.

Let $u_{0}=\mathsf{root},u_{1},\dots,u_{t}$ be the path in the While loop
(Line 17) from the root of the tree to the leaf with index $l\in[m]$. By the
construction of leaf node, we have

$\displaystyle
V_{1}=V_{2}V_{2}^{\top}=\begin{bmatrix}v_{(l-1)d+1}&\cdots&v_{ld}\end{bmatrix}\begin{bmatrix}v_{(l-1)d+1}^{\top}\\\
\vdots\\\ v_{ld}^{\top}\end{bmatrix}=\sum_{i=(l-1)d+1}^{ld}v_{i}v_{i}^{\top},$

which is the same as the $V$-matrix in Algorithm 4. Hence, similar to the
proof of Theorem 7.5, we have

$\displaystyle\Pr[u_{t}]=\prod_{j=1}^{t}\Pr[u_{j}|u_{j-1}]=\frac{\sum_{i=(l-1)d+1}^{ld}v_{i}^{\top}Av_{i}}{\sum_{i=1}^{n}v_{i}^{\top}Av_{i}}.$

where $\\{(l-1)d+1,\dots,ld\\}$ is the range of the node $u_{t}$ and
$\\{1,\dots,n\\}$ is the range of $u_{0}$.

Then, consider the BlockSampling procedure. Let $\\{v_{1},\dots,v_{d}\\}$ be
the vectors in the input block. At Line 9, we have

$\displaystyle U=V_{2}^{\top}AV_{2}=\begin{bmatrix}v_{1}^{\top}\\\ \vdots\\\
v_{d}^{\top}\end{bmatrix}A\begin{bmatrix}v_{1}&\cdots&v_{d}\end{bmatrix}.$

For $i\in[d]$, the $i$-th element in the diagonal of $U$ is

$\displaystyle U_{i,i}=v_{i}^{\top}Av_{i}.$

Hence,

$\displaystyle\Pr[\textsc{BlockSampling}=i]=\frac{v_{i}^{\top}Av_{i}}{\sum_{j=1}^{d}v_{j}^{\top}Av_{j}}.$

Therefore, for any $k\in[n]$, if $k=(l-1)d+r$ for some $l,r\in\mathbb{N}$,
then the sample probability is

$\displaystyle\Pr[\textsc{Query}(A)=k]=$
$\displaystyle~{}\Pr[\textsc{BlockSampling}=k~{}|~{}u_{t}=\text{Block}~{}l]\cdot\Pr[u_{t}=\text{Block}~{}l]$
$\displaystyle=$
$\displaystyle~{}\frac{v_{k}^{\top}Av_{k}}{\sum_{i=(l-1)d+1}^{ld}v_{i}^{\top}Av_{i}}\cdot\frac{\sum_{i=(l-1)d+1}^{ld}v_{i}^{\top}Av_{i}}{\sum_{i=1}^{n}v_{i}^{\top}Av_{i}}$
$\displaystyle=$
$\displaystyle~{}\frac{v_{k}^{\top}Av_{k}}{\sum_{i=1}^{n}v_{i}^{\top}Av_{i}}$
$\displaystyle=$ $\displaystyle~{}{\cal D}_{A}(k).$

The lemma is then proved. ∎

As a corollary, we get a WBSP using less space:

######  Corollary 7.11 (Space efficient implementation of WBSP).

By plugging-in the new data structure (Algorithms 5 and 6) to
FasterRandSamplingBSS (Algorithm 3), we get an algorithm taking
$O(|D|d^{2}+\gamma^{-2}d\cdot(d^{2}\log|D|+d^{\omega}))$-time and using
$O(|D|d)$-space.

###### Proof.

In the preprocessing stage of FasterRandSamplingBSS, we take
$O(|D|d^{2})$-time for Gram-Schmidt process and $O(|D|d^{\omega-1})$-time for
initializing the data structure (Algorithm 5).

The number of iterations is $\gamma^{-2}d$. In each iteration, the matrix
$E_{j}$ can be computed in $O(d^{\omega})$-time. And querying the data
structure takes $O(d^{2}\log(|D|/d)+d^{\omega})$-time.

Hence, the total running time is

$\displaystyle
O\left(|D|d^{2}+|D|d^{\omega-1}+\gamma^{-2}d(d^{2}\log(|D|/d)+d^{\omega})\right)=O\left(|D|d^{2}+\gamma^{-2}d^{\omega+1}+\gamma^{-2}d^{2}\log|D|\right).$

For the space complexity, the data structure uses $O(|D|d)$-space. The
algorithm uses $O(d^{2})$ extra space in preprocessing and each iteration.
Hence, the total space complexity is $O(|D|d)$. ∎

##  8 Sketch Distillation for Fourier Sparse Signals

In Section 6, we show an oblivious approach for sketching Fourier sparse
signals. However, there are two issues of using this sketching method in
Signal estimation: 1. The sketch size too large. 2. The noise in the observed
signal could have much larger energy on the sketching set than its average
energy. To resolve these two issues, in this section, we propose a method
called _sketch distillation_ to post-process the sketch obtained in Section 6
that can reduce the sketch size to $O(k)$ and prevent the energy of noise
being amplified too much. However, we need some extra information about the
signal $x^{*}(t)$: we assume that the frequencies of the noiseless signal
$x(t)$ are known. But the sketch distillation process can still be done
_partially oblivious_ , i.e., we do not need to access/sample the signal.

In Section 8.1, we show our distillation algorithms for one-dimensional
signals. Then, we generalize the sketch distillation for high-dimensional
signals in Section 8.2 and for discrete signals in Section 8.3.

###  8.1 Sketch distillation for one-dimensional signals

In this section, we show how to distill the sketch produced by Lemma 6.5 from
$O(k\log k)$-size to $O(k)$-size, using an $\varepsilon$-well-balanced
sampling procedure developed in Section 7.

######  Lemma 8.1 (Fast distillation for one-dimensional signal).

Given $f_{1},f_{2},\cdots,f_{k}\in\mathbb{R}$. Let $\eta=\min_{i\neq
j}|f_{j}-f_{i}|$. For any accuracy parameter $\varepsilon\in(0,0.1)$, there is
an algorithm FastDistill1D (Algorithm 7) that runs in
$O(\varepsilon^{-2}k^{\omega+1})$-time and outputs a set $S\subset[-T,T]$ of
size $s=O(k/\varepsilon^{2})$ and a weight vector $w\in\mathbb{R}^{s}_{\geq
0}$ such that, for any signal of the form
$x^{*}(t)=\sum_{j=1}^{k}v_{j}\exp({2\pi\mathbf{i}f_{j}t})$,

$\displaystyle(1-\varepsilon)\|x^{*}(t)\|_{T}\leq\|x^{*}(t)\|_{S,w}\leq(1+\varepsilon)\|x^{*}(t)\|_{T}$

holds with probability $0.99$.

Furthermore, for any noise signal $g(t)$, the following holds with high
probability:

$\displaystyle\|g\|_{S,w}^{2}\lesssim\|g\|_{T}^{2},$

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

###### Proof.

For the convenient, in the proof, we use time duration $[-T,T]$. Let $D(t)$ be
defined as follows:

$\displaystyle D(t)=\begin{cases}{c}/(1-|t/T|),&\text{ for }|t|\leq
T(1-{1}/k)\\\ c\cdot k,&\text{ for }|t|\in[T(1-{1}/k),T]\end{cases}$

where $c=O(T^{-1}\log^{-1}(k))$ a fixed value such that
$\int_{-T}^{T}D(t)\mathrm{d}t=1$.

First, we randomly pick up a set $S_{0}=\\{t_{1},\cdots,t_{s_{0}}\\}$ of
$s_{0}=O(\varepsilon_{0}^{-2}k\log(k)\log(1/\rho_{0}))$ i.i.d. samples from
$D(t)$, and let $w^{\prime}_{i}:=2/(Ts_{0}D(t_{i}))$ for $i\in[s_{0}]$ be the
weight vector, where $\varepsilon_{0},\rho_{0}$ are parameters to be chosen
later.

By Lemma 6.5, we know that $(S_{0},w^{\prime})$ gives a good weighted sketch
of the signal that can preserve the norm with high probability. More
specifically, with probability $1-\rho_{0}$,

$\displaystyle(1-\varepsilon_{0})\|x^{*}(t)\|^{2}_{T}\leq\|x^{*}(t)\|^{2}_{S_{0},w^{\prime}}\leq(1+\varepsilon_{0})\|x^{*}(t)\|^{2}_{T}.$
(17)

Then, we will select $s=O(k/\varepsilon_{1}^{2})$ elements from $S_{0}$ and
output the corresponding weights $w_{1},w_{2},\cdots,w_{s}$ by applying
RandBSS+ with the following parameter: replacing $d$ by $k$, $\varepsilon$ by
$\varepsilon_{1}^{2}$, and $D$ by
$D(t_{i})=w^{\prime}_{i}/\sum_{j\in[s_{0}]}w^{\prime}_{j}$ for $i\in[s_{0}]$.

By Theorem 7.3 and the property of WBSP (Definition 7.1), we obtain that with
probability $0.995$,

$\displaystyle(1-\varepsilon_{1})\|x^{*}(t)\|_{S_{0},w^{\prime}}^{2}\leq\|x^{*}(t)\|_{S,w}^{2}\leq(1+\varepsilon_{1})\|x^{*}(t)\|_{S_{0},w^{\prime}}^{2}.$

Combining with Eq. (17), we conclude that

$\displaystyle\|x^{*}\|_{S,w}^{2}\in$
$\displaystyle~{}[1-\varepsilon_{1},1+\varepsilon_{1}]\cdot\|x^{*}\|_{S_{0},w^{\prime}}^{2}$
$\displaystyle\in$
$\displaystyle~{}[(1-\varepsilon_{0})(1-\varepsilon_{1}),(1+\varepsilon_{0})(1+\varepsilon_{1})]\cdot\|x^{*}\|_{T}^{2}$
$\displaystyle\in$
$\displaystyle~{}[1-\varepsilon,1+\varepsilon]\cdot\|x^{*}\|_{T}^{2},$

where the second step follows from Eq. (17) and the last stpe follows by
taking $\varepsilon_{0}=\varepsilon_{1}=\varepsilon/4$.

The overall success probability follows by taking union bound over the two
steps and taking $\rho_{0}=0.001$. The running time of Algorithm 7 follows
from Claim 8.2. And the furthermore part follows from Claim 8.3.

The proof of the lemma is then completed. ∎

Algorithm 7 Fast distillation for one-dimensional signal

1:procedure WeightedSketch($k,\varepsilon,T,\mathcal{B}$)$\triangleright$
Lemma 6.5

2: $c\leftarrow O(T^{-1}\log^{-1}(k))$

3: $D(t)$ is defined as follows:  $\displaystyle
D(t)\leftarrow\begin{cases}{c}/((1-|t/T|)\log k),&\text{ if }|t|\leq
T(1-{1}/k),\\\ c\cdot k,&\text{ if }|t|\in[T(1-{1}/k),T].\end{cases}$

4: $S_{0}\leftarrow$ $O(\varepsilon^{-2}k\log(k))$ i.i.d. samples from $D$

5: for $t\in S_{0}$ do

6: $w_{t}\leftarrow\frac{2}{T\cdot|S_{0}|\cdot D(t)}$

7: end for

8: Set a new distribution $D^{\prime}(t)\leftarrow w_{t}/\sum_{t^{\prime}\in
S_{0}}w_{t^{\prime}}$ for all $t\in S_{0}$

9: return $D^{\prime}$

10:end procedure

11:procedure FastDistill1D($k$, $\varepsilon$, $F=\\{f_{1},\dots,f_{k}\\}$,
$T$) $\triangleright$ Lemma 8.1

12: Distribution
$D^{\prime}\leftarrow\textsc{WeightedSketch}(k,\varepsilon,T,\mathcal{B})$

13: Set the function family $\mathcal{F}$ as follows:
$\displaystyle{\mathcal{F}}:=\Big{\\{}f(t)=\sum_{j=1}^{k}v_{j}\exp(2\pi\mathbf{i}f_{j}t)~{}\Big{|}~{}v_{j}\in\mathbb{C}\Big{\\}}.$

14:
$s,\\{t_{1},t_{2},\cdots,t_{s}\\},w\leftarrow\textsc{RandBSS+}(k,\mathcal{F},D^{\prime},(\varepsilon/4)^{2})$
$\triangleright$ $s=O(k/\varepsilon^{2})$, Algorithm 3

15: return $\\{t_{1},t_{2},\cdots,t_{s}\\}$ and $w$

16:end procedure

######  Claim 8.2 (Running time of Procedure FastDistill1D in Algorithm 7).

Procedure FastDistill1D in Algorithm 7 runs in

$O(\varepsilon^{-2}k^{\omega+1})$

time.

###### Proof.

First, it is easy to see that Procedure WeightedSketch takes
$O(\varepsilon^{-2}k\log(k))$-time.

By Theorem 7.3 with $|D|=O(\varepsilon^{-2}k\log(k))$, $d=k$, we have that the
running time of Procedure RandBSS+ is

$\displaystyle~{}O\left(k^{2}\cdot\varepsilon^{-2}k\log(k)+\varepsilon^{-2}k^{3}\log\left(\varepsilon^{-2}k\log(k)\right)+\varepsilon^{-2}k^{\omega+1}\right)$
$\displaystyle=$ $\displaystyle~{}O\left(\varepsilon^{-2}k^{\omega+1}\right).$

Hence, the total running time of Algorithm 7 is
$O\left(\varepsilon^{-2}k^{\omega+1}\right)$.

∎

######  Claim 8.3 (Preserve the energy of noise).

Let $(S,w)$ be the outputs of Algorithm 7. Then, we have that

$\displaystyle\|g(t)\|^{2}_{S,w}\lesssim\|g(t)\|_{T}^{2},$

holds with probability $0.99$.

###### Proof.

For the convenient, in the proof, we use time duration $[-T,T]$. Algorithm 7
has two stages of sampling.

In the first stage, Procedure WeightedSketch samples a set
$S_{0}=\\{t_{1}^{\prime},\dots,t_{s_{0}}^{\prime}\\}$ of i.i.d. samples from
the distribution $D$, and a weight vector $w^{\prime}$. Then, we have

$\displaystyle\operatorname*{{\mathbb{E}}}\big{[}\|g(t)\|^{2}_{S_{0},w^{\prime}}\big{]}=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}\Big{[}\sum_{i=1}^{s_{0}}w^{\prime}_{i}|g(t_{i}^{\prime})|^{2}\Big{]}$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{s_{0}}\operatorname*{{\mathbb{E}}}_{t_{i}^{\prime}\sim
D}[w_{i}^{\prime}|g(t_{i}^{\prime})|^{2}]$ $\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{s_{0}}\operatorname*{{\mathbb{E}}}_{t_{i}^{\prime}\sim
D}\Big{[}\frac{2}{Ts_{0}D(t_{i}^{\prime})}|g(t_{i}^{\prime})|^{2}\Big{]}$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{s_{0}}\operatorname*{{\mathbb{E}}}_{t_{i}^{\prime}\sim\mathrm{Uniform([-T,T])}}[s_{0}^{-1}|g(t_{i}^{\prime})|^{2}]$
$\displaystyle=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{t\sim\mathrm{Uniform([-T,T])}}[|g(t)|^{2}]$
$\displaystyle=$ $\displaystyle~{}\|g(t)\|^{2}_{T}$

where the first step follows from the definition of the norm, the third step
follows from the definition of $w_{i}$, the forth step follows from
$\operatorname*{{\mathbb{E}}}_{t\sim
D_{0}(t)}[\frac{D_{1}(t)}{D_{0}(t)}f(t)]=\operatorname*{{\mathbb{E}}}_{t\sim
D_{1}(t)}f(t)$.

In the second stage, let $P$ denote the Procedure RandBSS+. With high
probability, $P$ is a $\varepsilon$-WBSP (Definition 7.1). By the Definition
7.1, each sample $t_{i}\sim D_{i}(t)$ and
$w_{i}=\alpha_{i}\cdot\frac{D^{\prime}(t_{i})}{D_{i}(t_{i})}$ in every
iteration $i\in[s]$, where $\sum_{i=1}^{s}\alpha_{i}\leq 5/4$ and
$D^{\prime}(t)=\frac{w^{\prime}_{t}}{\sum_{t^{\prime}\in
S_{0}}w^{\prime}_{t^{\prime}}}$. As a result,

$\displaystyle\operatorname*{{\mathbb{E}}}_{P}[\|g(t)\|^{2}_{S,w}]=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{P}\Big{[}\sum_{i=1}^{s}w_{i}|g(t_{i})|^{2}\Big{]}$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{s}\operatorname*{{\mathbb{E}}}_{t_{i}\sim
D_{i}(t_{i})}[w_{i}|g(t_{i})|^{2}]$ $\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{s}\operatorname*{{\mathbb{E}}}_{t_{i}\sim
D_{i}(t_{i})}\Big{[}\alpha_{i}\cdot\frac{D^{\prime}(t_{i})}{D_{i}(t_{i})}|g(t_{i})|^{2}\Big{]}$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{s}\operatorname*{{\mathbb{E}}}_{t_{i}\sim
D^{\prime}(t_{i})}[\alpha_{i}|g(t_{i})|^{2}]$ $\displaystyle\leq$
$\displaystyle~{}\underset{P}{\sup}\\{\sum_{i=1}^{s}\alpha_{i}\\}\operatorname*{{\mathbb{E}}}_{t\sim
D^{\prime}(t)}[|g(t)|^{2}]$ $\displaystyle=$
$\displaystyle~{}\underset{P}{\sup}\\{\sum_{i=1}^{s}\alpha_{i}\\}\|g(t)\|^{2}_{S_{0},w^{\prime}}\cdot(\sum_{t^{\prime}\in
S_{0}}w_{t^{\prime}}^{\prime})^{-1}$ $\displaystyle\lesssim$
$\displaystyle~{}\rho^{-1}\cdot\|g(t)\|^{2}_{S_{0},w^{\prime}}.$

where the first step follows from the definition of the norm, the third step
follows from $w_{i}=\alpha_{i}\cdot\frac{D^{\prime}(t_{i})}{D_{i}(t_{i})}$,
the forth step follows from $\operatorname*{{\mathbb{E}}}_{t\sim
D_{0}(t)}\frac{D_{1}(t)}{D_{0}(t)}f(t)=\operatorname*{{\mathbb{E}}}_{t\sim
D_{1}(t)}f(t)$, the sixth step follows from
$D^{\prime}(t)=\frac{w^{\prime}_{t}}{\sum_{t^{\prime}\in
S_{0}}w_{t^{\prime}}^{\prime}}$ and the definition of the norm, the last step
follows from $\sum_{i=1}^{s}\alpha_{i}\leq 5/4$ and $(\sum_{t^{\prime}\in
S_{0}}w^{\prime}_{t^{\prime}})^{-1}=O(\rho^{-1})$ with probability at least
$1-\rho/2$.

Hence, combining the two stages together, we have

$\displaystyle\operatorname*{{\mathbb{E}}}\big{[}\operatorname*{{\mathbb{E}}}_{P}[\|g(t)\|_{S,w}^{2}]\big{]}\lesssim\rho^{-1}\cdot\operatorname*{{\mathbb{E}}}\big{[}\|g(t)\|_{S_{0},w^{\prime}}^{2}\big{]}=\rho^{-1}\cdot\|g\|_{T}^{2}.$

And by Markov inequality and union bound, we have

$\displaystyle\Pr\left[\|g(t)\|^{2}_{S,w}\lesssim\rho^{-2}\|g(t)\|_{T}^{2}\right]\leq
1-\rho.$

∎

####  8.1.1 Sharper bound for the energy of orthogonal part of noise

In this section, we give a sharper analysis for the energy of $g^{\bot}$ on
the sketch, which is the orthogonal projection of $g$ to the space ${\cal F}$.
More specifically, we can decompose an arbitrary function $g$ into
$g^{\parallel}+g^{\bot}$, where $g^{\parallel}\in{\cal F}$ and
$\int_{[0,T]}\overline{h(t)}g^{\bot}(t)\mathrm{d}t=0$ for all $h\in{\cal F}$.
The motivation of considering $g^{\bot}$ is that $g^{\parallel}$ is also a
Fourier sparse signal and its energy will not be amplified in the Signal
Estimation problem. And the nontrivial part is to avoid the blowup of the
energy of $g^{\bot}$, which is shown in the following lemma:

######  Lemma 8.4 (Preserving the orthogonal energy).

Let ${\cal F}$ be an $m$-dimensional linear function family with an
orthonormal basis $\\{v_{1},\dots,v_{m}\\}$ with respect to a distribution
$D$. Let $P$ be the $\varepsilon$-WBSP that generate a sample set
$S=\\{t_{1},\dots,t_{s}\\}$ and coefficients $\alpha\in\mathbb{R}_{>0}^{s}$,
where each $t_{i}$ is sampled from distribution $D_{i}$ for $i\in[s]$. Define
the weight vector $w\in\mathbb{R}^{s}$ be such that
$w_{i}:=\alpha_{i}\frac{D(t_{i})}{D_{i}(t_{i})}$ for $i\in[s]$.

For any noise function $g(t)$ that is orthogonal to ${\cal F}$ with respect to
$D$, the following property holds with probability 0.99:

$\displaystyle\sum_{i=1}^{m}|\langle
g,v_{i}\rangle_{S,w}|^{2}\lesssim\varepsilon\|g\|_{D}^{2},$

where $\langle
g,v\rangle_{S,w}:=\sum_{j=1}^{s}w_{j}\overline{v(t_{j})}g(t_{j})$.

######  Remark 8.5.

We note that this lemma works for both continuous and discrete signals.

######  Remark 8.6.

$|\langle g,v_{i}\rangle_{S,w}|^{2}$ corresponds to the energy of $g$ on the
sketch points in $S$. On the other hand, if we consider the energy on the
whole time domain, we have $\langle g,v_{i}\rangle=0$ for all $i\in[m]$. The
above lemma indicates that this part of energy could be amplified by at most
$O(\varepsilon)$, as long as the sketch comes from a WBSP.

###### Proof.

We can upper-bound the expectation of $\sum_{i=1}^{m}|\langle
g,v_{i}\rangle_{S,w}|^{2}$ as follows:

$\displaystyle\operatorname*{{\mathbb{E}}}\Big{[}\sum_{i=1}^{m}|\langle
g,v_{i}\rangle_{S,w}|^{2}\Big{]}=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{D_{1},\dots,D_{s}}\Big{[}\|w\|_{1}^{2}\sum_{i=1}^{m}\big{|}\operatorname*{{\mathbb{E}}}_{t\sim
D^{\prime}}[\overline{v_{j}(t)}g(t)]\big{|}^{2}\Big{]}$ $\displaystyle=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{D_{1},\dots,D_{s}}\Big{[}\sum_{i=1}^{m}\big{|}\sum_{j=1}^{s}w_{j}\overline{v_{i}(t_{j})}g(t_{j})]\big{|}^{2}\Big{]}$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{m}\operatorname*{{\mathbb{E}}}_{D_{1},\dots,D_{s}}\Big{[}\big{|}\sum_{j=1}^{s}w_{j}\overline{v_{i}(t_{j})}g(t_{j})\big{|}^{2}\Big{]}$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{m}\operatorname*{{\mathbb{E}}}_{D_{1},\dots,D_{s}}\Big{[}\sum_{j=1}^{s}w_{j}^{2}|v_{i}(t_{j})|^{2}|g(t_{j})|^{2}\Big{]}$
$\displaystyle=$
$\displaystyle~{}\sum_{j=1}^{s}\operatorname*{{\mathbb{E}}}_{D_{j}}\Big{[}\sum_{i=1}^{m}w_{j}|v_{i}(t_{j})|^{2}\cdot
w_{j}|g(t_{j})|^{2}\Big{]}$ $\displaystyle\leq$
$\displaystyle~{}\sum_{j=1}^{s}\sup_{t\in
D_{j}}\Big{\\{}w_{j}\sum_{i=1}^{m}|v_{i}(t)|^{2}\Big{\\}}\cdot\operatorname*{{\mathbb{E}}}_{D_{j}}[w_{j}|g(t_{j})|^{2}],$

where the first step follows from Fact 8.7, the second step follows from the
definition of $D^{\prime}$, the third follows from the linearity of
expectation, the forth step follows from Fact 8.8, the last step follows by
pulling out the maximum value of $w_{j}\sum_{i=1}^{k}|v_{i}(t)|^{2}$ from the
expectation.

Next, we consider the first term:

$\displaystyle\sup_{t\in
D_{j}}\Big{\\{}w_{j}\sum_{i=1}^{m}|v_{i}(t)|^{2}\Big{\\}}=$
$\displaystyle~{}\sup_{t\in
D_{j}}\Big{\\{}\alpha_{j}\frac{D(t)}{D_{j}(t)}\sum_{i=1}^{m}|v_{i}(t)|^{2}\Big{\\}}$
$\displaystyle=$ $\displaystyle~{}\alpha_{j}\sup_{t\in
D_{j}}\Big{\\{}\frac{D(t)}{D_{j}(t)}\sup_{h\in\mathcal{F}}\big{\\{}\frac{|h(t)|^{2}}{\|h\|_{D}^{2}}\big{\\}}\Big{\\}}$
$\displaystyle=$ $\displaystyle~{}\alpha_{j}K_{\mathsf{IS},D_{j}}.$

where the first step follows from the definition of $w_{j}$, the second step
follows from Fact 8.9 that
$\underset{h\in\mathcal{F}}{\sup}\\{\frac{|h(t_{j})|^{2}}{\|h\|_{D}^{2}}\\}=\sum_{i=1}^{k}|v_{i}(t_{j})|^{2}$,
the last step follows from the definition of $K_{\mathsf{IS},D_{j}}$ (Eq.
(7)).

Then, we bound the last term:

$\displaystyle\operatorname*{{\mathbb{E}}}_{D_{j}}[w_{j}|g(t_{j})|^{2}]=\underset{t_{j}\sim
D_{j}}{\operatorname*{{\mathbb{E}}}}\Big{[}\alpha_{j}\frac{D(t_{j})}{D_{j}(t_{j})}|g(t_{j})|^{2}\Big{]}=\alpha_{j}\underset{t_{j}\sim
D}{\operatorname*{{\mathbb{E}}}}[|g(t_{j})|^{2}]=\alpha_{j}\|g\|_{D}^{2}.$

Combining the two terms together, we have

$\displaystyle\operatorname*{{\mathbb{E}}}\Big{[}\sum_{i=1}^{m}|\langle
g,v_{i}\rangle_{S,w}|^{2}\Big{]}\leq$
$\displaystyle~{}\sum_{j=1}^{s}(\alpha_{j}K_{\mathsf{IS},D_{j}}\cdot\alpha_{j}\|g\|_{D}^{2})$
$\displaystyle\leq$
$\displaystyle~{}\Big{(}\sum_{j=1}^{s}\alpha_{j}\Big{)}\cdot\max_{j\in[s]}\\{\alpha_{j}K_{\mathsf{IS},D_{j}}\\}\cdot\|g\|_{D}^{2}$
$\displaystyle\leq$ $\displaystyle~{}\varepsilon\|g\|_{D}^{2}.$

where the last step follows from $P$ being a $\varepsilon$-WBSP (Definition
7.1), which implies that $\sum_{j=1}^{s}\alpha_{j}=\frac{5}{4}$ and
$\alpha_{j}K_{\mathsf{IS},D_{j}}\leq\varepsilon/2$ for all $j\in[s]$.

Finally, by Markov’s inequality, we have that

$\displaystyle\sum_{i=1}^{m}|\langle
g,v_{i}\rangle_{S,w}|^{2}\lesssim\varepsilon\|g\|_{D}^{2}$

holds with probability $0.99$. ∎

######  Fact 8.7.

$\displaystyle\sum_{i=1}^{m}|\langle
g,v_{i}\rangle_{S,w}|^{2}=\|w\|_{1}^{2}\cdot\sum_{i=1}^{m}\Big{|}\operatorname*{{\mathbb{E}}}_{t\sim
D^{\prime}}[\overline{v_{i}(t)}g(t)]\Big{|}^{2},$

where $D^{\prime}$ is a distribution defined by
$D^{\prime}(t_{i}):=\frac{w_{i}}{\|w\|_{1}}$ for $i\in[s]$.

###### Proof.

We have:

$\displaystyle\sum_{i=1}^{m}|\langle g,v_{i}\rangle_{S,w}|^{2}=$
$\displaystyle~{}\sum_{i=1}^{m}\Big{|}\sum_{j=1}^{s}w_{j}\overline{v_{i}(t_{j})}g(t_{j})\Big{|}^{2}$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{m}\Big{|}\sum_{j=1}^{s}\frac{w_{j}\overline{v_{i}(t_{j})}g(t_{j})}{\sum_{j^{\prime}=1}^{s}w_{j^{\prime}}}\Big{|}^{2}\cdot\Big{(}\sum_{j^{\prime}=1}^{s}w_{j^{\prime}}\Big{)}^{2}$
$\displaystyle=$
$\displaystyle~{}\Big{(}\sum_{j^{\prime}=1}^{s}w_{j^{\prime}}\Big{)}^{2}\cdot\sum_{i=1}^{m}\Big{|}\operatorname*{{\mathbb{E}}}_{t\sim
D^{\prime}}[\overline{v_{i}(t)}g(t)]\Big{|}^{2}.$

∎

######  Fact 8.8.

For any $i\in[m]$, we have

$\displaystyle\operatorname*{{\mathbb{E}}}_{D_{1},\dots,D_{s}}\Big{[}\big{|}\sum_{j=1}^{s}w_{j}\overline{v_{i}(t_{j})}g(t_{j})\big{|}^{2}\Big{]}=\operatorname*{{\mathbb{E}}}_{D_{1},\dots,D_{s}}\Big{[}\sum_{j=1}^{m}w_{j}^{2}|v_{i}(t_{j})|^{2}|g(t_{j})|^{2}\Big{]}.$

###### Proof.

We first show that for any $i\in[m]$ and $j\in[s]$,

$\displaystyle\underset{t_{j}\sim
D_{j}}{\operatorname*{{\mathbb{E}}}}[w_{j}\overline{v_{i}(t_{j})}g(t_{j})]=$
$\displaystyle~{}\underset{t_{j}\sim
D_{j}}{\operatorname*{{\mathbb{E}}}}[\alpha_{j}\frac{D(t_{j})}{D_{j}(t_{j})}\overline{v_{i}(t_{j})}g(t_{j})]$
$\displaystyle=$ $\displaystyle~{}\alpha_{j}\underset{t_{j}\sim
D}{\operatorname*{{\mathbb{E}}}}[\overline{v_{i}(t_{j})}g(t_{j})]$
$\displaystyle=$ $\displaystyle~{}0.$ (18)

where the first step follows from the definition of $w_{i}$, the third step
follows from $g(t)$ is orthonormal with $v_{i}(t)$ for any $i\in[k]$.

Then, we can expand LHS as follows:

$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{D_{1},\dots,D_{s}}\Big{[}\big{|}\sum_{j=1}^{s}w_{j}\overline{v_{i}(t_{j})}g(t_{j})\big{|}^{2}\Big{]}$
$\displaystyle=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{D_{1},\dots,D_{s}}\Big{[}\big{(}\sum_{j=1}^{s}w_{j}\overline{v_{i}(t_{j})}g(t_{j})\big{)}^{*}\big{(}\sum_{j=1}^{s}w_{j}\overline{v_{i}(t_{j})}g(t_{j})\big{)}\Big{]}$
$\displaystyle=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{D_{1},\dots,D_{s}}\Big{[}\sum_{j,j^{\prime}=1}^{s}w_{j}w_{j^{\prime}}v_{i}(t_{j})\overline{g(t_{j})}\overline{v_{i}(t_{j^{\prime}})}g(t_{j^{\prime}})\Big{]}$
$\displaystyle=$
$\displaystyle~{}\sum_{j,j^{\prime}=1}^{s}\operatorname*{{\mathbb{E}}}_{D_{1},\dots,D_{s}}[w_{j}w_{j^{\prime}}v_{i}(t_{j})\overline{g(t_{j})}\overline{v_{i}(t_{j^{\prime}})}g(t_{j^{\prime}})]$
$\displaystyle=$
$\displaystyle~{}\sum_{j=1}^{s}\operatorname*{{\mathbb{E}}}[w_{j}^{2}|v_{i}(t_{j})|^{2}|g(t_{j})|^{2}]+\sum_{1\leq
j<j^{\prime}\leq
s}2\Re\operatorname*{{\mathbb{E}}}_{D_{1},\dots,D_{j}}[w_{j}w_{j^{\prime}}v_{i}(t_{j})\overline{g(t_{j})}\overline{v_{i}(t_{j^{\prime}})}g(t_{j^{\prime}})]$
$\displaystyle=$ $\displaystyle~{}\mathrm{RHS}+\sum_{1\leq j<j^{\prime}\leq
s}2\Re\operatorname*{{\mathbb{E}}}_{D_{1},\dots,D_{j}}\Big{[}w_{j}v_{i}(t_{j})\overline{g(t_{j})}\operatorname*{{\mathbb{E}}}_{D_{j+1},\dots,D_{j^{\prime}}}[w_{j^{\prime}}\overline{v_{i}(t_{j^{\prime}})}g(t_{j^{\prime}})]\Big{]}$
$\displaystyle=$ $\displaystyle~{}\mathrm{RHS}+\sum_{1\leq j<j^{\prime}\leq
s}2\Re\operatorname*{{\mathbb{E}}}_{D_{1},\dots,D_{j}}[w_{j}v_{i}(t_{j})\overline{g(t_{j})}\cdot
0]$ $\displaystyle=$ $\displaystyle~{}\mathrm{RHS},$

where the third step follows from the linearity of expectation, the fifth step
follows from $t_{j}$ only depends on $t_{1},\dots,t_{j-1}$, and the sixth step
follows from Eq. (18). ∎

######  Fact 8.9.

Let $\\{v_{1},\dots,v_{k}\\}$ be an orthonormal basis of ${\cal F}$ with
respect to the distribution $D$. Then, we have

$\displaystyle\underset{h\in\mathcal{F}}{\sup}\Big{\\{}\frac{|h(t)|^{2}}{\|h\|_{D}^{2}}\Big{\\}}=\sum_{i=1}^{k}|v_{i}(t)|^{2}$

###### Proof.

We have:

$\displaystyle\underset{h\in\mathcal{F}}{\sup}\Big{\\{}\frac{|h(t)|^{2}}{\|h\|_{D}^{2}}\Big{\\}}=$
$\displaystyle~{}\underset{a\in\mathbb{C}^{k}}{\sup}\Big{\\{}\frac{|\sum_{i=1}^{k}a_{i}v_{i}(t)|^{2}}{\|a\|_{2}^{2}}\Big{\\}}$
$\displaystyle=$
$\displaystyle~{}\sup_{a\in\mathbb{C}^{k}:\|a\|_{2}=1}\Big{|}\sum_{i=1}^{k}a_{i}v_{i}(t)\Big{|}^{2}$
$\displaystyle=$ $\displaystyle~{}\sum_{i=1}^{k}|v_{i}(t)|^{2},$

where the first step follows from each $h\in{\cal F}$ can be expanded as
$h=\sum_{i=1}^{k}a_{i}v_{i}$ and $\|h(t)\|_{D}^{2}=\|a\|_{2}^{2}$ (Fact 4.15),
the second step follows from the Cauchy-Schwartz inequality and taking
$a=\frac{v(t)}{\|v(t)\|_{2}}$. ∎

###  8.2 Sketch distillation for high-dimensional signals

The goal of this section is to prove Lemma 8.10, which can reduce the sketch
size of Corollary 6.3 for high-dimensional signals.

######  Lemma 8.10 (Distillation for high-dimensional signal).

Given $f_{1},f_{2},\cdots,f_{k}\in\mathbb{R}^{d}$. Let
$x^{*}(t)=\sum_{j=1}^{k}v_{j}e^{2\pi\mathbf{i}\langle f_{j},t\rangle}$ for
$t\in[0,T]^{d}$. Let $\eta=\min_{i\neq j}\|f_{j}-f_{i}\|_{\infty}$. For any
accuracy parameter $\varepsilon\in(0,1)$, there is an algorithm DistillHD
(Algorithm 8) that runs in $\widetilde{O}(\varepsilon^{-2}k^{O(d)})$-time and
outputs a set $S\subset[0,T]^{d}$ of size $s=O(k/\varepsilon^{2})$ and a
weight vector $w\in\mathbb{R}^{s}_{\geq 0}$ such that

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

holds with probability $0.99$.

Furthermore, for any noise function $g(t)$, with high probability, it holds
that

$\displaystyle\|g\|_{S,w}\lesssim\|g\|_{T}.$

###### Proof.

First, we randomly and uniformly sample a set $S_{0}$ of
$s_{0}=O(\varepsilon_{0}^{-2}k^{O(d)}\log(1/(\rho_{0}\varepsilon_{0})))$ real
number in $[0,T]^{d}$, where $\varepsilon_{0},\rho_{0}$ are parameters to be
chosen later.

By Corollary 6.3, we know that those points are good sketch of the high-
dimensional signal and can preserve the norm with a large probability. More
precisely, with probability $1-\rho_{0}$,

$\displaystyle(1-\varepsilon_{0})\|x^{*}\|_{T}^{2}\leq\|x^{*}\|_{S_{0}}^{2}\leq(1+\varepsilon_{0})\|x^{*}\|_{T}^{2}.$
(19)

Then, we will select $s=O(k)$ real number from $S_{0}$ and output $s$
corresponding weight $w_{1},w_{2},\cdots,w_{s}$ by applying the Procedure
RandBSS+ with setting the following parameter: replacing $d$ by $k$,
$\varepsilon$ by $\varepsilon_{1}^{2}$, $D$ by $\mathrm{Uniform}(S_{0})$, and
${\cal F}$ by

$\displaystyle{\mathcal{F}}=\Big{\\{}f(t)=\sum_{j=1}^{k}v_{j}\exp(2\pi\mathbf{i}\langle
f_{j},t\rangle)~{}\big{|}~{}v_{j}\in\mathbb{C}\Big{\\}}.$

Then, by Theorem 7.3 and the property of WBSP (Definition 7.1), we obtain that
with probability $0.995$,

$\displaystyle(1-\varepsilon_{1})\|x^{*}\|_{S_{0}}^{2}\leq\|x^{*}\|_{S,w}^{2}\leq(1+\varepsilon_{1})\|x^{*}\|_{S_{0}}^{2}.$

Combining with Eq. (19), we conclude that

$\displaystyle\|x^{*}\|_{S,w}^{2}\in$
$\displaystyle~{}[1-\varepsilon_{1},1+\varepsilon_{1}]\cdot\|x^{*}\|_{S_{0}}^{2}$
$\displaystyle\in$
$\displaystyle~{}[(1-\varepsilon_{0})(1-\varepsilon_{1}),(1+\varepsilon_{0})(1+\varepsilon_{1})]\cdot\|x^{*}\|_{T}^{2}$
$\displaystyle\in$
$\displaystyle~{}[1-\varepsilon,1+\varepsilon]\cdot\|x^{*}\|_{T}^{2},$

where the second step follows from Eq. (19), and the last step follows from
$\varepsilon_{0}=\varepsilon_{1}=\varepsilon/4$.

The running time of Algorithm 8 follows from Claim 8.11 and the success
probability follows from setting $\rho_{0}=0.001$. The furthermore part
follows from Claim 8.12.

The lemma is then proved. ∎

Algorithm 8 Distillation for high-dimensional signal.

1:procedure DistillHD($k,\varepsilon,d,F=\\{f_{1},\dots,f_{k}\\},T$)
$\triangleright$ Lemma 8.10

2: $S_{0}\leftarrow$ $O(\varepsilon^{-2}k^{O(d)}\log(1/\varepsilon))$ i.i.d.
samples from $\text{Uniform}([0,T]^{d})$

3: Set the function family $\mathcal{F}$ as follows:
$\displaystyle{\mathcal{F}}=\Big{\\{}f(t)=\sum_{j=1}^{k}v_{j}\exp(2\pi\mathbf{i}\langle
f_{j},t\rangle)~{}\big{|}~{}v_{j}\in\mathbb{C}\Big{\\}}.$

4:
$s,\\{t_{1},t_{2},\cdots,t_{s}\\},w\leftarrow\textsc{RandBSS+}(k,\mathcal{F},\mathrm{Uniform}(S_{0}),(\varepsilon/4)^{2})$
$\triangleright$ $s=O(k/\varepsilon^{2})$, Algorithm 3

5: return $\\{t_{1},t_{2},\cdots,t_{s}\\}$ and $w$

6:end procedure

######  Claim 8.11 (Running time of Procedure DistillHD in Algorithm 8).

Procedure DistillHD in Algorithm 8 runs in time

$O\left(\varepsilon^{-2}k^{O(d)}\log(1/\varepsilon)\right).$

###### Proof.

The first step of sampling $S_{0}$ takes
$O(\varepsilon^{-2}k^{O(d)}\log(1/\varepsilon))$-time.

Then, by Theorem 7.3 with
$|D|=O(\varepsilon^{-2}k^{O(d)}\log(1/\varepsilon))$, $d=k$, we have that the
running time of RandBSS+ is

$\displaystyle~{}O\left(k^{2}\cdot\varepsilon^{-2}k^{O(d)}\log(1/\varepsilon)+\varepsilon^{-2}k^{3}\log\left(\varepsilon^{-2}k^{O(d)}\log(1/\varepsilon)\right)+\varepsilon^{-2}k^{\omega+1}\right)$
$\displaystyle=$
$\displaystyle~{}O\left(\varepsilon^{-2}k^{O(d)}\log^{3}(k)\log(1/\varepsilon)\right).$

Hence, the total running time of Algorithm 8 is
$O\left(\varepsilon^{-2}k^{O(d)}\log^{3}(k)\log(1/\varepsilon)\right)$.

∎

######  Claim 8.12 (Preserve the energy of noise (high Dimension)).

Let $(S,w)$ be the outputs of Algorithm 8. Then, for any function $g(t)$,

$\displaystyle\|g(t)\|^{2}_{S,w}\lesssim\rho^{-2}\|g(t)\|_{T}^{2},$

holds with probability $1-\rho$.

###### Proof.

Let $P$ denote the Procedure
$\textsc{ImportantSampling}(k,\varepsilon,\rho,F,T,\mathcal{B})$. Because $P$
is a $\varepsilon$-well-balanced sampling procedure (Definition 7.1). By the
Definition 7.1, we have that $t_{i}\sim D_{i}(t)$ and
$w_{i}=\alpha_{i}\cdot\frac{D(t_{i})}{D_{i}(t_{i})}$ in every iteration
$i\in[s]$, where $\sum_{i=1}^{s}\alpha_{i}\leq 5/4$,
$D(t)=\text{Uniform}(S_{0})$.

As a result,

$\displaystyle\operatorname*{{\mathbb{E}}}_{P}[\|g(t)\|^{2}_{S,w}]=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{P}[\sum_{i=1}^{s}w_{i}|g(t_{i})|^{2}]$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{s}\operatorname*{{\mathbb{E}}}_{t_{i}\sim
D_{i}(t_{i})}[w_{i}|g(t_{i})|^{2}]$ $\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{s}\operatorname*{{\mathbb{E}}}_{t_{i}\sim
D_{i}(t_{i})}[\alpha_{i}\cdot\frac{D(t_{i})}{D_{i}(t_{i})}|g(t_{i})|^{2}]$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{s}\operatorname*{{\mathbb{E}}}_{t_{i}\sim
D(t_{i})}[\alpha_{i}|g(t_{i})|^{2}]$ $\displaystyle\leq$
$\displaystyle~{}\underset{P}{\sup}\\{\sum_{i=1}^{s}\alpha_{i}\\}\operatorname*{{\mathbb{E}}}_{t\sim
D(t)}[|g(t)|^{2}]$ $\displaystyle=$
$\displaystyle~{}\underset{P}{\sup}\\{\sum_{i=1}^{s}\alpha_{i}\\}\|g(t)\|^{2}_{S_{0}}$
$\displaystyle\leq$ $\displaystyle~{}2\|g(t)\|^{2}_{S_{0}}.$

where the first step follows from the definition of the norm, the third step
follows from $w_{i}=\alpha_{i}\cdot\frac{D(t_{i})}{D_{i}(t_{i})}$, the forth
step follows from $\operatorname*{{\mathbb{E}}}_{t\sim
D_{0}(t)}\frac{D_{1}(t)}{D_{0}(t)}f(t)=\operatorname*{{\mathbb{E}}}_{t\sim
D_{1}(t)}f(t)$, the sixth step follows from $D(t)=\text{Uniform}(S_{0})$ and
the definition of the norm, the last step follows from
$\sum_{i=1}^{s}\alpha_{i}\leq 5/4$.

Moreover,

$\displaystyle\operatorname*{{\mathbb{E}}}_{S_{0}}[\|g(t)\|^{2}_{S_{0}}]=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}_{t\sim\text{Uniform}([0,T])}|g(t)|^{2}$
$\displaystyle=$ $\displaystyle~{}\|g(t)\|_{T}^{2}$

So, by Markov’s inequality,

$\displaystyle\Pr[\|g(t)\|^{2}_{S,w}\leq\|g(t)\|^{2}_{S_{0}}/\varepsilon_{0}]\geq
1-\varepsilon_{0}/2,$

and

$\displaystyle\Pr[\|g(t)\|^{2}_{S_{0}}\leq\|g(t)\|_{T}^{2}/\varepsilon_{1}]\geq
1-\varepsilon_{1}.$

Then, with probability at least $(1-\varepsilon_{0}/2)(1-\varepsilon_{1})$
holds,

$\displaystyle\|g(t)\|^{2}_{S,w}\leq\|g(t)\|^{2}_{S_{0}}/\varepsilon_{0}\leq\|g(t)\|_{T}^{2}/(\varepsilon_{0}\varepsilon_{1}).$

Set $\varepsilon_{0}=\rho/10,\varepsilon_{1}=\rho/10$, we have that,

$\displaystyle\|g(t)\|^{2}_{S,w}\lesssim\|g(t)\|_{T}^{2}/\rho^{2},$

holds with probability $1-\rho$.

∎

###  8.3 Sketch distillation for discrete signals

The goal of this section is to prove Lemma 8.13, which can reduce the sketch
size of Corollary 6.4 for discrete signals in any dimension.

######  Lemma 8.13 (Distillation for discrete signal).

For any $d\geq 1$, let $n=p^{d}$ for some positive integer $p$. Let
$x^{*}\in\mathbb{C}^{[p]^{d}}$, such that
$\mathrm{supp}(\widehat{x^{*}})\subset[p]^{d}$ and
$|\mathrm{supp}(\widehat{x^{*}})|=k$. For any accuracy parameter
$\varepsilon\in(0,0.1)$, there is an algorithm (Algorithm 9) that runs in
$O(\varepsilon^{-2}k^{\omega+1})$-time and outputs a set $S\subset[n]$ of size
$s=O(k/\varepsilon^{2})$ and a weight vector $w\in\mathbb{R}^{s}_{\geq 0}$
such that,

$\displaystyle(1-\varepsilon)\|x^{*}\|_{2}\leq
n\|x^{*}\|_{S,w}\leq(1+\varepsilon)\|x^{*}\|_{2}$

holds with probability $0.99$.

###### Proof.

For the convenient, in the proof, we use $x$ to denote the $x^{*}$.

First, we randomly pick up a set $S_{0}=\\{t_{1},\cdots,t_{s_{0}}\\}$ of
$s_{0}=O(\varepsilon^{-2}k\log(k/\rho))$ i.i.d. samples from
$\mathrm{Uniform}([n])$, where $\varepsilon_{0},\rho_{0}$ are parameters to be
chosen later.

By Corollary 6.4, with probability $1-\rho_{0}$,

$\displaystyle(1-\varepsilon_{0})\|x\|^{2}_{2}\leq
n\|x\|^{2}_{S_{0}}\leq(1+\varepsilon_{0})\|x\|^{2}_{2}.$ (20)

Then, we will select $s=O(k/\varepsilon_{1}^{2})$ elements from $S_{0}$ and
output the corresponding weights $w_{1},w_{2},\cdots,w_{s}$ by applying
Procedure RandBSS+ with the following parameter: replacing $d$ by $k$,
$\varepsilon$ by $\varepsilon_{1}^{2}$, and $D$ by $\mathrm{Uniform}(S_{0})$.

By Theorem 7.3 and Definition 7.1, we obtain that with probability $0.995$,

$\displaystyle(1-\varepsilon_{1})\|x\|_{S,w}^{2}\leq\|x\|^{2}_{S_{0}}\leq(1+\varepsilon_{1})\|x\|^{2}_{S,w}.$

Combining with Eq. (20), we conclude that

$\displaystyle\|x\|_{S,w}^{2}\in$
$\displaystyle~{}[1-\varepsilon_{1},1+\varepsilon_{1}]\cdot\|x\|_{S_{0}}^{2}$
$\displaystyle\in$
$\displaystyle~{}[(1-\varepsilon_{0})(1-\varepsilon_{1}),(1+\varepsilon_{0})(1+\varepsilon_{1})]\cdot\|x\|_{2}^{2}/n$
$\displaystyle\in$
$\displaystyle~{}[1-\varepsilon,1+\varepsilon]\cdot\|x\|_{2}^{2}/n,$

where the second step follows from Eq. (20), and the last step follows by
taking $\varepsilon_{0}=\varepsilon_{1}=\varepsilon/4$.

By taking $\rho=0.001$, we get that the overall success probability is at
least 0.99.

Regarding the running time, if $d=1$, we run Procedure DistillDisc in
Algorithm 9, whose runtime follows from Claim 8.14. And if $d>1$, we run
Procedure DistillDiscHD in Algorithm 9, whose runtime follows from Claim 8.15.

The lemma is then proved. ∎

Algorithm 9 Distillation for discrete signal.

1:procedure DistillDisc($k,\varepsilon,F=\\{f_{1},\cdots,f_{k}\\},n$)
$\triangleright$ Lemma 8.13 (one-dimension)

2: $S_{0}\leftarrow$ $O(\varepsilon^{-2}k\log(k))$ i.i.d. samples from
$\text{Uniform}([n])$

3: Set the function family $\mathcal{F}$ as follows:
$\displaystyle{\mathcal{F}}=\\{f(t)=\sum_{j=1}^{k}v_{j}\exp(2\pi\mathbf{i}f_{j}t/n)|v_{j}\in\mathbb{C}\\}.$

4:
$s,\\{t_{1},t_{2},\cdots,t_{s}\\},w\leftarrow\textsc{RandBSS+}(k,\mathcal{F},\mathrm{Uniform}(S_{0}),(\varepsilon/4)^{2})$
$\triangleright$ $s=O(k/\varepsilon^{2})$, Algorithm 3

5: return $\\{t_{1},t_{2},\cdots,t_{s}\\}$ and $w$

6:end procedure

7:procedure DistillDiscHD($k,\varepsilon,F=\\{f_{1},\cdots,f_{k}\\},p,d$)
$\triangleright$ Lemma 8.13 (high-dimension)

8: $S_{0}\leftarrow$ $O(\varepsilon^{-2}k\log(k))$ i.i.d. samples from
$\text{Uniform}([p]^{d})$

9: $A\leftarrow\begin{bmatrix}{t_{1}^{\prime}}^{\top}\\\ \vdots\\\
{t^{\prime}_{s_{0}}}^{\top}\end{bmatrix}\in\mathbb{R}^{s_{0}\times d}$,
$B\leftarrow\begin{bmatrix}f_{1}&\cdots&f_{k}\end{bmatrix}\in\mathbb{R}^{d\times
k}$

10: $C\leftarrow A\cdot B\in\mathbb{R}^{s_{0}\times k}$

11: ${\cal F}_{ij}\leftarrow\exp(2\pi\mathbf{i}C_{ij})$ for each
$(i,j)\in[s_{0}]\times[k]$

12:
$s,\\{t_{1},t_{2},\cdots,t_{s}\\},w\leftarrow\textsc{RandBSS+}(k,\mathcal{F},\mathrm{Uniform}(S_{0}),(\varepsilon/4)^{2})$
$\triangleright$ $s=O(k/\varepsilon^{2})$, Algorithm 3

13: return $\\{t_{1},t_{2},\cdots,t_{s}\\}$ and $w$

14:end procedure

######  Claim 8.14 (Running time of Procedure DistillDisc in Algorithm 9).

Procedure DistillDisc in Algorithm 9 runs in

$O\left(\varepsilon^{-2}k^{\omega+1}\right)$

time.

###### Proof.

The first step of sampling $S_{0}$ takes $O(\varepsilon^{-2}k\log(k))$-time.

Then, by Theorem 7.3 with $|D|=O(\varepsilon^{-2}k\log(k))$, $d=k$, we have
that the running time of RandBSS+ is

$\displaystyle~{}O\left(k^{2}\cdot\varepsilon^{-2}k\log(k)+\varepsilon^{-2}k^{3}\log\left(\varepsilon^{-2}k\log(k)\right)+\varepsilon^{-2}k^{\omega+1}\right)$
$\displaystyle=$ $\displaystyle~{}O\left(\varepsilon^{-2}k^{\omega+1}\right).$

Hence, the total running time is $O\left(\varepsilon^{-2}k^{\omega+1}\right)$.
∎

######  Claim 8.15 (Running time of Procedure DistillDiscHD in Algorithm 9).

Procedure DistillDiscHD in Algorithm 9 runs in

$O\left(\varepsilon^{-2}k^{\omega+1}+\varepsilon^{-2}dk^{\omega-1}\log
k\right)$

time.

###### Proof.

The first step of sampling $S_{0}$ takes $O(\varepsilon^{-2}k\log(k)d)$-time.

Then, we need to implement the function family

$\displaystyle{\mathcal{F}}=\\{f(t)=\sum_{j=1}^{k}v_{j}\exp(2\pi\mathbf{i}\langle
f_{j},t\rangle/p)|v_{j}\in\mathbb{C}\\}.$

Naively, for each $f\in{\cal F}$, it takes $O(d)$-time per evaluation. We
observe that in the distribution sent to RandBSS+ is
$\mathrm{Uniform}(S_{0})$, which is discrete with support size
$s_{0}=|S_{0}|$. And in Procedure RandBSS+, we only need to find an
orthonormal basis for ${\cal F}$ with respect to this distribution, which is
equivalent to orthogonalize the columns of the matrix defined at Line 11. To
compute the matrix ${\cal F}$, we need to multiply an $s_{0}$-by-$d$ matrix
with a $d$-by-$k$ matrix. By fast matrix multiplication, by Fact 4.3, it takes

$\displaystyle{\cal
T}_{\mathrm{mat}}(k,d,s_{0})=\begin{cases}O(\varepsilon^{-2}k^{\omega}\log
k)&\text{if}~{}d\leq k,\\\ O(\varepsilon^{-2}dk^{\omega-1}\log
k)&\text{if}~{}d>k.\end{cases}$

For Procedure RandBSS+, by Theorem 7.3 with $|D|=O(\varepsilon^{-2}k\log(k))$,
$d=k$, we have that the running time of RandBSS+ is

$\displaystyle~{}O\left(k^{2}\cdot\varepsilon^{-2}k\log(k)+\varepsilon^{-2}k^{3}\log\left(\varepsilon^{-2}k\log(k)\right)+\varepsilon^{-2}k^{\omega+1}\right)$
$\displaystyle=$ $\displaystyle~{}O\left(\varepsilon^{-2}k^{\omega+1}\right).$

Hence, the total running time of the procedure is

$\displaystyle
O\left(\varepsilon^{-2}dk\log(k)+\varepsilon^{-2}k^{\omega+1}+{\cal
T}_{\mathrm{mat}}(k,d,s_{0})\right)=O\left(\varepsilon^{-2}k^{\omega+1}+\varepsilon^{-2}dk^{\omega-1}\log
k\right).$

∎

##  9 One-dimensional Signal Estimation

In this section, we apply the tools developed in previous sections to show two
efficient reductions from Frequency Estimation to Signal Estimation for one-
dimensional semi-continuous Fourier signals. The first reduction in Section
9.1 is optimal in sample complexity, which takes linear number of samples from
the signal but only achieves constant accuracy. The section reduction in
Section 9.2 takes nearly-linear number of samples but can achieve very high-
accuracy (i.e., $(1+\varepsilon)$-estimation error).

###  9.1 Sample-optimal reduction

The main theorem of this section is Theorem 9.1. The optimal sample complexity
is achieved via the sketch distillation in Lemma 8.1.

######  Theorem 9.1 (Sample-optimal algorithm for one-dimensional Signal
Estimation).

For $\eta\in\mathbb{R}$, let $\Lambda(\mathcal{B})\subset\mathbb{R}$ denote
the lattice $\Lambda(\mathcal{B})=\\{c\eta~{}|~{}c\in\mathbb{Z}\\}$. Suppose
that $f_{1},f_{2},\cdots,f_{k}\in\Lambda(\mathcal{B})$. Let
$x^{*}(t)=\sum_{j=1}^{k}v_{j}\exp({2\pi\mathbf{i}f_{j}t})$, and let $g(t)$
denote the noise. Given observations of the form $x(t)=x^{*}(t)+g(t)$,
$t\in[0,T]$. Let $\eta=\min_{i\neq j}|f_{j}-f_{i}|$.

Given $D,\eta\in\mathbb{R}_{+}$. Suppose that there is an algorithm FreqEst
that

  * •

takes $\mathcal{S}_{\mathsf{freq}}$ samples,

  * •

runs in $\mathcal{T}_{\mathsf{freq}}$-time, and

  * •

outputs a set ${\cal L}$ of frequencies such that with probability $0.99$, the
following condition holds:

$\displaystyle\forall i\in[k],~{}\exists f^{\prime}_{i}\in{\cal
L}~{}\text{s.t.}~{}|f_{i}-f^{\prime}_{i}|\leq\frac{D}{T}.$

Then, there is an algorithm (Algorithm 10) such that

  * •

takes $O(\widetilde{k}+\mathcal{S}_{\mathsf{freq}})$ samples

  * •

runs $O(\widetilde{k}^{\omega+1}+\mathcal{T}_{\mathsf{freq}})$ time,

  * •

outputs
$y(t)=\sum_{j=1}^{\widetilde{k}}v_{j}^{\prime}\cdot\exp(2\pi\mathbf{i}f_{j}^{\prime}t)$
with $\widetilde{k}=O(|{\cal L}|(1+D/(T\eta)))$ such that with probability at
least $0.9$, we have

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

Algorithm 10 Signal estimation algorithm for one-dimensional signals (sample
optimal version)

1:procedure SignalEstimationFast($x,k,F,T,\mathcal{B}$) $\triangleright$
Theorem 9.1

2: $\varepsilon\leftarrow 0.01$

3: $L\leftarrow\textsc{FreqEst}(x,k,D,F,T,\mathcal{B})$

4:
$\\{f^{\prime}_{1},f^{\prime}_{2},\cdots,f^{\prime}_{\widetilde{k}}\\}\leftarrow\\{f\in\Lambda(\mathcal{B})~{}|~{}\exists
f^{\prime}\in L,~{}|f^{\prime}-f|<D/T\\}$

5:
$s,\\{t_{1},t_{2},\cdots,t_{s}\\},w\leftarrow\textsc{FastDistill1D}(\widetilde{k},\sqrt{\varepsilon},\\{f^{\prime}_{i}\\}_{i\in[\widetilde{k}]},T,\mathcal{B})$
$\triangleright$ $\widetilde{k}$, $w\in\mathbb{R}^{\widetilde{k}}$, Algorithm
7

6: $A_{i,j}\leftarrow\exp(2\pi\mathbf{i}f^{\prime}_{j}t_{i})$,
$A\in\mathbb{C}^{s\times\widetilde{k}}$

7: $b\leftarrow(x(t_{1}),x(t_{2}),\cdots,x(t_{s}))^{\top}$

8: Solving the following weighted linear regression$\triangleright$ Fact 4.4
$\displaystyle
v^{\prime}\leftarrow\underset{v^{\prime}\in\mathbb{C}^{\widetilde{k}}}{\arg\min}\|\sqrt{w}\circ(Av^{\prime}-b)\|_{2}.$

9: return
$y(t)=\sum_{j=1}^{\widetilde{k}}v_{j}^{\prime}\cdot\exp(2\pi\mathbf{i}f_{j}^{\prime}t)$.

10:end procedure

###### Proof.

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

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

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

We use $\widetilde{k}$ to denote the size of set $\widetilde{L}$. And we use
$\widetilde{f}_{1},\widetilde{f}_{2},\cdots,\widetilde{f}_{\widetilde{k}}$ to
denote the frequencies in the set $\widetilde{L}$. It is easy to see that

$\displaystyle\widetilde{k}\leq|{\cal L}|(1+D/(T\eta)).$

Next, we focus on recovering magnitude
$v^{\prime}\in\mathbb{C}^{\widetilde{k}}$. First we run Procedure
FastDistill1D in Algorithm 7 and obtain a set
$S=\\{t_{1},t_{2},\cdots,t_{s}\\}\subset[0,T]$ of size $s=O(\widetilde{k})$
and a weight vector $w\in\mathbb{R}_{>0}^{s}$. Then, we sample the signal at
$t_{1},\dots,t_{s}$ and let $x(t_{1}),\dots,x(t_{s})$ be the samples. Consider
the following weighted linear regression problem:

$\displaystyle\underset{v^{\prime}\in\mathbb{C}^{\widetilde{k}}}{\min}~{}\left\|\sqrt{w}\circ(Av^{\prime}-b)\right\|_{2},$
(21)

where $\sqrt{w}:=(\sqrt{w_{1}},\dots,\sqrt{w_{s}})$, and the coefficients
matrix $A\in\mathbb{C}^{s\times\widetilde{k}}$ and the target vector
$b\in\mathbb{C}^{s}$ are defined as follows:

$\displaystyle
A:=\begin{bmatrix}\exp(2\pi\mathbf{i}\widetilde{f}_{1}t_{1})&\exp(2\pi\mathbf{i}\widetilde{f}_{2}t_{1})&\cdots&\exp(2\pi\mathbf{i}\widetilde{f}_{\widetilde{k}}t_{1})\\\
\exp(2\pi\mathbf{i}\widetilde{f}_{1}t_{2})&\exp(2\pi\mathbf{i}\widetilde{f}_{2}t_{2})&\cdots&\exp(2\pi\mathbf{i}\widetilde{f}_{\widetilde{k}}t_{2})\\\
\vdots&\vdots&\ddots&\vdots\\\
\exp(2\pi\mathbf{i}\widetilde{f}_{1}t_{s})&\exp(2\pi\mathbf{i}\widetilde{f}_{2}t_{s})&\cdots&\exp(2\pi\mathbf{i}\widetilde{f}_{\widetilde{k}}t_{s})\end{bmatrix}~{}\text{and}~{}b:=\begin{bmatrix}x(t_{1})\\\
x(t_{2})\\\ \vdots\\\ x(t_{s})\end{bmatrix}$

Then, we output a signal

$\displaystyle
y(t)=\sum_{j=1}^{\widetilde{k}}v_{j}^{\prime}\cdot\exp(2\pi\mathbf{i}\widetilde{f}_{j}t),$

where $v^{\prime}$ is an optimal solution of Eq. (21).

The running time follows from Lemma 9.2. And the estimation error guarantee
$\|y(t)-x(t)\|_{T}\lesssim\|g(t)\|_{T}$ follows from Lemma 9.3.

The theorem is then proved. ∎

######  Lemma 9.2 (Running time of Algorithm 10).

Algorithm 10 takes $O(\widetilde{k}^{\omega+1})$-time, giving the output of
Procedure FreqEst.

###### Proof.

At Line 5, we run Procedure FastDistill1D, which takes
$O(\widetilde{k}^{\omega+1})$-time by Lemma 8.1.

At Line 8, we solve the weighted linear regression, which takes

$\displaystyle O(s\widetilde{k}^{\omega-1})=O(\widetilde{k}^{\omega})$

time by Fact 4.4.

Thus, the total running time is $O(\widetilde{k}^{\omega+1})$. ∎

######  Lemma 9.3 (Estimation error of Algorithm 10).

Let $y(t)$ be the output signal of Algorithm 10. With high probability, we
have

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

###### Proof.

We have

$\displaystyle\|y(t)-x(t)\|_{T}\leq$
$\displaystyle~{}\|y(t)-x^{*}(t)\|_{T}+\|g(t)\|_{T}$ $\displaystyle\leq$
$\displaystyle~{}(1+\varepsilon)\|y(t)-x^{*}(t)\|_{S,w}+\|g(t)\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}(1+\varepsilon)\|y(t)-x(t)\|_{S,w}+(1+\varepsilon)\|g(t)\|_{S,w}+\|g(t)\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}(1+\varepsilon)\|x^{*}(t)-x(t)\|_{S,w}+(1+\varepsilon)\|g(t)\|_{S,w}+\|g(t)\|_{T}$
$\displaystyle\lesssim$ $\displaystyle~{}\|x^{*}(t)-x(t)\|_{S,w}+\|g(t)\|_{T}$
$\displaystyle\lesssim$ $\displaystyle~{}\|x^{*}(t)-x(t)\|_{T}+\|g(t)\|_{T}$
$\displaystyle\lesssim$ $\displaystyle~{}\|g(t)\|_{T},$ (22)

where the first step follows from triangle inequality, the second step follows
from Lemma 8.1 with $0.99$ probability, the third step follows from triangle
inequality, the forth step follows from $y(t)$ is the optimal solution of the
linear system, the fifth step follows from Claim 8.3, the sixth step follows
from Lemma 8.1, and the last step follows from the definition of $g(t)$. ∎

###  9.2 High-accuracy reduction

In this section, we prove Theorem 9.4, which achieves
$(1+\varepsilon)$-estimation error by a sharper bound on the energy of noise
in Lemma 8.4.

######  Theorem 9.4 (High-accuracy algorithm for one-dimensional Signal
Estimation).

For $\eta\in\mathbb{R}$, let $\Lambda(\mathcal{B})\subset\mathbb{R}$ denote
the lattice $\Lambda(\mathcal{B})=\\{c\eta~{}|~{}c\in\mathbb{Z}\\}$. Suppose
that $f_{1},f_{2},\cdots,f_{k}\in\Lambda(\mathcal{B})$. Let
$x^{*}(t)=\sum_{j=1}^{k}v_{j}\exp({2\pi\mathbf{i}f_{j}t})$, and let $g(t)$
denote the noise. Given observations of the form $x(t)=x^{*}(t)+g(t)$,
$t\in[0,T]$. Let $\eta=\min_{i\neq j}|f_{j}-f_{i}|$.

Given $D,\eta\in\mathbb{R}_{+}$. Suppose that there is an algorithm FreqEst
that

  * •

takes $\mathcal{S}_{\mathsf{freq}}$ samples,

  * •

runs in $\mathcal{T}_{\mathsf{freq}}$-time, and

  * •

outputs a set ${\cal L}$ of frequencies such that, for each $f_{i}$, there
exists an $f^{\prime}_{i}\in{\cal L}$ with $|f_{i}-f^{\prime}_{i}|\leq D/T$,
holds with probability $0.99$.

Then, there is an algorithm (Algorithm 11) such that

  * •

takes $O(\varepsilon^{-1}\widetilde{k}\log(\widetilde{k})+\mathcal{S})$
samples,

  * •

runs
$O(\varepsilon^{-1}\widetilde{k}^{\omega}\log(\widetilde{k})+\mathcal{T})$
time,

  * •

outputs
$y(t)=\sum_{j=1}^{\widetilde{k}}v_{j}^{\prime}\cdot\exp(2\pi\mathbf{i}f_{j}^{\prime}t)$
with $\widetilde{k}=O(|{\cal L}|(1+D/(T\eta)))$ such that with probability at
least $0.9$, we have

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

######  Remark 9.5.

For simplicity, we state the constant failure probability. It is
straightforward to get failure probability $\rho$ by blowing up a
$\log(1/\rho)$ factor in both samples and running time.

###### Proof.

Let $L$ be the set of frequencies output by the Frequency Estimation algorithm
FreqEst. We have the guarantee that with probability 0.99, for each true
frequency $f_{i}$, there exists an $f^{\prime}_{i}\in{\cal L}$ with
$|f_{i}-f^{\prime}_{i}|\leq D/T$. Conditioning on this event, we define a set
$\widetilde{L}$ as follows:

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

Since we assume that $\\{f_{1},\dots,f_{k}\\}\subset\Lambda({\cal B})$, we
have $\\{f_{1},\dots,f_{k}\\}\subset\widetilde{L}$. We use $\widetilde{k}$ to
denote the size of set $\widetilde{L}$, and we denote the frequencies in
$\widetilde{L}$ by
$\widetilde{f}_{1},\widetilde{f}_{2},\cdots,\widetilde{f}_{\widetilde{k}}$.

Next, we need to recover magnitude $v^{\prime}\in\mathbb{C}^{\widetilde{k}}$.

We first run Procedure WeightedSketch in Algorithm 7 and obtain a set
$S=\\{t_{1},t_{2},\cdots,t_{s}\\}\subset[0,T]$ of size
$s=O(\varepsilon^{-2}\widetilde{k}\log(\widetilde{k}))$ and a weight vector
$w\in\mathbb{R}_{>0}^{s}$. Then, we sample the signal at $t_{1},\dots,t_{s}$
and let $x(t_{1}),\dots,x(t_{s})$ be the samples. Consider the following
weighted linear regression problem:

$\displaystyle\underset{v^{\prime}\in\mathbb{C}^{\widetilde{k}}}{\min}~{}\left\|\sqrt{w}\circ(Av^{\prime}-b)\right\|_{2},$
(23)

where $\sqrt{w}:=(\sqrt{w_{1}},\dots,\sqrt{w_{s}})$, and the coefficients
matrix $A\in\mathbb{C}^{s\times\widetilde{k}}$ and the target vector
$b\in\mathbb{C}^{s}$ are defined as follows:

$\displaystyle
A:=\begin{bmatrix}\exp(2\pi\mathbf{i}\widetilde{f}_{1}t_{1})&\exp(2\pi\mathbf{i}\widetilde{f}_{2}t_{1})&\cdots&\exp(2\pi\mathbf{i}\widetilde{f}_{\widetilde{k}}t_{1})\\\
\exp(2\pi\mathbf{i}\widetilde{f}_{1}t_{2})&\exp(2\pi\mathbf{i}\widetilde{f}_{2}t_{2})&\cdots&\exp(2\pi\mathbf{i}\widetilde{f}_{\widetilde{k}}t_{2})\\\
\vdots&\vdots&\ddots&\vdots\\\
\exp(2\pi\mathbf{i}\widetilde{f}_{1}t_{s})&\exp(2\pi\mathbf{i}\widetilde{f}_{2}t_{s})&\cdots&\exp(2\pi\mathbf{i}\widetilde{f}_{\widetilde{k}}t_{s})\end{bmatrix}~{}\text{and}~{}b:=\begin{bmatrix}x(t_{1})\\\
x(t_{2})\\\ \vdots\\\ x(t_{s})\end{bmatrix}$

Note that if $v^{\prime}$ corresponds to the true coefficients $v$, then we
have $\|\sqrt{w}\circ(Av^{\prime}-b)\|_{2}=\|\sqrt{w}\circ
g(S)\|_{2}=\|g\|_{S,w}$. Let $v^{\prime}$ be the exact solution of the
weighted linear regression in Eq. (23), i.e.,

$\displaystyle
v^{\prime}:=\arg\min_{v^{\prime}\in\mathbb{C}^{\widetilde{k}}}~{}\left\|\sqrt{w}\circ(Av^{\prime}-b)\right\|.$

And we define the output signal to be:

$y(t):=\sum_{j=1}^{\widetilde{k}}v_{j}^{\prime}\cdot\exp(2\pi\mathbf{i}f_{j}^{\prime}t).$

The estimation error guarantee
$\|y(t)-x^{*}(t)\|_{T}\leq(1+\varepsilon)\|g(t)\|_{T}$ follows from Lemma 9.7.
The running time follows from Lemma 9.6.

The theorem is then proved. ∎

Algorithm 11 Signal estimation algorithm for one-dimensional signals (high-
accuracy version)

1:procedure SignalEstimationAcc($x,\varepsilon,k,F,T,\mathcal{B}$)
$\triangleright$ Theorem 9.4

2: $L\leftarrow\textsc{FreqEst}(x,k,D,F,T,\mathcal{B})$

3:
$\\{f^{\prime}_{1},f^{\prime}_{2},\cdots,f^{\prime}_{\widetilde{k}}\\}\leftarrow\\{f\in\Lambda(\mathcal{B})~{}|~{}\exists
f^{\prime}\in L,~{}|f^{\prime}-f|<D/T\\}$

4:
$s,\\{t_{1},t_{2},\cdots,t_{s}\\},w\leftarrow\textsc{WeightedSketch}(\widetilde{k},\sqrt{\varepsilon},T,\mathcal{B})$
$\triangleright$ $\widetilde{k}$, $w\in\mathbb{R}^{\widetilde{k}}$, Algorithm
7

5: $A_{i,j}\leftarrow\exp(2\pi\mathbf{i}f^{\prime}_{j}t_{i})$,
$A\in\mathbb{C}^{s\times\widetilde{k}}$

6: $b\leftarrow(x(t_{1}),x(t_{2}),\cdots,x(t_{s}))^{\top}$

7: Solving the following weighted linear regression$\triangleright$ Fact 4.4
$\displaystyle
v^{\prime}\leftarrow\underset{v^{\prime}\in\mathbb{C}^{\widetilde{k}}}{\arg\min}\|\sqrt{w}\circ(Av^{\prime}-b)\|_{2}.$

8: return
$y(t)=\sum_{j=1}^{\widetilde{k}}v_{j}^{\prime}\cdot\exp(2\pi\mathbf{i}f_{j}^{\prime}t)$.

9:end procedure

######  Lemma 9.6 (Running time of Algorithm 11).

Algorithm 11 takes
$O(\varepsilon^{-1}\widetilde{k}^{\omega}\log(\widetilde{k}))$-time, giving
the output of Procedure FreqEst.

###### Proof.

At Line 7, the regression solver takes

$\displaystyle
O(s\widetilde{k}^{\omega-1})=O(\varepsilon^{-1}\widetilde{k}\log(\widetilde{k})\cdot\widetilde{k}^{\omega-1})=O(\varepsilon^{-1}\widetilde{k}^{\omega}\log(\widetilde{k}))$

time. The remaining part of Algorithm 11 takes at most $O(s)$-time. ∎

######  Lemma 9.7 (Estimation error of Algorithm 11).

Let $y(t)$ be the output signal of Algorithm 11. With high probability, we
have

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

###### Proof.

Let $\cal F$ be the family of signals with frequencies in $\widetilde{L}$:

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

Suppose the dimension of ${\cal F}$ is $m\leq k$. Let
$\\{u_{1},u_{2},\cdots,u_{m}\\}$ be an orthonormal basis of ${\cal F}$, i.e.,

$\displaystyle\frac{1}{T}\int_{[0,T]}u_{i}(t)\overline{u_{j}(t)}\mathrm{d}t=$
$\displaystyle~{}{\bf 1}_{i=j},\quad\forall i,j\in[m],$

On the other hand, since $u_{i}\in{\cal F}$, we can also expand these basis
vectors in the Fourier basis. Let $V\in\mathbb{C}^{m\times{\widetilde{k}}}$ be
an linear transformation151515When $m<\widetilde{k}$, $V$ is not unique, and
we take any one of such linear transformation. such that

$\displaystyle
u_{i}=\sum_{j=1}^{\widetilde{k}}V_{i,j}\cdot\exp(2\pi\mathbf{i}\widetilde{f}_{j}t)~{}~{}~{}\forall
i\in[m].$

Then, we have

$\displaystyle\begin{bmatrix}\exp(2\pi\mathbf{i}\widetilde{f}_{1}t)\\\
\vdots\\\
\exp(2\pi\mathbf{i}\widetilde{f}_{\widetilde{k}}t)\end{bmatrix}=V^{+}\cdot\begin{bmatrix}u_{1}\\\
\vdots\\\ u_{m}\end{bmatrix},$

where $V^{+}\in\mathbb{C}^{\widetilde{k}\times m}$ is the pseudoinverse of
$V$; or equivalently, the $i$-th row of $V^{+}$ contains the coefficients of
expanding $\exp(2\pi\mathbf{i}\widetilde{f}_{i}t)$ under
$\\{u_{1},\dots,u_{m}\\}$. Define a linear operator $\alpha:{\cal
F}\rightarrow\mathbb{C}^{m}$ such that for any
$h(t)=\sum_{j=1}^{\widetilde{k}}v_{j}\exp(2\pi\mathbf{i}f_{j}t)$,

$\displaystyle\alpha(h):=V^{+}\cdot v,$

which gives the coefficients of $h$ under the basis
$\\{u_{1},\cdots,u_{\widetilde{k}}\\}$.

Define an $s$-by-$m$ matrix $B$ as follows:

$\displaystyle B:=A\cdot
V^{\top}=\begin{bmatrix}u_{1}(t_{1})&u_{2}(t_{1})&\cdots&u_{m}(t_{1})\\\
u_{1}(t_{2})&u_{2}(t_{2})&\cdots&u_{m}(t_{2})\\\
\vdots&\vdots&\ddots&\vdots\\\
u_{1}(t_{s})&u_{2}(t_{s})&\cdots&u_{m}(t_{s})\end{bmatrix}.$

$B=AV$. It is easy to see that $\mathrm{Im}(B)=\mathrm{Im}(A)$. Thus, solving
Eq. (23) is equivalent to solving:

$\displaystyle\underset{z\in\mathbb{C}^{m}}{\min}\|\sqrt{w}\circ(Bz-b)\|_{2}.$
(24)

Since $y(t)$ is an solution of Eq. (23), we also know that $\alpha(y)$ is an
solution of Eq. (24).

For convenience, we define some notations. Let
$\sqrt{W}:=\mathrm{diag}(\sqrt{w})$ and define

$\displaystyle B_{w}:=$ $\displaystyle~{}\sqrt{W}\cdot B,$ $\displaystyle
X_{w}:=$
$\displaystyle~{}\sqrt{W}\cdot\begin{bmatrix}x(t_{1})&x(t_{2})&\cdots&x(t_{s})\end{bmatrix}^{\top}$
$\displaystyle X^{*}_{w}:=$
$\displaystyle~{}\sqrt{W}\cdot\begin{bmatrix}x^{*}(t_{1})&x^{*}(t_{2})&\cdots&x^{*}(t_{s})\end{bmatrix}^{\top}$

By Fact 4.4, we know that the solution of the weighted linear regression Eq.
(24) has the following closed form:

$\displaystyle\alpha(y)=(B^{*}WB)^{-1}B^{*}Wb=(B_{w}^{*}B_{w})^{-1}B_{w}^{*}X_{w}.$
(25)

Then, consider the noise in the signal. Since $g$ is an arbitrary noise, let
$g^{\parallel}$ be the projection of $g(x)$ to ${\cal F}$ and
$g^{\bot}=g-g^{\parallel}$ be the orthogonal part to ${\cal F}$ such that

$\displaystyle g^{\parallel}(t)\in{\cal
F},~{}\text{and}~{}\int_{[0,T]}g^{\parallel}(t)\overline{g^{\bot}(t)}\mathrm{d}t=0.$

Similarly, we also define

$\displaystyle g_{w}:=$
$\displaystyle~{}\sqrt{W}\cdot\begin{bmatrix}g(t_{1})&g(t_{2})&\cdots&g(t_{s})\end{bmatrix}^{\top}$
$\displaystyle g^{\parallel}_{w}:=$
$\displaystyle~{}\sqrt{W}\cdot\begin{bmatrix}g^{\parallel}(t_{1})&g^{\parallel}(t_{2})&\cdots,g^{\parallel}(t_{s})\end{bmatrix}^{\top},$
$\displaystyle g^{\bot}_{w}:=$
$\displaystyle~{}\sqrt{W}\cdot\begin{bmatrix}g^{\bot}(t_{1})&g^{\bot}(t_{2})&\cdots,g^{\bot}(t_{s})\end{bmatrix}^{\top}.$

By Claim 9.8, the error can be decomposed into two terms:

$\displaystyle\|y(t)-x^{*}(t)\|_{T}\leq\left\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot
g^{\bot}_{w}\right\|_{2}+\left\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot
g^{\parallel}_{w}\right\|_{2}.$

By Claim 9.10, we have

$\displaystyle\left\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot
g^{\bot}_{w}\right\|_{2}^{2}\lesssim$
$\displaystyle~{}\varepsilon\left\|g^{\bot}(t)\right\|_{T}^{2}.$

And by Claim 9.13, we have

$\displaystyle\left\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot
g^{\parallel}_{w}\right\|_{2}^{2}=\left\|g^{\parallel}\right\|_{T}^{2}.$

Combining them together (and re-scaling $\varepsilon$ be an constant factor),
we have that

$\displaystyle\|y(t)-x^{*}(t)\|_{T}\leq\|g^{\parallel}\|_{T}+\sqrt{\varepsilon}\|g^{\bot}\|_{T}.$

Since $\|g^{\parallel}\|_{T}^{2}+\|g^{\bot}\|_{T}^{2}=\|g\|_{T}^{2}$, by
Cauchy–Schwarz inequality, we have that

$\displaystyle(\|g^{\parallel}\|_{T}+\sqrt{\varepsilon}\|g^{\bot}\|_{T})^{2}\leq(\|g^{\parallel}\|_{T}^{2}+\|g^{\bot}\|_{T}^{2})\cdot(1+\varepsilon)=(1+\varepsilon)\cdot\|g\|_{T}^{2}.$

That is,

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

∎

######  Claim 9.8 (Error decomposition).

$\displaystyle\|y(t)-x^{*}(t)\|_{T}\leq\left\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot
g^{\bot}_{w}\right\|_{2}+\left\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot
g^{\parallel}_{w}\right\|_{2}.$

###### Proof.

Since $y,x^{*}\in{\cal F}$ and $\\{u_{1},\dots,u_{\widetilde{k}}\\}$ is an
orthonormal basis, we have $\|y-x^{*}\|_{T}=\|\alpha(y)-\alpha(x^{*})\|_{2}$.
Furthermore, by Eq. (25), we have
$\alpha(y)=(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot X_{w}$. And by Fact 9.9, since
$x^{*}\in{\cal F}$, we have $\alpha(x^{*})=(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot
X_{w}^{*}$.

Thus, we have

$\displaystyle\|\alpha(y)-\alpha(x^{*})\|_{2}=$
$\displaystyle~{}\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot(X_{w}-X_{w}^{*})\|_{2}$
$\displaystyle=$ $\displaystyle~{}\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot
g_{w}\|_{2}$ $\displaystyle=$
$\displaystyle~{}\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot(g^{\bot}_{w}+g^{\parallel}_{w})\|_{2}$
$\displaystyle\leq$ $\displaystyle~{}\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot
g^{\bot}_{w}\|_{2}+\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot
g^{\parallel}_{w}\|_{2}$

where the second step follows from the definition of $g_{w}$, the forth step
follows from $g_{w}=g^{\parallel}+g^{\bot}$, and the last step follows from
triangle inequality.

Hence, we get that
$\|y(t)-x^{*}(t)\|_{T}\leq\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot
g^{\bot}_{w}\|_{2}+\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot
g^{\parallel}_{w}\|_{2}$. ∎

######  Fact 9.9.

For any $h\in{\cal F}$,

$\displaystyle\alpha(h)=(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot h_{w},$

where
$h_{w}=\sqrt{W}\begin{bmatrix}h(t_{1})&\cdots&h(t_{s})\end{bmatrix}^{\top}$.

###### Proof.

Suppose
$h(t)=\sum_{j=1}^{\widetilde{k}}v_{j}\exp(2\pi\mathbf{i}\widetilde{f}_{j}t)$.
We have

$\displaystyle B_{w}\alpha(h)=$ $\displaystyle~{}\sqrt{W}B\cdot\alpha(h)$
$\displaystyle=$ $\displaystyle~{}\sqrt{W}B\cdot(V^{+}v)$ $\displaystyle=$
$\displaystyle~{}h_{w},$

where the second step follows from $V^{+}$ is a change of coordinates.

Hence, by the Moore-Penrose inverse, we have

$\displaystyle\alpha(h)=B_{w}^{\dagger}h_{w}=(B_{w}^{*}B_{w})^{-1}B_{w}^{*}h_{w}.$

∎

######  Claim 9.10 (Bound the first term).

The following holds with high probability:

$\displaystyle\left\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot
g^{\bot}_{w}\right\|_{2}^{2}\lesssim$
$\displaystyle~{}\varepsilon\left\|g^{\bot}(t)\right\|_{T}^{2}.$

###### Proof.

By Lemma 6.5, with high probability, we have

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

where $(S,w)$ is the output of Procedure WeightedSketch. Conditioned on this
event, by Lemma 4.17,

$\displaystyle\lambda(B_{w}^{*}B_{w})\in[1-\varepsilon,1+\varepsilon],$

since $B_{w}$ is the same as the matrix $A$ in the lemma.

Hence,

$\displaystyle\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot
g^{\bot}_{w}\|_{2}^{2}\leq$
$\displaystyle~{}\lambda_{\max}((B^{*}_{w}B_{w})^{-1})^{2}\cdot\|B^{*}_{w}\cdot
g^{\bot}_{w}\|_{2}^{2}$ $\displaystyle\leq$
$\displaystyle~{}(1-\varepsilon)^{-2}\|B^{*}_{w}\cdot g^{\bot}_{w}\|_{2}^{2}$
$\displaystyle\lesssim$ $\displaystyle~{}\varepsilon\|g^{\bot}(t)\|_{T}^{2}$

where the second step follows from
$\lambda_{\max}((B_{w}^{*}B_{w})^{-1})\leq(1-\varepsilon)^{-1}$, and the third
step follows from Lemma 8.4 and Corollary 9.12. ∎

######  Lemma 9.11 (Lemma 6.2 of [CP19a]).

There exists a universal constant $C_{1}$ such that given any distribution
$D^{\prime}$ with the same support of $D$ and any $\varepsilon>0$, the random
sampling procedure with $m=C_{1}(K_{D^{\prime}}\log
d+\varepsilon^{-1}K_{D^{\prime}})$ i.i.d. random samples from $D^{\prime}$ and
coefficients $\alpha_{1}=\cdots=\alpha_{m}=1/m$ is an $\varepsilon$-_well-
balanced sampling procedure_.

######  Corollary 9.12.

Procedure WeightedSketch in Algorithm 7 is a $\varepsilon$-WBSP (Definition
7.1).

######  Claim 9.13 (Bound the second term).

$\displaystyle\left\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot
g^{\parallel}_{w}\right\|_{2}^{2}=\left\|g^{\parallel}\right\|_{T}^{2}.$

###### Proof.

$\displaystyle\|(B^{*}_{w}B_{w})^{-1}B^{*}_{w}\cdot
g^{\parallel}_{w}\|_{2}^{2}=\|\alpha(g^{\parallel})\|^{2}_{2}=$
$\displaystyle\|g^{\parallel}\|_{T}^{2},$

where the first step follows from Fact 9.9 and $g^{\parallel}\in{\cal F}$, the
second step follows from the definition of ${\alpha}$. ∎

##  10 High-dimensional Signal Estimation

In this section, we show a sample-optimal reduction from Frequency Estimation
to Signal Estimation for high-dimensional signals in Section 10.1, which
generalize Theorem 9.1. The key difference is that in high dimensions, we need
to upper-bound the number of lattice points within a $d$-dimensional sphere,
which turns out to be related to the output signal’s Fourier sparsity, and the
results are given in Section 10.2.

###  10.1 Sample-optimal reduction

######  Theorem 10.1 (Sample-optimal algorithm for high dimension Signal
Estimation).

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}$ and let
$g(t)$ denote the noise. Given observations of the form $x(t)=x^{*}(t)+g(t)$,
$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 FreqEst
that

  * •

takes $\mathcal{S}_{\mathsf{freq}}$ samples,

  * •

runs in $\mathcal{T}_{\mathsf{freq}}$-time,

  * •

outputs a set ${\cal L}$ of frequencies such that with probability $0.99$, the
following condition holds:

$\displaystyle\forall i\in[k],~{}\exists f^{\prime}_{i}\in{\cal
L}~{}\text{s.t.}~{}\|f_{i}-f^{\prime}_{i}\|_{2}\leq\frac{D}{T}.$

Then, there is an algorithm that

  * •

takes $O(\widetilde{k}+\mathcal{S}_{\mathsf{freq}})$ samples

  * •

runs in $O(\widetilde{k}^{O(d)}+\mathcal{T}_{\mathsf{freq}})$ time,

  * •

output
$y(t)=\sum_{j=1}^{\widetilde{k}}v_{j}^{\prime}\cdot\exp(2\pi\mathbf{i}\langle
f_{j}^{\prime},t\rangle)$ with $\widetilde{k}\leq|L|\cdot(D/T+\sqrt{m}\|{\cal
B}\|)^{m}\cdot\frac{\pi^{m/2}}{(m/2)!}\cdot\frac{1}{|\det({\cal B})|}$ such
that with probability 0.9, we have

$\int_{[0,T]^{d}}|y(t)-x(t)|^{2}\mathrm{d}t\lesssim\int_{[0,T]^{d}}|g(t)|^{2}\mathrm{d}t.$

###### Proof.

The algorithm is almost the same as Algorithm 10. First, we recover the
frequencies by calling Procedure $\textsc{FreqEst}(x,k,d,T,F,\mathcal{B})$.
Let $L$ be the set of frequencies output by the algorithm.

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

$\displaystyle\widetilde{L}:=\\{f\in\Lambda(\mathcal{B})~{}|~{}\exists
f^{\prime}\in L,~{}\|f^{\prime}-f\|_{2}<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}\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}}$. We run Procedure DistillHD in
Algorithm 8 and obtain a set $S=\\{t_{1},t_{2},\cdots,t_{s}\\}$ of
$s=O(\widetilde{k})$ samples in the duration $[0,T]^{d}$, and a weight vector
$w\in\mathbb{R}^{s}$.

Then, we consider the following weighted linear regression problem

$\displaystyle\underset{v^{\prime}\in\mathbb{C}^{\widetilde{k}}}{\min}\|\sqrt{w}\circ(Av^{\prime}-b)\|_{2},$

where $A\in\mathbb{C}^{s\times\widetilde{k}}$ and $b\in\mathbb{C}^{s}$ are
defined as follows:

$\displaystyle
A:=\begin{bmatrix}\exp(2\pi\mathbf{i}\langle\widetilde{f}_{1},t_{1}\rangle)&\cdots&\exp(2\pi\mathbf{i}\langle\widetilde{f}_{\widetilde{k}},t_{1}\rangle)\\\
\vdots&\ddots&\vdots\\\
\exp(2\pi\mathbf{i}\langle\widetilde{f}_{1},t_{s}\rangle)&\cdots&\exp(2\pi\mathbf{i}\langle\widetilde{f}_{\widetilde{k}},t_{s}\rangle)\end{bmatrix}~{}\text{and}~{}b:=\begin{bmatrix}x(t_{1})\\\
\vdots\\\ x(t_{s})\end{bmatrix}$

Let $v^{\prime}$ be an optimal solution of the regression and we output the
signal

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

Finally, we prove that $\|y(t)-x(t)\|_{T}\lesssim\|g(t)\|_{T}$, holds with a
large constant probability.

$\displaystyle\|y(t)-x(t)\|_{T}\leq$
$\displaystyle~{}\|y(t)-x^{*}(t)\|_{T}+\|g(t)\|_{T}$ $\displaystyle\leq$
$\displaystyle~{}(1+\varepsilon)\|y(t)-x^{*}(t)\|_{S,w}+\|g(t)\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}(1+\varepsilon)\|y(t)-x(t)\|_{S,w}+(1+\varepsilon)\|g(t)\|_{S,w}+\|g(t)\|_{T}$
$\displaystyle\leq$
$\displaystyle~{}(1+\varepsilon)\|x^{*}(t)-x(t)\|_{S,w}+(1+\varepsilon)\|g(t)\|_{S,w}+\|g(t)\|_{T}$
$\displaystyle\lesssim$ $\displaystyle~{}\|x^{*}(t)-x(t)\|_{S,w}+\|g(t)\|_{T}$
$\displaystyle\lesssim$ $\displaystyle~{}\|x^{*}(t)-x(t)\|_{T}+\|g(t)\|_{T}$
$\displaystyle\lesssim$ $\displaystyle~{}\|g(t)\|_{T},$ (26)

where the first step follows from triangle inequality, the second step follows
from Lemma 8.10 with $0.99$ probability, the third step follows from triangle
inequality, the forth step follows from $y(t)$ is the optimal solution of the
linear system, the fifth step follows from Claim 8.12, the sixth step follows
from Lemma 8.10, and the last step follows from the definition of $g(t)$.

The running time of the reduction follows from Lemma 8.10. ∎

###  10.2 Bounding the sparsity

In this section, we show that the Fourier sparsity of the output signal can be
bounded by the number of lattice points within a sphere. The intuition is that
for each frequency $f^{\prime}$ outputted by Procedure FreqEst, there could be
$|B_{d}(f^{\prime},D/T)\cap\Lambda({\cal B})|$ many candidates of true
frequencies, where $B_{d}(x,r)$ denotes the $d$-dimensional sphere centered at
$x$ with radius $r$. In Lemma 10.2, we upper-bound the sparsity for the case
when $D/T$ is larger than $\lambda_{1}(\Lambda({\cal B}))$, the shortest
vector length of the lattice. When $D/T$ is small, we show in Lemma 10.3 that
Procedure FreqEst finds all true frequencies.

######  Lemma 10.2 (Bounding sparsity for large $D/T$).

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{\\}},$

and let

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

be the output sparsity. Then, we have

  * •

(Spectral bound, which is better when $D/T<O(\|{\cal B}\|)$)

$\displaystyle\widetilde{k}\leq|L|\cdot(1+2D/(T\sigma_{\min}({\cal B})))^{m}.$

  * •

(Volume bound, which is better when $D/T>O(\|{\cal B}\|)$)

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

###### Proof.

Spectral bound: Let
$c=\begin{bmatrix}c_{1}&c_{2}&\cdots&c_{m}\end{bmatrix}^{\top}\in\mathbb{Z}^{m}$.
Then $z={\cal B}c\in\Lambda(\mathcal{B})$, and

$\displaystyle\|z\|_{2}=\|{\cal B}c\|_{2}\geq\sigma_{\min}({\cal
B})\cdot\|c\|_{2}$

Then we have that,

$\displaystyle\widetilde{k}=$
$\displaystyle~{}|\\{f\in\Lambda(\mathcal{B})~{}|~{}\exists f^{\prime}\in
L,~{}\|f^{\prime}-f\|_{2}<D/T\\}|$ $\displaystyle\leq$
$\displaystyle~{}|L|\cdot|\\{z\in\Lambda(\mathcal{B})~{}|~{}\|z\|_{2}<D/T\\}|$
$\displaystyle\leq$
$\displaystyle~{}|L|\cdot|\\{c\in\mathbb{Z}^{m}~{}|~{}\|c\|_{2}\leq
D/(T\sigma_{\min}({\cal B}))\\}|$ $\displaystyle\leq$
$\displaystyle~{}|L|\cdot|\\{c\in\mathbb{Z}^{m}~{}|~{}\|c\|_{\infty}\leq
D/(T\sigma_{\min}({\cal B}))\\}|$ $\displaystyle\leq$
$\displaystyle~{}|L|\cdot(1+2D/(T\sigma_{\min}{\cal B}))^{m}.$

where the first step follows from $f^{\prime}-f\in\Lambda(\mathcal{B})$, the
second step follows from if $\|c\|_{2}\geq D/(T\sigma_{\min})$, then
$\|z\|_{2}\geq D/T$, the third step follows from
$\|c\|_{\infty}\leq\|c\|_{2}$, and the last step follows from $c$ is a bounded
integer vector.

##### Volume bound:

Using Lemma 4.9, we have

$\displaystyle\widetilde{k}\leq|L|\cdot(1+\frac{\sqrt{m}\|{\cal
B}\|}{D/T})^{m}\cdot\frac{\mathrm{vol}({\cal
B}_{m}(0,D/T))}{\mathrm{vol}({\cal P}({\cal B}))}.$ (27)

We can upper bound volume of a ball as follows:

$\displaystyle\mathrm{vol}({\cal
B}_{m}(0,D/T))\leq\frac{\pi^{m/2}}{(m/2)!}\cdot(D/T)^{m}.$ (28)

Combining the above two equations, we have

$\displaystyle\mathrm{LHS}\leq$
$\displaystyle~{}|L|\cdot(1+\frac{\sqrt{m}\|{\cal
B}\|}{D/T})^{m}\cdot\frac{\pi^{m/2}}{(m/2)!}\cdot(D/T)^{m}\cdot\frac{1}{\mathrm{vol}({\cal
P}({\cal B}))}$ $\displaystyle\leq$
$\displaystyle~{}|L|\cdot(D/T+\sqrt{m}\|{\cal
B}\|)^{m}\cdot\frac{\pi^{m/2}}{(m/2)!}\cdot\frac{1}{|\det({\cal B})|},$

where the first step follows from Eq. (27) and Eq. (28).

∎

######  Lemma 10.3 (Bounding sparsity for tiny $D/T$).

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{\\}}$

and let

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

be the output sparsity. If $D/T\leq\lambda_{1}(\Lambda({\cal B}))$161616When
$m$ is small, we can solve the shortest vector problem (SVP) exactly to decide
the sparsity. Otherwise, we can check $D/T<\min_{i}\|b^{*}_{i}\|_{2}$ by
Theorem 4.11., then we have

$\displaystyle\widetilde{k}\leq|L|.$

###### Proof.

Since the radius $D/T$ is at most the shortest vector length of the lattice
$\Lambda({\cal B})$, for each $f^{\prime}\in L$, the sphere
$B_{d}(f^{\prime},D/T)$ contains at most one lattice point. ∎

###  10.3 High-accuracy reduction

######  Theorem 10.4 (High-dimensional Signal Estimation algorithm).

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}$ and let
$g(t)$ denote the noise. Given observations of the form $x(t)=x^{*}(t)+g(t)$,
$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 FreqEst
that

  * •

takes $\mathcal{S}_{\mathsf{freq}}$ samples,

  * •

runs in $\mathcal{T}_{\mathsf{freq}}$-time,

  * •

outputs a set ${\cal L}$ of frequencies such that with probability $0.99$, the
following condition holds:

$\displaystyle\forall i\in[k],~{}\exists f^{\prime}_{i}\in{\cal
L}~{}\text{s.t.}~{}\|f_{i}-f^{\prime}_{i}\|_{2}\leq\frac{D}{T}.$

Then, there is an algorithm that

  * •

takes $O(\varepsilon^{-1}\widetilde{k}^{O(d)}+\mathcal{S}_{\mathsf{freq}})$
samples

  * •

runs in $O(\varepsilon^{-1}\widetilde{k}^{O(d)}+\mathcal{T}_{\mathsf{freq}})$
time,

  * •

output
$y(t)=\sum_{j=1}^{\widetilde{k}}v_{j}^{\prime}\cdot\exp(2\pi\mathbf{i}\langle
f_{j}^{\prime},t\rangle)$ with $\widetilde{k}\leq|L|\cdot(D/T+\sqrt{m}\|{\cal
B}\|)^{m}\cdot\frac{\pi^{m/2}}{(m/2)!}\cdot\frac{1}{|\det({\cal B})|}$ such
that with probability 0.9, we have

$\int_{[0,T]^{d}}|y(t)-x(t)|^{2}\mathrm{d}t\leq(1+O(\varepsilon))\int_{[0,T]^{d}}|g(t)|^{2}\mathrm{d}t.$

######  Remark 10.5.

The difference between Theorem 10.4 and Theorem 10.1 is one is achieving
$(1+\varepsilon)$ error and the other is achieving $O(1)$ error.

###### Proof.

We can prove this theorem by using Theorem 5.2. The proof is similar as
Theorem 9.4. ∎

##  11 Discrete Fourier Set Query in One Dimension

In this section, we study the Fourier set-query problem, where we only care
about the Fourier coefficients of a discrete signal in a given set of
frequencies. We apply our framework and achieve optimal sample complexity and
high-accuracy. In Section 11.1, we show our main result on discrete Fourier
set query. A key step to prove this result is a WBSP Composition Lemma in
Section 11.2, which might be of independent interest.

###  11.1 Sample-optimal set query algorithm

In this section, we show our discrete Fourier set query result in the
following theorem, which works for discrete signals in any dimension.

######  Theorem 11.1 (Discrete Fourier Set Query).

For any $d\geq 1$, let $n=p^{d}$ where both $p$ and $d$ are positive integers.
Given a vector $x\in\mathbb{C}^{[p]^{d}}$, for $1\leq k\leq n$, any
$S\subseteq[n]$, $|S|=k$, there exists an algorithm (Algorithm 12) that takes
$O(\varepsilon^{-1}k)$ samples, runs in
$O(\varepsilon^{-1}k^{\omega+1}+\varepsilon^{-1}dk^{\omega-1}\log k)$ time,
and outputs a vector $x^{\prime}\in\mathbb{C}^{[p]^{d}}$ such that

$\displaystyle\|(\widehat{x}^{\prime}-\widehat{x})_{S}\|_{2}^{2}\leq\varepsilon\|\widehat{x}_{\overline{S}}\|_{2}^{2}$

holds with probability at least $0.9$.

In particular, for $d=1$, the runtime of Algorithm 12 is
$O(\varepsilon^{-1}k^{\omega+1})$.

###### Proof.

Let $\\{f_{1},f_{2},\cdots,f_{k}\\}\subseteq[p]^{d}$ denote $S$. If $d=1$, we
run Procedure DistillDisc in Algorithm 9, and if $d>1$, we run Procedure
DistillDiscHD in Algorithm 9. Then, we obtain a set
$L=\\{t_{1},t_{2},\cdots,t_{s}\\}\subseteq[p]^{d}$ of $s=O(\varepsilon^{-1}k)$
samples together with a weight vector $w\in\mathbb{R}^{s}$.

Then, we consider the following weighted linear regression problem:

$\displaystyle\underset{v^{\prime}\in\mathbb{C}^{k}}{\min}\|\sqrt{w}\circ(Av^{\prime}-b)\|_{2}.$
(29)

where $A\in\mathbb{C}^{s\times k}$ and $b\in\mathbb{C}^{s}$ are defined as
follows:

$\displaystyle
A:=\begin{bmatrix}\exp(2\pi\mathbf{i}f_{1}t_{1}/n)&\cdots&\exp(2\pi\mathbf{i}f_{k}t_{1}/n)\\\
\vdots&\ddots&\vdots\\\
\exp(2\pi\mathbf{i}f_{1}t_{s}/n)&\cdots&\exp(2\pi\mathbf{i}f_{k}t_{s}/n)\end{bmatrix}~{}\text{and}~{}b:=\begin{bmatrix}x(t_{1})\\\
\vdots\\\ x(t_{s})\end{bmatrix}$

Let $v^{\prime}$ be an optimal solution of Eq. (29). And we output a vector

$\displaystyle\widehat{x}^{\prime}_{f_{i}}=v^{\prime}_{i}~{}~{}~{}\forall
i\in[k].$

The running time follows from Lemma 11.2, and the estimation error guarantee
follows from Lemma 11.3.

The proof of the theorem is then completed. ∎

Algorithm 12 Discrete signal set-query algorithm.

1:procedure SetQuery($x$, $n$, $k$, $S$, $\varepsilon$) $\triangleright$
Theorem 11.1 (one-dimension)

2: $\\{f_{1},f_{2},\cdots,f_{k}\\}\leftarrow S$

3:
$s,\\{t_{1},t_{2},\cdots,t_{s}\\},w\leftarrow\textsc{DistillDisc}(k,\sqrt{\varepsilon},F,n)$
$\triangleright$ Algorithm 9

4: $A_{i,j}\leftarrow\exp(2\pi\mathbf{i}f_{j}t_{i}/n)$,
$A\in\mathbb{C}^{s\times k}$

5: $b\leftarrow(x(t_{1}),x(t_{2}),\cdots,x(t_{s}))^{\top}$

6: Solving the following weighted linear regression$\triangleright$ Fact 4.4
$\displaystyle
v^{\prime}\leftarrow\underset{v^{\prime}\in\mathbb{C}^{\widetilde{k}}}{\arg\min}\|\sqrt{w}\circ(Av^{\prime}-b)\|_{2}.$

7: return $\widehat{x}^{\prime}$ such that
$\widehat{x}^{\prime}_{f_{j}}=v^{\prime}_{j}$ for $j\in[k]$

8:end procedure

9:procedure SetQueryHD($x$, $n$, $k$, $S$, $\varepsilon$) $\triangleright$
Theorem 11.1 (high-dimension)

10: $\\{f_{1},f_{2},\cdots,f_{k}\\}\leftarrow S$

11:
$s,\\{t_{1},t_{2},\cdots,t_{s}\\},w\leftarrow\textsc{DistillDiscHD}(k,\sqrt{\varepsilon},F,n)$
$\triangleright$ Algorithm 9

12: $F_{\mathrm{batch}}=[f_{1},f_{2},\cdots,f_{k}]\in[p]^{d\times k}$

13: $T_{\mathrm{batch}}=[t_{1},t_{2},\cdots,t_{s}]\in[p]^{d\times s}$

14: $U=F_{\mathrm{batch}}^{\top}T_{\mathrm{batch}}\in\mathbb{Z}^{k\times s}$
$\triangleright$ Fact 4.3

15: $A_{i,j}\leftarrow\exp(2\pi\mathbf{i}U_{j,i}/p)$, $A\in\mathbb{C}^{s\times
k}$

16: $b\leftarrow(x(t_{1}),x(t_{2}),\cdots,x(t_{s}))^{\top}$

17: Solving the following weighted linear regression$\triangleright$ Fact 4.4
$\displaystyle
v^{\prime}\leftarrow\underset{v^{\prime}\in\mathbb{C}^{\widetilde{k}}}{\arg\min}\|\sqrt{w}\circ(Av^{\prime}-b)\|_{2}.$

18: return $\widehat{x}^{\prime}$ such that
$\widehat{x}^{\prime}_{f_{j}}=v^{\prime}_{j}$ for $j\in[k]$

19:end procedure

######  Lemma 11.2 (Running time of Algorithm 12).

The time complexity of Algorithm 12 is as follows:

  * •

Procedure SetQuery runs in $O(\varepsilon^{-1}k^{\omega+1})$-time.

  * •

Procedrue SetQueryHD runs in
$O(\varepsilon^{-1}k^{\omega+1}+\varepsilon^{-1}dk^{\omega-1}\log k)$-time.

###### Proof.

We first show the time complexity of Procedure DistillDisc. At Line 3,
Procedure DistillDisc takes $O(\varepsilon^{-1}k^{\omega+1})$-time by Lemma
8.13.

At Line 6, by Fact 4.4, it takes $O(\varepsilon^{-1}k\cdot
k^{\omega-1})=O(\varepsilon^{-1}k^{\omega})$-time.

Thus, the total running time is $O(\varepsilon^{-1}k^{\omega+1})$.

Then, we show the time complexity of Procedure DistillDiscHD. At Line 11,
Procedure DistillDiscHD takes
$O(\varepsilon^{-1}k^{\omega+1}+\varepsilon^{-1}dk^{\omega-1}\log k)$-time by
Lemma 8.13.

At Line 14, by Fact 4.3, it takes the time ${\cal T}_{\mathrm{mat}}(k,d,s)$.
We know that $s\geq k$. We can consider two cases.

  * •

In case 1, $d\leq k$, we can just simply bound the time by ${\cal
T}_{\mathrm{mat}}(k,k,s)=O(k^{\omega}\cdot(s/k))=O(k^{\omega-1}s)=O(\varepsilon^{-1}k^{\omega})$.
(In this regime, this part running time is dominated by Line 11)

  * •

In case 2, $d\geq k$, we can just bound the time by ${\cal
T}_{\mathrm{mat}}(k,d,s)=O(k^{\omega}\cdot(d/k)\cdot(s/k))=dsk^{\omega-2}=O(\varepsilon^{-1}dk^{\omega-1})$

At Line 17, by Fact 4.4, it takes $O(\varepsilon^{-1}k\cdot
k^{\omega-1})=O(\varepsilon^{-1}k^{\omega})$-time.

Thus, the total running time is
$O(\varepsilon^{-1}k^{\omega+1}+\varepsilon^{-1}dk^{\omega-1}\log k)$. ∎

######  Lemma 11.3 (Estimation error of Algorithm 12).

Let $\widehat{x}^{\prime}$ be the output of Algorithm 12 (with $d=1$ or
$d>1$). Then, with high probability,

$\displaystyle\|(\widehat{x}^{\prime}-\widehat{x})_{S}\|_{2}^{2}\lesssim\|\widehat{x}_{\overline{S}}\|_{2}^{2}.$

###### Proof.

Let $D:=\mathrm{Uniform}([p]^{d})$. Recall that $n=p^{d}$. Let $\cal F$ be the
family of length-$n$ discrete signals with frequencies in $S$:

$\displaystyle{\cal F}=\Big{\\{}\sum_{j=1}^{k}v_{j}e^{2\pi\mathbf{i}\langle
f_{j},t\rangle/p}~{}\big{|}~{}v_{j}\in\mathbb{C}\Big{\\}}$

Then, it is well-known that $\\{v_{j}(t)=\exp(2\pi\mathbf{i}\langle
f_{j},t\rangle/p)\\}_{j\in[k]}$ forms an orthonormal basis for ${\cal F}$ with
respect to the distribution $D$, i.e.,

$\displaystyle\operatorname*{{\mathbb{E}}}_{t\sim
D}[\overline{v_{i}(t)}v_{j}(t)]={\bf 1}_{i=j}~{}~{}~{}\forall i,j\in[k].$

Now, we define some notations. Let $\alpha:{\cal F}\rightarrow\mathbb{C}^{k}$
be a linear operator such that for any
$h(t)=\sum_{j=1}^{k}a_{j}\exp(2\pi\mathbf{i}\langle f_{j},t\rangle/p)$,

$\displaystyle\alpha(h):=\begin{bmatrix}a_{1}&a_{2}&\cdots&a_{k}\end{bmatrix}^{\top}.$

Suppose the true discrete signal
$x(t)=\sum_{j=1}^{n}v_{j}\exp(2\pi\mathbf{i}\langle j,t\rangle/p)$. Define

$\displaystyle x_{S}(t):=$ $\displaystyle~{}\sum_{f\in
S}v_{f}\exp(2\pi\mathbf{i}\langle f,t\rangle/p),$ $\displaystyle
x_{\overline{S}}(t):=$
$\displaystyle~{}\sum_{f\in\overline{S}}v_{f}\exp(2\pi\mathbf{i}\langle
f,t\rangle/p).$

Let $\sqrt{W}\in\mathbb{R}^{s\times s}$ denote the diagonal matrix
$\mathrm{diag}(\sqrt{w_{1}},\dots,\sqrt{w_{s}})$. Define

$\displaystyle A_{w}:=$ $\displaystyle~{}\sqrt{W}\cdot A,$ $\displaystyle
X_{w}:=$
$\displaystyle~{}\sqrt{W}\cdot\begin{bmatrix}x(t_{1})&\cdots&x(t_{s})\end{bmatrix}^{\top},$
$\displaystyle X_{w}^{S}:=$
$\displaystyle~{}\sqrt{W}\cdot\begin{bmatrix}x_{S}(t_{1})&\cdots&x_{S}(t_{s})\end{bmatrix}^{\top},$
$\displaystyle X_{w}^{\overline{S}}:=$
$\displaystyle~{}\sqrt{W}\cdot\begin{bmatrix}x_{\overline{S}}(t_{1})&\cdots&x_{\overline{S}}(t_{s})\end{bmatrix}^{\top}.$

Notice that for any $h=\sum_{i=1}^{k}a_{i}\exp(2\pi\mathbf{i}\langle
f_{i},t\rangle/p)\in{\cal F}$,

$\displaystyle
A_{w}\alpha(h)=\sqrt{W}\cdot\begin{bmatrix}\exp(2\pi\mathbf{i}f_{1}t_{1}/n)&\cdots&\exp(2\pi\mathbf{i}f_{k}t_{1}/n)\\\
\vdots&\ddots&\vdots\\\
\exp(2\pi\mathbf{i}f_{1}t_{s}/n)&\cdots&\exp(2\pi\mathbf{i}f_{k}t_{s}/n)\end{bmatrix}\begin{bmatrix}a_{1}\\\
\vdots\\\ a_{k}\end{bmatrix}=\begin{bmatrix}\sqrt{w_{1}}h(t_{1})\\\ \vdots\\\
\sqrt{w_{s}}h(t_{s})\end{bmatrix}.$

Thus, by Moore-Penrose inverse, we have

$\displaystyle\alpha(h)=(A^{*}_{w}A_{w})^{-1}A^{*}_{w}\cdot\begin{bmatrix}\sqrt{w_{1}}h(t_{1})\\\
\vdots\\\ \sqrt{w_{s}}h(t_{s})\end{bmatrix}.$ (30)

Let
$x^{\prime}(t):=\sum_{j=1}^{k}\widehat{x}^{\prime}_{f_{j}}\exp(2\pi\mathbf{i}\langle
f_{j},t\rangle/p)$ be the output signal in the time domain. Then we claim that

$\displaystyle\|x^{\prime}-x_{S}\|^{2}_{D}=$
$\displaystyle~{}\|\alpha(x^{\prime})-\alpha(x_{S})\|^{2}_{2}$
$\displaystyle=$
$\displaystyle~{}\|(A^{*}_{w}A_{w})^{-1}A^{*}_{w}\cdot(X_{w}-X_{w}^{S})\|^{2}_{2}$
$\displaystyle=$ $\displaystyle~{}\|(A^{*}_{w}A_{w})^{-1}A^{*}_{w}\cdot
X^{\overline{S}}_{w}\|^{2}_{2}$ $\displaystyle\leq$
$\displaystyle~{}\lambda_{\max}((A^{*}_{w}A_{w})^{-1})^{2}\cdot\|A^{*}_{w}\cdot
X^{\overline{S}}_{w}\|_{2}^{2}$ $\displaystyle\leq$
$\displaystyle~{}\|A^{*}_{w}\cdot X^{\overline{S}}_{w}\|_{2}^{2},$

where the first step follows from the definition of $\alpha$, the second step
follows from $\alpha(x^{\prime})=v^{\prime}$ being the optimal solution of Eq.
(29) and Eq. (30) for $x_{S}$, the third step follows from
$x=x_{S}+x_{\overline{S}}$, the fifth step follows from Lemma 4.17 and Lemma
8.13 and holds with high probability.

Notice that $x_{\overline{S}}$ is orthogonal to ${\cal F}$. And by Lemma 11.4,
we know that $(L,w)$ is generated by an $\varepsilon$-WBSP. Hence, by Lemma
8.4, we have

$\displaystyle\|x^{\prime}-x_{S}\|^{2}_{D}\leq\|A^{*}_{w}\cdot
X^{\overline{S}}_{w}\|_{2}^{2}\lesssim\varepsilon\|x_{\overline{S}}\|_{D}^{2}.$

By Parseval’s theorem (Theorem 5.8), we conclude that

$\displaystyle\|\widehat{x}^{\prime}-\widehat{x}_{S}\|_{2}^{2}\leq\varepsilon\|\widehat{x}_{\overline{S}}\|_{2}^{2}$

holds with high probability.

∎

###  11.2 Composition of two WBSPs

In this section, we prove the following key lemma on the composition of two
WBSPs for discrete signals.

######  Lemma 11.4 (WBSP Composition Lemma).

Let $m_{0},m_{1},n\in\mathbb{Z}_{+}$, $m_{1}\leq m_{0}\leq n$. Let
$\\{f_{1},\cdots,f_{k}\\}\subseteq[n]$. Let ${\cal F}$ be the family of
discrete $k$-sparse signals in $t\in[n]$:

$\displaystyle{\cal
F}=\Big{\\{}v_{0}+\sum_{j=1}^{k}v_{j}\cdot\exp(2\pi\mathbf{i}f_{j}t/n)~{}|~{}\forall
v_{j}\in\mathbb{C},j=\\{0,\dots,k\\}\Big{\\}}$

Define the following two WBSPs for ${\cal F}$:

  * •

Let $P_{1}$ be an $\varepsilon$-WBSP generating $m_{1}$ samples, with input
distribution $D_{1}$, coefficients $\alpha_{1}$, and output distributions
$D_{1,i}$ for $i\in[m_{1}]$.

  * •

Let $P_{2}$ be an $\varepsilon$-WBSP generating $m_{2}$ samples, with input
distribution $D_{2}$, coefficients $\alpha_{2}$, and output distributions
$D_{2,i}$ for $i\in[m_{2}]$.

We can composite $P_{1}$ and $P_{2}$ by taking
$D_{2}(x_{i}):=\frac{w_{1,i}}{\sum_{j\in[m_{1}]}w_{1,j}}$ for $i\in[m_{1}]$.
Let $P_{1}\circ P_{2}$ denote the composition of $P_{1},P_{2}$.

Then, if $P_{1}$ satisfies $D_{1,i}=D_{1}=\mathrm{Uniform}([n])$, then
$P_{1}\circ P_{2}$ is an $O(\varepsilon)$-WBSP generating $m_{2}$ samples,
with input distribution $D_{1}$, coefficients $w_{2}$, and output
distributions $D_{1}$ for all $i\in[m_{2}]$.

###### Proof.

Let $S_{1}=\\{x_{1},\dots,x_{m_{1}}\\}$ denote the set sampled by $P_{1}$ and
$S_{2}=\\{x_{1}^{\prime},\dots,x^{\prime}_{m_{2}}\\}$ denote the set sampled
by $P_{2}$. Then, we have $S_{2}\subset S_{1}$. In the followings, we show
that $P_{1}\circ P_{2}$ satisfies all the stated properties.

##### Input distribution and the first WBSP property.

We first show that $P_{1}\circ P_{2}$ satisfies the first property of WBSP in
Definition 7.1 with respect to distribution $D_{1}$, that is,

$\displaystyle\|f\|_{S_{2},w_{2}}\in[1-O(\sqrt{\varepsilon}),1+O(\sqrt{\varepsilon})]\|f\|_{D_{1}}^{2}~{}~{}~{}\forall
f\in{\cal F}.$

By definition of $\varepsilon$-WBSP (Definition 7.1), we have for any
$f\in{\cal F}$,

$\displaystyle\|f\|_{S_{1},w_{1}}^{2}\in[1-\sqrt{\varepsilon},1+\sqrt{\varepsilon}]\cdot\|f\|_{D_{1}}^{2},~{}\text{and}$
(31)
$\displaystyle\|f\|_{S_{2},w_{2}}^{2}\in[1-\sqrt{\varepsilon},1+\sqrt{\varepsilon}]\cdot\|f\|_{D_{2}}^{2}.$

By the definition of $D_{2}$, we have
$\|f\|_{D_{2}}^{2}=\|f\|_{S_{1},w_{1}}^{2}$ (assuming $\|w_{1}\|_{1}=1$
without loss of generality). Thus, we get that

$\displaystyle\|f\|_{S_{2},w_{2}}^{2}\in$
$\displaystyle~{}[1-\sqrt{\varepsilon},1+\sqrt{\varepsilon}]\|f\|_{S_{1},w_{1}}^{2}$
$\displaystyle\in$
$\displaystyle~{}[1-\sqrt{\varepsilon},1+\sqrt{\varepsilon}]\cdot[1-\sqrt{\varepsilon},1+\sqrt{\varepsilon}]\|f\|_{D_{1}}^{2}$
$\displaystyle\in$
$\displaystyle~{}[1-3\sqrt{\varepsilon},1+3\sqrt{\varepsilon}]\|f\|_{D_{1}}^{2}.$
(32)

##### Coefficients.

Then, consider the equivalent coefficients $\alpha_{3}$ of $P_{1}\circ P_{2}$.
Let $D_{3,i}$ be the output distribution of the $i$-th sample $x^{\prime}_{i}$
produced by $P_{1}\circ P_{2}$. By Fact 11.5,

$\displaystyle D_{3,i}(x^{\prime}_{i})=\sum_{j=1}^{m_{1}}D_{2,i}(x_{j})\cdot
D_{1,j}(x^{\prime}_{i})=D_{1}(x^{\prime}_{i}),$

where the second step follows from the assumption that $D_{1,j}=D_{1}$ for all
$j\in[m_{1}]$. Thus, we have $D_{3,i}=D_{1}$ for all $i\in[m_{2}]$. Since its
weight vector is $w_{2}$ and input distribution is $D_{1}$, by definition, we
have for $i\in[m_{2}]$,

$\displaystyle\alpha_{3,i}=w_{2,i}\cdot\frac{D_{3,i}(x_{i}^{\prime})}{D_{1}(x_{i}^{\prime})}=w_{2,i}.$

Thus, the coefficients of $P_{1}\circ P_{2}$ is $w_{2}$.

##### The second WBSP property.

We first bound $\sum_{i=1}^{m_{2}}\alpha_{3,i}$. Since $\alpha_{3}=w_{2}$, we
just need to bound $\sum_{i=1}^{m_{2}}w_{2,i}$. Let
$f_{1}:=\begin{bmatrix}1&1&\cdots&1\end{bmatrix}^{\top}\in\mathbb{C}^{n}$.
Then, it is easy to see that $f_{1}\in{\cal F}$ with $v_{0}=1$ and $v_{i}=0$
for $i\in[k]$. By Eq. (11.2), we have

$\displaystyle\|f_{1}\|_{S_{2},w_{2}}^{2}=$
$\displaystyle~{}\sum_{i=1}^{m_{2}}w_{2,i}$ $\displaystyle\in$
$\displaystyle~{}[1-\sqrt{\varepsilon},1+\sqrt{\varepsilon}]\cdot\|f_{1}\|_{D_{1}}^{2}$
$\displaystyle=$
$\displaystyle~{}[1-\sqrt{\varepsilon},1+\sqrt{\varepsilon}],$

where the last step follows from
$\|f_{1}\|_{D_{1}}^{2}=\sum_{i=1}^{n}D_{1}(i)=1$. Hence,

$\displaystyle\sum_{i=1}^{m_{2}}\alpha_{3,i}=\sum_{i=1}^{m_{2}}w_{2,i}\leq
1+\sqrt{\varepsilon}\leq\frac{5}{4}.$

We also need to show that $\alpha_{3,i}K_{\mathsf{IS},D_{3,i}}=O(\varepsilon)$
for all $i\in[m_{2}]$. By definition, we have

$\displaystyle K_{\mathsf{IS},D_{3,i}}=$
$\displaystyle~{}\underset{t}{\sup}\bigg{\\{}\frac{D_{1}(t)}{D_{3,i}(t)}\cdot\underset{f\in\mathcal{F}}{\sup}\big{\\{}\frac{|f(t)|^{2}}{\|f\|_{D_{1}}^{2}}\big{\\}}\bigg{\\}}$
$\displaystyle=$ $\displaystyle~{}\sup_{t}\sup_{f\in{\cal
F}}\Big{\\{}\frac{|f(t)|^{2}}{\|f\|_{D_{1}}^{2}}\Big{\\}}$ $\displaystyle\leq$
$\displaystyle~{}k,$ (33)

where the second step follows from $D_{3,i}=D_{1}$ and the last step follows
from the energy bound (Theorem 5.6) and the assumption that
$D_{1}=\mathrm{Uniform}([n])$.

Since $P_{2}$ is an $\varepsilon$-WBPS, we have

$\displaystyle K_{\mathsf{IS},D_{2,i}}=$
$\displaystyle~{}\underset{t}{\sup}\bigg{\\{}\frac{D_{2}(t)}{D_{2,i}(t)}\cdot\underset{f\in\mathcal{F}}{\sup}\big{\\{}\frac{|f(t)|^{2}}{\|f\|_{D_{2}}^{2}}\big{\\}}\bigg{\\}}$
$\displaystyle=$
$\displaystyle~{}\underset{t}{\sup}\bigg{\\{}\frac{D_{2}(t)}{D_{2,i}(t)}\cdot\underset{f\in\mathcal{F}}{\sup}\big{\\{}\frac{|f(t)|^{2}}{\|f\|_{S_{1},w_{1}}^{2}}\big{\\}}\bigg{\\}}$
$\displaystyle\geq$
$\displaystyle~{}(1+\sqrt{\varepsilon})^{-1}\cdot\underset{t}{\sup}\bigg{\\{}\frac{D_{2}(t)}{D_{2,i}(t)}\cdot\underset{f\in\mathcal{F}}{\sup}\big{\\{}\frac{|f(t)|^{2}}{\|f\|_{D_{1}}^{2}}\big{\\}}\bigg{\\}},$

where the second step follows from $\|f\|_{D_{2}}=\|f\|_{S_{1},w_{1}}$, the
third step follows from Eq. (31). And for all $i\in[m_{2}]$,

$\displaystyle\alpha_{2,i}K_{\mathsf{IS},D_{2,i}}=O(\varepsilon),$

which implies that

$\displaystyle\alpha_{2,i}\cdot\underset{t}{\sup}\bigg{\\{}\frac{D_{2}(t)}{D_{2,i}(t)}\cdot\underset{f\in\mathcal{F}}{\sup}\big{\\{}\frac{|f(t)|^{2}}{\|f\|_{D_{1}}^{2}}\big{\\}}\bigg{\\}}=O(\varepsilon).$

Since $D_{1}$ is uniform, we know that
$\\{\exp(2\pi\mathbf{i}f_{j}t)\\}_{j\in[k]}$ form an orthonormal basis with
respect to $D_{1}$. Thus, by Fact 8.9, for any $t\in[n]$,

$\displaystyle\underset{f\in\mathcal{F}}{\sup}\\{\frac{|f(t)|^{2}}{\|f\|_{D^{\prime}}^{2}}\\}=\sum_{j=1}^{k}|\exp(2\pi\mathbf{i}f_{j}t)|^{2}=k.$

Hence, we get that

$\displaystyle\alpha_{2,i}\cdot\underset{t}{\sup}\bigg{\\{}\frac{D_{2}(t)}{D_{2,i}(t)}\bigg{\\}}=O(\varepsilon/k)$

Therefore,

$\displaystyle\alpha_{3,i}K_{\mathsf{IS},D_{3,i}}\leq$
$\displaystyle~{}w_{2,i}\cdot k$ $\displaystyle=$
$\displaystyle~{}\alpha_{2,i}\cdot\frac{D_{2}(x_{i})}{D_{2,i}(x_{i})}\cdot k$
$\displaystyle\leq$
$\displaystyle~{}\alpha_{2,i}\cdot\underset{t}{\sup}\bigg{\\{}\frac{D_{2}(t)}{D_{2,i}(t)}\bigg{\\}}\cdot
k$ $\displaystyle=$ $\displaystyle~{}O(\varepsilon/k)\cdot k$ $\displaystyle=$
$\displaystyle~{}O(\varepsilon).$

where the first step follows from $\alpha_{3}=w_{2}$ and Eq. (11.2), the
second step follows from the definition of $w_{2,i}$.

Thus, we prove that $P_{1}\circ P_{2}$ is an $O(\varepsilon)$-WBSP with input
distribution $D_{1}$, output distributions $D_{1}$, coefficients $w_{2}$. ∎

######  Fact 11.5 (Double-sampling distribution).

For $i\in[n]$, let $D_{i}$ be a distribution over the domain $G$. Suppose we
first sample $x_{i}$ from $D_{i}$ for each $i\in[n]$. Let
$w_{1},\cdots,w_{n}\in\mathbb{R}_{+}$ such that $\sum_{i=1}^{n}w_{i}=1$.
Conditioned on the samples $\\{x_{1},\dots,x_{n}\\}$, let $D^{\prime}$ be a
distribution over these samples such that $D^{\prime}(x_{i})=w_{i}$. Then, we
sample an $x^{\prime}$ from $D^{\prime}$.

Then, the distribution of $x^{\prime}$ is $D^{\prime\prime}$, where

$\displaystyle D^{\prime\prime}(x)=\sum_{i=1}^{n}w_{i}D_{i}(x)~{}~{}~{}\forall
x\in G.$

###### Proof.

Notice that the second sampling process is equivalent to sample an index ${\sf
i}\in[n]$. Hence, for any $a\in G$,

$\displaystyle\Pr[x^{\prime}=a]=$ $\displaystyle~{}\sum_{j=1}^{n}\Pr[{\sf
i}=j]\cdot\Pr_{D_{j}}[x_{j}=a~{}|~{}{\sf i}=j]$ $\displaystyle=$
$\displaystyle~{}\sum_{j=1}^{n}w_{j}\cdot\Pr_{D_{j}}[x_{j}=a]$
$\displaystyle=$ $\displaystyle~{}\sum_{j=1}^{n}w_{j}D_{j}(a)$
$\displaystyle=$ $\displaystyle~{}D^{\prime\prime}(a).$

where the first step follows from law of total probability, and the second
step follows from sampling $x_{j}$ from $D_{j}$ is independent to sampling the
index ${\sf i}$ from $D^{\prime}$. ∎

##  12 High-Accuracy Fourier Interpolation Algorithm

In this section, we propose an algorithm for one-dimensional continuous
Fourier interpolation problem, which significantly improves the accuracy of
the algorithm in [CKPS16].

This section is organized as follows. In Sections 12.1 and 12.2, we provide
some technical tools for Fourier-sparse signals, low-degree polynomials and
filter functions. In Section 12.3, we design a high sensitivity frequency
estimation method using these tools. In Section 12.4, we combine the frequency
estimation with our Fourier set query framework, and give a
$(7+\varepsilon)$-approximate Fourier interpolation algorithm. Then, in
Section 12.5, we build a sharper error control, and in Section 12.6, we
analysis the HashToBins procedure. Based on these result, in Section 12.8, we
develop the ultra-high sensitivity frequency estimation method. In Section
12.10, we show the a $(1+\sqrt{2}+\varepsilon)$-approximate Fourier
interpolation algorithm.

###  12.1 Technical tools i@: Fourier-polynomial equivalence

In this section, we show that low-degree polynomials and Fourier-sparse
signals can be transformed to each other with arbitrarily small errors.

The following lemma upper-bounds the error of using low-degree polynomial to
approximate Fourier-sparse signal.

######  Lemma 12.1 (Fourier signal to polynomial, [CKPS16]).

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

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

such that

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

As a corollary, we can expand a Fourier-sparse signal under the _mixed
Fourier-monomial basis_ (i.e., $\\{e^{2\pi\mathbf{i}f_{i}t}\cdot
t^{j}\\}_{i\in[k],j\in[d]}$).

######  Corollary 12.2 (Mixed Fourier-polynomial approximation).

For any $\Delta>0$, $\delta>0$, $n_{j}\in\mathbb{Z}_{\geq
0},j\in[k],\sum_{j\in[k]}n_{j}=k$. Let

$\displaystyle
x^{*}(t)=\sum_{j\in[k]}e^{2\pi\mathbf{i}f_{j}t}\sum_{i=1}^{n_{j}}v_{j,i}e^{2\pi\mathbf{i}f^{\prime}_{j,i}t},$

where $|f^{\prime}_{j,i}|\leq\Delta$ for each $j\in[k],i\in[n_{j}]$. There
exist $k$ polynomials $P_{j}(t)$ for $j\in[k]$ of degree at most

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

such that

$\Big{\|}\sum_{j\in[k]}e^{2\pi\mathbf{i}f_{j}t}P_{j}(t)-x^{*}(t)\Big{\|}^{2}_{T}\leq\delta\|x^{*}(t)\|^{2}_{T}.$

The following lemma bounds the error of approximating a low-degree polynomial
using Fourier-sparse signal.

######  Lemma 12.3 (Polynomial to Fourier signal, [CKPS16]).

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

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

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

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

###  12.2 Technical tools ii@: filter functions

In this section, we introduce the filter functions $H$ and $G$ designed by
[CKPS16], and we generalize their constructions to achieve higher sensitivity.

We first construct the $H$-filter, which uses $\mathrm{rect}$ and
$\operatorname{sinc}$ functions.

######  Fact 12.4 ($\mathrm{rect}$ function Fourier transform).

For $s>0$, let $\mathrm{rect}_{s}(t):={\bf 1}_{|t|\leq s/2}$. Then, we have

$\displaystyle\widehat{\mathrm{rect}_{s}}(f)=\operatorname{sinc}(sf)=\frac{\sin(sf)}{\pi
sf}.$

######  Definition 12.5.

Given $s_{1},s_{2}>0$ and an even number $\ell\in\mathbb{N}_{+}$, we define
the filter function $H_{1}(t)$ and its Fourier transform $\widehat{H}_{1}(f)$
as follows:

$\displaystyle H_{1}(t)$ $\displaystyle=$ $\displaystyle
s_{0}\cdot(\operatorname{sinc}^{\ell}(s_{1}t))\star\mathrm{rect}_{s_{2}}(t)$
$\displaystyle\widehat{H}_{1}(f)$ $\displaystyle=$ $\displaystyle
s_{0}\cdot(\mathrm{rect}_{s_{1}}\star\cdots\star\mathrm{rect}_{s_{1}})(f)\cdot\operatorname{sinc}\left(fs_{2}\right)$

where $s_{0}=C_{0}s_{1}\sqrt{\ell}$ is a normalization parameter such that
$H_{1}(0)=1$, and $\star$ means convolution.

######  Definition 12.6 ($H$-filter’s construction, [CKPS16]).

Given any $0<s_{1},s_{3}<1$, $0<\delta<1$, we define
$H_{s_{1},s_{3},\delta}(t)$ from the filter function $H_{1}(t)$ (Definition
12.5) as follows:

  * •

let $\ell:=\Theta(k\log(k/\delta))$, $s_{2}:=1-\frac{2}{s_{1}}$, and

  * •

shrink $H_{1}$ by a factor $s_{3}$ in time domain, i.e.,

$\displaystyle H_{s_{1},s_{3},\delta}(t)$ $\displaystyle:=$ $\displaystyle
H_{1}(t/s_{3})$ (34) $\displaystyle\widehat{H_{s_{1},s_{3},\delta}}(f)$
$\displaystyle=$ $\displaystyle s_{3}\widehat{H_{1}}(s_{3}f)$ (35)

We call the “filtered cluster" around a frequency $f_{0}$ to be the support of
$(\delta_{f_{0}}\star\widehat{H_{s_{1},s_{3},\delta}})(f)$ in the frequency
domain and use

$\Delta_{h}=|\mathrm{supp}(\widehat{H_{s_{1},s_{3},\delta}})|=\frac{s_{1}\cdot\ell}{s_{3}}$
(36)

to denote the width of the cluster.

######  Lemma 12.7 (High sensitivity $H$-filter’s properties).

Given $\varepsilon\in(0,0.1)$, $s_{1},s_{3}\in(0,1)$ with
$\min(\frac{1}{1-s_{3}},s_{1})\geq\widetilde{O}(k^{4})/\varepsilon$, and
$\delta\in(0,1)$. Let the filter function $H:=H_{s_{1},s_{3},\delta}(t)$
defined in Definition 12.6. Then, $H$ satisfies the following properties:

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

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

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

######  Remark 12.8.

By Property i@, and ii@, and iii@, we have that $H(t)\leq 1$ for $t\in[0,T]$.

###### Proof.

The proof of Property I - V easily follows from [CKPS16]. We prove Property VI
in below.

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

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

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

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

Then we can show

$\displaystyle~{}\int_{\overline{S}}|x^{*}(t)|^{2}\mathrm{d}t$
$\displaystyle\leq$
$\displaystyle~{}|\overline{S}|\cdot\underset{t\in[-1/2,1/2]}{\max}|x^{*}(t)|^{2}$
$\displaystyle\leq$
$\displaystyle~{}(1-s_{3}(1-\frac{2}{s_{1}}))\cdot{O}(k^{2})\int_{-\frac{1}{2}}^{\frac{1}{2}}|x^{*}(t)|^{2}\mathrm{d}t$
$\displaystyle\leq$
$\displaystyle~{}\varepsilon\int_{-\frac{1}{2}}^{\frac{1}{2}}|x^{*}(t)|^{2}\mathrm{d}t$
(38)

where the first step follows from $\overline{S}\subset[-1/2,1/2]$, the second
step follows from Theorem 5.1, the third step follows from
$(1-s_{3}(1-\frac{2}{s_{1}}))\cdot{O}(k^{2})\leq\varepsilon$.

Combining Equations (37) and (12.2) gives a lower bound for LHS,

$\displaystyle\int_{-\infty}^{+\infty}|x^{*}(t)\cdot
H(t)\cdot\mathrm{rect}_{1}(t)|^{2}\mathrm{d}t$ $\displaystyle\geq$
$\displaystyle~{}\int_{S}|x^{*}(t)H(t)|^{2}\mathrm{d}t$ $\displaystyle\geq$
$\displaystyle~{}(1-2\delta)\int_{S}|x^{*}(t)|^{2}\mathrm{d}t$
$\displaystyle=$
$\displaystyle~{}(1-2\delta)\int_{S\cup\overline{S}}|x^{*}(t)|^{2}\mathrm{d}t-(1-2\delta)\int_{\overline{S}}|x^{*}(t)|^{2}\mathrm{d}t$
$\displaystyle\geq$
$\displaystyle~{}(1-2\delta)\int_{S\cup\overline{S}}|x^{*}(t)|^{2}\mathrm{d}t-(1-2\delta)\varepsilon\int_{S\cup\overline{S}}|x^{*}(t)|^{2}\mathrm{d}t$
$\displaystyle=$
$\displaystyle~{}(1-2\delta-\varepsilon)\int_{-\frac{1}{2}}^{\frac{1}{2}}|x^{*}(t)|^{2}\mathrm{d}t$
$\displaystyle\geq$
$\displaystyle~{}(1-2\varepsilon)\int_{-\infty}^{+\infty}|x^{*}(t)\cdot\mathrm{rect}_{1}(t)|^{2}\mathrm{d}t,$

where the first step follows from $S\subset[-1/2,1/2]$, the second step
follows from Eq. (37), the third step follows from
$S\cap\overline{S}=\emptyset$, the forth step follows from Eq. (12.2), the
fifth step follows from $S\cup\overline{S}=[-1/2,1/2]$, the last step follows
from $\varepsilon\gg\delta$.

∎

As remarked in [CKPS16], to match $(H(t),\widehat{H}(f))$ on $[-1/2,1/2]$ with
signal $x(t)$ on $[0,T]$, we will scale the time domain from $[-1/2,1/2]$ to
$[-T/2,T/2]$ and shift it to $[0,T]$. Then, in frequency domain, the Property
iv@ in Lemma 12.7 becomes

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

We also need another filter function, $G$, whose construction and properties
are given below.

######  Definition 12.9 ($G$-filter’s construction, [CKPS16]).

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

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

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

######  Lemma 12.10 ($G$-filter’s properties, [CKPS16]).

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

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

###  12.3 High sensitivity frequency estimation

In this section, we show a high sensitivity frequency estimation. Compared
with the result in [CKPS16], we relax the condition of the frequencies that
can be recovered by the algorithm.

######  Definition 12.11 (Definition 2.4 in [CKPS16]).

Given
$x^{*}(t)=\overset{k}{\underset{j=1}{\sum}}v_{j}e^{2\pi\mathbf{i}f_{j}t}$, any
$\mathcal{N}>0$, and a filter function $H$ with bounded support in frequency
domain. Let $L_{j}$ denote the interval of
$~{}\mathrm{supp}(\widehat{e^{2\pi\mathbf{i}f_{j}t}\cdot H})$ for each
$j\in[k]$. Define an equivalence relation $\sim$ on the frequencies $f_{i}$ as
follows:

$\displaystyle f_{i}\sim f_{j}~{}~{}\text{iff}~{}~{}L_{i}\cap
L_{j}\neq\emptyset~{}~{}~{}\forall i,j\in[k].$

Let $S_{1},\ldots,S_{n}$ be the equivalence classes under this relation for
some $n\leq k$.

Define $C_{i}:=\underset{f\in S_{i}}{\cup}L_{i}$ for each $i\in[n]$. We say
$C_{i}$ is an ${\cal N}$-heavy cluster iff

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

The following claim gives a tight error bound for approximating the true
signal $x^{*}(t)$ by the signal $x_{S^{*}}(t)$ whose frequencies are in heavy-
clusters. It improves the Claim 2.5 in [CKPS16].

######  Claim 12.12 (Approximation by heavy-clusters).

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

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

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

###### Proof.

Let $H$ be the filter function defined as in Definition 12.6.

Let

$\displaystyle
x_{\overline{{S^{*}}}}(t):=\underset{j\in[k]\backslash{S^{*}}}{\sum}v_{j}e^{2\pi\mathbf{i}f_{j}t}.$

Notice that $\|x^{*}-x_{S^{*}}\|_{T}^{2}=\|x_{\overline{{S^{*}}}}\|^{2}_{T}$.

By Property vi@ in Lemma 12.7 with setting $\varepsilon=\varepsilon/2$, let
$\varepsilon_{0}=\varepsilon/2$, we have

$\displaystyle(1-\varepsilon_{0})\cdot T\|x_{\overline{{S^{*}}}}\|_{T}^{2}=$
$\displaystyle~{}(1-\varepsilon_{0})\int_{0}^{T}|x_{\overline{{S^{*}}}}(t)|^{2}\mathrm{d}t$
$\displaystyle=$
$\displaystyle~{}(1-\varepsilon_{0})\int_{0}^{T}|x_{\overline{{S^{*}}}}(t)\cdot\mathrm{rect}_{T}(t)|^{2}\mathrm{d}t$
$\displaystyle\leq$
$\displaystyle~{}\int_{-\infty}^{+\infty}|x_{\overline{{S^{*}}}}(t)\cdot
H(t)\cdot\mathrm{rect}_{T}(t)|^{2}\mathrm{d}t,$ $\displaystyle\leq$
$\displaystyle~{}\int_{-\infty}^{+\infty}|x_{\overline{{S^{*}}}}(t)\cdot
H(t)|^{2}\mathrm{d}t,$

where the first step follows from the definition of the norm, the second step
follows from the definition of $\mathrm{rect}_{T}(t)=1,\forall t\in[0,T]$, the
third step follows from Lemma 12.7, the forth step follows from
$\mathrm{rect}_{T}(t)\leq 1$.

From Definition 12.11, we have

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

where the first step follows from Parseval’s theorem, the second step follows
from Definition 12.11, Property iv@ of Lemma 12.7, the definition of
${S^{*}}$, thus, $\mathrm{supp}(\widehat{x_{S^{*}}\cdot
H}(f))=C_{1}\cup\cdots\cup C_{l}$, $\mathrm{supp}(\widehat{x_{S^{*}}\cdot
H}(f))\cap\mathrm{supp}(\widehat{x_{\overline{{S^{*}}}}\cdot
H}(f)))=\emptyset$, the last step follows from Definition 12.11.

Overall, we have
$(1-\varepsilon_{0})\|x_{\overline{{S^{*}}}}\|^{2}_{T}\leq\mathcal{N}^{2}$.
Thus,
$\|x_{S^{*}}(t)-x^{*}(t)\|_{T}^{2}\leq(1-l/k)(1+\varepsilon)\mathcal{N}^{2}$.
∎

Due to the noisy observations, not all frequencies in heavy-clusters are
recoverable. Thus, we define the recoverable frequency as follows:

######  Definition 12.13 (Recoverable frequency).

A frequency $f$ is _$({\cal N}_{1},{\cal N}_{2})$ -recoverable_ if $f$ is in
an ${\cal N}_{1}$-heavy cluster $C$ that satisfies:

$\displaystyle\int_{C}|\widehat{x\cdot H}(f)|^{2}\geq T{\cal N}_{2}^{2}/k.$

The following lemma shows that most frequencies in the heavy-clusters are
actually recoverable.

######  Lemma 12.14 (Heavy-clusters are almost recoverable).

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}^{2}:=\|g\|_{T}^{2}+\delta\|x^{*}\|_{T}^{2}$. Let
$C_{1},\cdots,C_{l}$ are the $2\mathcal{N}$-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]$. Let $S\subset S^{*}$ be the set of $(2{\cal N},{\cal
N})$-recoverable frequencies.

Then we have that,

$\displaystyle\|x_{S}-x^{*}\|_{T}\leq(3-l/k+\varepsilon)\mathcal{N}.$

###### Proof.

If a cluster $C_{i}$ is $2{\cal N}$-heavy but not ${\cal N}$-recoverable, then
it holds that:

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

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

So,

$\displaystyle\int_{C_{i}}|\widehat{H\cdot g}(f)|^{2}\mathrm{d}f=$
$\displaystyle~{}\int_{C_{i}}|\widehat{H\cdot(x-x^{*})}(f)|^{2}\mathrm{d}f$
$\displaystyle\geq$ $\displaystyle~{}\left(\sqrt{\int_{C_{i}}|\widehat{H\cdot
x^{*}}(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}{4}\int_{C_{i}}|\widehat{H\cdot
x^{*}}(f)|^{2}\mathrm{d}f$ (41)

where the first step follows from $g(t)=x(t)-x^{*}(t)$, and the second step
follows from triangle inequality, the last step follows from Eq. (40).

Let $C^{\prime}:=\bigcup_{f_{j}\in S^{*}\backslash S}C_{j}$, i.e., the union
of heavy but not recoverable clusters. Then, we have

$\displaystyle\|\widehat{H\cdot g}\|_{2}^{2}\geq\sum_{C_{i}\in
C^{\prime}}\int_{C_{i}}|\widehat{H\cdot
g(f)}|^{2}\mathrm{d}f\geq\frac{1}{4}\sum_{C_{i}\in
C^{\prime}}\int_{C_{i}}|\widehat{H\cdot x^{*}}(f)|^{2}\mathrm{d}f$ (42)

where the first step follows from the definition of the norm and $C_{i}\cap
C_{j}=\emptyset,\forall i\neq j$, the second step follows from Eq. (41).

Then we have that

$\displaystyle T\|x_{S*\backslash S}\|_{T}^{2}\leq$
$\displaystyle~{}\frac{T}{1-\varepsilon/2}\|x_{S*\backslash S}\cdot
H\|_{T}^{2}$ $\displaystyle\leq$
$\displaystyle~{}(1+\varepsilon)\sum_{C_{i}\in
C^{\prime}}\int_{C_{i}}|\widehat{H\cdot x^{*}}(f)|^{2}\mathrm{d}f$
$\displaystyle\leq$ $\displaystyle~{}4(1+\varepsilon)\|\widehat{H\cdot
g}\|_{2}^{2}$ $\displaystyle=$ $\displaystyle~{}4(1+\varepsilon)T\|H\cdot
g\|_{T}^{2}$ $\displaystyle\leq$
$\displaystyle~{}4(1+\varepsilon)T\|g\|_{T}^{2}$ $\displaystyle\leq$
$\displaystyle~{}4(1+\varepsilon)T\mathcal{N}^{2}.$

where the first step follows from Property vi@ of $H$ in Lemma 12.7 (taking
$\varepsilon$ there to be $\varepsilon/2$), the second step follows from
$\varepsilon\in[0,1]$ and the definition of $C_{i}$, the third step follows
from Eq. (42), the forth step follows from $g(t)=0,\forall t\not\in[0,T]$, the
fifth step follows from Remark 12.8, the last step follows from the definition
of $\mathcal{N}^{2}$. Thus, we get that:

$\displaystyle\|x_{S*\backslash S}\|_{T}\leq(2-l/k+\varepsilon){\cal N},$ (43)

which follows from $\sqrt{1+\varepsilon}\leq 1+\varepsilon/2$.

Finally, we can conclude that

$\displaystyle\|x_{S}-x^{*}\|_{T}\leq$
$\displaystyle~{}\|x_{S}-x_{S^{*}}\|_{T}+\|x_{S^{*}}-x^{*}\|_{T}$
$\displaystyle=$ $\displaystyle~{}\|x_{S*\backslash
S}\|_{T}+\|x_{S^{*}}-x^{*}\|_{T}$ $\displaystyle\leq$
$\displaystyle~{}\|x_{S*\backslash S}\|_{T}+(1+\varepsilon)\mathcal{N}$
$\displaystyle\leq$ $\displaystyle~{}(3-l/k+2\varepsilon)\mathcal{N},$

where the first step follows from triangle inequality, the second step follows
from the definition of $x_{S*\backslash S}$, the third step follows from Claim
12.12, the last step follows from Eq. (43). The lemma follows by re-scaling
$\varepsilon$ to $\varepsilon/2$. ∎

###  12.4 $(9+\varepsilon)$-approximate Fourier interpolation algorithm

The goal of this section is to prove Theorem 12.20, which gives a Fourier
interpolation algorithm with approximation error $(9+\varepsilon)$. It
improves the constant (more than 1000) error algorithm in [CKPS16].

######  Claim 12.15 (Mixed Fourier-polynomial energy bound, [CKPS16]).

For any

$u(t)\in\mathrm{span}\left\\{e^{2\pi\mathbf{i}{f}_{i}t}\cdot
t^{j}~{}\bigg{|}~{}j\in\\{0,\cdots,d\\},i\in[k]\right\\},$

we have that

$\max_{t\in[0,T]}~{}|u(t)|^{2}\lesssim(kd)^{4}\log^{3}(kd)\cdot\|u\|^{2}_{T}$

######  Claim 12.16 (Condition number of Mixed Fourier-polynomial).

Let ${\cal F}$ is a linear function family as follows:

${\cal F}:=\mathrm{span}\left\\{e^{2\pi\mathbf{i}{f}_{i}t}\cdot
t^{j}~{}\bigg{|}~{}j\in\\{0,\cdots,d\\},i\in[k]\right\\},$

Then the condition number of $\mathrm{Uniform}[0,T]$ with respect to ${\cal
F}$ is as follows:

$K_{\mathrm{Uniform}[0,T]}:=\sup_{t\in[0,T]}\sup_{f\in{\mathcal{F}}}\frac{|f(t)|^{2}}{\|f\|_{T}^{2}}=O((kd)^{4}\log^{3}(kd))$

The following definition extends the well-balanced sampling procedure
(Definition 7.1) to high probability.

######  Definition 12.17 (($\varepsilon,\rho$)-well-balanced sampling
procedure).

Given a linear family $\mathcal{F}$ and underlying distribution $D$, let $P$
be a random sampling procedure that terminates in $m$ iterations ($m$ is not
necessarily fixed) and provides a coefficient $\alpha_{i}$ and a distribution
$D_{i}$ to sample $x_{i}\sim D_{i}$ in every iteration $i\in[m]$.

We say $P$ is an $\varepsilon$-WBSP if it satisfies the following two
properties:

  1. 1.

With probability $1-\rho$, for weight
$w_{i}=\alpha_{i}\cdot\frac{D(x_{i})}{D_{i}(x_{i})}$ of each $i\in[m]$,

$\sum_{i=1}^{m}w_{i}\cdot|h(x_{i})|^{2}\in\left[1-10\sqrt{\varepsilon},1+10\sqrt{\varepsilon}\right]\cdot\|h\|_{D}^{2}\quad\forall
h\in\mathcal{F}.$

  2. 2.

The coefficients always have $\sum_{i=1}^{m}\alpha_{i}\leq\frac{5}{4}$ and
$\alpha_{i}\cdot K_{\mathsf{IS},D_{i}}\leq\frac{\varepsilon}{2}$ for all
$i\in[m]$.

The following lemma is a generalization of Lemma 9.11, showing an
$(\varepsilon,\rho)$-WBSP for mixed Fourier-polynomial family.

######  Lemma 12.18 (WBSP for mixed Fourier-polynomial family).

Given any distribution $D^{\prime}$ with the same support of $D$ and any
$\varepsilon>0$, the random sampling procedure with
$m=O(\varepsilon^{-1}K_{\mathsf{IS},D^{\prime}}\log(d/\rho))$ i.i.d. random
samples from $D^{\prime}$ and coefficients $\alpha_{1}=\cdots=\alpha_{m}=1/m$
is an $(\varepsilon,\rho)$-WBSP.

###### Proof.

By Lemma 4.18 with setting $\varepsilon=\sqrt{\varepsilon}$, we have that, as
long as $m\geq O(\frac{1}{\varepsilon}\cdot
K_{\mathsf{IS},D^{\prime}}\log\frac{d}{\rho})$, then with probability
$1-\rho$,

$\displaystyle\|A^{*}A-I\|_{2}\leq\sqrt{\varepsilon}$

By Lemma 4.17, we have that, for every $h\in{\mathcal{F}}$,

$\displaystyle\sum_{j=1}^{s}w_{j}\cdot|h(x_{j})|^{2}\in[1\pm\varepsilon]\cdot\|h\|_{D}^{2},$

where $S$ is the $m$ i.i.d. random samples from $D^{\prime}$,
$w_{i}=\alpha_{i}D(x_{i})/D^{\prime}(x_{i})$.

Moreover, $\sum_{i=1}^{m}\alpha_{i}=1\leq 5/4$ and

$\displaystyle\alpha_{i}\cdot
K_{\mathsf{IS},D^{\prime}}=~{}\frac{K_{\mathsf{IS},D^{\prime}}}{m}\leq~{}\frac{\varepsilon}{\log(d/\rho)}\leq~{}{\varepsilon},$

where the first step follows from the definition of $\alpha_{i}$, the second
step follows from the definition of $m$, the third step follows from
$\log(d/\rho)>1$. ∎

Then, similar to Theorem 9.4, we can solve the Signal Estimation problem for
mixed Fourier-polynomial signals.

######  Lemma 12.19 (Mixed Fourier-polynomial signal estimation).

Given $d$-degree polynomials $P_{j}(t),j\in[k]$ and frequencies
$f_{j},j\in[k]$. Let
$x_{S}(t)=\sum_{j=1}^{k}P_{j}(t)\exp({2\pi\mathbf{i}f_{j}t})$, and let $g(t)$
denote the noise. Given observations of the form
$x(t):=x_{S}(t)+g^{\prime}(t)$ for arbitrary noise $g^{\prime}$ in time
duration $t\in[0,T]$.

Then, there is an algorithm such that

  * •

takes $O(\varepsilon^{-1}\mathrm{poly}(kd)\log(1/\rho))$ samples from $x(t)$,

  * •

runs $O(\varepsilon^{-1}\mathrm{poly}(kd)\log(1/\rho))$ time,

  * •

outputs $y(t)=\sum_{j=1}^{k}P^{\prime}_{j}(t)\exp({2\pi\mathbf{i}f_{j}t})$
with $d$-degree polynomial $P^{\prime}_{j}(t)$, such that with probability at
least $1-\rho$, we have

$\displaystyle\|y-x_{S}\|_{T}^{2}\leq(1+\varepsilon)\|g^{\prime}\|_{T}^{2}.$

###### Proof sketch.

The proof is almost the same as Theorem 9.4 where we follow the three-step
Fourier set-query framework. Claim 12.15 gives the energy bound for the family
of mixed Fourier-polynomial signals, which implies that uniformly sampling
$m=\widetilde{O}(\varepsilon^{-1}|L|^{4}d^{4})$ points in $[0,T]$ forms an
oblivious sketch for $x^{*}$. Moreover, by Lemma 12.18, we know that it is
also an $(\varepsilon,\rho)$-WBSP, which gives the error guarantee. Then, we
can obtain a mixed Fourier-polynomial signal $y(t)$ by solving a weighted
linear regression. ∎

Now, we are ready to prove the main result of this section, a
$(9+\varepsilon)$-approximate Fourier interpolation algorithm.

######  Theorem 12.20 (Fourier interpolation with
$(9+\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(7+\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,\log(1/\delta))\varepsilon^{-1.5}$-Fourier-
sparse signal.

###### Proof.

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

First, by Lemma 12.14, 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}\leq(3+O(\varepsilon))\mathcal{N}.$ (44)

Furthermore, each $f_{j}$ with $j\in S$ belongs to an $\mathcal{N}$-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}^{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}^{2}/k.$

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

By applying Theorem 12.35, there is an algorithm that outputs a set of
frequencies $L\subset\mathbb{R}$ such that, $|L|=O(k)$, 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}$, the last step
follows from interchanging the summations.

For each $\widetilde{f}_{i}\in L$, by Corollary 12.2 with
$x^{*}=x_{S_{f}},\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\delta\|x_{S_{f}}(t)\|_{T}$
(45)

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\|y^{\prime}(t)-\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\|_{T}\leq(1+\varepsilon)\|x(t)-\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)\|_{T}$ (46)

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}\leq\delta^{\prime}$ (47)

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)=\varepsilon^{-1.5}\mathrm{poly}(k,\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+o(1))\Big{\|}y-\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. (47))
$\displaystyle\leq$
$\displaystyle~{}(1+\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. (46))
$\displaystyle\leq$
$\displaystyle~{}(1+2\varepsilon)\|g\|_{T}+(2+\varepsilon)\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+2\varepsilon)\|g\|_{T}+(2+\varepsilon)\Big{\|}\sum_{\widetilde{f}_{i}\in
L}e^{2\pi\mathbf{i}\widetilde{f}_{i}t}P_{i}(t)-x_{S_{f}}\Big{\|}_{T}+(2+\varepsilon)\|x_{S_{f}}-x^{*}\|_{T}$
(Triangle inequality) $\displaystyle\leq$
$\displaystyle~{}(1+2\varepsilon)\|g\|_{T}+(2+\varepsilon)\delta\|x_{S_{f}}\|_{T}+(2+\varepsilon)\|x_{S_{f}}-x^{*}\|_{T}$
(Eq. (45)) $\displaystyle\leq$
$\displaystyle~{}(1+2\varepsilon)\|g\|_{T}+O(\delta)\|x^{*}\|_{T}+(2+\varepsilon)(1+\delta)\|x_{S_{f}}-x^{*}\|_{T}$
(Triangle inequality) $\displaystyle\leq$
$\displaystyle~{}(1+2\varepsilon)\|g\|_{T}+O(\delta)\|x^{*}\|_{T}+(2+\varepsilon)(1+\delta)(\|x_{S_{f}}-x_{S}\|_{T}+\|x_{S}-x^{*}\|_{T})$
(Triangle inequality) $\displaystyle\leq$
$\displaystyle~{}(1+2\varepsilon)\|g\|_{T}+O(\delta)\|x^{*}\|_{T}+(2+\varepsilon+O(\delta))(4+O(\varepsilon)){\cal
N}$ (Eq. (44) and Lemma 12.40) $\displaystyle=$
$\displaystyle~{}(1+2\varepsilon)\|g\|_{T}+O(\delta)\|x^{*}\|_{T}+(8+O(\varepsilon+\delta)){\cal
N},$

Since we take

$\mathcal{N}=\sqrt{\|g\|_{T}^{2}+\delta\|x^{*}\|_{T}^{2}}\leq\|g\|_{T}+\sqrt{\delta}\|x^{*}\|_{T},$

we have

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

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

∎

###  12.5 Sharper error control by signal-noise cancellation effect

In this section, we significantly improve the error analysis in Section 12.3.
Our key observation is the _signal-noise cancellation effect_ : if there is a
frequency $f^{*}$ in a ${\cal N}_{1}$-heavy cluster but not $({\cal
N}_{1},{\cal N}_{2})$-recoverable for some ${\cal N}_{2}<{\cal N}_{1}$, then
it indicates that the contribution of $f^{*}$ to the signal $x^{*}$’s energy
are cancelled out by the noise $g$.

In the following lemma, we improving Lemma 12.14 by considering $g$’s effect
in the gap between heavy-cluster signal and recoverable signal.

######  Lemma 12.21 (Sharper error bound for recoverable signal, an improved
version of Lemma 12.14).

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]$. Let $S\subset S^{*}$ be the set of $({\cal
N}_{1},\sqrt{\varepsilon_{2}}{\cal N}_{1})$-recoverable frequencies
(Definition 12.13).

Then we have that,

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

###### Proof.

Let $g^{\prime}(t):=g(t)+x^{*}(t)-x_{S^{*}}(t)=x(t)-x_{S^{*}}(t)$.

In order for cluster $C_{i}$ to be missed, we must have that