**footnotetext: These authors contributed equally to this work.

# Efficiently Computing Sparse Fourier Transforms of $q$-ary Functions

Yigit Efe Erginbas∗, Justin Singh Kang∗, Amirali Aghazadeh,
Kannan Ramchandran

###### Abstract

Fourier transformations of pseudo-Boolean functions are popular tools for
analyzing functions of binary sequences. Real-world functions often have
structures that manifest in a sparse Fourier transform, and previous works
have shown that under the assumption of sparsity the transform can be computed
efficiently. But what if we want to compute the Fourier transform of functions
defined over a $q$-ary alphabet? These types of functions arise naturally in
many areas including biology. A typical workaround is to encode the $q$-ary
sequence in binary, however, this approach is computationally inefficient and
fundamentally incompatible with the existing sparse Fourier transform
techniques. Herein, we develop a sparse Fourier transform algorithm
specifically for $q$-ary functions of length $n$ sequences, dubbed $q$-SFT,
which provably computes an $S$-sparse transform with vanishing error as
$q^{n}\rightarrow\infty$ in $O(Sn)$ function evaluations and $O(Sn^{2}\log q)$
computations, where $S=q^{n\delta}$ for some $\delta<1$. Under certain
assumptions, we show that for fixed $q$, a robust version of $q$-SFT has a
sample complexity of $O(Sn^{2})$ and a computational complexity of $O(Sn^{3})$
with the same asymptotic guarantees. We present numerical simulations on
synthetic and real-world RNA data, demonstrating the scalability of $q$-SFT to
massively high dimensional $q$-ary functions.

##  I Introduction

Pseudo-Boolean functions [1] are powerful tools for modeling systems across
many fields including computer science [2], biology [3] and game theory [4].
In many of these applications, the Fourier transform, also known as the Walsh-
Hadamard transform, plays an important role. In particular, a Pseudo-Boolean
function $f:\mathbb{Z}_{2}^{n}\rightarrow\mathbb{R}$ can be represented as a
real, multilinear polynomial in terms of its Fourier transform $F$, i.e.,

$f[\mathbf{m}]=\sum_{\mathbf{k}\in\mathbb{Z}_{2}^{n}}F[\mathbf{k}](-1)^{\left\langle\mathbf{m},\mathbf{k}\right\rangle},\;\;\mathbf{m}\in\mathbb{Z}_{2}^{n},$
(1)

where $N=2^{n}$ and $\mathbb{Z}_{2}=\\{0,1\\}$. The transform $F$ measures
interactions between subsets of coordinates in ${\bf k}$ and is often more
interpretable than $f$. In fact, Fourier techniques are now being used for
explaining deep neural networks in real-world problems [5, 6]. It is known
that $F$ can be computed in $O(N\log{N})$ computations using the seminal fast-
Fourier transform (FFT) algorithm. This exponential dependence in $n$ makes
computing $F$ impractical for even moderate values of $n$. In most
applications, however, $F$ has some exploitable low-dimensional structure. By
far the most commonly considered structure is sparsity of the Fourier
transform [7]. Compressed sensing theory shows that algorithms like LASSO [8]
achieve the optimal sample complexity of $O(S\log(N/S))$ in recovering an
$S$-sparse Fourier transform $F$ (i.e., a function with only $S$ non-zero
values). More recent _sparse Fourier transform_ algorithms [9, 10, 11, 12]
demonstrate that the sparsity in $F$ can be exploited even further to
significantly reduce the computational complexity of Fourier transforms. In
particular, it is shown that a Boolean $S$-sparse Fourier transform can be
computed in only $O(S\log^{2}N)=O(Sn^{2})$ time complexity [11].

Though Pseudo-Boolean functions are a complete model for functions of binary
sequences, in practice real data may involve $q$-ary sequences like DNA or
proteins, which are defined over a grammar in a $q$-ary alphabet with $q>2$:
$q=4$ for DNA, $q=20$ for proteins, and $q=4^{\ell}$ for the $\ell$-mer
representation of DNA. To address the large and important class of problems
with $q>2$, here we introduce $q$-SFT for computing an $S$-sparse $q$-ary
Fourier transform:

$F[\mathbf{k}]=\frac{1}{N}\sum_{\mathbf{m}\in\mathbb{Z}_{q}^{n}}f[\mathbf{m}]\omega^{-\left\langle\mathbf{m},\mathbf{k}\right\rangle},\;\;\mathbf{k}\in\mathbb{Z}_{q}^{n},\vspace{-2pt}$
(2)

where $\omega:=e^{j\frac{2\pi}{q}}$, $N=q^{n}$, $\mathbb{Z}_{q}$ denotes the
ring of integers modulo $q$, and $\mathbb{Z}_{q}^{n}$ denotes the module of
dimension $n$ over $\mathbb{Z}_{q}$. $q$-SFT has a sample complexity of
$O(Sn)$ and a computational complexity of $O(Sn^{2}\log q)$ in the noiseless
case. In the presence of noise, for any fixed $q\geq 2$ $q$-SFT has a sample
complexity of $O(Sn^{2})$ in $O(Sn^{3})$ computations. In both cases, this is
a significant improvement over the existing approaches. We achieve this result
via subsampling over affine spaces of the module $\mathbb{Z}_{q}^{n}$ and
peeling-based erasure decoding [13].

Our approach to design a solution specific to $q$-ary sequences is a sharp
departure from the common workaround in machine learning: _One-hot encoding_
converts a $q$-ary sequence of length $n$ to a interpretable binary sequence
of length $qn$ [14]. The downside of this approach is that the sequence length
grows linearly in $q$, and thus the computational complexity of algorithms
built on this approach is also at least linear in $q$. Furthermore, since the
encoding is injective and non-surjective, there are many length $qn$ binary
sequences that do not correspond to a $q$-ary sequence. For example, the all
$0$s sequence is a valid $qn$ binary sequence but has no corresponding $q$-ary
sequence. This _sampling incompatibility_ over linear spaces is fundamentally
at odds with most sparse Fourier algorithms. Other approaches, such as binary
coding of a $q$-ary sequence to one of length
$\left\lceil\log_{2}q\right\rceil n$, suffer a similar sampling
incompatibility issue when $q$ is not a power of $2$, besides loosing the
interpretability of one-hot encoding.

The potential wide range of applications for efficient $q$-ary Fourier
transforms is a key motivation of this work. For example, in biological
applications $F$ is used to identify which amino acids, or specific subsets of
amino acids are responsible for certain functions [5, 15], but even in these
cases computation remains a bottleneck. In addition to this manuscript, we
also release the associated software***https://github.com/basics-lab/qsft,
which will enable computation of $q$-ary Fourier transforms at scales never
before seen.

###  I-A Contribution

This paper studies the sparse Fourier transform of a $q$-ary function. We
summarize the main contributions below:

  * •

We develop $q$-SFT, the first algorithm for computing the Fourier transform of
a $q$-ary function with sample complexity $O(Sn)$ and computational complexity
$(Sn^{2}\log q)$ in the presence of no additive noise.

  * •

Noise robustness is critical for practical use, thus we also present a noise-
robust version of $q$-SFT that for fixed $q>1$ has sample complexity of
$O(Sn)$ at a cost of $O(nq^{n})$ computational complexity. Alternatively, by
increasing the sample complexity to $O(Sn^{2})$, we show a computational
complexity of $O(Sn^{3})$ can be achieved.

  * •

Using systematic simulations on sparse $q$-ary functions, we show that $q$-SFT
performs well and is significantly more efficient than LASSO, allowing for
computation at a massive scale.

  * •

Numerical experiments also show $q$-SFT performs well on real world data where
the assumptions related to sparsity may not exactly hold.

###  I-B Related Work

At their core, sparse Fourier algorithms are built on the principles of
sampling and aliasing in signal processing. In [11, 12], which deal with the
case of $q=2$, a pseudo-Boolean function is subsampled multiple times,
according to an affine subsampling pattern. This leads to destructive
aliasing. However, since the Fourier transform is sparse, and the affine
subsampling method makes the aliasing predictable, a peeling decoding
technique can be used to undo the aliasing and recover the original function.
Our algorithm in Section III and IV relies on similar techniques and shows
that similar guarantees can be derived for the case of $q>2$. In [12] the case
where $f$ has degree at most $t$ is also considered, and a sample complexity
of $O(tS\log n)$ is achieved. In [16] the bounded degree problem is connected
to perfect codes, however, the proposed algorithm is most efficient when
Fourier coefficients are dense up to $t$th order. A combinatorial approach to
computing sparse Fourier transforms can be found in [17].

There are other works that consider sparse Fourier transforms in other
settings. Of note, [18, 19] both offer practical approaches for computing the
sparse DFT of a signal. Furthermore, since the Fourier transform is a linear
operation, computing the sparse Fourier transform may also be viewed as a
linear inverse problem, and the existing approaches to _compressed sensing_
[20, 21] and _group testing_ [22] are also relevant. In particular, LASSO [8]
and AMP [23, 24] can be used to solve for $F$ in (2), but the computational
complexity in both cases is exponential in $n$. We also note that decoding
cyclic Reed-Solomon codes [25] is related to sparse Fourier transforms over
finite fields.

##  II Problem Statement

This work addresses the problem of computing the $S$-sparse Fourier transform
$F$ of a $q$-ary function $f$ as in (2). We consider a oracle model that takes
in an index $\mathbf{m}\in\mathbb{Z}_{q}^{n}$, and outputs a function
evaluation:

$\textrm{Oracle}:\mathbf{m}\longrightarrow
f[\mathbf{m}]+v,\;\;v\sim\mathcal{CN}(0,\sigma^{2}),$ (3)

where $v$ is sampled i.i.d. from a complex Gaussian distribution (i.e., noise)
for each query. _Sample Complexity_ denotes the number of oracle queries. The
following assumptions are used to establish our theoretical guarantees.

######  Assumption 1.

Let $F:\mathbb{Z}_{q}^{n}\to\mathbb{C}$ be a Fourier transform with support
$\mathcal{S}:=\mathrm{supp}(F)$. To facilitate our analysis throughout this
paper, we make the following assumptions:

  1. 1.

Each element in the support set $\mathcal{S}$ is chosen independently and
uniformly at random from $\mathbb{Z}_{q}^{n}$.

  2. 2.

The sparsity $S=|\mathcal{S}|=O(N^{\delta})$ is sub-linear in $N$ for some
$0<\delta<1$.

######  Assumption 2.

  1. 1.

Each coefficient $F[{\bf k}]$ for ${\bf k}\in\mathcal{S}$ is chosen from a
finite set
$\mathcal{X}:=\\{\rho,\rho\phi,\rho\phi^{2},\dots,\rho\phi^{\kappa-1}\\}$
uniformly at random, where $\phi=e^{j2\pi/\kappa}$ and $\kappa$ is a constant.

  2. 2.

The signal-to-noise ratio (SNR) is defined as

$\mathrm{SNR}=\frac{\|f\|^{2}}{N\sigma^{2}}=\frac{\|F\|^{2}}{\sigma^{2}}=\frac{S\rho^{2}}{\sigma^{2}}$
(4)

and is assumed to be an arbitrary constant value, i.e. $\rho$ scales with
$\sqrt{1/S}$.

##  III Algorithm: Noiseless

We begin by treating the case where samples of $f$ are obtained as in (3) with
$\sigma^{2}=0$. Algorithm 1 describes the complete procedure, divided into
three parts. In the first part, the function is subsampled, and the transform
of the subsampled signal is computed. The key innovation to deal with $q>2$ is
to consider subsampling over an affine space in the module
$\mathbb{Z}^{n}_{q}$. We show that if we subsample in this way the aliasing
patterns are described by an affine function over the module. In the second
part, the subsampled transforms are processed, and singletons are identified
by using the complex-valued transform coefficients to create a linear equation
for a nonzero coefficient $\mathbf{k}$, again over the module. In the final
phase, a peeling decoding process enables us to create more singletons, by
subtracting the value of the originally identified singletons. Under
assumptions, Theorem 1 provides convergence guarantees.

Algorithm 1 $q$-SFT

1:$P$, $C$, $b<n$, $\mathbf{M}_{c}\in\mathbb{Z}_{q}^{n\times b}$,
$\mathbf{D}_{c}\in\mathbb{Z}_{q}^{P\times n}$ for $c\in[C]$.

2:$\hat{F}[\boldsymbol{\mathbf{k}}]\leftarrow
0\;\;\forall\boldsymbol{\mathbf{k}}$

3:for $c\in[C]$ do $\triangleright$ Sub-Sampling Phase

4: for $p\in[P]$ do

5: Compute
$U_{c,p}[\mathbf{j}]\;\;\forall\boldsymbol{\mathbf{j}}\in\mathbb{Z}_{q}^{b}$

6: end for

7: Compute
$\mathrm{Type}\left({\boldsymbol{\mathbf{U}}_{c}[\boldsymbol{\mathbf{j}}]}\right)\;\;\forall\boldsymbol{\mathbf{j}}\in\mathbb{Z}_{q}^{b}$

8:end for

9:$\mathcal{K}=\emptyset$;
$\mathcal{S}=\left\\{(c,\boldsymbol{\mathbf{j}},\boldsymbol{\mathbf{k}},v):\mathrm{Type}\left({\boldsymbol{\mathbf{U}}_{c}[\boldsymbol{\mathbf{j}}]}\right)=\mathcal{H}_{S}(\boldsymbol{\mathbf{k}},v)\right\\}$

10:while $\left\lvert{\mathcal{S}}\right\rvert>0$ do $\triangleright$ Peeling
Phase

11: for $(c,\boldsymbol{\mathbf{j}},\boldsymbol{\mathbf{k}},v)\in\mathcal{S}$,
with $\boldsymbol{\mathbf{k}}\notin\mathcal{K}$ do

12: $\hat{F}[\boldsymbol{\mathbf{k}}]\leftarrow v$;
$\mathcal{K}\leftarrow\mathcal{K}\cup\\{\boldsymbol{\mathbf{k}}\\}$

13: for $c^{\prime}\in[C]$ do

14:
${\boldsymbol{\mathbf{U}}_{c^{\prime}}[\boldsymbol{\mathbf{M}}_{c^{\prime}}^{\textrm{T}}\boldsymbol{\mathbf{k}}]}\leftarrow{\boldsymbol{\mathbf{U}}_{c^{\prime}}[\boldsymbol{\mathbf{M}}_{c^{\prime}}^{\textrm{T}}\boldsymbol{\mathbf{k}}]}-\hat{F}[\boldsymbol{\mathbf{k}}]\omega^{\boldsymbol{\mathbf{D}}_{c^{\prime}}\boldsymbol{\mathbf{k}}}$

15: Recompute
$\mathrm{Type}\left({\boldsymbol{\mathbf{U}}_{c^{\prime}}[\boldsymbol{\mathbf{j}}]}\right)$

16: end for

17: end for

18: Update $\mathcal{S}$

19:end while

20:Fourier Transform Estimate $\hat{F}$

###  III-A Subsampling and Aliasing

We construct $C$ subsampling groups, each characterized by a subsampling
matrix $\boldsymbol{\mathbf{M}}_{c}\in\mathbb{Z}_{q}^{n\times b}$ defining a
linear space and a set of $P$ offsets
$\boldsymbol{\mathbf{d}}_{c,p}\in\mathbb{Z}_{q}^{n}$ for $p\in[P]$ for a total
of $PB$ oracle queries with $B:=q^{b}$. For each $c,p$ we compute:

$U_{c,p}[\boldsymbol{\mathbf{j}}]=\frac{1}{B}\sum_{\boldsymbol{\ell}\in\mathbb{Z}_{q}^{b}}f[\boldsymbol{\mathbf{M}}_{c}\boldsymbol{\ell}+\boldsymbol{\mathbf{d}}_{c,p}]\omega^{-\langle\boldsymbol{\mathbf{j}},\boldsymbol{\ell}\rangle},$
(5)

for all $\boldsymbol{\mathbf{j}}\in\mathbb{Z}_{q}^{b}$. In Appendix -B, we
show that

$U_{c,p}[\boldsymbol{\mathbf{j}}]=\sum_{\boldsymbol{\mathbf{k}}\;:\;\boldsymbol{\mathbf{M}}_{c}^{\textrm{T}}\boldsymbol{\mathbf{k}}=\boldsymbol{\mathbf{j}}}F[\boldsymbol{\mathbf{k}}]\omega^{\langle\boldsymbol{\mathbf{d}}_{c,p},\boldsymbol{\mathbf{k}}\rangle},$
(6)

and thus the coefficients $U_{c,p}[\boldsymbol{\mathbf{j}}]$ are aliased
versions of the coefficients $F[\boldsymbol{\mathbf{k}}]$. It can be observed
that the aliasing pattern is invariant with respect to the offsets
$\boldsymbol{\mathbf{d}}_{c,p}$ used in subsampling. Therefore, we can group
the observations according to their aliasing pattern to write
$\boldsymbol{\mathbf{U}}_{c}[\boldsymbol{\mathbf{j}}]=[\dots,U_{c,p}[\boldsymbol{\mathbf{j}}],\dots]^{\textrm{T}}$
by stacking the $\boldsymbol{\mathbf{j}}$th coefficient associated with all
the offsets. Then the aliasing pattern for the coefficients can be written as

$\boldsymbol{\mathbf{U}}_{c}[\boldsymbol{\mathbf{j}}]=\sum_{\boldsymbol{\mathbf{k}}\;:\;\boldsymbol{\mathbf{M}}_{c}^{\textrm{T}}\boldsymbol{\mathbf{k}}=\boldsymbol{\mathbf{j}}}F[\boldsymbol{\mathbf{k}}]\omega^{\boldsymbol{\mathbf{D}}_{c}\boldsymbol{\mathbf{k}}},$
(7)

where $\omega^{(\cdot)}$ is the element-wise exponentiation operator.

###  III-B Bin Detection

Each observation vector $\boldsymbol{\mathbf{U}}_{c}[\boldsymbol{\mathbf{j}}]$
in (7) is a linear combination of the unknown coefficients. The goal of bin
detection is to identify which
$\boldsymbol{\mathbf{U}}_{c}[\boldsymbol{\mathbf{j}}]$ correspond to singleton
bins, and for what value $\boldsymbol{\mathbf{k}}$ that singleton corresponds
to. To do so, define

  1. 1.

$\mathrm{Type}\left({\boldsymbol{\mathbf{U}}_{c}[\boldsymbol{\mathbf{j}}]}\right)=\mathcal{H}_{Z}$
denotes a _zero-ton_ , for which there does not exist
$F[\boldsymbol{\mathbf{k}}]\neq 0$ such that
$\boldsymbol{\mathbf{M}}_{c}^{\textrm{T}}\boldsymbol{\mathbf{k}}=\boldsymbol{\mathbf{j}}$.

  2. 2.

$\mathrm{Type}\left({\boldsymbol{\mathbf{U}}_{c}[\boldsymbol{\mathbf{j}}]}\right)=\mathcal{H}_{S}(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}])$
denotes a _singleton_ with only one $\boldsymbol{\mathbf{k}}$ with
$F[\boldsymbol{\mathbf{k}}]\neq 0$ such that
$\boldsymbol{\mathbf{M}}_{c}^{\textrm{T}}\boldsymbol{\mathbf{k}}=\boldsymbol{\mathbf{j}}$.

  3. 3.

$\mathrm{Type}\left({\boldsymbol{\mathbf{U}}_{c}[\boldsymbol{\mathbf{j}}]}\right)=\mathcal{H}_{M}$
denotes a _multi-ton_ for which there exists more than one
$F[\boldsymbol{\mathbf{k}}]\neq 0$ such that
$\boldsymbol{\mathbf{M}}_{c}^{\textrm{T}}\boldsymbol{\mathbf{k}}=\boldsymbol{\mathbf{j}}$.

We use the following rule to compute the bin type:

$\mathrm{Type}\left({\boldsymbol{\mathbf{U}}_{c}[\boldsymbol{\mathbf{j}}]}\right)=\begin{cases}\mathcal{H}_{Z},&\boldsymbol{\mathbf{U}}_{c}[\boldsymbol{\mathbf{j}}]=\boldsymbol{\mathbf{0}}\\\
\mathcal{H}_{M},&\exists
p\in[P]:\left\lvert{\frac{U_{c,p}[\boldsymbol{\mathbf{j}}]}{U_{c,1}[\boldsymbol{\mathbf{j}}]}}\right\rvert\neq
1\\\
\mathcal{H}_{S}(\boldsymbol{\mathbf{k}},X[\boldsymbol{\mathbf{k}}]),&\text{else.}\end{cases}$
(8)

When $\boldsymbol{\mathbf{U}}_{c}[\boldsymbol{\mathbf{j}}]$ is a singleton, we
must determine the values
$(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}])$. Note that each
singleton bin satisfies
$U_{c,p}[\boldsymbol{\mathbf{j}}]=F[\boldsymbol{\mathbf{k}}]\omega^{\langle\boldsymbol{\mathbf{d}}_{c,p},\boldsymbol{\mathbf{k}}\rangle}$
and hence we need to get rid of $F[\boldsymbol{\mathbf{k}}]$ to identify
$\boldsymbol{\mathbf{k}}$. To achieve this, in addition to the offset matrix
$\boldsymbol{\mathbf{D}}_{c}$, we choose a fixed delay
$\boldsymbol{\mathbf{d}}_{c,0}=\boldsymbol{\mathbf{0}}$ such that
$U_{c,0}[\boldsymbol{\mathbf{j}}]=F[\boldsymbol{\mathbf{k}}]$. Using these
observations, we can write the following set of linear equations in
$\boldsymbol{\mathbf{k}}$:

$\begin{bmatrix}\text{arg}_{q}[U_{c,1}[\boldsymbol{\mathbf{j}}]/U_{c,0}[\boldsymbol{\mathbf{j}}]]\\\
\vdots\\\
\text{arg}_{q}[U_{c,P}[\boldsymbol{\mathbf{j}}]/U_{c,0}[\boldsymbol{\mathbf{j}}]]\\\
\end{bmatrix}=\boldsymbol{\mathbf{D}}_{c}\boldsymbol{\mathbf{k}}.$ (9)

where $\text{arg}_{q}:\mathbb{C}\to\mathbb{Z}_{q}$ is the $q$-quantization of
the argument of a complex number defined as

$\text{arg}_{q}(z):=\left\lfloor\frac{q}{2\pi}\text{arg}(ze^{j\pi/q})\right\rfloor.$
(10)

If we choose $\boldsymbol{\mathbf{D}}_{c}=\boldsymbol{\mathbf{I}}_{n}$, then
$\boldsymbol{\mathbf{k}}$ can be obtained directly from (9) and the value of
the coefficient can be obtained as
$F[\boldsymbol{\mathbf{k}}]=U_{c,0}[\boldsymbol{\mathbf{j}}]$. If we have
additional information about $\mathbf{k}$, we can further reduce the number of
rows in $\boldsymbol{\mathbf{D}}_{c}$ required to recover
$\boldsymbol{\mathbf{k}}$. In particular, if $f$ has degree no greater than
$t$, i.e., $\left\lVert{\boldsymbol{\mathbf{k}}}\right\rVert_{0}>t\implies
F[\boldsymbol{\mathbf{k}}]=0$, we can prove the following result.

######  Proposition 1.

For any prime $q$ and $\boldsymbol{\mathbf{k}}\in\mathbb{Z}_{q}^{n}$ such that
$\left\lVert{\boldsymbol{\mathbf{k}}}\right\rVert_{0}\leq t$ there exists a
$\boldsymbol{\mathbf{D}}_{c}\in\mathbb{Z}_{q}^{P\times n}$ with
$P=2t\left\lceil\log_{q}(n)\right\rceil$ such that $\boldsymbol{\mathbf{k}}$
can be exactly recovered from
$\boldsymbol{\mathbf{D}}_{c}\boldsymbol{\mathbf{k}}$.

As a final note, we point out that Proposition 1 can be used to significantly
reduce the constant factor in [12] when $q=2$.

###  III-C Peeling Decoder

Once we have determined the bin detection procedure, the final step is the use
of a peeling decoder. Algorithm 1 describes the procedure in detail. It is
analogous to decoding a code over a bipartite graph, where the variable nodes
are the non-zero $F[\boldsymbol{\mathbf{k}}]$ and the check nodes are
$U_{c}[\boldsymbol{\mathbf{j}}]$, respectively. There is an edge between
$\boldsymbol{\mathbf{U}}_{c}[\boldsymbol{\mathbf{j}}]$ and
$F[\boldsymbol{\mathbf{k}}]$ only if
$\boldsymbol{\mathbf{M}}_{c}^{\textrm{T}}\boldsymbol{\mathbf{k}}=\boldsymbol{\mathbf{j}}$.
After sub-sampling, the singletons are identified, and their values are
subtracted from the $\boldsymbol{\mathbf{U}}_{c}$ values that they are
connected to. This can be thought of as “peeling" an edge of the bipartite
graph. With the careful choice of parameters, we can prove the following
performance guarantee.

Figure 1: Bipartite graph representation of the peeling phase. Red edges
correspond to singletons. These edges can be “peeled” from the graph and the
value of the variable node that they are connected to can be determined. Then
the blue edges can also be removed, revealing more singletons. This process
iterates until either all edges have been peeled, or no singletons remain.

######  Theorem 1 (Noiseless Peeling Decoder Performance).

Consider a $q$-ary function $f$ as (2) satisfying Assumption 1. For inputs
$C=O(1)$, $P=n$, $q^{b}=O(S)$, $\boldsymbol{\mathbf{D}}_{c}=\mathbf{I}_{n}$,
there exist some $\boldsymbol{\mathbf{M}}_{c}$ such that the output q-SFT is
exactly $F$ with probability at least $1-O(1/S)$. With these inputs q-SFT
requires $O(Sn)$ samples and $O(Sn^{2}\log q)$ computations.

###### Proof.

See Appendix -C. ∎

##  IV Algorithm: Noise Robust

The key to robustness is changing the bin detection scheme of Section III-B to
account for noise by subsampling carefully. We have seen that the offset
signature $\omega^{\boldsymbol{\mathbf{D}}\boldsymbol{\mathbf{k}}}$ is the key
to decoding the unknown pair
$(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}])$. Denoting
$\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}=\omega^{\boldsymbol{\mathbf{D}}\boldsymbol{\mathbf{k}}}$,
let
$\boldsymbol{\mathbf{S}}=[\dotsc,\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}},\dotsc]$
be the offset signatures associated with offsets $\boldsymbol{\mathbf{D}}$.
Then, in the presence of noise the bin observation vector
$\boldsymbol{\mathbf{U}}$ ***For simplicity in this section, we drop the group
index $c$ and bin index $\boldsymbol{\mathbf{j}}$ when we mention bin
observations, e.g. we write $\boldsymbol{\mathbf{U}}$ to denote
$\boldsymbol{\mathbf{U}}_{c}[\boldsymbol{\mathbf{j}}]$.  can be written as
$\boldsymbol{\mathbf{U}}=\boldsymbol{\mathbf{S}}\boldsymbol{\mathbf{\alpha}}+\boldsymbol{\mathbf{W}}$
for some sparse vector
$\boldsymbol{\mathbf{\alpha}}=[\dots,\alpha[\boldsymbol{\mathbf{k}}],\dots]^{\mathrm{T}}$
such that $\alpha[\boldsymbol{\mathbf{k}}]=F[\boldsymbol{\mathbf{k}}]$ if
$\boldsymbol{\mathbf{M}}^{\mathrm{T}}\boldsymbol{\mathbf{k}}=\boldsymbol{\mathbf{j}}$
and $\alpha[\boldsymbol{\mathbf{k}}]=0$ otherwise. In the case of single-tons,
$\boldsymbol{\mathbf{\alpha}}$ is 1-sparse and therefore
$\boldsymbol{\mathbf{U}}$ can be regarded as the noise-corrupted version of
some code word from the codebook $\boldsymbol{\mathbf{S}}$. Further, it can be
shown that $\boldsymbol{\mathbf{W}}$ has multivariate complex Gaussian
distribution with zero mean and covariance $\nu^{2}\boldsymbol{\mathbf{I}}$
where $\nu^{2}:=\sigma^{2}/B$.

###  IV-A Near-linear Time Robust Bin Detection

The near-linear (in $N$) time bin identification scheme uses $P$ random
offsets $\boldsymbol{\mathbf{d}}_{p}$ for $p\in[P]$ chosen independently and
uniformly at random over $\mathbb{Z}_{q}^{n}$. For some $\gamma\in(0,1)$,
detection is performed by proceeding with the following steps.

  1. 1.

Zero-ton verification:  We first rule out zero-tons. We declare
$\mathrm{Type}\left({\boldsymbol{\mathbf{U}}}\right)=\mathcal{H}_{Z}$ if
$\frac{1}{P}\|\boldsymbol{\mathbf{U}}\|^{2}\leq(1+\gamma)\nu^{2}.$

  2. 2.

Single-ton search:  The next step is to estimate
$(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}])$ assuming that bin
$\boldsymbol{\mathbf{j}}$ is a singleton. We compute the Maximum Likelihood
Estimate (MLE) of $\boldsymbol{\mathbf{k}}$, which involves a search over the
$N/B=q^{n-b}$ possible values of $\boldsymbol{\mathbf{k}}$ that satisfy
$\boldsymbol{\mathbf{M}}_{c}^{\textrm{T}}\boldsymbol{\mathbf{k}}=\boldsymbol{\mathbf{j}}$.
For each location $\boldsymbol{\mathbf{k}}$, we write MLE of the single-ton
coefficient as
$\widehat{\alpha}[\boldsymbol{\mathbf{k}}]=\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}^{\textrm{T}}\boldsymbol{\mathbf{U}}/P$,
thus

$\widehat{\boldsymbol{\mathbf{k}}}=\operatorname*{arg\,min}_{\boldsymbol{\mathbf{k}}\;:\;\boldsymbol{\mathbf{M}}_{c}^{\textrm{T}}\boldsymbol{\mathbf{k}}=\boldsymbol{\mathbf{j}}}\|\boldsymbol{\mathbf{U}}-\widehat{\alpha}[\boldsymbol{\mathbf{k}}]\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}\|^{2}.$
(11)

Given that $F$ satisfies Assumption 2, we estimate the value of the
coefficient corresponding to $\widehat{\boldsymbol{\mathbf{k}}}$ as

$\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}]=\operatorname*{arg\,min}_{\alpha\in\mathcal{X}}\|\alpha-\boldsymbol{\mathbf{s}}_{\widehat{\boldsymbol{\mathbf{k}}}}^{\textrm{T}}\boldsymbol{\mathbf{U}}/P\|.$
(12)

  3. 3.

Singleton verification:  This step confirms whether the bin with estimated
singleton pair
$(\widehat{\boldsymbol{\mathbf{k}}},\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}])$
is a singleton via a residual test. We declare
$\mathrm{Type}\left({\boldsymbol{\mathbf{U}}}\right)=\mathcal{H}_{S}(\widehat{\boldsymbol{\mathbf{k}}},\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}])$
if

$\frac{1}{P}\left\lVert{\boldsymbol{\mathbf{U}}-\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}]\boldsymbol{\mathbf{s}}_{\widehat{\boldsymbol{\mathbf{k}}}}}\right\rVert^{2}\leq(1+\gamma)\nu^{2}.$
(13)

Otherwise, we declare
$\mathrm{Type}\left({\boldsymbol{\mathbf{U}}}\right)=\mathcal{H}_{M}$.

###  IV-B Sub-linear Time Robust Bin Detection

The design described in the previous section requires an exhaustive search due
to a lack of structure in random offsets. In order to overcome this bottleneck
in computational complexity, we design offsets that enable symbol-by-symbol
recovery of the singleton index $\boldsymbol{\mathbf{k}}$. We let $P=P_{1}n$
and generate $P_{1}$ random offsets $\boldsymbol{\mathbf{d}}_{p}$ for
$p\in[P_{1}]$ chosen independently and uniformly at random over
$\mathbb{Z}_{q}^{n}$. We continue to perform zero-ton and singleton
verification steps using this set of $P_{1}$ random offsets as in the previous
section. However, to achieve sub-linear time for the single-ton search step,
we generate $n$ modulated offsets $\boldsymbol{\mathbf{d}}_{p,r}$ for each
$p\in[P_{1}]$ such that

$\boldsymbol{\mathbf{d}}_{p}\oplus_{q}\boldsymbol{\mathbf{e}}_{r}=\boldsymbol{\mathbf{d}}_{p,r},\quad\forall
r\in[n]$ (14)

where $\boldsymbol{\mathbf{e}}_{r}$ is the $r$-th column of the identity
matrix. Given these offsets, we can identify the $r$-th symbol of
$\boldsymbol{\mathbf{k}}$ by jointly considering the observations associated
with offsets $\\{\boldsymbol{\mathbf{d}}_{p,r}\\}_{p\in P_{1}}$. In
particular, the observations satisfy the following proposition.

######  Proposition 2.

Given a single-ton bin $(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}])$,
the $q$-quantized argument of the ratio of observations

$U_{p}=F[\boldsymbol{\mathbf{k}}]\omega^{\langle\boldsymbol{\mathbf{d}}_{p},\boldsymbol{\mathbf{k}}\rangle}+W_{p},\;\;U_{p,r}=F[\boldsymbol{\mathbf{k}}]\omega^{\langle\boldsymbol{\mathbf{d}}_{p,r},\boldsymbol{\mathbf{k}}\rangle}+W_{p,r}$
(15)

satisfies
$\text{arg}_{q}[U_{p,r}/U_{p}]=\langle\boldsymbol{\mathbf{e}}_{r},\boldsymbol{\mathbf{k}}\rangle\oplus_{q}Z_{p,r}$
where $Z_{p,r}$ is a random variable over $\mathbb{Z}_{q}$ with
$p_{i}:=\mathbb{P}(Z_{p,r}=i)$. The distribution satisfies $p_{i}<p_{0}$ for
all $i\neq 0$ and $\sum_{i\neq
0}p_{i}\leq\mathbb{P}_{e}:=2e^{-\frac{\zeta}{2}\text{SNR}}$ for
$\zeta:=\eta\sin^{2}{(\pi/2q)}$.

###### Proof.

See Appendix -D ∎

Based on this observation, we can apply a majority test to estimate $r$-th
entry of $\boldsymbol{\mathbf{k}}$ as

$\hat{k}[r]=\arg\max_{a\in\mathbb{Z}_{q}}\sum_{p\in[P_{1}]}\mathbb{1}\\{a=\text{arg}_{q}[U_{p,r}/U_{p}]\\}$
(16)

Then, using the estimation $\widehat{\boldsymbol{\mathbf{k}}}$ of the index,
the estimation for the value of the coefficient is obtained as in (12).

######  Theorem 2 (Robust Peeling Decoder Performance).

Consider a $q$-ary function $f$ as (2) satisfying Assumption 1 and 2. For
inputs $C=O(1)$, $P=n$, $q^{b}=O(S)$, $\boldsymbol{\mathbf{D}}_{c}$ chosen
uniformly at random over $\mathbb{Z}_{q}^{P\times n}$, there exist some
$\boldsymbol{\mathbf{M}}_{c}$ such that the output q-SFT is exactly $F$ with
probability at least $1-O(1/S)$. With these inputs q-SFT requires $O(Sn)$
samples and $O(nq^{n})$ computations as $n$ grows with fixed $q$. If instead,
we have $P=n^{2}$ and $\boldsymbol{\mathbf{D}}_{c}$ chosen as in (14), the
same result holds with $O(Sn^{2})$ samples and $O(Sn^{3})$ computations as $n$
grows.

###### Proof.

See Appendix -E. The ideas are similar to Theorem 1, but it requires the use
of Proposition 2 to deal with noise. ∎

##  V Numerical Experiments

In this section, we provide numerical experiments that showcases the
performance of $q$-SFT in practice. In addition to studying the algorithm’s
performance in recovering synthetically generated signals that are sparse in
the Fourier transform domain, we discuss the problem of recovering the mean
free energy values of RNA given its sequence. We consider the following
simulation setting. For given parameters $q$ and $n$, we synthetically
generate a signal $f$ such that its $q$-ary Fourier transform $F$ is
$S$-sparse and $\mathcal{S}=\mathrm{supp}(F)$ chosen uniformly at random over
$\mathbb{Z}_{q}^{n}$ with values

$F[\mathbf{k}]=\begin{cases}V[\mathbf{k}]e^{-j\Omega[\mathbf{k}]},&\text{if
}\mathbf{k}\in\mathcal{S}\\\ 0&\text{otherwise}.\end{cases}$ (17)

where $V[\mathbf{k}]\in[\rho_{\mathrm{min}},\rho_{\mathrm{max}}]$ are
independent random variables and $\Omega[\mathbf{k}]$ are independent uniform
random variables over $[0,2\pi)$. To demonstrate the robust recovery
performance of $q$-SFT in the presence of noise, we assume access to noisy
observations as in (3). Note that our theoretical results for robust recovery
are given under Assumption 2 which corresponds to having
$\rho_{\mathrm{min}}=\rho_{\mathrm{max}}=\rho$ and $\Omega[\mathbf{k}]$ taking
values over a finite set of size $\kappa$, however, we consider a more general
scenario to demonstrate that our algorithm can achieve robust recovery in more
general settings.

We measure the accuracy of the outputs using the normalized mean-squared error
(NMSE) metric defined as

$\mathrm{NMSE}=\frac{\|\widehat{F}-F\|^{2}}{\|F\|^{2}}=\frac{\|\widehat{f}-f\|^{2}}{\|f\|^{2}}.$
(18)

Fig. 2(a) and 2(b) compare $q$-SFT with LASSO in terms of the number of
samples and runtime. To implement LASSO in this complex-valued problem, we
consider group regularization [26] followed by ridge regression refinement
[27]. We set $q=3$, $\rho_{\mathrm{min}}=1$, $\rho_{\mathrm{max}}=5$, $S=100$
and $\sigma^{2}$ such that SNR is fixed at 10dB. For $q$-SFT, we vary hyper-
parameters $b$, $C$, and $P$ such that each combination results in a different
number of samples used. Similarly, we set the number of uniformly chosen
samples over $\mathbb{Z}_{q}^{n}$ provided to LASSO to compare its performance
with $q$-SFT at a given sample complexity. LASSO is successful in recovering
Fourier coefficients for small problems, but Fig. 2(b) indicates that
$q$-SFT’s runtime scales linearly in $n$ whereas LASSO’s scales exponentially
in $n$ (linearly in $N$). While our algorithm continues to work in a
reasonable time for problem sizes as large as $n=18$ in under $0.1$ seconds,
LASSO does not run on our computer for larger problems.

Fig. 2(c) shows the relation between noise level and recovery performance. We
fix $n=20$, $q=4$ and $S$ as well as hyper-parameters $b$, $C$ and $P$. We run
$q$-SFT at various SNRs, observing a sharp phase transition where our
algorithm is successful at high SNR and fails at low SNR. As expected, the
transition point is at a lower SNR for sparser signals.

Finally, Fig. 2(d) depicts the performance of $q$-SFT on learning a real-world
function $f$. Specifically, we consider ViennaRNA [28], a computational tool
that computes the Mean Free Energy (MFE) of RNA sequences. We represent each
base with an element of $\mathbb{Z}_{4}$ and denote different length-$n$ RNA
sequences by $\mathbf{k}\in\mathbb{Z}_{4}^{n}$. Then, we consider
$\textrm{MFE}(\mathbf{k})$ computed by ViennaRNA to be noisy observations of
$f[\mathbf{k}]$. We run $q$-SFT with these noisy observations to construct
$\widehat{F}$ (hence $\widehat{f}$) and calculate a Test NMSE by calculating
the NMSE only over a uniformly randomly chosen support. As can be seen in Fig.
2(d), in all cases $q$-SFT is able to achieve a Test NMSE of $0.1$ when enough
samples are provided. For instance, when $n=18$, only $0.01\%$ of the total
number of sequences is sufficient to achieve a test NMSE of less than $0.1$.

(a)

(b)

(c)

(d)

Figure 2:  (a) NMSE of $q$-SFT for a range of sample complexity and $N$ on
synthetically generated data (note that the transition threshold appears
logarithmic in $N$), (b) runtime plotted against $N$ for the experiment in (a)
as well as LASSO on the same data (note the exponential runtime of LASSO,
while $q$-SFT is sub-linear in $N$), (c) NMSE phase transition of $q$-SFT
against SNR (note that $q$-SFT is successful for lower SNR if the sparsity is
lower), (d) performance of $q$-SFT on the Mean Free Energy function of RNA
sequences ($q=4$) as computed by the ViennaRNA [28] (for the larger values of
$n$ pictured, $q$-SFT needs only to query a small fraction of the total
function evaluations to achieve a test NMSE of less than $0.1$).

##  VI Conclusion and Future Work

This manuscript presents a fast and sample efficient algorithm to computing
$S$ sparse Fourier transforms of $q$-ary functions. With the wide range of
problems that are well modeled by $q$-ary functions, our algorithm $q$-SFT can
be applied broadly. We identify recent advancements in deep generative
modeling enabled by AlphaFold [29] and protein language models [30] as a
significant potential area of application; they allow us to sample biological
functions at scale, enabling a compact and explainable representation in terms
of high-order sparse polynomials using $q$-ary Fourier transform. Furthermore,
though the progress we make in this work is significant, challenges still
remain. For example, in the aforementioned biological application $q$-ary
functions of bounded degree are of interest. We speculate that that for prime
$q$, BCH codes can be used to design efficient offsets $\mathbf{D}$, and it
may be possible to design more efficient algorithms in general in that case.

###  -A Future Work: Bounded Degree

In this section we prove Proposition 1. We note that when the Hamming weight
of $\boldsymbol{\mathbf{k}}$ is low, (9) can be viewed as a set of parity
check equations, and $\boldsymbol{\mathbf{D}}_{c}\boldsymbol{\mathbf{k}}$ the
corresponding syndrome. Thus, if $\boldsymbol{\mathbf{D}}_{c}$ is a parity
check matrix for a $t$-error correcting code, $\boldsymbol{\mathbf{k}}$ can be
reconstructed.

###### Proof.

Note that since $q$ is prime, $\mathbb{Z}_{q}$ is equivalent to the field
$\mathbb{F}_{q}$. Let $c\triangleq\left\lceil\log_{q}(n)\right\rceil$ for
brevity. There exists the $t$-error correcting Reed-Solomon code
$\mathcal{C}_{\mathrm{RS}}=\mathrm{RS}(q^{c},q^{c}-2t)_{q^{c}}$. Thus, there
exists a sub-field-sub-code
$\mathcal{C}_{\mathrm{BCH}}=\mathbb{F}^{q^{c}}_{q}\cap\mathcal{C}_{\mathrm{RS}}$.
Furthermore, such a code can be shortened by $q^{c}-n$ symbols to obtain
$\mathcal{C}^{\prime}_{\mathrm{BCH}}$. Since shortening and considering sub-
codes does not reduce the minimum distance, the shortened code is still
$t$-error correcting. Let
$\boldsymbol{\mathbf{H}}_{\mathrm{BCH}}\in\mathbb{F}_{q}^{2tc\times n}$
represent the parity check matrix of $\mathcal{C}^{\prime}_{\mathrm{BCH}}$
over $\mathbb{F}_{q}$. Taking
$\boldsymbol{\mathbf{D}}_{c}=\boldsymbol{\mathbf{H}}_{\mathrm{BCH}}$ gives us
the desired result. ∎

Ideas from Section IV can be applied on top of Proposition 1 for robustness.
In practice, we find that $q$-SFT with $\boldsymbol{\mathbf{D}}_{c}$ chosen as
above performs well with random $\boldsymbol{\mathbf{M}}_{c}$ in the bounded
degree problem. Due to lack of independence in the aliasing pattern however, a
rigorous proof has remained elusive. We also point out that Proposition 1 can
be used to significantly reduce the constant factor in [12].

Note that Proposition 1 holds only for prime $q$ because we leverage algebraic
coding theory, which has mostly focused on the problem of defining codes over
fields. While it is possible to construct BCH codes over rings [31, 32], they
are generally inferior and yield a weaker result.

Fig. 3(a) and 3(b) show the performance of coded $q$-SFT in terms of the
number of samples and runtime. We set $q=3$, $\rho_{\mathrm{min}}=1$,
$\rho_{\mathrm{max}}=1$, $S=1000$ $t=5$, and $\sigma^{2}$ such that SNR is
fixed at 20dB. We vary hyper-parameters $b$, $C$, and $P$ such that each
combination results in a different number of samples used.

(a)

(b)

Figure 3:  (a) NMSE of coded $q$-SFT for a range of sample complexity and $N$
values on synthetically generated data (note that the transition threshold
appears sub-logarithmic in $N$), (b) runtime plotted against $N$ for the
experiment in (a)

###  -B Proof of the Aliasing Pattern

First, we assume $\mathbf{d}_{p}=\boldsymbol{\mathbf{0}}$.

$\displaystyle U_{c,p}[\mathbf{j}]$ $\displaystyle=$
$\displaystyle\frac{1}{B}\sum_{\boldsymbol{\ell}\in\mathbb{Z}_{q}^{b}}f[\mathbf{\mathbf{M}\boldsymbol{\ell}}]\omega^{-\langle\mathbf{j},\boldsymbol{\ell}\rangle},$
(19) $\displaystyle=$
$\displaystyle\frac{1}{B}\sum_{\boldsymbol{\mathbf{\ell}}\in\mathbb{Z}_{q}^{n}}\left(\sum_{\mathbf{k}\in\mathbb{Z}_{q}^{n}}F[\mathbf{k}]\omega^{\langle\mathbf{M}\boldsymbol{\mathbf{\ell}},\mathbf{k}\rangle}\right)\omega^{-\langle\mathbf{j},\boldsymbol{\ell}\rangle},$
(20) $\displaystyle=$
$\displaystyle\frac{1}{B}\sum_{\mathbf{k}\in\mathbb{Z}_{q}^{n}}F[\mathbf{k}]\left(\sum_{\boldsymbol{\mathbf{\ell}}\in\mathbb{Z}_{q}^{b}}\omega^{\langle\mathbf{M}^{\mathrm{T}}\mathbf{k}-\mathbf{j},\boldsymbol{\mathbf{\ell}}\rangle}\right),$
(21) $\displaystyle=$
$\displaystyle\sum_{\mathbf{k}\;:\;\mathbf{M}^{\top}\mathbf{k}=\mathbf{j}}F[\mathbf{k}].$
(22)

where the last inequality follows from Lemma 24. Finally, by using the
shifting property, for arbitrary $\mathbf{d}_{p}$, we have:

$U_{c,p}[\mathbf{j}]=\sum_{\mathbf{k}\;:\;\mathbf{M}^{\mathrm{T}}\mathbf{k}=\mathbf{j}}F[\mathbf{k}]\omega^{\langle\mathbf{d}_{p},\mathbf{k}\rangle}.$
(23)

######  Lemma 1.

Let $\omega=\exp(-i2\pi/q)$, and $\boldsymbol{a}\in\mathbb{Z}_{q}^{b}$. Then,

$0=\sum_{\boldsymbol{\ell}\in\mathbb{F}_{q}^{b}}\omega^{\langle\boldsymbol{\ell},\boldsymbol{a}\rangle}\iff\boldsymbol{a}\neq\boldsymbol{0}$
(24)

###### Proof.

$\displaystyle\sum_{\boldsymbol{\ell}\in\mathbb{Z}_{q}^{b}}\omega^{\langle\boldsymbol{\ell},\boldsymbol{a}\rangle}$
$\displaystyle=$
$\displaystyle\sum_{\boldsymbol{\ell}\in\mathbb{Z}_{q}^{b}}\omega^{\sum_{i=1}^{b}\ell_{i}a_{i}}$
(25) $\displaystyle=$
$\displaystyle\sum_{\boldsymbol{\ell}\in\mathbb{Z}_{q}^{b}}\prod_{i=1}^{b}\omega^{\ell_{i}a_{i}}=\prod_{i=1}^{b}\sum_{\ell_{i}\in\mathbb{Z}_{q}}\omega^{\ell_{i}a_{i}}$
(26)

For proving the forward direction, if $\boldsymbol{a}=\boldsymbol{0}$, then
the right hand is equal to $B=q^{b}$ which is nonzero. For proving the
converse, if $\boldsymbol{a}\neq\boldsymbol{0}$, then at least for one $i$, we
have $a_{i}\neq 0$. Since $\omega$ is the $q$-th root of unity, the $i$-th
term of the product is equal to
$\sum_{\ell_{i}\in\mathbb{F}_{q}}\omega^{\ell_{i}a_{i}}=0$ making the right
hand side equal to 0. ∎

###  -C Proof of Theorem 1

We let $\mathcal{G}(S,\eta,C,\\{\boldsymbol{\mathbf{M}}_{c}\\}_{c\in[C]})$
represent the set of all bipartite graphs that are induced by subsampling with
$B=\eta S$ and subsampling matrices
$\\{\boldsymbol{\mathbf{M}}_{c}\\}_{c\in[C]}$. By Assumption 1, the graph that
we must decode over in Algorithm 1 is uniformly distributed over this set.

By the choice of $\boldsymbol{\mathbf{D}}_{c}$, for any singleton index
$U_{c}[\mathbf{j}]$, $F[\mathbf{k}]$ and $\mathbf{k}$ are retrieved with
probability $1$ using the methods described in Section III-B. What remains
then is to show that taking $C$ to be $O(1)$ is sufficient for the peeling to
peel every edge in the graph. Due to our uniformly distributed support
assumption, the argument is essentially identical to the binary case in [11]
Appendix B. In this section, we sketch the proof for $0\leq\delta\leq 1/3$,
but the other cases follow a similar argument, and are described in [11]. In
this case, $\mathbf{M}_{c}$ may be constructed as:

$\boldsymbol{\mathbf{M}}_{c}=[\boldsymbol{\mathbf{0}}_{b\times(c-1)},\boldsymbol{\mathbf{I}}_{b\times
b},\boldsymbol{\mathbf{0}}_{b\times(n-cb)}]^{\mathrm{T}},\;\;c\in[C]$ (27)

Choosing $\boldsymbol{\mathbf{M}}_{c}$ in this way ensures that the edge
degree distribution is easily computed. Specifically, the number of edges
connected to check nodes with degree $j$ when $\eta S=B$ is:

$\rho_{j}=\frac{({1}/{\eta})^{j-1}e^{-1/\eta}}{(j-1)!},\;j=0,\dotsc,S,$ (28)

and zero otherwise. For the next step, we define the neighborhood of an edge
$e=(v,c)$, where $v$ and $c$ are the connected variable and check node
respectively as follows: $\mathcal{N}_{e}^{\ell}$ is the induced sub-graph
containing the edges and nodes of all paths $e_{1},\dotsc,e_{\ell}$ where
$v\in e_{1}$ and $e_{1}\neq e$. If we consider an arbitrary edge in our
decoding graph, such that $\mathcal{N}_{e}^{2i}$ is a tree, the probability
that it will not be removed after the $i$th iteration $p_{i}$ can be written
as: $p_{i}=\left(1-\sum_{j}\rho_{j}\left(1-p_{i-1}\right)^{j-1}\right)^{C-1}$,
for sufficiently large $S$ this is well approximated by

$p_{i}=\left(1-e^{-\frac{1}{\eta}p_{i-1}}\right)^{C-1}.$ (29)

From this equation, we can see that for any choice of $C$ there exists an
$\eta$ such that $p_{i}$ goes to zero as $i$ does. Then let $\mathcal{T}_{i}$
denote the event that for every edge $e$ the neighbourhood
$\mathcal{N}_{e}^{2i}$ is a tree, and let $Z_{i}$ represent the number of
edges that are still not decoded after the $i$th peeling iteration. Let
$Z_{i}=\sum_{e}Z_{i}^{e}$, where
$Z_{i}^{e}=\mathds{1}\\{\text{Edge}\;e\;\text{is not peeled}\\}$. We can now
bound $\mathbb{E}\left[Z_{i}\lvert\mathcal{T}_{i}\right]$ as follows:

$\mathbb{E}\left[Z_{i}\lvert\mathcal{T}_{i}\right]=\sum_{e}\left[Z_{i}\lvert\mathcal{T}_{i}\right]=CSp_{i}.$
(30)

Since it is possible to choose $\eta$ such that $p_{i}$ can be made
arbitrarily small, we conclude that for $\epsilon>0$ there exist some $i$ such
that $\mathbb{E}\left[Z_{i}\lvert\mathcal{T}_{i}\right]=CS\epsilon/4$. Then,
via Lemma 6 in [11], which is similar to [33], we can show that for large $S$,
$\mathcal{T}_{i}$ occurs with high probability. Thus we can bound the absolute
difference between the conditional and unconditional mean as:

$\left\lvert{\mathbb{E}\left[Z_{i}\right]-\mathbb{E}\left[Z_{i}\lvert\mathcal{T}_{i}\right]}\right\rvert\leq
CS\epsilon/4,$ (31)

allowing us to conclude that there is some $i$ such that
$\mathbb{E}\left[Z_{i}\right]\leq CS\epsilon/2$ for $S$ greater than some
constant. We can further show that $Z_{i}$ is well concentrated around its
mean by constructing a suitable martingale, and applying Azuma’s Inequality.
This allows us to establish:

$\mathrm{Pr}\left(\left\lvert{Z_{i}-\mathbb{E}\left[Z_{i}\right]}\right\rvert>CS\epsilon/2\right)\leq
2\mathrm{exp}\left(-\beta\epsilon^{2}S^{\frac{1}{4i+1}}\right),$ (32)

for some constant $\beta>0$. Thus, we have shown that with high probability,
our peeling phase terminates with the number of remaining edges
$Z_{i}<CS\epsilon$ for any $\epsilon>0$. Note now, if we could choose
$\epsilon=1/CS$, we would be done, however, this would cause our bound in (32)
to be meaningless. Instead, we use graph expander properties to complete the
argument.

We call a bipartite graph in
$\mathcal{G}(S,\eta,C,\\{\boldsymbol{\mathbf{M}}_{c}\\}_{c\in[C]})$ an
$\epsilon$-expander if for all subsets $\mathcal{S}$ of variable nodes with
$\left\lvert{\mathcal{S}}\right\rvert<\epsilon S$, there exists a check node
neighbourhood of $\mathcal{S}$ in one of the sub-sampling groups $c$ denoted
as $\mathcal{N}_{c}(\mathcal{S})$ that satisfies
$\left\lvert{\mathcal{N}_{c}(\mathcal{S})}\right\rvert>\left\lvert{S}\right\rvert/2$.
It can be easily shown, based on (27) that if the graph is uniformly chosen
over $\mathcal{G}(S,\eta,C,\\{\boldsymbol{\mathbf{M}}_{c}\\}_{c\in[C]})$, it
is an $\epsilon$-expander with probability at least $1-O(1/S)$ if $C\geq 3$.
This is done in Appendix B.7 of [11] using a counting argument and elementary
inequalities.

Let the set of $Z_{i}$ remaining edges be connected to the variable nodes
$\mathcal{S}$. A sufficient condition for all the right nodes in at least one
group $\mathcal{N}_{c}(\mathcal{S})$ to have at least one singleton is that
the corresponding average degree is less than 2, which implies that
$\left\lvert{S}\right\rvert/\left\lvert{\mathcal{N}_{c}(\mathcal{S})}\right\rvert\leq
2$ and hence
$\left\lvert{\mathcal{N}_{c}(\mathcal{S})}\right\rvert\geq\left\lvert{S}\right\rvert/2$.
Since the graph is an expander with probability at least $1-O(1/S)$ this
condition is satisfied, and all the edges will be peeled with at least this
probability.

Note that the number of samples required is $O(PCB)=O(Sn)$. The total number
of computations is dominated by the subsampling, which requires $O(PB\log
B)=O(PS\log S)=O(PS\log N)$ because $S=O(N^{\delta})$. As a result, this gives
a total complexity of $O(PSn\log q)=O(Sn^{2}\log q)$. ∎

###  -D Proof of Proposition 2

Given a singleton bin with an index-value pair
$(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}])$, we can write

$\text{arg}[U_{p}]=\text{arg}[F[\boldsymbol{\mathbf{k}}]]+\frac{2\pi}{q}\langle\boldsymbol{\mathbf{d}}_{p},\boldsymbol{\mathbf{k}}\rangle+Y_{p}$

where the additions are modulo-$2\pi$ and $Y_{p}$ is a random variable over
$[-\pi,\pi)$ that satisfies

$\displaystyle\mathrm{Pr}(|Y_{p}|\geq\alpha)$
$\displaystyle\leq\mathrm{Pr}(|W_{p}|\geq|F[\boldsymbol{\mathbf{k}}]|\sin{(\alpha)})$
$\displaystyle\leq\exp\left(-\frac{|F[\boldsymbol{\mathbf{k}}]|^{2}\sin^{2}{(\alpha)}}{2\sigma^{2}/B}\right)$
$\displaystyle=\exp\left(-\frac{\eta\sin^{2}{(\alpha)}}{2}\text{SNR}\right)$

for $0\leq\alpha\leq\pi/2$. Similarly, we can write

$\text{arg}[U_{p,r}]=\text{arg}[F[\boldsymbol{\mathbf{k}}]]+\frac{2\pi}{q}\langle\boldsymbol{\mathbf{d}}_{p,r},\boldsymbol{\mathbf{k}}\rangle+Y_{p,r}$

for a random variable $Y_{p,r}$ over $[-\pi,\pi)$ that satisfies

$\displaystyle\mathrm{Pr}(|Y_{p,r}|\geq\alpha)\leq\exp\left(-\frac{\eta\sin^{2}{(\alpha)}}{2}\text{SNR}\right)$

for $0\leq\alpha\leq\pi/2$. Then, we can write

$\text{arg}[U_{p,r}/U_{p}]=\frac{2\pi}{q}\langle\boldsymbol{\mathbf{e}}_{r},\boldsymbol{\mathbf{k}}\rangle+Y_{p,r}-Y_{p}.$

Therefore,

$\displaystyle\mathrm{Pr}(Z_{p,r}\neq 0)$
$\displaystyle=\mathrm{Pr}(\text{arg}_{q}[U_{p,r}/U_{p}]\neq\langle\boldsymbol{\mathbf{e}}_{r},\boldsymbol{\mathbf{k}}\rangle)$
$\displaystyle\leq\mathrm{Pr}(|Y_{p}|\geq\pi/2q)+\mathrm{Pr}(|Y_{p,r}|\geq\pi/2q)$
$\displaystyle\leq
2\exp\left(-\frac{\eta\sin^{2}{(\pi/2q)}}{2}\text{SNR}\right).\hfill\qed$

###  -E Proof of Theorem 2

As stated in the theorem, we assume the alphabet size $q$ is a fixed constant
throughout this proof. The success rate of the algorithm depends on each bin
$\boldsymbol{\mathbf{j}}$ to be processed correctly, meaning that each bin is
correctly identified as a zero-ton, singleton or multi-ton. Define
$\mathcal{E}$ as the the error event where bin detector makes a mistake in
$O(S)$ peeling iterations. If the error probability satisfies
$\mathrm{Pr}(\mathcal{E})\leq O(1/S)$, the probability of failure of peeling
decoder can be written as

$\displaystyle\mathbb{P}_{F}$ $\displaystyle=\mathrm{Pr}\left(\widehat{F}\neq
F|\mathcal{E}^{\mathrm{c}}\right)\mathrm{Pr}(\mathcal{E}^{\mathrm{c}})+\mathrm{Pr}\left(\widehat{F}\neq
F|\mathcal{E}\right)\mathrm{Pr}(\mathcal{E})$
$\displaystyle\leq\mathrm{Pr}\left(\widehat{F}\neq
F|\mathcal{E}^{\mathrm{c}}\right)+\mathrm{Pr}(\mathcal{E})$
$\displaystyle=O(1/S)$

where the first term in the last inequality is obtained from Theorem 1 for the
peeling decoder with an oracle such that the event $\mathcal{E}^{\mathrm{c}}$
holds.

Then, we define $\mathcal{E}_{b}$ as the the error event where a bin
$\boldsymbol{\mathbf{j}}$ is decoded wrongly and then, using a union bound
over different bins and different iterations, the probability of the algorithm
making a mistake in bin identification satisfies

$\mathrm{Pr}(\mathcal{E})\leq\text{(\\# of iterations)}\times\text{(\\# of
bins)}\times\mathrm{Pr}(\mathcal{E}_{b})$

The number of bins is $\eta S$ and the number of iterations is at most $CS$
(at least one edge is peeled off at each iteration in the worst case). Hence,
$\mathrm{Pr}(\mathcal{E})\leq\eta CS^{2}\mathrm{Pr}(\mathcal{E}_{b})$. In
order to satisfy $\mathrm{Pr}(\mathcal{E})\leq O(1/S)$, we need to show that
$\mathrm{Pr}(\mathcal{E}_{b})\leq O(1/S^{3})$.

In the following, we prove that $\mathrm{Pr}(\mathcal{E}_{b})\leq O(1/S^{3})$
holds using the observation model. In the following analysis, we consider
separate cases where the bin in consideration is fixed as a zero-ton,
singleton or multi-ton.

######  Proposition 3.

The error probability $\mathrm{Pr}(\mathcal{E}_{b})$ for an arbitrary bin can
be upper bounded as $\mathrm{Pr}(\mathcal{E}_{b})\leq O(1/S^{3})$.

###### Proof.

The error probability $\mathrm{Pr}(\mathcal{E}_{b})$ for an arbitrary bin can
be upper bounded as

$\displaystyle\mathrm{Pr}(\mathcal{E}_{b})\leq$
$\displaystyle\sum_{\mathcal{F}\in\\{\mathcal{H}_{Z},\mathcal{H}_{M}\\}}\mathrm{Pr}(\mathcal{F}\leftarrow\mathcal{H}_{S}(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}]))$
$\displaystyle+$
$\displaystyle\sum_{\mathcal{F}\in\\{\mathcal{H}_{Z},\mathcal{H}_{M}\\}}\mathrm{Pr}(\mathcal{H}_{S}(\widehat{\boldsymbol{\mathbf{k}}},\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}])\leftarrow\mathcal{F})$
$\displaystyle+$
$\displaystyle\mathrm{Pr}(\mathcal{H}_{S}(\widehat{\boldsymbol{\mathbf{k}}},\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}])\leftarrow\mathcal{H}_{S}(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}]))$

where the events refer to:

  1. 1.

$\\{\mathcal{F}\leftarrow\mathcal{H}_{S}(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}])\\}$:
missed verification in which the singleton verification fails when the ground
truth is in fact a singleton.

  2. 2.

$\\{\mathcal{H}_{S}(\widehat{\boldsymbol{\mathbf{k}}},\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}])\leftarrow\mathcal{F}\\}$:
false verification in which the singleton verification is passed when the
ground truth is not a singleton.

  3. 3.

$\\{\mathcal{H}_{S}(\widehat{\boldsymbol{\mathbf{k}}},\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}])\leftarrow\mathcal{H}_{S}(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}])\\}$:
crossed verification in which a singleton with a wrong index-value pair passes
the singleton verification when the ground truth is another singleton pair.

Since all the error probabilities decay exponentially with respect to $P_{1}$,
it is clear that if $P_{1}$ is chosen as $P_{1}=O(n)=O(\log N)$, the
probability can be bounded as $\mathrm{Pr}(\mathcal{E}_{b})\leq O(1/N^{3})$.
Then, the result follows by noting $S\leq N$.

Note that the number of samples required is $O(PB)=O(PS)$. For near-linear
time bin detection, the total number of computations is dominated by the
singleton search which requires $O(SNn)=O(Snq^{n})$. On the other hand, for
sublinear time bin detection, the total number of computations is dominated by
the subsampling, which requires $O(PB\log B)=O(PS\log S)=O(PS\log N)$ because
$S=O(N^{\delta})$. As a result, this gives a total complexity of
$O(PSn)=O(Sn^{3})$. ∎

######  Proposition 4 (False Verification Rate).

For $0<\gamma<\frac{\eta}{2}\mathrm{SNR}$, the false verification rate for
each bin hypothesis satisfies:

$\displaystyle\mathrm{Pr}(\mathcal{H}_{S}(\widehat{\boldsymbol{\mathbf{k}}},\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}])\leftarrow\mathcal{H}_{Z})$
$\displaystyle\leq e^{-\frac{P_{1}}{2}(\sqrt{1+2\gamma}-1)^{2}},$
$\displaystyle\mathrm{Pr}(\mathcal{H}_{S}(\widehat{\boldsymbol{\mathbf{k}}},\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}])\leftarrow\mathcal{H}_{M})$
$\displaystyle\leq
e^{-\frac{P_{1}\gamma^{2}}{2(1+4\gamma)}}+4N^{2}e^{-\epsilon\left(1-\frac{2\gamma\nu^{2}}{L\rho^{2}}\right)^{2}P_{1}},$

where $P_{1}$ is the number of the random offsets in the near-linear time and
sublinear time robust bin detection algorithms.

###### Proof.

The probability of detecting a zero-ton as a singleton can be upper bounded by
the probability of a zero-ton failing the zero-ton verification. Thus,

$\displaystyle\mathrm{Pr}(\mathcal{H}_{S}(\widehat{\boldsymbol{\mathbf{k}}},\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}])\leftarrow\mathcal{H}_{Z})$
$\displaystyle\leq\mathrm{Pr}\left(\frac{1}{P_{1}}\|\boldsymbol{\mathbf{W}}\|^{2}\geq(1+\gamma)\nu^{2}\right)$
$\displaystyle\leq e^{-\frac{P_{1}}{2}(\sqrt{1+2\gamma}-1)^{2}}$

by noting that
$\boldsymbol{\mathbf{W}}\sim\mathcal{CN}(0,\nu^{2}\boldsymbol{\mathbf{I}})$
and applying Lemma 2.

On the other hand, given some multi-ton observation
$\boldsymbol{\mathbf{U}}=\boldsymbol{\mathbf{S}}\boldsymbol{\mathbf{\alpha}}+\boldsymbol{\mathbf{W}}$,
the probability of detecting it as a singleton with index-value pair
$(\widehat{\boldsymbol{\mathbf{k}}},\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}])$
can be written as

$\displaystyle\mathrm{Pr}(\mathcal{H}_{S}(\widehat{\boldsymbol{\mathbf{k}}},\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}])\leftarrow\mathcal{H}_{Z})=\mathrm{Pr}\left(\frac{1}{P_{1}}\left\|\boldsymbol{\mathbf{g}}+\boldsymbol{\mathbf{v}}\right\|^{2}\leq(1+\gamma)\nu^{2}\right),$

where
$\boldsymbol{\mathbf{g}}:=\boldsymbol{\mathbf{S}}(\boldsymbol{\mathbf{\alpha}}-\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}]\boldsymbol{\mathbf{e}}_{\widehat{\boldsymbol{\mathbf{k}}}})$
and $\boldsymbol{\mathbf{v}}:=\boldsymbol{\mathbf{W}}$. Then, we can upper
bound this probability by

$\displaystyle\mathrm{Pr}\left(\frac{1}{P_{1}}\left\|\boldsymbol{\mathbf{g}}+\boldsymbol{\mathbf{v}}\right\|^{2}\leq(1+\gamma)\nu^{2}\middle|\frac{\|\boldsymbol{\mathbf{g}}\|^{2}}{P_{1}}\geq
2\gamma\nu^{2}\right)$
$\displaystyle+\mathrm{Pr}\left(\frac{\|\boldsymbol{\mathbf{g}}\|^{2}}{P_{1}}\leq
2\gamma\nu^{2}\right).$

Using Lemma 2, the first term is upper bounded by
$\exp\\{-(P_{1}\gamma^{2})/(2(1+4\gamma))\\}$. To analyze the second term, we
let
$\boldsymbol{\mathbf{\beta}}=\boldsymbol{\mathbf{\alpha}}-\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}]\boldsymbol{\mathbf{e}}_{\widehat{\boldsymbol{\mathbf{k}}}}$
and write
$\boldsymbol{\mathbf{g}}=\boldsymbol{\mathbf{S}}\boldsymbol{\mathbf{\beta}}$.
Denoting its support as
$\mathcal{L}:=\mathrm{supp}(\boldsymbol{\mathbf{\beta}})$, we can further
write
$\boldsymbol{\mathbf{S}}\boldsymbol{\mathbf{\beta}}=\boldsymbol{\mathbf{S}}_{\mathcal{L}}\boldsymbol{\mathbf{\beta}}_{\mathcal{L}}$
where $\boldsymbol{\mathbf{S}}_{\mathcal{L}}$ is the sub-matrix of
$\boldsymbol{\mathbf{S}}$ consisting of the columns in $\mathcal{L}$ and
$\boldsymbol{\mathbf{\beta}}_{\mathcal{L}}$ is the sub-vector consisting of
the elements in $\mathcal{L}$. Then, we consider two scenarios:

  * •

The multi-ton size is a constant, i.e., $|\mathcal{L}|=L=O(1)$. In this case,
we have

$\lambda_{\mathrm{min}}(\boldsymbol{\mathbf{S}}_{\mathcal{L}}^{\mathrm{H}}\boldsymbol{\mathbf{S}}_{\mathcal{L}})\|\boldsymbol{\mathbf{\beta}}_{\mathcal{L}}\|^{2}\leq\|\boldsymbol{\mathbf{S}}_{\mathcal{L}}\boldsymbol{\mathbf{\beta}}_{\mathcal{L}}\|^{2}$

Using $\|\boldsymbol{\mathbf{\beta}}_{\mathcal{L}}\|^{2}\geq L\rho^{2}$, the
probability can be bounded as

$\mathrm{Pr}\left(\frac{\|\boldsymbol{\mathbf{g}}\|^{2}}{P_{1}}\leq
2\gamma\nu^{2}\right)\leq\mathrm{Pr}\left(\lambda_{\mathrm{min}}\left(\frac{1}{P_{1}}\boldsymbol{\mathbf{S}}_{\mathcal{L}}^{\mathrm{H}}\boldsymbol{\mathbf{S}}_{\mathcal{L}}\right)\leq\frac{2\gamma\nu^{2}}{L\rho^{2}}\right)$

Then, according to the Gershgorin Circle Theorem,

$\lambda_{\mathrm{min}}\left(\frac{1}{P_{1}}\boldsymbol{\mathbf{S}}_{\mathcal{L}}^{\mathrm{H}}\boldsymbol{\mathbf{S}}_{\mathcal{L}}\right)\geq
1-L\mu,$

where $\mu$ is the mutual coherence of $\boldsymbol{\mathbf{S}}$ defined in
Lemma 3. Using the bound for $\mu$ and letting
$\mu_{0}=\frac{1}{L}\left(1-\frac{2\gamma\nu^{2}}{L\rho^{2}}\right)$,

$\displaystyle\mathrm{Pr}\left(\frac{\|\boldsymbol{\mathbf{g}}\|^{2}}{P_{1}}\leq
2\gamma\nu^{2}\right)\leq
4N^{2}e^{-\frac{1}{8L^{2}}\left(1-\frac{2\gamma\nu^{2}}{L\rho^{2}}\right)^{2}P_{1}}$

which holds as long as
$\gamma<L\rho^{2}/2\nu^{2}=\frac{L\eta}{2}\mathrm{SNR}$.

  * •

The multi-ton size grows asymptotically with respect to S, i.e.,
$|\mathcal{L}|=L=\omega(1)$. As a result, the vector of random variables
$\boldsymbol{\mathbf{g}}=\boldsymbol{\mathbf{S}}_{\mathcal{L}}\boldsymbol{\mathbf{\beta}}_{\mathcal{L}}$
becomes asymptotically Gaussian due to the central limit theorem with zero
mean and a covariance

$\mathbb{E}[\boldsymbol{\mathbf{g}}\boldsymbol{\mathbf{g}}^{\mathrm{H}}]=L\rho^{2}\boldsymbol{\mathbf{I}}$

Therefore, by Lemma 2, we have

$\displaystyle\mathrm{Pr}\left(\frac{\|\boldsymbol{\mathbf{g}}\|^{2}}{P_{1}}\leq
2\gamma\nu^{2}\right)\leq
e^{-\frac{P_{1}}{2}\left(1-\frac{2\gamma\nu^{2}}{L\rho^{2}}\right)}$

which holds as long as
$\gamma<L\rho^{2}/2\nu^{2}=\frac{L\eta}{2}\mathrm{SNR}$.

By combining the results from both cases, there exists some absolute constant
$\epsilon>0$ such that

$\displaystyle\mathrm{Pr}\left(\frac{\|\boldsymbol{\mathbf{g}}\|^{2}}{P_{1}}\leq
2\gamma\nu^{2}\right)\leq
4N^{2}e^{-\epsilon\left(1-\frac{2\gamma\nu^{2}}{L\rho^{2}}\right)^{2}P_{1}}$

as long as $\gamma<\rho^{2}/2\nu^{2}=\frac{\eta}{2}\mathrm{SNR}$. ∎

######  Proposition 5 (Missed Verification Rate).

For $0<\gamma<\frac{\eta}{2}\mathrm{SNR}$, the missed verification rate for
each bin hypothesis satisfies

$\displaystyle\mathrm{Pr}(\mathcal{H}_{Z}\leftarrow\mathcal{H}_{S}(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}]))\leq
e^{-\frac{P_{1}}{2}\frac{(\rho^{2}/\nu^{2}-\gamma)^{2}}{1+2\rho^{2}/\nu^{2}}}$
$\displaystyle\mathrm{Pr}(\mathcal{H}_{M}\leftarrow\mathcal{H}_{S}(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}]))$
$\displaystyle\quad\leq
e^{-\frac{P_{1}}{2}(\sqrt{1+2\gamma}-1)^{2}}+2e^{-\frac{\rho^{2}\sin^{2}(\pi/\kappa)}{2\nu^{2}}P_{1}}$
$\displaystyle\quad+\begin{cases}4Ne^{-\frac{P_{1}}{2}\left(\sqrt{2\gamma+1}-1\right)^{2}}\\\
\quad+4N^{2}e^{-\frac{P_{1}}{8}\left(1-\sqrt{16(1+\gamma)\nu^{2}/\rho^{2}}\right)^{2}},&\text{NLT}\\\
4ne^{-\frac{1}{2q}\epsilon^{2}P_{1}},&\text{SLT}\end{cases}$

where $P_{1}$ is the number of the random offsets in the near-linear time and
sublinear time robust bin detection algorithms.

###### Proof.

The probability of detecting a singleton as a zero-ton can be upper bounded by
the probability of a singleton passing the zero-ton verification. Hence, by
noting that
$\boldsymbol{\mathbf{W}}\sim\mathcal{CN}(0,\nu^{2}\boldsymbol{\mathbf{I}})$
and applying Lemma 2,

$\displaystyle\mathrm{Pr}$
$\displaystyle(\mathcal{H}_{Z}\leftarrow\mathcal{H}_{S}(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}]))$
$\displaystyle\leq\mathrm{Pr}\left(\frac{1}{P_{1}}\|F[\boldsymbol{\mathbf{k}}]\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}+\boldsymbol{\mathbf{W}}\|^{2}\leq(1+\gamma)\nu^{2}\right)$
$\displaystyle\leq
e^{-\frac{P_{1}}{2}\frac{(\rho^{2}/\nu^{2}-\gamma)^{2}}{1+2\rho^{2}/\nu^{2}}}.$

which holds as long as $\gamma<\rho^{2}/\nu^{2}=\eta\mathrm{SNR}$.

On the other hand, the probability of detecting a singleton as a multi-ton can
be written as the probability of failing the singleton verification step for
some index-value pair
$(\widehat{\boldsymbol{\mathbf{k}}},\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}])$.
Denoting the error event by

$\mathcal{E}_{V}=\left\\{\frac{1}{P}\left\|\boldsymbol{\mathbf{U}}-\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}]\boldsymbol{\mathbf{s}}_{\widehat{k}}\right\|^{2}\geq(1+\gamma)\nu^{2}\right\\},$

we can write,

$\displaystyle\mathrm{Pr}(\mathcal{H}_{M}\leftarrow\mathcal{H}_{S}(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}]))$
$\displaystyle=\mathrm{Pr}(\mathcal{E}_{V})$
$\displaystyle\leq\mathrm{Pr}(\mathcal{E}_{V}|\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}]=F[\boldsymbol{\mathbf{k}}]\wedge\widehat{\boldsymbol{\mathbf{k}}}=\boldsymbol{\mathbf{k}})$
$\displaystyle+\mathrm{Pr}(\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}]\neq
F[\boldsymbol{\mathbf{k}}]\vee\widehat{\boldsymbol{\mathbf{k}}}\neq\boldsymbol{\mathbf{k}}).$

Here, the first term is bounded as

$\displaystyle\mathrm{Pr}(\mathcal{E}_{V}|\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}]=F[\boldsymbol{\mathbf{k}}]\wedge\widehat{\boldsymbol{\mathbf{k}}}=\boldsymbol{\mathbf{k}})$
$\displaystyle\leq\mathrm{Pr}\Big{(}\frac{1}{P_{1}}\|\boldsymbol{\mathbf{W}}\|^{2}\geq(1+\gamma)\nu^{2}\Big{)}$
$\displaystyle\leq e^{-\frac{P_{1}}{2}(\sqrt{1+2\gamma}-1)^{2}}.$

The second term is bounded as

$\displaystyle\mathrm{Pr}(\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}]$
$\displaystyle\neq
F[\boldsymbol{\mathbf{k}}]\vee\widehat{\boldsymbol{\mathbf{k}}}\neq\boldsymbol{\mathbf{k}})$
$\displaystyle\leq\mathrm{Pr}(\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}]\neq
F[\boldsymbol{\mathbf{k}}])+\mathrm{Pr}(\widehat{\boldsymbol{\mathbf{k}}}\neq\boldsymbol{\mathbf{k}})$
$\displaystyle=\mathrm{Pr}(\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}]\neq
F[\boldsymbol{\mathbf{k}}]|\widehat{\boldsymbol{\mathbf{k}}}\neq\boldsymbol{\mathbf{k}})\mathrm{Pr}(\widehat{\boldsymbol{\mathbf{k}}}\neq\boldsymbol{\mathbf{k}})$
$\displaystyle\qquad+\mathrm{Pr}(\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}]\neq
F[\boldsymbol{\mathbf{k}}]|\widehat{\boldsymbol{\mathbf{k}}}=\boldsymbol{\mathbf{k}})\mathrm{Pr}(\widehat{\boldsymbol{\mathbf{k}}}=\boldsymbol{\mathbf{k}})$
$\displaystyle\qquad+\mathrm{Pr}(\widehat{\boldsymbol{\mathbf{k}}}\neq\boldsymbol{\mathbf{k}})$
$\displaystyle\leq\mathrm{Pr}(\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}]\neq
F[\boldsymbol{\mathbf{k}}]|\widehat{\boldsymbol{\mathbf{k}}}=\boldsymbol{\mathbf{k}})+2\mathrm{Pr}(\widehat{\boldsymbol{\mathbf{k}}}\neq\boldsymbol{\mathbf{k}})$

The first term is the error probability of a $\kappa$-point PSK signal with
constellation points
$\\{\rho,\rho\phi,\rho\phi^{2},\dots,\rho\phi^{\kappa-1}\\}$, and can be
bounded as

$\mathrm{Pr}(\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}]\neq
F[\boldsymbol{\mathbf{k}}]|\widehat{\boldsymbol{\mathbf{k}}}=\boldsymbol{\mathbf{k}})\leq
2e^{-\frac{\rho^{2}\sin^{2}(\pi/\kappa)}{2\nu^{2}}P_{1}}$

Since the second term
$\mathrm{Pr}(\widehat{\boldsymbol{\mathbf{k}}}\neq\boldsymbol{\mathbf{k}})$ is
the error probability of the singleton search, we use Lemmas 4 and 5. ∎

######  Proposition 6 (Crossed Verification Rate).

For $0<\gamma<\frac{\eta}{2}\mathrm{SNR}$, the crossed verification rate for
each bin hypothesis satisfies

$\displaystyle\mathrm{Pr}(\mathcal{H}_{S}(\widehat{\boldsymbol{\mathbf{k}}},\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}])\leftarrow\mathcal{H}_{S}(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}]))$
$\displaystyle\qquad\leq
4N^{2}e^{-\frac{1}{32}\left(1-\frac{2\gamma\nu^{2}}{2\rho^{2}}\right)^{2}P_{1}}+e^{-\frac{P_{1}\gamma^{2}}{2(1+4\gamma)}}$

where $P_{1}$ is the number of the random offsets in the near-linear time and
sublinear time robust bin detection algorithms.

###### Proof.

This error event can only occur if a singleton with index-value pair
$(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}])$ passes the singleton
verification step for some index-value pair
$(\widehat{\boldsymbol{\mathbf{k}}},\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}])$
such that $\boldsymbol{\mathbf{k}}\neq\widehat{\boldsymbol{\mathbf{k}}}$.
Hence,

$\displaystyle\mathrm{Pr}(\mathcal{H}_{S}(\widehat{\boldsymbol{\mathbf{k}}},\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}])\leftarrow\mathcal{H}_{S}(\boldsymbol{\mathbf{k}},F[\boldsymbol{\mathbf{k}}]))$
$\displaystyle\leq\mathrm{Pr}\left(\frac{1}{P_{1}}\|F[\boldsymbol{\mathbf{k}}]\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}-\widehat{F}[\widehat{\boldsymbol{\mathbf{k}}}]\boldsymbol{\mathbf{s}}_{\widehat{\boldsymbol{\mathbf{k}}}}+\boldsymbol{\mathbf{W}}\|^{2}\leq(1+\gamma)\nu^{2}\right)$
$\displaystyle=\mathrm{Pr}\left(\frac{1}{P_{1}}\|\boldsymbol{\mathbf{S}}\boldsymbol{\mathbf{\beta}}+\boldsymbol{\mathbf{W}}\|^{2}\leq(1+\gamma)\nu^{2}\right)$
$\displaystyle=\mathrm{Pr}\left(\frac{1}{P_{1}}\|\boldsymbol{\mathbf{S}}\boldsymbol{\mathbf{\beta}}+\boldsymbol{\mathbf{W}}\|^{2}\leq(1+\gamma)\nu^{2}\middle|\|\boldsymbol{\mathbf{S}}\boldsymbol{\mathbf{\beta}}\|^{2}\geq
2\gamma\nu^{2}\right)$
$\displaystyle\qquad+\mathrm{Pr}\left(\|\boldsymbol{\mathbf{S}}\boldsymbol{\mathbf{\beta}}\|^{2}\leq
2\gamma\nu^{2}\right)$

where $\boldsymbol{\mathbf{\beta}}$ is a $2$-sparse vector with non-zero
entries from $\\{\rho,\rho\phi,\rho\phi^{2},\dots,\rho\phi^{\kappa-1}\\}$.
Using Lemma 2, the first term is upper-bounded by
$e^{-\frac{P_{1}\gamma^{2}}{2(1+4\gamma)}}$. By Lemma 3, the second term is
upper bounded by
$4N^{2}e^{-\frac{1}{32}\left(1-\frac{2\gamma\nu^{2}}{2\rho^{2}}\right)^{2}P_{1}}$.
∎

######  Lemma 2 (Non-central Tail Bounds).

Given $\boldsymbol{\mathbf{g}}\in\mathbb{C}^{P}$ and a complex Gaussian vector
$\boldsymbol{\mathbf{v}}\sim\mathcal{CN}(0,\nu^{2}\boldsymbol{\mathbf{I}})$,
the following tail bounds hold:

$\displaystyle\mathrm{Pr}\left(\frac{1}{P}\|\boldsymbol{\mathbf{g}}+\boldsymbol{\mathbf{v}}\|^{2}\geq\tau_{1}\right)$
$\displaystyle\leq
e^{-\frac{P}{2}(\sqrt{2\tau_{1}/\nu^{2}-1}-\sqrt{1+2\theta_{0}})^{2}}$
$\displaystyle\mathrm{Pr}\left(\frac{1}{P}\|\boldsymbol{\mathbf{g}}+\boldsymbol{\mathbf{v}}\|^{2}\leq\tau_{2}\right)$
$\displaystyle\leq
e^{-\frac{P}{2}\frac{\left(1+\theta_{0}-\tau_{2}/\nu^{2}\right)^{2}}{1+2\theta_{0}}}$

for any $\tau_{1}$ and $\tau_{2}$ that satisfy

$\tau_{1}\geq\nu^{2}(1+\theta_{0})\geq\tau_{2},$

where $\theta_{0}$ is the normalized non-centrality parameter given by

$\theta_{0}:=\frac{\|\boldsymbol{\mathbf{g}}\|^{2}}{P\nu^{2}}.$

###### Proof.

We apply Lemma 11 in [11] to
$\widetilde{\boldsymbol{\mathbf{g}}}=[\mathrm{Re}[\boldsymbol{\mathbf{g}}],\mathrm{Im}[\boldsymbol{\mathbf{g}}]]^{\mathrm{T}}\in\mathbb{R}^{2P}$
and
$\widetilde{\boldsymbol{\mathbf{v}}}=[\mathrm{Re}[\boldsymbol{\mathbf{v}}],\mathrm{Im}[\boldsymbol{\mathbf{v}}]]^{\mathrm{T}}\sim\mathcal{N}(0,\frac{\nu^{2}}{2}\boldsymbol{\mathbf{I}})$.
∎

######  Lemma 3.

Denote the mutual coherence of $\boldsymbol{\mathbf{S}}$ by

$\mu:=\max_{\boldsymbol{\mathbf{k}}\neq\boldsymbol{\mathbf{m}}}\frac{1}{P_{1}}|\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}^{\mathrm{H}}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{m}}}|.$

Then, we have $\mathrm{Pr}(\mu\geq\mu_{0})\leq
4N^{2}e^{-\frac{\mu_{0}^{2}}{8}P_{1}}$ for any $\mu_{0}>0$.

###### Proof.

The columns of $\boldsymbol{\mathbf{S}}$ are given as
$\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}=\omega^{\boldsymbol{\mathbf{D}}\boldsymbol{\mathbf{k}}}$.
Let us denote the $p$-th entry of
$\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}$ by
$\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}[p]=\omega^{\langle\boldsymbol{\mathbf{d}}_{p},\boldsymbol{\mathbf{k}}\rangle}$
for $p\in[P_{1}]$. Therefore, each multiplication can be written as
$\boldsymbol{\mathbf{y}}[p]:=\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}[p]^{\mathrm{H}}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{m}}}[p]=\omega^{\langle\boldsymbol{\mathbf{d}}_{p},\boldsymbol{\mathbf{m}}\ominus_{q}\boldsymbol{\mathbf{k}}\rangle}$.
Since
$\boldsymbol{\mathbf{m}}\ominus_{q}\boldsymbol{\mathbf{k}}\neq\boldsymbol{\mathbf{0}}$
for all $\boldsymbol{\mathbf{k}}\neq\boldsymbol{\mathbf{m}}$, each
$\boldsymbol{\mathbf{y}}[p]$ term is uniformly distributed over the set
$\\{\rho,\rho\omega,\rho\omega^{2},\dots,\rho\omega^{q-1}\\}$. Then, due to
independence in choosing offsets $\boldsymbol{\mathbf{d}}_{p}$, we can apply a
Hoeffding bound to obtain

$\displaystyle\mathrm{Pr}\left(\frac{|\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}^{\mathrm{H}}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{m}}}|}{P_{1}}\geq\mu_{0}\right)$
$\displaystyle=\mathrm{Pr}(|\boldsymbol{\mathbf{y}}|\geq P_{1}\mu_{0})$
$\displaystyle\leq 2\mathrm{Pr}(\mathrm{Re}|\boldsymbol{\mathbf{y}}|\geq
P_{1}\mu_{0}/\sqrt{2})$ $\displaystyle\leq 4e^{-\frac{\mu_{0}^{2}}{8}P_{1}}.$

By applying a union bound over all
$(\boldsymbol{\mathbf{k}},\boldsymbol{\mathbf{m}})$ pairs, we obtain the
result. ∎

######  Lemma 4.

The singleton search error probability of the near-linear time robust bin
detection is upper bounded as

$\mathrm{Pr}(\widehat{\boldsymbol{\mathbf{k}}}\neq\boldsymbol{\mathbf{k}})\leq
4Ne^{-\frac{P}{2}\left(\sqrt{2\epsilon+1}-1\right)^{2}}+4N^{2}e^{-\frac{P}{8}\left(1-\sqrt{\frac{16(1+\epsilon)\nu^{2}}{\rho^{2}}}\right)^{2}}$

for some constant $\epsilon>0$.

###### Proof.

The error occurs if the residual energy for some
$\boldsymbol{\mathbf{m}}\neq\boldsymbol{\mathbf{k}}$ is lower than the
residual energy for true singleton index $\boldsymbol{\mathbf{k}}$. Let
$\mathcal{H}$ denote the event
$\\{\mu<1-\sqrt{16(1+\epsilon)\nu^{2}/\rho^{2}}\\}$ where $\mu$ is the mutual
coherence of $\boldsymbol{\mathbf{S}}$ and $\gamma$ is a constant.
Furthermore, let $\mathrm{Pr}_{\mathcal{H}}$ denote probabilities conditioned
on $\mathcal{H}$. Then, for any given
$\boldsymbol{\mathbf{m}}\neq\boldsymbol{\mathbf{k}}$,

$\displaystyle\mathrm{Pr}_{\mathcal{H}}(\widehat{\boldsymbol{\mathbf{k}}}=\boldsymbol{\mathbf{m}})$
$\displaystyle\qquad\leq\mathrm{Pr}_{\mathcal{H}}\Bigg{(}\left\|\frac{1}{P}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{m}}}^{\mathrm{T}}\boldsymbol{\mathbf{U}}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{m}}}-\boldsymbol{\mathbf{U}}\right\|\leq\left\|\frac{1}{P}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}^{\mathrm{T}}\boldsymbol{\mathbf{U}}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}-\boldsymbol{\mathbf{U}}\right\|\Bigg{)}$
$\displaystyle\quad=\mathrm{Pr}_{\mathcal{H}}\Bigg{(}\left\|\frac{1}{P}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{m}}}^{\mathrm{T}}\left(F[\boldsymbol{\mathbf{k}}]\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}+\boldsymbol{\mathbf{W}}\right)\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{m}}}-F[\boldsymbol{\mathbf{k}}]\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}-\boldsymbol{\mathbf{W}}\right\|$
$\displaystyle\quad\qquad\qquad\leq\left\|\frac{1}{P}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}^{\mathrm{T}}\left(F[\boldsymbol{\mathbf{k}}]\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}+\boldsymbol{\mathbf{W}}\right)\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}-F[\boldsymbol{\mathbf{k}}]\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}-\boldsymbol{\mathbf{W}}\right\|\Bigg{)}$
$\displaystyle\quad=\mathrm{Pr}_{\mathcal{H}}\Bigg{(}\left\|F[\boldsymbol{\mathbf{k}}]\left(\frac{1}{P}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{m}}}^{\mathrm{T}}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{m}}}-\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}\right)+\frac{1}{P}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{m}}}^{\mathrm{T}}\boldsymbol{\mathbf{W}}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{m}}}-\boldsymbol{\mathbf{W}}\right\|$
$\displaystyle\quad\qquad\qquad\leq\left\|\frac{1}{P}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}^{\mathrm{T}}\boldsymbol{\mathbf{W}}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}-\boldsymbol{\mathbf{W}}\right\|\Bigg{)}.$

Then,

$\displaystyle\mathrm{Pr}_{\mathcal{H}}(\widehat{\boldsymbol{\mathbf{k}}}=\boldsymbol{\mathbf{m}})$
$\displaystyle\qquad\leq\mathrm{Pr}_{\mathcal{H}}\Bigg{(}\rho\left\|\frac{1}{P}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{m}}}^{\mathrm{T}}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{m}}}-\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}\right\|-\left\|\frac{1}{P}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{m}}}^{\mathrm{T}}\boldsymbol{\mathbf{W}}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{m}}}-\boldsymbol{\mathbf{W}}\right\|$
$\displaystyle\qquad\qquad\qquad\leq\left\|\frac{1}{P}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}^{\mathrm{T}}\boldsymbol{\mathbf{W}}\boldsymbol{\mathbf{s}}_{\boldsymbol{\mathbf{k}}}-\boldsymbol{\mathbf{W}}\right\|\Bigg{)}$
$\displaystyle\qquad\leq
4\mathrm{Pr}_{\mathcal{H}}\Bigg{(}\frac{1}{P}\left\|\boldsymbol{\mathbf{W}}\right\|^{2}\geq(1+\epsilon)\nu^{2}\Bigg{)}$
$\displaystyle\qquad\leq
4e^{-\frac{P}{2}\left(\sqrt{2\epsilon+1}-1\right)^{2}}.$

Next, by a union bound over all
$\boldsymbol{\mathbf{m}}\in\mathbb{Z}_{q}^{n}$, we have

$\mathrm{Pr}_{\mathcal{H}}(\widehat{\boldsymbol{\mathbf{k}}}=\boldsymbol{\mathbf{k}})\leq
4Ne^{-\frac{P}{2}\left(\sqrt{2\epsilon+1}-1\right)^{2}}.$

Lastly, we can write

$\displaystyle\mathrm{Pr}(\widehat{\boldsymbol{\mathbf{k}}}$
$\displaystyle=\boldsymbol{\mathbf{k}})\leq\mathrm{Pr}(\widehat{\boldsymbol{\mathbf{k}}}=\boldsymbol{\mathbf{k}}|\mathcal{H})+\mathrm{Pr}(\mathcal{H}^{\mathrm{c}})$
$\displaystyle\leq
4Ne^{-\frac{P}{2}\left(\sqrt{2\epsilon+1}-1\right)^{2}}+4N^{2}e^{-\frac{P}{8}\left(1-\sqrt{\frac{16(1+\epsilon)\nu^{2}}{\rho^{2}}}\right)^{2}}.$

∎

######  Lemma 5.

The singleton search error probability of the sub-linear time robust bin
detection is upper bounded as

$\mathrm{Pr}(\widehat{\boldsymbol{\mathbf{k}}}\neq\boldsymbol{\mathbf{k}})\leq
2ne^{-\frac{1}{2q}\epsilon^{2}P_{1}}$

for some constant $\epsilon>0$.

###### Proof.

Recall that $\text{arg}_{q}[U_{p,r}/U_{p}]=k[r]\oplus_{q}Z_{p,r}$ where
$Z_{p,r}$ is a random variable over $\mathbb{Z}_{q}$ with parameters
$(p_{0},p_{1},\dots,p_{q-1})$ such that $p_{0}-p_{i}\geq\epsilon$ for all
$i\neq 0$ for some constant $\epsilon>0$. Then, the error probability of the
singleton search for the $r$-th symbol of $\boldsymbol{\mathbf{k}}$ is

$\displaystyle\mathrm{Pr}$ $\displaystyle(\widehat{k}[r]\neq k[r])$
$\displaystyle=\mathrm{Pr}\Big{(}\arg\max_{a\in\mathbb{Z}_{q}}\sum_{p\in[P_{1}]}\mathbb{1}\\{\text{arg}_{q}[U_{p,r}/U_{p}]=a\\}\neq
k[r]\Big{)}$
$\displaystyle=\mathrm{Pr}\Big{(}\arg\max_{a\in\mathbb{Z}_{q}}\sum_{p\in[P_{1}]}\mathbb{1}\\{Z_{p,r}=a\\}\neq
0\Big{)}$
$\displaystyle\leq\mathrm{Pr}\Big{(}\|\boldsymbol{\mathbf{p}}-\widehat{\boldsymbol{\mathbf{p}}}\|_{1}\geq\epsilon\Big{)}$
$\displaystyle\leq 2e^{-\frac{1}{2q}\epsilon^{2}P_{1}}.$

where $\boldsymbol{\mathbf{p}}=[p_{0},p_{1},\dots,p_{q-1}]^{\mathrm{T}}$ is a
vector, $\widehat{\boldsymbol{\mathbf{p}}}$ is a random vector with
distribution $\frac{1}{n}\textrm{Multinomial}(P_{1},\boldsymbol{\mathbf{p}})$
and the last step uses the result from [34]. By union bounding over all $n$
symbols, we have the final result. ∎

## References

  * [1] R. O’Donnell, _Analysis of Boolean Functions_. Cambridge, UK: Cambridge University Press, 2014.
  * [2] A. Bockmayr, “Logic programming with pseudo-Boolean constraints,” _Max-Planck-Institut für Informatik_ , 1991.
  * [3] H. Kargupta and B.-h. Park, “Gene expression and fast construction of distributed evolutionary representation,” _Evol. Comput._ , vol. 9, no. 1, p. 43–69, Jan. 2001.
  * [4] J.-L. Marichal, “The influence of variables on pseudo-Boolean functions with applications to game theory and multicriteria decision making,” _Discrete Appl. Math._ , vol. 107, no. 1-3, pp. 139–164, Dec. 2000.
  * [5] A. Aghazadeh, H. Nisonoff, O. Ocal, D. Brookes, Y. Huang, O. Koyluoglu, J. Listgarten, and K. Ramchandran, “Epistatic net allows the sparse spectral regularization of deep neural networks for inferring fitness functions,” _Nature Comm._ , vol. 12, no. 1, pp. 1–10, Sep. 2021.
  * [6] W. Ha, C. Singh, F. Lanusse, S. Upadhyayula, and B. Yu, “Adaptive wavelet distillation from neural networks through interpretations,” _Adv. Neural Inf. Proc. Sys (NeurIPS)_ , vol. 34, Dec. 2021.
  * [7] Y. Mansour, _Learning Boolean Functions via the Fourier Transform_. Boston, MA: Springer US, 1994, pp. 391–424.
  * [8] R. Tibshirani, “Regression shrinkage and selection via the LASSO,” _J. Royal Stat. Soc.: Ser. B (Methodological)_ , vol. 58, no. 1, pp. 267–288, 1996\.
  * [9] P. Stobbe and A. Krause, “Learning Fourier sparse set functions,” in _Art. Intell. and Stat._ , Dec. 2012, pp. 1125–1133.
  * [10] R. Scheibler, S. Haghighatshoar, and M. Vetterli, “A fast Hadamard transform for signals with sub-linear sparsity,” in _Allerton Conf. on Comm., Control, and Comp._ , Allerton, CA, Oct. 2013, pp. 1250–1257.
  * [11] X. Li, J. K. Bradley, S. Pawar, and K. Ramchandran, “SPRIGHT: A fast and robust framework for sparse Walsh-Hadamard transform,” Aug. 2015. [Online]. Available: {https://arxiv.org/abs/1508.06336}
  * [12] A. Amrollahi, A. Zandieh, M. Kapralov, and A. Krause, “Efficiently learning Fourier sparse set functions,” in _Adv. Neural Inf. Proc. Sys (NeurIPS)_ , vol. 32, Vancouver, Canada, Dec. 2019.
  * [13] M. Luby, M. Mitzenmacher, M. Shokrollahi, and D. Spielman, “Efficient erasure correcting codes,” _IEEE Trans. Inf. Theory_ , vol. 47, no. 2, pp. 569–584, Feb. 2001.
  * [14] S. Gelman, S. A. Fahlberg, P. Heinzelman, P. A. Romero, and A. Gitter, “Neural networks to learn protein sequence–function relationships from deep mutational scanning data,” _Proc. Nat. Acad. Sci._ , vol. 118, no. 48, Nov. 2021.
  * [15] D. Brookes, A. Aghazadeh, and J. Listgarten, “On the sparsity of fitness functions and implications for learning,” _Proc. Nat. Acad. Sci._ , vol. 119, no. 1, Nov. 2022.
  * [16] O. Ocal, S. Kadhe, and K. Ramchandran, “Low-degree pseudo-Boolean function recovery using codes,” in _IEEE Int. Symp. Inf. Theory. (ISIT)_ , Paris, France, Jul. 2019, pp. 1207–1211.
  * [17] S.-S. Choi, K. Jung, and J. H. Kim, “Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions,” _J. of Comp. Sys. Sci._ , no. 6, pp. 1039–1053, Nov. 2011.
  * [18] H. Hassanieh, P. Indyk, D. Katabi, and E. Price, “Nearly optimal sparse fourier transform,” in _Proc. ACM Symp. Theory Comp. (STOC)_ , New York, NY, 2012, p. 563–578.
  * [19] S. Pawar and K. Ramchandran, “R-FFAST: A robust sub-linear time algorithm for computing a sparse DFT,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 1, pp. 451–466, Jan. 2018.
  * [20] D. Donoho, “Compressed sensing,” _IEEE Trans. Inf. Theory_ , vol. 52, no. 4, pp. 1289–1306, Apr. 2006.
  * [21] E. Candes, J. Romberg, and T. Tao, “Stable signal recovery from incomplete and inaccurate measurements,” _Comm. Pure Appl. Math_ , vol. 59, no. 8, pp. 1207–1223, Mar. 2006.
  * [22] M. Aldridge, O. Johnson, and J. Scarlett, “Group testing: An information theory perspective,” _Foundations and Trends® in Communications and Information Theory_ , vol. 15, no. 3-4, pp. 196–392, 2019.
  * [23] D. Donoho, A. Maleki, and A. Montanari, “Message-passing algorithms for compressed sensing,” _Proc. Nat. Acad. Sci._ , vol. 106, no. 45, pp. 18 914–18 919, Nov. 2009.
  * [24] A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,” _SIAM J. Imag. Sci._ , vol. 2, no. 1, pp. 183–202, Mar. 2009.
  * [25] R. E. Blahut, _Theory and Practice of Error Control Codes_. Boston, MA: Addison-Wesley, 1983.
  * [26] M. Yuan and Y. Lin, “Model selection and estimation in regression with grouped variables,” _J. Royal Stat. Soc.: Ser. B (Methodological)_ , vol. 68, no. 1, pp. 49–67, 2006.
  * [27] A. E. Hoerl and R. W. Kennard, “Ridge regression: Biased estimation for nonorthogonal problems,” _Technometrics_ , vol. 12, no. 1, pp. 55–67, 1970\.
  * [28] R. Lorenz, S. H. Bernhart, C. Höner zu Siederdissen, H. Tafer, C. Flamm, P. F. Stadler, and I. L. Hofacker, “ViennaRNA package 2.0,” _Alg. for Molecular Bio._ , no. 1, p. 26, 2011.
  * [29] J. Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tunyasuvunakool, R. Bates, A. Žídek, A. Potapenko, A. Bridgland, C. Meyer, S. A. A. Kohl, A. J. Ballard, A. Cowie, B. Romera-Paredes, S. Nikolov, R. Jain, J. Adler, T. Back, S. Petersen, D. Reiman, E. Clancy, M. Zielinski, M. Steinegger, M. Pacholska, T. Berghammer, S. Bodenstein, D. Silver, O. Vinyals, A. W. Senior, K. Kavukcuoglu, P. Kohli, and D. Hassabis, “Highly accurate protein structure prediction with AlphaFold,” _Nature_ , vol. 596, no. 7873, pp. 583–589, 2021.
  * [30] Z. Lin, H. Akin, R. Rao, B. Hie, Z. Zhu, W. Lu, N. Smetanin, R. Verkuil, O. Kabeli, Y. Shmueli, A. dos Santos Costa, M. Fazel-Zarandi, T. Sercu, S. Candido, and A. Rives, “Evolutionary-scale prediction of atomic level protein structure with a language model,” 2022. [Online]. Available: https://www.biorxiv.org/content/early/2022/10/31/2022.07.20.500902
  * [31] I. F. Blake, “Codes over certain rings,” _Inf. and Control_ , vol. 20, no. 4, pp. 396–404, 1972.
  * [32] P. Shankar, “On BCH codes over arbitrary integer rings (corresp.),” _IEEE Trans. Inf. Theory_ , vol. 25, no. 4, pp. 480–483, Apr. 1979.
  * [33] T. Richardson and R. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding,” _IEEE Trans. Inf. Theory_ , vol. 47, no. 2, pp. 599–618, Feb. 2001.
  * [34] T. Weissman, E. Ordentlich, G. Seroussi, S. Verdu, and M. J. Weinberger, “Inequalities for the L1 deviation of the empirical distribution,” _Tech. Rep. HPL-2003-97R1, Hewlett-Packard Labs_ , 2003.