# Fast Distance Oracles for Any Symmetric Norm

Yichuan Deng<EMAIL_ADDRESS>University of Science and Technology of
China. Zhao Song<EMAIL_ADDRESS>Adobe Research. Omri Weinstein
<EMAIL_ADDRESS>The Hebrew University and Columbia University. Supported
by NSF CAREER award CCF-1844887, ISF grant #3011005535, and ERC Starting Grant
#101039914. Ruizhe Zhang<EMAIL_ADDRESS>The University of Texas at Austin.

In the _Distance Oracle_ problem, the goal is to preprocess $n$ vectors
$x_{1},x_{2},\cdots,x_{n}$ in a $d$-dimensional metric space
$(\mathbb{X}^{d},\|\cdot\|_{l})$ into a cheap data structure, so that given a
query vector $q\in\mathbb{X}^{d}$ and a subset $S\subseteq[n]$ of the input
data points, all distances $\|q-x_{i}\|_{l}$ for $x_{i}\in S$ can be quickly
approximated (faster than the trivial $\sim d|S|$ query time). This primitive
is a basic subroutine in machine learning, data mining and similarity search
applications. In the case of $\ell_{p}$ norms, the problem is well understood,
and optimal data structures are known for most values of $p$.

Our main contribution is a fast $(1+\varepsilon)$ distance oracle for _any
symmetric_ norm $\|\cdot\|_{l}$. This class includes $\ell_{p}$ norms and
Orlicz norms as special cases, as well as other norms used in practice, e.g.
top-$k$ norms, max-mixture and sum-mixture of $\ell_{p}$ norms, small-support
norms and the box-norm. We propose a novel data structure with
$\widetilde{O}(n(d+\mathrm{mmc}(l)^{2}))$ preprocessing time and space, and
$t_{q}=\widetilde{O}(d+|S|\cdot\mathrm{mmc}(l)^{2})$ query time, for computing
distances to a subset $S$ of data points, where $\mathrm{mmc}(l)$ is a
complexity-measure (concentration modulus) of the symmetric norm. When
$l=\ell_{p}$ , this runtime matches the aforementioned state-of-art oracles.

##  1 Introduction

Estimating and detecting similarities in datasets is a fundamental problem in
computer science, and a basic subroutine in most industry-scale ML
applications, from optimization [16, 15, 52] and reinforcement learning [45],
to discrepancy theory [48] and covariance estimation [50, 3], Kernel SVMs [18,
43], compression and clustering [25, 36], to mention a few. Such applications
often need to quickly compute distances of online (test) points to a subset of
points in the input data set (e.g., the training data) for transfer-learning
and classification. These applications have motivated the notion of _distance
oracles_ (DO) [40, 21, 51]: In this problem, the goal is to preprocess a
dataset of $n$ input points $X=(x_{1},x_{2},\ldots,x_{n})$ in some
$d$-dimensional metric space, into a small-space data structure which, given a
query vector $q$ and a subset $\mathsf{S}\subseteq[n]$, can quickly estimate
all the distances $\mathsf{d}(q,x_{i})$ of $q$ to $\mathsf{S}$ (note that the
problem of estimating a _single_ distance $\mathsf{d}(q,x_{i})$ is not
interesting in $\mathbb{R}^{d}$, as this can be trivially done in $O(d)$ time,
which is necessary to merely read the query $q$). The most well-studied case
(in both theory and practice) is when the metric space is in fact a _normed_
space, i.e., the data points $\\{x_{i}\\}_{i\in[n]}\in\mathbb{R}^{d}$ are
endowed with some predefined norm $\|\cdot\|$, and the goal is to quickly
estimate $\|x_{i}-q\|$ simultaneously for all $i$, i.e., in time $\ll nd$
which is the trivial query time. Distance oracles can therefore be viewed as
generalizing _matrix-vector_ multiplication: for the inner-product distance
function $\langle x_{i},q\rangle$, the query asks to approximate $X\cdot q$ in
$\ll nd$ time.

For the most popular distance metrics—the Euclidean distance ($\ell_{2}$-norm)
and Manhattan distance ($\ell_{1}$-norm)—classic dimension-reduction
(sketching) provide very efficient distance oracles [28, 1, 31]. However, in
many real-world problems, these metrics do not adequately capture similarities
between data points, and a long line of work has demonstrated that more
complex (possibly _learnable_) metrics can lead to substantially better
prediction and data compression [19]. In particular, many works over the last
decade have been dedicated to extending various optimization problems beyond
Euclidean/Manhattan distances, for example in (kernel) linear regression [46],
approximate nearest neighbor [6, 7], sampling [34], matrix column subset
selection [47], and statistical queries [33].

For $\ell_{p}$ norms, the DO problem is well-understood [12],where the
standard tool for constructing the data structure is via randomized _linear
sketching_ : The basic idea is to reduce the dimension ($d$) of the data
points by applying some _sketching matrix_ $\Phi\in\mathbb{R}^{m\times d}$
($m\ll d$) to each data point $x_{i}$ and store the sketch $\Phi
x_{i}\in\mathbb{R}^{m}$. For a query point $q$, linearity then allows to
estimate the distance from $\Phi(q-x_{i})$. The seminal works of [28, 5, 13,
49] developed polylogarithmic-size sketching methods for the $\ell_{2}$-norm,
which was extended, in a long line of work, to any $\ell_{p}$ norm with
$0<p<2$ [24, 29, 17]. For $p>2$, the sketch-size ($d$) becomes _polynomial_ ,
yet still sublinear in $d$ [42, 12].

In this work, we consider general _symmetric norms_ , which generalize
$\ell_{p}$ norms. More formally, a norm norm
$l:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is symmetric if, for all
$x\in\mathbb{R}^{d}$ and every $d\times d$ permutation matrix $P$, it
satisfies $l(Px)=l(x)$ and also $l(|x|)=l(x)$, where $|x|$ is the coordinate-
wise absolute value of $x$ (for a broader introduction, see [11] Chapter IV).
Important special cases of symmetric norms are $\ell_{p}$ norms and _Orlicz
norms_ [4], which naturally arise in harmonic analysis and model data with
sub-gaussian properties. Other practical examples of symmetric norms include
top-$k$ norms, max-mix of $\ell_{p}$ norms, sum-mix of $\ell_{p}$ norms, the
$k$-support norm [2] and the box-norm [37].

Several recent works have studied dimension-reduction (sketching) for special
cases of symmetric norms such as the Orlicz norm [10, 46, 4], for various
numerical linear algebra primitives [47]. These sketching techniques are quite
ad-hoc and are carefully tailored to the norm in question. It is therefore
natural to ask whether _symmetry alone_ is enough to guarantee dimensionality-
reduction for symmetric similarity search, in other words

Is there an efficient $(1+\epsilon)$-distance oracle for general symmetric
norms?

By “efficient”, we mean small space and preprocessing time (ideally $\sim
nd$), fast query time ($\ll n|S|$ for a query $(q,S\subseteq[n])$) and ideally
supporting dynamic updates to $x_{i}$’s in $\widetilde{O}(d)$ time. Indeed,
most ML applications involve rapidly-changing _dynamic datasets_ , and it is
becoming increasingly clear that static data structures do not adequately
capture the requirements of real-world applications [27, 16, 15]. As such, it
is desirable to design a _dynamic distance oracle_ which has both small update
time ($t_{u}$) for adding/removing a point $x_{i}\in\mathbb{R}^{d}$, and small
query time ($t_{q}$) for distance estimation. We remark that most known DOs
are dynamic by nature (as they rely on linear sketching techniques), but for
general metrics (e.g., graph shortest-path or the $\ell_{\infty}$ norm) this
is much less obvious, and indeed _linearity_ of encoding/decoding will be a
key challenge in our data structure (see next section). The problem is
formally defined as follows:

######  Definition 1.1 (Symmetric-Norm Distance Oracles).

Let $\|\cdot\|_{\mathrm{sym}}$ denote the symmetric norm. We need to design a
data structure that efficiently supports any sequence of the following
operations:

  * •

Init$(\\{x_{1},x_{2},\cdots,x_{n}\\}\subset\mathbb{R}^{d},\epsilon\in(0,1),\delta\in(0,1))$.
The data structure takes $n$ data points
$\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d}$, an accuracy parameter
$\epsilon$ and a failure probability $\delta$ as input.

  * •

UpdateX$(z\in\mathbb{R}^{d},i\in[n])$. Update the data structure with the
$i$-th new data point $z$.

  * •

EstPair$(i,j\in[n])$ Outputs a number $\mathrm{pair}$ such that
$(1-\epsilon)\|x_{i}-x_{j}\|_{\mathrm{sym}}\leq\mathrm{pair}\leq(1+\epsilon)\cdot\|x_{i}-x_{j}\|_{\mathrm{sym}}$
with probability at least $1-\delta$.

  * •

Query$(q\in\mathbb{R}^{d})$. Outputs a vector $\mathrm{dist}\in\mathbb{R}^{n}$
such that $\forall
i\in[n],(1-\epsilon)\|q-x_{i}\|_{\mathrm{sym}}\leq\mathrm{dst}_{i}\leq(1+\epsilon)\|q-x_{i}\|_{\mathrm{sym}}$.
with probability at least $1-\delta$.

where $\|x\|_{\mathrm{sym}}$ is the symmetric norm of vector $x$.

This problem can be viewed as an _online_ version of the (approximate)
_closest-pair_ problem [50], which asks to find the closest pair of points
among an _offline batch_ of data points
$X=x_{1},\ldots,x_{n}\in\mathbb{R}^{d}$, or equivalently, the smallest entry
of the _covariance matrix_ $XX^{\top}$. One major (theoretical) advantage of
the offline case is that it enables the use of fast matrix-multiplication
(FMM) to speed-up the computation of the covariance matrix [50, 8, 9, 3]
(i.e., sub-linear amortized per query). By contrast, in the online setting
such speedups are conjectured to be impossible [23, 35].

#### Notations.

For any positive integer $n$, we use $[n]$ to denote $\\{1,2,\cdots,n\\}$. For
any function $f$, we use $\widetilde{O}(f)$ to denote
$f\cdot\operatorname{poly}(\log f)$. We use $\Pr[]$ to denote probability. We
use $\operatorname*{{\mathbb{E}}}[]$ to denote expectation. We use both
$l(\cdot)$ and $\|\cdot\|_{\mathrm{sym}}$ to denote the symmetric norm. We use
$\|\cdot\|_{2}$ to denote the entry-wise $\ell_{2}$ norm. We define a tail
notation which is very standard in sparse recover/compressed sensing
literature. For any given vector $x\in\mathbb{R}^{d}$ and an integer $k$, we
use $x_{\overline{[k]}}$ or $x_{\mathrm{tail}(k)}$ to denote the vector that
without (zeroing out) top-$k$ largest entries (in absolute). For a vector $x$,
we use $x^{\top}$ to denote the transpose of $x$. For a matrix $A$, we use
$A^{\top}$ to denote the transpose of $A$. We use ${\bf 1}_{n}$ denote a
length-$n$ vector where every entry $1$. We use ${\bf 0}_{n}$ denote a
length-$n$ vector where every entry is $0$.

###  1.1 Our Results

Two important complexity measures of (symmetric) norms, which capture their
“intrinsic dimensionality”, are the _concentration modulus_ ($\mathrm{mc}$)
and _maximum modulus_ ($\mathrm{mmc}$) parameters. We now define these
quantities along the lines of [10, 46].

######  Definition 1.2 (Modulus of concentration ($\mathrm{mc}$)).

Let $X\in\mathbb{R}^{n}$ be uniformly distributed on $S^{n-1}$, the $l_{2}$
unit sphere. The median of a symmetric norm $l$ is the (unique) value $M_{l}$
such that $\Pr{[l(X)\geq M_{l}]}\geq 1/2$ and $\Pr{[l(X)\leq M_{l}]}\geq 1/2$.
Similarly, $\mathfrak{b}_{l}$ denotes the maximum value of $l(x)$ over $x\in
S^{n-1}$. We call the ratio

$\displaystyle\mathrm{mc}(l):=\mathfrak{b}_{l}/M_{l}$

the modulus of concentration of the norm $l$.

For every $k\in[n]$, the norm $l$ induces a norm $l^{(k)}$ on $\mathbb{R}^{k}$
by setting

$\displaystyle
l^{(k)}((x_{1},x_{2},\dots,x_{k})):=l((x_{1},x_{2},\dots,x_{k},\dots,0,\dots,0))$

######  Definition 1.3 ($\mathrm{mmc}$).

Define the maximum modulus of concentration of the norm $l$ as

$\displaystyle\mathrm{mmc}(l):=\max_{k\in[n]}\mathrm{mc}(l^{(k)})=\max_{k\in[n]}\frac{\mathfrak{b}_{l^{(k)}}}{M_{l^{(k)}}}$

Next, we present a few examples (in Table 1) for different norm $l$’s
$\mathrm{mmc}(l)$.

Norm $l$ | $\mathrm{mmc}(l)$
---|---
$\ell_{p}(p\leq 2)$ | $\Theta(1)$
$\ell_{p}(p>2)$ | $\Theta(d^{1/2-1/p})$
top-$k$ norms | $\widetilde{\Theta}(\sqrt{d/k})$
$k$-support norms and the box-norm | $O(\log d)$
max-mix and sum-mix of $\ell_{1}$ and $\ell_{2}$ | $O(1)$
Orlicz norm $\|\cdot\|_{G}$ | $O(\sqrt{C_{G}\log d})$
Table 1: Examples of $\mathrm{mmc}(l)$, where max-mix of $\ell_{1}$ and
$\ell_{2}$ is defined as $\max\\{\|x\|_{2},c\|x\|_{1}\\}$ for a real number
$c$, sum-mix of $\ell_{1}$ and $\ell_{2}$ is defined as $\|x\|_{2}+c\|x\|_{1}$
for a real number $c$, and $C_{G}$ of Orlicz norm is defined as the number
that for all $0<x<y$, $G(y)/G(x)\leq C_{G}(y/x)^{2}$.

We are now ready to state our main result:

######  Theorem 1.4 (Main result, informal version of Theorem D.1).

Let $\|\cdot\|_{l}$ be any symmetric norm on $\mathbb{R}^{d}$. There is a data
structure for the online symmetric-norm Distance Oracle problem (Definition
1.1), which uses
$n(d+\mathrm{mmc}(l)^{2})\cdot\operatorname{poly}(1/\epsilon,\log(nd/\delta))$
space, supporting the following operations:

  * •

Init$(\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d},\epsilon\in(0,1),\delta\in(0,1))$:
Given $n$ data points $\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d}$, an
accuracy parameter $\epsilon$ and a failure probability $\delta$ as input, the
data structure preprocesses in time
$n(d+\mathrm{mmc}(l)^{2})\cdot\operatorname{poly}(1/\epsilon,\log(nd/\delta))$.
Note that $\mathrm{mmc}()$ is defined as Definition 1.3.

  * •

UpdateX$(z\in\mathbb{R}^{d},i\in[n])$: Given an update vector
$z\in\mathbb{R}^{d}$ and index $i\in[n]$, the data data structure receives $z$
and $i$ as inputs, and updates the $i$-th data point $x_{i}\leftarrow z$, in
$d\cdot\operatorname{poly}(1/\epsilon,\log(nd/\delta))$ time.

  * •

Query$(q\in\mathbb{R}^{d},\mathsf{S}\subseteq[n])$: Given a query point
$q\in\mathbb{R}^{d}$ and a subset of the input points
$\mathsf{S}\subseteq[n]$, the Query operation outputs a $\epsilon$\-
multiplicative approximation to each distance from $q$ to points in
$\mathsf{S}$, in time

$\displaystyle(d+|\mathsf{S}|\cdot\mathrm{mmc}(l)^{2})\cdot\operatorname{poly}(1/\epsilon,\log(nd/\delta))$

i.e. it provides a set of estimates $\\{\mathrm{dst}_{i}\\}_{i\in\mathsf{S}}$
such that:

$\displaystyle\forall
i\in\mathsf{S},(1-\epsilon)\|q-x_{i}\|_{l}\leq\mathrm{dst}_{i}\leq(1+\epsilon)\|q-x_{i}\|_{l}$

with probability at least $1-\delta$.

  * •

EstPair$(i,j\in[n])$ Given indices $i,j\in[n]$, the EstPair operation takes
$i$ and $j$ as input and approximately estimates the symmetric norm distances
from $i$-th to the $j$-th point $x_{i},x_{j}\in\mathbb{R}^{d}$ in time
$\mathrm{mmc}(l)^{2}\cdot\operatorname{poly}(1/\epsilon,\log(nd/\delta))$ i.e.
it provides a estimated distance $\mathrm{pair}$ such that:

$\displaystyle(1-\epsilon)\|x_{i}-x_{j}\|_{l}\leq\mathrm{pair}\leq(1+\epsilon)\|x_{i}-x_{j}\|_{l}$

with probability at least $1-\delta$.

#### Roadmap.

In Section 2, we give an overview of techniques we mainly use in the work.
Section 3 gives an introduction of the Sparse Recovery Data we use for
sketching. Section 4 analyze the running time and space of our data structure
with their proofs, respectively. Section 5 show the correctness of our data
structure and give its proof. Finally in Section 6 we conclude our work.

##  2 Technique Overview

Our distance oracle follows the “sketch-and-decode” approach, which was
extensively used in many other sublinear-time compressed sensing and sparse
recovery problems [41, 22, 32, 38, 44]. The main idea is to compress the data
points into smaller dimension by computing, for each data point
$x_{i}\in\mathbb{R}^{d}$, a (randomized) linear sketch $\Phi\cdot
x_{i}\in\mathbb{R}^{d^{\prime}}$ with $d^{\prime}\ll d$ at preprocessing time,
where $\Phi x_{i}$ is an unbiased estimator of $\|x_{i}\|$. At query time,
given a query point $q\in\mathbb{R}^{d}$, we analogously compute its sketch
$\Phi q$. By _linearity_ of $\Phi$, the distance between $q$ and $x_{i}$
(i.e., $\ell(q-x_{i})$) can be trivially decoded from the sketch _difference_
$\Phi q-\Phi x_{i}$. As we shall see, this simple virtue of linearity is less
obvious to retain when dealing with general symmetric norms.

#### Layer approximation

Our algorithm uses the _layer approximation_ method proposed by Indyk and
Woodruff in [26] and generalized to symmetric norms in [10, 46]. Since
symmetric norms are invariant under reordering of the coordinates, the main
idea in [26] is to construct a “layer vector” as follows: for a vector
$v\in\mathbb{R}^{d}$, round (the absolute value of) each coordinate to the
nearest power $\alpha^{i}$ for some fixed $\alpha\in\mathbb{R}$ and
$i\in\mathbb{N}$, and then sort the coordinates in an increasing order. This
ensures that the $i$-th layer contains all the coordinates $j\in[d]$
satisfying: $\alpha^{i-1}<|v_{j}|\leq\alpha^{i}$. In particular, the layer
vector of $v$ has the form

$\displaystyle\mathcal{L}(v):=(\underbrace{\alpha^{1},\dots,\alpha^{1}}_{b_{1}~{}\text{times}},~{}\underbrace{\alpha^{2},\dots,\alpha^{2}}_{b_{2}~{}\text{times}},~{}\cdots,\underbrace{\alpha^{P},\dots,\alpha^{P}}_{b_{P}~{}\text{times}},~{}0,\dots,0)\in\mathbb{R}^{d},$

where $b_{i}$ is the number of coordinates in layer-$i$. More importantly,
since the norm is symmetric, the layer vector $\mathcal{L}(v)$ has a succinct
representation: $(b_{i})_{i\in[P]}$.

Then, it suffices to estimate $b_{i}$ for each $i\in[P]$, where the Indyk-
Woodruff sketching technique can be used to approximate the vector. At the
$i$-th layer, each coordinate of $v$ is sampled with probability $P/b_{i}$,
and then the algorithm identifies the _$\ell_{2}$ -heavy-hitters_ of the
sampled vector. [10] gave a criterion for identifying the important layers,
whose heavy-hitter coordinates in the corresponding _sampled_ vectors, is
enough to recover the entire symmetric norm $\|v\|_{\mathrm{sym}}$.

Unfortunately, this technique for norm estimation does not readily translate
to estimating _distances_ efficiently:

  * •

Too many layers: In previous works, each data point $x_{i}$ is sub-sampled
_independently_ in $R$ layers, i.e, generates $R$ subsets of coordinates
$S_{i}^{1},\dots,S_{i}^{R}\subset[d]$. The sketch of the query point $S(q)$
then needs to be compared to each $S(x_{i})$ in every layer. Since there are
$R=\Omega(n)$ layers in [10, 26] of size $\Omega(d)$ across all all data
points, the total time complexity will be at least $\Omega(nd)$, which is the
trivial query time.

  * •

Non-linearity:  The aforementioned sketching algorithms [10, 26] involve
nonlinear operations, and thus cannot be directly used for distance
estimation.

  * •

Slow decoding:  The aforementioned sketches take linear time to decode the
distance from the sketch, which is too slow for our application.

To overcome these challenges, we use the following ideas:

#### Technique I: shared randomness

To reduce the number of layers, we let all the data points use the same set of
layers. That is, in the initialization of our algorithm, we independently
sample $R$ subsets $S^{1},\dots,S^{R}$ with different probabilities. Then, for
each data point $x_{i}$, we consider $(x_{i})_{S^{j}}$ as the sub-sample for
the $j$-th layer, and perform sketch on it. Hence, the number of different
layer sets is reduced from $nt$ to $t$. For a query point $q$, we just need to
compute the sketches for $(q)_{S^{1}},\dots,(q)_{S^{R}}$. And the distance
between $q$ and $x_{i}$ can be decoded from
$\\{\Phi(x_{i})_{S^{j}}-\Phi(q)_{S^{j}}\\}_{j\in[R]}$. We also prove that the
shared randomness in all data points will not affect the correctness of layer
approximation.

#### Technique II: linearization

We choose a different sketching method called BatchHeavyHitter (see Theorem
D.3 for details) to generate and maintain the _linear sketches_ , which allows
us to decode the distance from sketch difference.

#### Technical III: locate-and-verify decoding

We design a _locate-and-verify_ style decoding method to recover distance from
sketch. In our data structure, we not only store the sketch of each sub-sample
vector, but also the vector itself. Then, in decoding a sketch, we can first
apply the efficient sparse-recovery algorithm to identify the position of
heavy-hitters. Next, we directly check the entries at those positions to
verify that they are indeed “heavy” (comparing the values with some
threshold), and drop the non-heavy indices. This verification step is a
significant difference from the typical sparse recovery approaches, which
employ complex (and time-consuming) subroutines to _reconstruct the values_ of
the heavy-hitter coordinates. Instead, our simple verification procedure
eliminates all the _false-positive_ heavy-hitters, therefore dramatically
reducing the running time of the second step, which can now be performed
directly by reading-off the values from the memory.

With these three techniques, we obtain our sublinear-time distance estimation
algorithm. Our data structure first generate a bunch of randomly selected
subsets of coordinates as the layer sets. Then, for each data point, we run
the BatchHeavyHitter procedure to sketch the sub-sample vector in each
layer111The total sketch size of each data point is
$\mathrm{mmc}(l)^{2}\cdot\operatorname{poly}\log d$. In the $\ell_{p}$-norm
case with $p>2$, $\mathrm{mmc}(l)=d^{1/2-1/p}$ (see Table 1) and our sketch
size is $\widetilde{O}(d^{1-2/p})$, matching the lower bound of
$\ell_{p}$-sketching. When $p\in(0,2]$, $\mathrm{mmc}(l)=\Theta(1)$ and our
sketch size is $\widetilde{O}(1)$, which is also optimal.. In the query phase,
we call the Decode procedure of BatchHeavyHitter for the sketch differences
between the query point $q$ and each data point $x_{i}$, and obtain the heavy
hitters of each layer. We then select some “important layers” and use them to
approximately recover the layer vector $\mathcal{L}(q-x_{i})$, which gives the
estimated distance $\|q-x_{i}\|_{\mathrm{sym}}$.

Finally, we summarize the time and space costs of our data structure. Let
$\epsilon$ be the precision parameter and $\delta$ be the failure probability
parameter. Our data structure achieves
$\widetilde{O}(n(d+\mathrm{mmc}(l)^{2}))$-time for initialization ,
$\widetilde{O}(d)$-time per data point update, and
$\widetilde{O}(d+n\cdot\mathrm{mmc}(l)^{2}))$-time per query. As for space
cost, our data structure uses the space of
$\widetilde{O}(n(d+\mathrm{mmc}(l)^{2}))$ in total. Note that $\mathrm{mmc}$
is defined as Defnition 1.3.

##  3 Sparse Recovery Data Structure

We design a data structure named BatchHeavyHitter to generate sketches and
manage them. In our design, it is a “linear sketch” data structure, and
providing the following functions:

  * •

Init$(\epsilon\in(0,0.1),n,d)$. Create a set of Random Hash functions and all
the $n$ copies of sketches share the same hash functions. This step takes
${\cal T}_{\mathrm{init}}(\epsilon,n,d)$ time.

  * •

Encode$(i\in[n],z\in\mathbb{R}^{d},d)$. This step takes ${\cal
T}_{\mathrm{encode}}(d)$ encodes $z$ into $i$-th sketched location and store a
size ${\cal S}_{\mathrm{space}}$ linear sketch.

  * •

EncodeSingle$(i\in[n],j\in[d],z\in\mathbb{R},d)$. This step takes ${\cal
T}_{\mathrm{encodesingle}}(d)$ updates one sparse vector
$e_{j}z\in\mathbb{R}^{d}$ into $i$-th sketched location.

  * •

Subtract$(i,j,l\in[n])$. Update the sketch at $i$-th location by $j$-th sketch
minus $l$-th sketch.

  * •

Decode$(i\in[n],\epsilon\in(0,0.1),d)$. This step takes ${\cal
T}_{\mathrm{decode}}(\epsilon,d)$ such that it returns a set $L\subseteq[d]$
of size $|L|=O(\epsilon^{-2})$ containing all $\epsilon$-heavy hitters
$i\in[n]$ under $\ell_{p}$. Here we say $i$ is an $\epsilon$-heavy hitter
under $\ell_{2}$ if
$|x_{i}|\geq\epsilon\cdot\|x_{\overline{[\epsilon^{-2}]}}\|_{2}$ where
$x_{\overline{[k]}}$ denotes the vector $x$ with the largest $k$ entries (in
absolute value) set to zero. Note that the number of heavy hitters never
exceeds $2/\epsilon^{2}$.

With this data structure, we are able to generate the sketches for each point,
and subtract each other with its function. And one can get the output of heavy
hitters of each sketch stored in it with Decode function. More details are
deferred to Section D.2.

##  4 Running Time and Space of Our Algorithm

Algorithm 1 Data structure for symmetric norm estimation: members, init,
informal version of Algorithm 4 and Algorithm 5

1:data structure DistanceOnSymmetricNorm $\triangleright$ Theorem D.1

2:members

3: $\\{x_{i}\\}_{i=1}^{n}\in\mathbb{R}^{d}$

4: $\\{S_{r,l,u}\\}_{r\in[R],l\in[L],u\in[U]}$ $\triangleright$ A list of the
BatchHeavyHitter

5: $\\{H_{r,l,u}\\}_{r\in[R],l\in[L],u\in[U]}\subset[d]\times\mathbb{R}$

6:end members

7:

8:public:

9:procedure
Init($\\{x_{1},\cdots,x_{n}\\}\subset\mathbb{R}^{d},\delta,\epsilon$)
$\triangleright$ Lemma 4.1

10: Initialize the sparse-recovery data structure $\\{S_{r,l,u}\\}$

11: Create $\\{\mathrm{bmap}_{r,l,u}\\}$ shared by all $i\in[n]$
$\triangleright$ $\\{\mathrm{bmap}_{r,l,u}\\}$ is list of a layer set map

12: for $i\in[n],j\in[d]$ do

13: if $\mathrm{bmap}_{r,u,l}[j]=1$ then

14: Sample $x_{i,j}$ into each subvector $\overline{x}_{r,u,l,i}$

15: end if

16: end for

17: Encode $\\{x_{r,u,l,i}\\}_{i\in[n]}$ into $\\{S_{r,l,u}\\}$

18:end procedure

19:end data structure

Algorithm 2 Data structure for symmetric norm estimation: query, informal
version of Algorithm 7

1:data structure DistanceOnSymmetricNorm

2:public:

3:procedure Query($q\in\mathbb{R}^{d}$) $\triangleright$ Lemma 4.3, 5.1

4: Encode $q$ into $\\{S_{r,l,u}\\}$

5: for $i\in[n]$ do

6: Subtract the sketch of $x_{i}$ and $q$, get the estimated heavy-hitters of
$q-x_{i}$

7: Decode the sketch and store returned estimation of heavy-hitters into
$H_{r,l,u}$

8: for $u\in[U]$ do

9: if $H_{r,l,u}$ provide correct indices of heavy hitters then

10: Select it as good set and store it in $H_{r,l}$

11: end if

12: end for

13: Generate estimated layer sizes $\\{c^{i}_{k}\\}_{k\in[P]}$

14:
$\mathrm{dst}_{i}\leftarrow\textsc{LayerVetcorApprox}(\alpha,c^{i}_{1},c^{i}_{2},\dots,c^{i}_{P},d)$

15: Reset $\\{H_{r,l,u}\\}$ for next distance

16: end for

17: return $\\{\mathrm{dst}_{i}\\}_{i\in[n]}$

18:end procedure

19:end data structure

We first analyze the running time of different procedures of our data
structure DistanceOnSymmetricNorm. See Algorithm 5, with the linear sketch
technique, we spend the time of $\widetilde{O}(n(d+\mathrm{mmc}(l)^{2}))$ for
preprocessing and generate the sketches stored in the data structure. When it
comes a data update (Algorithm 6), we spend $\widetilde{O}(d)$ to update the
sketch. And when a query comes (Algorithm 7), we spend
$\widetilde{O}(d+n\cdot\mathrm{mmc}(l)^{2}))$ to get the output distance
estimation. The lemmas of running time and their proof are shown below in this
section.

######  Lemma 4.1 (Init time, informal).

Given data points $\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d}$, an
accuracy parameter $\epsilon\in(0,1)$, and a failure probability
$\delta\in(0,1)$ as input, the procedure init (Algorithm 5) runs in time

$\displaystyle
O(n(d+\mathrm{mmc}(l)^{2})\cdot\operatorname{poly}(1/\epsilon,\log(nd/\delta))).$

###### Proof.

The Init time includes these parts:

  * •

Line 12 takes $O(RLU\cdot{\cal T}_{\mathrm{init}}(\sqrt{\beta},n,d))$ to
initialize sketches

  * •

Line 17 to Line 19 takes $O(RUdL)$ to generate the bmap;

  * •

Line 24 takes $O(ndRUL\cdot\mathcal{T}_{\mathrm{encodesingle}}(d))$ to
generate sketches

By Theorems D.3, we have

  * •

$\mathcal{T}_{\mathrm{init}}(\sqrt{\beta},n,d))=n\cdot
O(\beta^{-1}\log^{2}d)=O(n\cdot\mathrm{mmc}(l)^{2}\log^{7}(d)\epsilon^{-5})$,

  * •

$\mathcal{T}_{\mathrm{encodesingle}}(d)=O(\log^{2}(d))$.

Adding them together we got the time of

$\displaystyle~{}O(RLU{\cal
T}_{\mathrm{init}}(\sqrt{\beta},n,d))+O(RUdL)+O(ndRUL\cdot\mathcal{T}_{\mathrm{encodesingle}}(d))$
$\displaystyle=$ $\displaystyle~{}O(RLU({\cal
T}_{\mathrm{init}}(\sqrt{\beta},n,d)+nd\cdot\mathcal{T}_{\mathrm{encodesingle}}(d)))$
$\displaystyle=$
$\displaystyle~{}O(\epsilon^{-4}\log(1/\delta)\log^{4}(d)\cdot\log(d)\cdot\log(d^{2}/\delta\cdot\log(nd))(n\cdot\mathrm{mmc}(l)^{2}\log^{7}(d)\epsilon^{-5}+nd\log^{2}(d)))$
$\displaystyle=$
$\displaystyle~{}O(n(d+\mathrm{mmc}(l)^{2})\cdot\operatorname{poly}(1/\epsilon,\log(nd/\delta))),$

where the first step follows from merging the terms, the second step follows
from the definition of $R,L,U,\mathcal{T}_{\mathrm{encodesingle}}(d),{\cal
T}_{\mathrm{init}}$, the third step follows from merging the terms.

Thus, we complete the proof. ∎

######  Lemma 4.2 (Update time, informal).

Given a new data point $z\in\mathbb{R}^{d}$, and an index $i$ where it should
replace the original data point $x_{i}\in\mathbb{R}^{d}$. The procedure Update
(Algorithm 6) runs in time

$\displaystyle O(d\cdot\operatorname{poly}(1/\epsilon,\log(nd/\delta))$

###### Proof.

The Update operation calls BatchHeavyHitter.Encode for $RLU$ times, so it has
the time of

$\displaystyle O(RLU\cdot\mathcal{T}_{\mathrm{encode}}(d))=$
$\displaystyle~{}O(\epsilon^{-4}\log(1/\delta)\log^{4}(d)\cdot\log(d)\cdot\log(d^{2}/\delta)\cdot
d\log^{2}(d)\cdot\log(nd))$ $\displaystyle=$
$\displaystyle~{}O(\epsilon^{-4}d\log^{9}(nd/\delta))$

where the first step follows from the definition of
$R,L,U,\mathcal{T}_{\mathrm{encode}}(d)$, the second step follows from

$\displaystyle~{}\log(1/\delta)\log^{4}(d)\log(d)\log(d^{2}/\delta)\log^{2}(d)\log(nd)$
$\displaystyle=$ $\displaystyle~{}(\log(1/\delta))(\log^{7}d)(2\log
d+\log(1/\delta))\log(nd)$ $\displaystyle=$
$\displaystyle~{}O(\log^{9}(nd/\delta)).$

Thus, we complete the proof. ∎

Here, we present a Query for outputting all the $n$ distances. In Section E,
we provide a more general version, which can take any input set
$\mathsf{S}\subseteq[n]$, and output distance for only them in a shorter time
that proportional to $|\mathsf{S}|$.

######  Lemma 4.3 (Query time, informal).

Given a query point $q\in\mathbb{R}^{d}$, the procedure Query (Algorithm 7)
runs in time

$\displaystyle
O((d+n\cdot\mathrm{mmc}(l)^{2})\cdot\operatorname{poly}(1/\epsilon,\log(nd/\delta))).$

###### Proof.

The Query operation has the following two parts:

  * •

Part 1: Line 5 takes $O(RLU\cdot\mathcal{T}_{\mathrm{encode}})$ time to call
Encode to generate sketches for $q$.

  * •

Part 2: For every $i\in[n]$:

    * –

Line 13 takes $O(RLU\cdot\mathcal{T}_{\mathrm{subtract}})$ time to compute
sketch of the difference between $q$ and $x_{i}$, and store the sketch at
index of $n+1$.

    * –

Line 14 takes $O(RLU\cdot\mathcal{T}_{\mathrm{decode}})$ time to decode the
BatchHeavyHitter and get estimated heavy hitters of $q-x_{i}$.

    * –

Line 16 to Line 24 takes $O(RLU\cdot 2/\beta)$ time to analyze the
BatchHeavyHitter and get the set of indices, where $2/\beta$ is the size of
the set.

    * –

Line 30 takes $O(LP\cdot 2/\beta)$ time to compute size of the layer sets cut
by $\alpha$.

    * –

Line 32 to Line 36 takes $O(PL)$ time to compute the estimation of each layer.

The total running time of this part is:

$\displaystyle~{}n\cdot(O(RLU\cdot\mathcal{T}_{\mathrm{subtract}})+O(RLU\cdot\mathcal{T}_{\mathrm{decode}})+O(RLU\cdot
2/\beta)+O(LP\cdot 2/\beta)+O(LP))$ $\displaystyle=$
$\displaystyle~{}O(nL(RU(\mathcal{T}_{\mathrm{subtract}}+\mathcal{T}_{\mathrm{decode}}+\beta^{-1})+P\beta^{-1}))$

time in total.

Taking these two parts together we have the total running time of the Query
procedure:

$\displaystyle~{}O(RLU\cdot\mathcal{T}_{\mathrm{encode}})+O(nL(RU(\mathcal{T}_{\mathrm{subtract}}+\mathcal{T}_{\mathrm{decode}}+\beta^{-1})+P\beta^{-1}))$
$\displaystyle=$
$\displaystyle~{}O(RLU(\mathcal{T}_{\mathrm{encode}}+n\cdot\mathcal{T}_{\mathrm{subtract}}+n\cdot\mathcal{T}_{\mathrm{decode}}+n\beta^{-1})+nLP\beta^{-1})$
$\displaystyle=$
$\displaystyle~{}O(\epsilon^{-4}\log^{6}(d/\delta)\log(nd)(d\log^{2}(d)+n\beta^{-1}\log^{2}(d))+n\epsilon^{-1}\log^{2}(d)\beta^{-1})$
$\displaystyle=$
$\displaystyle~{}O((d+n\cdot\mathrm{mmc}(l)^{2})\cdot\operatorname{poly}(1/\epsilon,\log(nd/\delta)))$

where the first step follows from the property of big $O$ notation, the second
step follows from the definition of $R,L,U,\mathcal{T}_{\mathrm{encode}}$,
$\mathcal{T}_{\mathrm{encode}},\mathcal{T}_{\mathrm{subtract}},\mathcal{T}_{\mathrm{decode}}$
(Theorem D.3) $,P$, the third step follows from merging the terms.

Thus, we complete the proof.

∎

Next, we analyze the space usage in our algorithm. We delay the proofs into
Section G.

######  Lemma 4.4 (Space complexity of our data structure, informal version of
Lemma G.1).

Our data structure (Algorithm 1 and 2) uses space

$\displaystyle
O(n(d+\mathrm{mmc}(l)^{2})\cdot\operatorname{poly}(1/\epsilon,\log(d/\delta))).$

##  5 Correctness of Our Algorithm

The correctness of our distance oracle is proved in the following lemma:

######  Lemma 5.1 (Query correctness).

Given a query point $q\in\mathbb{R}^{d}$, the procedure Query (Algorithm 7)
takes $q$ as input and approximately estimates
$\\{\mathrm{dst}_{i}\\}_{i\in[n]}$ the distance between $q$ and every $x_{i}$
with the norm $l$, such that for every $\mathrm{dst}_{i}$, with probability at
least $1-\delta$, we have

$\displaystyle(1-\epsilon)\cdot\|q-x_{i}\|_{\mathrm{sym}}\leq\mathrm{dst}_{i}\leq(1+\epsilon)\cdot\|q-x_{i}\|_{\mathrm{sym}}$

###### Proof.

Without loss of generality, we can consider a fixed $i\in[n]$. For simplicity,
we denote $x_{i}$ by $x$.

Let $v:=q-x$. By Lemma C.3, it is approximated by its layer vector
$\mathcal{L}(v)$, namely,

$\displaystyle\|v\|_{\mathrm{sym}}\leq\|\mathcal{L}(v)\|_{\mathrm{sym}}\leq(1+O(\epsilon))\|v\|_{\mathrm{sym}},$
(1)

where $\|\cdot\|_{\mathrm{sym}}$ is a symmetric norm, denoted also by
$l(\cdot)$.

We assume without loss of generality that $\epsilon\geq
1/\operatorname{poly}(d)$. Our algorithm maintains a data structure that
eventually produces a vector $\mathcal{J}(v)$, which is created with the layer
sizes $c_{1},c_{2},\dots,c_{P}$, where $c$’s denotes the estimated layer sizes
output by out data structure, and the $b$’s are the ground truth layer sizes.
We will show that with high probability, $\|\mathcal{J}(v)\|_{\mathrm{sym}}$
approximates $\|\mathcal{L}(v)\|_{\mathrm{sym}}$. Specifically, to achieve
$(1\pm\epsilon)$-approximation to $\|v\|_{\mathrm{sym}}$, we set the
approximation guarantee of the layer sets (Definition C.1) to be
$\epsilon_{1}:=O(\frac{\epsilon^{2}}{\log(d)})$ and the importance guarantee
to be $\beta_{0}:=O(\frac{\epsilon^{5}}{\mathrm{mmc}(l)^{2}\log^{5}(d)})$,
where $\mathrm{mmc}(l)$ is defined as Definition 1.3.

Observe that the number of non-empty layer sets
$P=O(\log_{\alpha}(d))=O(\log(d)/\epsilon)$. Let $E_{\mathrm{succeed}}$ denote
the event $(1-\epsilon_{1})b_{k}\leq c_{k}\leq b_{k}$. By Lemma F.1, it
happens with high probability $1-\delta$. Conditioned on this event.

Denote by $\mathcal{J}(v)$ the vector generated with the layer sizes given by
Line 35, and by $\mathcal{L}^{*}(v)$ the vector $\mathcal{L}(v)$ after
removing all buckets (Definition C.2) that are not $\beta$-contributing
(Definition C.5), and define $\mathcal{J}^{*}(v)$ similar to
$\mathcal{L}^{*}(v)$, where we set
$\beta:=\epsilon/P=O(\epsilon^{2}/\log(d))$. Every $\beta$-contributing layer
is necessarily $\beta_{0}$-important (Definition C.1) by Lemma C.7 and Lemma
C.8 and therefore satisfies $c_{k}\geq(1-\epsilon_{1})b_{k}$ (Lemma F.1). We
bound the error of $\|\mathcal{L}^{*}(v)\|_{\mathrm{sym}}$ by Lemma C.6,
namely,

$\displaystyle(1-O(\epsilon))\|\mathcal{L}(v)\|_{\mathrm{sym}}\leq(1-O(\log_{\alpha}d)\cdot\beta)\|\mathcal{L}(v)\|_{\mathrm{sym}}\leq\|\mathcal{L}^{*}(v)\|_{\mathrm{sym}}\leq\|\mathcal{L}(v)\|_{\mathrm{sym}}.$

where the first step follows from the definition of $\beta$, the second step
and the third step follow from Lemma C.6.

Then, we have

$\displaystyle\|\mathcal{J}(v)\|_{\mathrm{sym}}\geq$
$\displaystyle~{}\|\mathcal{J}^{*}(v)\|_{\mathrm{sym}}$ $\displaystyle=$
$\displaystyle~{}\|\mathcal{L}^{*}(v)\backslash\mathcal{L}_{k_{1}}(v)\cup\mathcal{J}_{k_{1}}(v)\dots\backslash\mathcal{L}_{k_{\kappa}}(v)\cup\mathcal{J}_{k_{\kappa}}(v)\|_{\mathrm{sym}}$
$\displaystyle\geq$
$\displaystyle~{}(1-\epsilon_{1})^{P}\|\mathcal{L}^{*}(v)\|_{\mathrm{sym}}$
$\displaystyle\geq$
$\displaystyle~{}(1-O(\epsilon))\|\mathcal{L}^{*}(v)\|_{\mathrm{sym}}.$ (2)

where the first step follows from monotonicity (Lemma B.1), the second step
follows from the definition of $\mathcal{J}^{*}(v)$, the third step follows
from Lemma C.4, and the fourth step follows from the definition of
$\epsilon_{1}$ and $P$.

Combining Eq. (1) and (5), we have

$\displaystyle(1-O(\epsilon))\cdot\|v\|_{\mathrm{sym}}\leq\|\mathcal{J}^{*}(v)\|_{\mathrm{sym}}\leq\|v\|_{\mathrm{sym}},$
(3)

which bounds the error of $\|\mathcal{J}^{*}(v)\|_{\mathrm{sym}}$ as required.
Note that, with Lemma C.6 we have

$\displaystyle(1-O(\epsilon))\cdot\|\mathcal{J}(v)\|_{\mathrm{sym}}\leq\|\mathcal{J}^{*}(v)\|_{\mathrm{sym}}\leq\|\mathcal{J}(v)\|_{\mathrm{sym}}$
(4)

Combining the Eq.(3) and (4) we have

$\displaystyle(1-O(\epsilon))\cdot\|v\|_{\mathrm{sym}}\leq\|\mathcal{J}(v)\|_{\mathrm{sym}}\leq(1+O(\epsilon))\cdot\|v\|_{\mathrm{sym}}$

Note that $E_{\mathrm{succeed}}$ has a failure probability of $\delta$. Thus,
we complete the proof. ∎

##  6 Conclusion

Similarity search is the backbone of many large-scale applications in machine-
learning, optimization, databases and computational geometry. Our work
strengthens and unifies a long line of work on metric embeddings and
sketching, by presenting the first Distance Oracle _for any symmetric norm_ ,
with nearly-optimal query and update times. The generality of our data
structure allows to apply it as a _black-box_ for data-driven _learned_
symmetric distance metrics [19] and in various optimization problems involving
symmetric distances.

Our work raises several open questions for future study:

  * •

The efficiency of our data structure depends on $\mathrm{mmc}(l)$, the
concentration property of the symmetric norm. Is this dependence necessary?

  * •

Can we generalize our data structure to certain _asymmetric norms_ ?

We believe our work is also likely to influence other fundamental problems in
high-dimensional optimization and search, e.g, kernel linear regression,
geometric sampling and near-neighbor search.

## References

  * AC [09] Nir Ailon and Bernard Chazelle.  The fast johnson–lindenstrauss transform and approximate nearest neighbors.  SIAM Journal on computing, 39(1):302–322, 2009.
  * AFS [12] Andreas Argyriou, Rina Foygel, and Nathan Srebro.  Sparse prediction with the $k$-support norm.  Advances in Neural Information Processing Systems (NeurIPS), 25, 2012.
  * Alm [19] Josh Alman.  An illuminating algorithm for the light bulb problem.  In 2nd Symposium on Simplicity in Algorithms (SOSA). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
  * ALS+ [18] Alexandr Andoni, Chengyu Lin, Ying Sheng, Peilin Zhong, and Ruiqi Zhong.  Subspace embedding and linear regression with orlicz norm.  In International Conference on Machine Learning (ICML), pages 224–233. PMLR, 2018.
  * AMS [99] Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  Journal of Computer and system sciences, 58(1):137–147, 1999.
  * ANN+ [17] Alexandr Andoni, Huy L Nguyen, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten.  Approximate near neighbors for general symmetric norms.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 902–913, 2017.
  * ANN+ [18] Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten.  Hölder homeomorphisms and approximate nearest neighbors.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 159–169. IEEE, 2018.
  * AWY [14] Amir Abboud, Ryan Williams, and Huacheng Yu.  More applications of the polynomial method to algorithm design.  In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 218–230. SIAM, 2014.
  * AWY [18] Josh Alman, Joshua R Wang, and Huacheng Yu.  Cell-probe lower bounds from online communication complexity.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1003–1012, 2018.
  * BBC+ [17] Jarosław Błasiok, Vladimir Braverman, Stephen R Chestnut, Robert Krauthgamer, and Lin F Yang.  Streaming symmetric norms via measure concentration.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 716–729, 2017.
  * Bha [97] Rajendra Bhatia.  Matrix analysis, volume 169 of.  Graduate texts in mathematics, 1997.
  * BYJKS [04] Ziv Bar-Yossef, Thathachar S Jayram, Ravi Kumar, and D Sivakumar.  An information statistics approach to data stream and communication complexity.  Journal of Computer and System Sciences, 68(4):702–732, 2004.
  * CCF [04] Moses Charikar, Kevin C. Chen, and Martin Farach-Colton.  Finding frequent items in data streams.  Theor. Comput. Sci., 312(1):3–15, 2004.
  * Che [52] Herman Chernoff.  A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.  The Annals of Mathematical Statistics, pages 493–507, 1952.
  * CLP+ [20] Beidi Chen, Zichang Liu, Binghui Peng, Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, and Christopher Re.  Mongoose: A learnable lsh framework for efficient neural network training.  In International Conference on Learning Representations (ICLR), 2020\.
  * CMF+ [20] Beidi Chen, Tharun Medini, James Farwell, Charlie Tai, Anshumali Shrivastava, et al.  Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems.  Proceedings of Machine Learning and Systems, 2:291–306, 2020.
  * CN [20] Yeshwanth Cherapanamjeri and Jelani Nelson.  On adaptive distance estimation.  In Advances in Neural Information Processing Systems, 2020.
  * CS [09] Youngmin Cho and Lawrence Saul.  Kernel methods for deep learning.  Advances in neural information processing systems, 22, 2009.
  * DKJ+ [07] Jason V Davis, Brian Kulis, Prateek Jain, Suvrit Sra, and Inderjit S Dhillon.  Information-theoretic metric learning.  In Proceedings of the 24th international conference on Machine learning, pages 209–216, 2007.
  * GMS [86] M Gromov, V Milman, and G Schechtman.  Asymptotic theory of finite dimensional normed spaces, volume 1200 of lectures notes in mathematics, 1986.
  * GPPR [04] Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz.  Distance labeling in graphs.  Journal of Algorithms, 53(1):85–112, 2004.
  * HIKP [12] Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price.  Nearly optimal sparse fourier transform.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing (STOC), pages 563–578, 2012.
  * HKNS [15] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak.  Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture.  In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 21–30, 2015.
  * Ind [06] Piotr Indyk.  Stable distributions, pseudorandom generators, embeddings, and data stream computation.  Journal of the ACM (JACM), 53(3):307–323, 2006.
  * IRW [17] Piotr Indyk, Ilya Razenshteyn, and Tal Wagner.  Practical data-dependent metric compression with provable guarantees.  Advances in Neural Information Processing Systems, 30, 2017.
  * IW [05] Piotr Indyk and David Woodruff.  Optimal approximations of the frequency moments of data streams.  In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 202–208, 2005.
  * JKDG [08] Prateek Jain, Brian Kulis, Inderjit S Dhillon, and Kristen Grauman.  Online metric learning and fast similarity search.  In NIPS, volume 8, pages 761–768. Citeseer, 2008.
  * JL [84] William B Johnson and Joram Lindenstrauss.  Extensions of lipschitz mappings into a hilbert space.  Contemporary mathematics, 26(189-206):1, 1984.
  * KNPW [11] Daniel M Kane, Jelani Nelson, Ely Porat, and David P Woodruff.  Fast moment estimation in data streams in optimal space.  In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 745–754, 2011.
  * KNW [10] Daniel M Kane, Jelani Nelson, and David P Woodruff.  On the exact space complexity of sketching and streaming small norms.  In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1161–1178. SIAM, 2010.
  * LDFU [13] Yichao Lu, Paramveer Dhillon, Dean P Foster, and Lyle Ungar.  Faster ridge regression via the subsampled randomized hadamard transform.  In Advances in neural information processing systems (NIPS), pages 369–377, 2013.
  * LNNT [16] Kasper Green Larsen, Jelani Nelson, Huy L Nguyên, and Mikkel Thorup.  Heavy hitters via cluster-preserving clustering.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 61–70. IEEE, 2016.
  * LNRW [19] Jerry Li, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten.  On mean estimation for general norms with statistical queries.  In Conference on Learning Theory (COLT), pages 2158–2172. PMLR, 2019.
  * LSV [18] Yin Tat Lee, Zhao Song, and Santosh S Vempala.  Algorithmic theory of odes and sampling from well-conditioned logconcave densities.  arXiv preprint arXiv:1812.06243, 2018.
  * LW [17] Kasper Green Larsen and Ryan Williams.  Faster online matrix-vector multiplication.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2182–2189. SIAM, 2017.
  * MMR [22] Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn.  Performance of johnson–lindenstrauss transform for k-means and k-medians clustering.  SIAM Journal on Computing, (0):STOC19–269, 2022.
  * MPS [14] Andrew M McDonald, Massimiliano Pontil, and Dimitris Stamos.  Spectral k-support norm regularization.  Advances in neural information processing systems, 27, 2014.
  * NS [19] Vasileios Nakos and Zhao Song.  Stronger l2/l2 compressed sensing; without iterating.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 289–297, 2019.
  * Pag [13] Rasmus Pagh.  Compressed matrix multiplication.  ACM Transactions on Computation Theory (TOCT), 5(3):1–17, 2013\.
  * Pel [00] David Peleg.  Proximity-preserving labeling schemes.  Journal of Graph Theory, 33(3):167–176, 2000.
  * Pri [11] Eric Price.  Efficient sketches for the set query problem.  In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 41–56, 2011.
  * SS [02] Michael Saks and Xiaodong Sun.  Space lower bounds for distance approximation in the data stream model.  In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 360–369, 2002.
  * SSSSC [11] Shai Shalev-Shwartz, Yoram Singer, Nathan Srebro, and Andrew Cotter.  Pegasos: Primal estimated sub-gradient solver for svm.  Mathematical programming, 127(1):3–30, 2011.
  * SSWZ [22] Zhao Song, Baocheng Sun, Omri Weinstein, and Ruizhe Zhang.  Sparse fourier transform over lattices: A unified approach to signal reconstruction.  http://arxiv.org/abs/2205.00658, 2022.
  * SSX [21] Anshumali Shrivastava, Zhao Song, and Zhaozhuo Xu.  Sublinear least-squares value iteration via locality sensitive hashing.  arXiv preprint arXiv:2105.08285, 2021.
  * SWY+ [19] Zhao Song, Ruosong Wang, Lin Yang, Hongyang Zhang, and Peilin Zhong.  Efficient symmetric norm regression via linear sketching.  Advances in Neural Information Processing Systems, 32, 2019.
  * SWZ [19] Zhao Song, David Woodruff, and Peilin Zhong.  Towards a zero-one law for column subset selection.  Advances in Neural Information Processing Systems, 32, 2019.
  * SXZ [22] Zhao Song, Zhaozhuo Xu, and Lichen Zhang.  Speeding up sparsification with inner product search data structures.  arXiv preprint arXiv:2204.03209, 2022.
  * TZ [12] Mikkel Thorup and Yin Zhang.  Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation.  SIAM J. Comput., 41(2):293–331, 2012.
  * Val [12] Gregory Valiant.  Finding correlations in subquadratic time, with applications to learning parities and juntas.  In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 11–20. IEEE, 2012.
  * WP [11] Oren Weimann and David Peleg.  A note on exact distance labeling.  Information processing letters, 111(14):671–673, 2011.
  * XSS [21] Zhaozhuo Xu, Zhao Song, and Anshumali Shrivastava.  Breaking the linear iteration cost barrier for some well-known conditional gradient methods using maxip data-structures.  Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.

#### Roadmap.

We divide the appendix into the following sections. Section A gives the
preliminaries for our work. Section B introduces some useful properties of
symmetric norms. Section C gives the proofs for the layer approximation
technique. Section D states the formal version of our main theorem and
algorithms. Section E gives more details about the time complexity proofs.
Section F gives some details about the correctness proofs. Section G shows the
space complexity of our algorithm. Section H states a streaming lower bound
for the norm estimation problem and shows that our result is tight in this
case. Section I gives an instantiation of the sparse recovery data structure
(BatchHeavyHitter) that simplifies the analysis in prior work.

##  Appendix A Preliminaries

In Section A.1, we define the notations we use in this paper. In Section A.2,
we introduce some probability tools. In Section A.3, we define $p$-stable
distributions.

###  A.1 Notations

For any positive integer $n$, we use $[n]$ to denote a set
$\\{1,2,\cdots,n\\}$. We use $\operatorname*{{\mathbb{E}}}[]$ to denote the
expectation. We use $\Pr[]$ to denote the probability. We use
$\operatorname*{\mathrm{Var}}[]$ to denote the variance. We define the unit
vector
$\xi^{(d_{1})}:=\frac{1}{\sqrt{d_{1}}}(1,1,1,,\dots,1,0,\dots,0)\in\mathbb{R}^{d}$,
for any $d_{1}\in[d]$, which has $d_{1}$ nonzero coordinates. We abuse the
notation to write $\xi^{(d_{1})}\in\mathbb{R}^{d_{1}}$ by removing zero
coordinates, and vice-versa by appending zeros. We use $\|x\|_{2}$ to denote
entry-wise $\ell_{2}$ norm of a vector. We use $\|x\|_{\mathrm{sym}}$ to
denote the symmetric norm of a vector $x$.

We define tail as follows

######  Definition A.1 (Tail of a vector).

For a given $x\in\mathbb{R}^{d}$ and an integer $k$, we use
$x_{\overline{[k]}}$ or $x_{\mathrm{tail}(k)}$ to denote the vector that
without largest top-$k$ values (in absolute).

###  A.2 Probability Tools

We state some useful inequalities in probability theory in below.

######  Lemma A.2 (Chernoff bound [14]).

Let $X=\sum_{i=1}^{n}X_{i}$, where $X_{i}=1$ with probability $p_{i}$ and
$X_{i}=0$ with probability $1-p_{i}$, and all $X_{i}$ are independent. Let
$\mu=\operatorname*{{\mathbb{E}}}[X]=\sum_{i=1}^{n}p_{i}$. Then

  * •

$\Pr[X\geq(1+\delta)\mu]\leq\exp(-\delta^{2}\mu/3)$, $\forall\delta>0$;

  * •

$\Pr[X\leq(1-\delta)\mu]\leq\exp(-\delta^{2}\mu/2)$, $\forall 0<\delta<1$.

######  Lemma A.3 (Chebyshev’s inequality).

Let $X$ be a random variable with finite expected value $\mu$ and finite non-
zero variance $\sigma^{2}$. Then for any real number $k>0$,

$\displaystyle\Pr[|X-\mu|\geq k\sigma]\leq\frac{1}{k^{2}}.$

######  Theorem A.4 (Levy’s isoperimetric inequality, [20]).

For a continuous function $f:S^{d-1}\rightarrow\mathbb{R}$, Let $M_{f}$ be the
median of $f$, i.e., $\mu(\\{x:f(x)\leq M_{f}\\})\geq 1/2$ and
$\mu(\\{x:f(x)\geq M_{f}\\})\geq 1/2$, where $\mu(\cdot)$ is the Haar
probability measure on the unit sphere $S^{d-1}$. Then

$\displaystyle\mu(\\{x:f(x)=M_{f}\\}_{\epsilon})\geq
1-\sqrt{\pi/2}e^{-\epsilon^{2}d/2},$

where for a set $A\subset S^{d-1}$ we denote
$A_{\epsilon}:=\\{x:l_{2}(x,A)\leq\epsilon\\}$ and $l_{2}(x,A):=\inf_{y\in
A}\|x-y\|_{2}$.

###  A.3 Stable Distributions

We define $p$-stable distributions.

######  Definition A.5 ([24]).

A distribution $\mathcal{D}_{p}$ is called p-stable, if there exists $p\geq 0$
such that for any $d$ real numbers $a_{1},a_{2},\dots,a_{d}$ and i.i.d.
variables $x_{1},x_{2},\dots,x_{d}$ from distribution $\mathcal{D}_{p}$. the
random variable $\sum_{i=1}^{d}a_{i}x_{i}$ has the same distribution as the
variable $\|a\|_{p}y$, where y is a random variable from distribution
$\mathcal{D}_{p}$.

##  Appendix B Symmetric Norms

In this section, we give several technical tools for the symmetric norms. In
Section B.1, we show the monotonicity of symmetric norms. In Section B.2, we
show the concentration properties of symmetric norms. In Section B.3, we show
some properties of the median of symmetric norm.

###  B.1 Monotonicity Property of Symmetric Norm

######  Lemma B.1 (Monotonicity of Symmetric Norms, see e.g. Proposition
IV.1.1 in [11] ).

If $\|\cdot\|_{\mathrm{sym}}$ is a symmetric norm and $x,y\in\mathbb{R}^{d}$
satisfy that for all $i\in[d]$ , $|x_{i}|\leq|y_{i}|$, then
$\|x\|_{\mathrm{sym}}\leq\|y\|_{\mathrm{sym}}$.

###  B.2 Concentration Property of Symmetric Norms

Let us give the results of concentration of measure as followed. The following
tools and proofs can be found in [10]. However, for the completeness, we state
them in below.

######  Lemma B.2 (Concentration of $M_{l}$).

For every norm $l$ on $\mathbb{R}^{d}$, if $x\in S^{d-1}$ is drawn uniformly
at random according to Haar measure on the sphere, then

$\displaystyle\Pr[\|x\|_{l}-M_{l}|>\frac{2\mathfrak{b}_{l}}{\sqrt{d}}]<\frac{1}{3}$

###### Proof.

With Theorem A.4, we know that, for a random $x$ distributed according to the
Haar measure on the $l_{2}$-sphere, with probability at least
$1-\sqrt{\pi/2}e^{-2}>\frac{2}{3}$, we can always find some $y\in S^{d-1}$,
such that

$\displaystyle\|x-y\|_{2}$ $\displaystyle\leq\frac{2}{\sqrt{d}},\text{ and}$
$\displaystyle\|y\|_{l}$ $\displaystyle=M_{l}.$

If we view the norm $l$ as a function, then it is obvious that it is
$\mathfrak{b}_{l}$-Lipschitz with respect to $\|\cdot\|_{2}$, so that we have

$\displaystyle|\|x\|_{l}-M_{l}|=$ $\displaystyle~{}|\|x\|_{l}-\|y\|_{l}|$
$\displaystyle\leq$ $\displaystyle~{}\|x-y\|_{l}$ $\displaystyle\leq$
$\displaystyle~{}\mathfrak{b}_{l}\|x-y\|$ $\displaystyle\leq$
$\displaystyle~{}\frac{2\mathfrak{b}_{l}}{\sqrt{d}}$

where the first step follows from the definition of $y$, the second step
follows from triangle inequality, the third step follows from that norm $l$ is
$\mathfrak{b}_{l}$-Lipschitz with respect to $\|\cdot\|_{2}$, and the last
step follows from the definition of $y$.

Thus, we complete the proof. ∎

######  Lemma B.3 (Concentration inequalities for norms ).

For every $d>0$, and norm $l$ on $\mathbb{R}^{n}$, there is a vector $x\in
S^{d-1}$ satisfying

  * •

$|\|x\|_{\infty}-M_{l_{\infty}^{(d)}}|\leq 2/\sqrt{d}$

  * •

$|\|x\|_{l}-M_{l^{(d)}}|\leq 2\mathfrak{b}_{l^{(d)}}/\sqrt{d}$, and

  * •

$|\\{i:|x_{i}|>\frac{1}{K\sqrt{d}}\\}|>\frac{d}{2}$ for some universal
constant $K$.

###### Proof.

Let $x$ be drawn uniformly randomly from a unit sphere. From Lemma B.2, we
have

$\displaystyle\Pr[|\|x\|_{l}-M_{l_{\infty}^{(d)}}|>\frac{2}{\sqrt{d}}]$
$\displaystyle~{}<\frac{1}{3}$ $\displaystyle
and\quad\Pr[|\|x\|_{l}-M_{l^{(d)}}|>\frac{2\mathfrak{b}_{l}}{\sqrt{d}}]$
$\displaystyle~{}<\frac{1}{3}.$

Define $\tau(x,t):=|\\{i\in[d]:|x_{i}|<t\\}|$. Now we are giving the proof to
show that, for a constant $K$, over a choice of $x$, we have
$\tau(x,\frac{1}{K\sqrt{d}})<\frac{d}{2}$ with probability lager than $2/3$ .

Let’s consider an random vector $z\in\mathbb{R}^{d}$, such that each entry
$z_{i}$ is independent standard normal random variable. It is well known that
$\frac{z}{\|z\|_{2}}$ is distributed uniformly over a sphere, so it has the
same distribution as $x$. There is a universal constant $K_{1}$ such that

$\displaystyle\Pr[\|z\|_{2}>K_{1}\sqrt{d}]<\frac{1}{6},$

and similarly, there is a constant $K_{2}$, such that

$\displaystyle\Pr[|z_{i}|<\frac{1}{K_{2}}]<\frac{1}{12}.$

Therefore, by Markov bound we have

$\displaystyle\Pr[\tau(z,\frac{1}{K_{2}})>\frac{d}{2}]<\frac{1}{6}.$

By union bound, with probability larger than $2/3$, it holds simultaneously
that

$\displaystyle\|z\|_{2}~{}\leq
K_{1}\sqrt{d}\quad\text{and}\quad\tau(z,\frac{1}{K_{2}})~{}<\frac{d}{2},$

which imply:

$\displaystyle\tau(\frac{z}{\|z\|_{2}},\frac{1}{K_{1}K_{2}\sqrt{d}})<\frac{d}{2}.$

Now, by union bound, a random vector $x$ satisfies all of the conditions in
the statement of the lemma with positive probability.

Thus, we complete the proof. ∎

###  B.3 Median of Symmetric Norm

We state a well-known fact before introducing Lemma B.5.

######  Fact B.4 (Concentration for median on infinity norm, [20]).

There are absolute constants $0<\gamma_{1}<\gamma_{2}$ such that for every
integer $d\geq 1$,

$\displaystyle\gamma_{1}\sqrt{\log(d)/d}\leq
M_{l^{(d)}_{\infty}}\leq\gamma_{2}\sqrt{\log(d)/d}$

We now give the following Lemma, which says that the $l$-norm of the
(normalized) unit vector $\xi^{(d)}$ is closely related to the median of the
norm. We are considering this vector because that it is related to a single
layer of $\mathcal{L}$.

######  Lemma B.5 (Flat Median Lemma ).

Let $l:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be a symmetric norm. Then

$\displaystyle\lambda_{1}M_{l}/\sqrt{\log(d)}\leq
l(\xi^{(d)})\leq\lambda_{2}M_{l}$

where $\lambda_{1},\lambda_{2}>0$ are absolute constants.

We notice that the first inequality is tight for $l_{\infty}$.

###### Proof.

Using Lemma B.3, we can find a vector $x\in S^{d-1}$ and a constant
$\lambda>0$ satisfying

  * •

$|\|x\|_{\infty}-M_{l_{\infty}}|\leq\lambda\sqrt{1/d}$

  * •

$|\|x\|_{l}-M_{l}|\leq\lambda\mathfrak{b}_{l}/\sqrt{d}$, and

  * •

$|\\{i:|x_{i}|>\frac{1}{K\sqrt{d}}\\}|>\frac{d}{2}$ for some universal
constant $K$.

With Fact B.4, $M_{l_{\infty}}=\Theta(\sqrt{\log(d)/d})$. On the other hand,
let $\mathrm{mmc}(l)$ be defined as Definition 1.3, we have

$\displaystyle\mathrm{mmc}(l)\leq\gamma\sqrt{d}$

for sufficiently small $\gamma$, thus

$\displaystyle\frac{\lambda\mathfrak{b}_{l}}{\sqrt{d}}<M_{l}.$

So with constants $\gamma_{1},\gamma_{2}>0$, we have

$\displaystyle\gamma_{1}M_{l}$
$\displaystyle~{}\leq\|x\|_{l}\leq\gamma_{2}M_{l}$ $\displaystyle
and\quad\gamma_{1}\sqrt{\log(d)/d}$
$\displaystyle~{}\leq\|x\|_{\infty}\leq\gamma_{2}\sqrt{\log(d)/d}.$

So that we have

$\displaystyle|x|\leq\gamma_{2}\sqrt{\log(d)}\cdot\xi^{(d)},$

where the inequality is entry-wise, and with monotonicity of symmetric norms
(Lemma B.1), we have

$\displaystyle\gamma_{1}\leq\|x\|_{l}\leq\gamma_{2}\sqrt{\log(d)}\cdot\|\xi^{(d)}\|_{l}.$

Now we move to the second condition of the lemma, we first let
$M=\\{i:|x_{i}|>\frac{1}{K\sqrt{d}}\\}$. As $|M|>\frac{d}{2}$, we can find a
permutation $\pi$ satisfying

$\displaystyle[d]-M\in\pi(M).$

We define a vector $\pi(x)$ to be the vector by applying the permutation $\pi$
to each entry of $x$. Denote by $|x|$ the vector of taking absolute value of
$x$ entry-wise. Notice $|x|+\pi(|x|)>\frac{\xi^{(d)}}{K}$ entry-wise, so that
we have

$\displaystyle\frac{1}{K}\cdot\|\xi^{(d)}\|_{l}\leq$
$\displaystyle~{}\||x|+\pi(|x|)\|_{l}$ $\displaystyle\leq$
$\displaystyle~{}\||x|\|_{l}+\|\pi(|x|)\|_{l}$ $\displaystyle=$
$\displaystyle~{}2\|x\|_{l}$ $\displaystyle\leq$
$\displaystyle~{}2\gamma_{2}M_{l},$

where the first step follows from the monotonicity of symmetric norm (Lemma
B.1), the second step follows from the triangle inequality, the third step
follows from the definition of $\pi$, and the last step follows from the
definition of $\gamma_{2}$.

Thus, we complete the proof. ∎

The following lemma shows the monotonicity of the median (in $d$), a very
useful property in the norm approximation.

######  Lemma B.6 (Monotonicity of Median).

Let $l:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be a symmetric norm. For all
$d_{1}\leq d_{2}$, where $d_{1},d_{2}\in[n]$, let $\mathrm{mmc}(l)$ be defined
as Definition 1.3, we have

$\displaystyle
M_{l^{(d_{1})}}\leq\lambda\cdot\mathrm{mmc}(l)\cdot\sqrt{\log(d_{1})}M_{l^{(d_{2})}},$

where $\lambda>0$ is an absolute constant.

###### Proof.

By Lemma B.5 and the fact that $\xi^{(d_{1})}$ is also a vector in
$S^{d_{2}-1}$,

$\displaystyle\lambda
M_{l^{(d_{1})}}/\sqrt{\log(d_{1})}\leq\|\xi^{(d_{1})}\|_{l}\leq\mathfrak{b}_{l^{(d_{2})}}\leq\mathrm{mmc}(l)M_{l^{(d_{2})}}.$

Thus, we complete the proof. ∎

##  Appendix C Analysis of Layer Approximation

In this section, we show how to estimate the symmetric norm $l(\cdot)$ of a
vector using the layer vectors. Section C.1 gives the definitions of layer
vectors and important layers. Section C.2 shows that we can approximate the
exact value of the norm and the layer vector. Section C.3 defines the
contributing layer and shows its concentration property. Section C.4 proves
that contributing layers are also important.

Throughout this section, let $\epsilon\in(0,1)$ be the precision, $\alpha>0$
and $\beta\in(0,1]$ be some parameters depending on $d$, $\epsilon$ and
$\mathrm{mmc}(l)$, where $\mathrm{mmc}(l)$ is defined as Definition 1.3.
Furthermore, we assume $\mathrm{mmc}(l)\leq\gamma\sqrt{d}$, for constant
parameter $0\leq\gamma\ll 1/2$ small enough.222We note that beyond this
regime, the streaming lower bound in Theorem H.2 implies that a linear-sized
memory (time) is required to approximate the norm.

###  C.1 Layer Vectors and Important Layers

######  Definition C.1 (Important Layers).

For $v\in\mathbb{R}^{d}$, define layer $i\in\mathbb{N}_{+}$ as

$\displaystyle B_{i}:=\\{j\in[d]:\alpha^{i-1}<|v_{j}|\leq\alpha^{i}\\},$

and denote its size by $b_{i}:=|B_{i}|$. We denote the number of non-zero
$b_{i}$’s by $t$, the number of non-empty layers. And we say that layer-$i$ is
$\beta$-important if

  * •

$b_{i}>\beta\cdot\sum_{j=i+1}^{t}b_{j}$

  * •

$b_{i}\alpha^{2i}\geq\beta\cdot\sum_{j\in[i]}b_{j}\alpha^{2j}$

With out loss of generality, We restrict the entries of the vector $v$ to be
in $[-m,m]$, and that $m=\operatorname{poly}(d)$. Then we know that the number
of non-zero $b_{i}$’s is at most $P=O(\log_{\alpha}(d))$. In the view of
$\ell_{2}$-norm, for an arbitrary vector $v\in\mathbb{R}^{d}$, if we normalize
it to a unit vector, then the absolute value of each non-zero entry is at
least $1/\operatorname{poly}(d)$. In order to simplify our analysis and
algorithm for approximating $\|v\|_{\mathrm{sym}}$, we introduce the notations
we use as follows.

######  Definition C.2 (Layer Vectors and Buckets).

For each $i\in[P]$, let $\alpha^{i}\cdot{\bf 1}_{b_{i}}\in\mathbb{R}^{b_{i}}$
denote a vector that has length $b_{i}$ and every entry is $\alpha^{i}$.
Define the layer vector for $v\in\mathbb{R}^{d}$ with integer coordinates to
be

$\displaystyle\mathcal{L}(v):=(\alpha^{1}\cdot{\bf
1}_{b_{1}},\alpha^{2}\cdot{\bf 1}_{b_{2}},\cdots,\alpha^{P}\cdot{\bf
1}_{b_{P}},0\cdot{\bf 1}_{d-\sum_{j\in[P]}b_{j}})\in\mathbb{R}^{d};$

and define the $i$-th bucket of $\mathcal{L}(v)$ to be

$\displaystyle\mathcal{L}_{i}(v):=(0\cdot{\bf
1}_{b_{1}+b_{2}+\dots+b_{i-1}},\alpha^{i}\cdot{\bf 1}_{b_{i}},0\cdot{\bf
1}_{d-\sum_{j\in[i]}b_{j}})\in\mathbb{R}^{d};$

We also define $\mathcal{J}(v)$ and $\mathcal{J}_{i}(v)$ as above by replacing
$\\{b_{i}\\}$ with the approximated values $\\{c_{i}\\}$. Denote
$\mathcal{L}(v)\backslash\mathcal{L}_{i}(v)$ as the vector with the $i$-th
bucket of $\mathcal{L}(v)$ replaced by 0. We also denote
$(\mathcal{L}(v)\backslash\mathcal{L}_{i}(v))\cup\mathcal{J}_{i}(v)$ as the
vector by replacing the $i$-th bucket of $\mathcal{L}(v)$ with
$\mathcal{J}_{i}(v)$, i.e.,

$\displaystyle(\mathcal{L}(v)\backslash\mathcal{L}_{i}(v))\cup\mathcal{J}_{i}(v):=(\alpha^{1}\cdot{\bf
1}_{b_{1}},\alpha^{2}\cdot{\bf 1}_{b_{2}},\cdots,\alpha^{i}\cdot{\bf
1}_{c_{i}},\cdots,\alpha^{P}\cdot{\bf 1}_{b_{P}},0\cdot{\bf
1}_{d-\sum_{j\in[P]}b_{j}+b_{i}-c_{i}})\in\mathbb{R}^{d};$

###  C.2 Approximated Layers Provides a Good Norm Approximation

We now proof that, $\|v\|_{\mathrm{sym}}$ can be approximated by using layer
vector $V$. We first choose a base to be $\alpha:=1+O(\epsilon)$.

######  Lemma C.3 (Approximattion with Layer Vector).

For all $v\in\mathbb{R}^{d}$, we have

$\displaystyle\|\mathcal{L}(v)\|_{\mathrm{sym}}/\alpha\leq\|v\|_{\mathrm{sym}}\leq\|\mathcal{L}(v)\|_{\mathrm{sym}}.$

###### Proof.

The lemma follows from the monotonicity of symmetric norms(Lemma B.1)
directly. ∎

The next key lemma shows that $\|\mathcal{J}(v)\|_{\mathrm{sym}}$ is a good
approximation to $\|\mathcal{L}(v)\|_{\mathrm{sym}}$.

######  Lemma C.4 (Bucket Approximation ).

For every layer $i\in[P]$,

  * •

if $c_{i}\leq b_{i}$, then
$\|(\mathcal{L}(v)\backslash\mathcal{L}_{i}(v))\cup\mathcal{J}_{i}(v)\|_{\mathrm{sym}}\leq\|\mathcal{L}(v)\|_{\mathrm{sym}}$;

  * •

if $c_{i}\geq(1-\epsilon)b_{i}$, then
$\|(\mathcal{L}(v)\backslash\mathcal{L}_{i}(v))\cup\mathcal{J}_{i}(v)\|_{\mathrm{sym}}\geq(1-\epsilon)\|\mathcal{L}(v)\|_{\mathrm{sym}}$.

###### Proof.

With the monotonicity of norm (Lemma B.1), the upper bound is quite obvious.
So we just focus on the lower bound. Let us take the vector

$\displaystyle\mathcal{J}_{i}(v):=(0\cdot{\bf
1}_{c_{1}+c_{2}+\dots+c_{i-1}},\alpha^{i}\cdot{\bf
1}_{c_{i}},0,\cdots,0)\in\mathbb{R}^{d};$

Here we define $\mathcal{K}(v):=\mathcal{L}(v)-\mathcal{L}_{i}(v)$. Then
notice that $\mathcal{K}(v)+\mathcal{J}_{i}(v)$ is a permutation of the vector
$(\mathcal{L}(v)\backslash\mathcal{L}_{i}(v))\cup\mathcal{J}_{i}(v)$. We will
then show that, under assumptions of the lemma, we have

$\displaystyle\|\mathcal{K}(v)+\mathcal{J}_{i}(v)\|_{\mathrm{sym}}\geq(c_{i}/b_{i})\|\mathcal{L}(v)\|_{\mathrm{sym}}.$

Assume a vector $v\in\mathbb{R}^{d}$ and a permutation $\pi\in\Sigma_{d}$, we
define a vector $\pi(x)$ to be the vector by applying the permutation $\pi$ to
each entry of $x$. Using the property of the symmetric norm, we have that
$\|v\|_{\mathrm{sym}}=\|\pi(v)\|_{\mathrm{sym}}$. Consider a set of
permutations that are cyclic shifts over the non-zero coordinates of
$\mathcal{L}_{i}$, and do not move any other coordinates. That is, there is
exactly $b_{i}$ permutations in $S$, and for every $\pi\in S$, we have
$\pi(\mathcal{K}(v))=\mathcal{K}(v)$. By the construction of $S$, we have,

$\displaystyle\sum_{\pi\in S}\pi(\mathcal{J}_{i}(v))=c_{i}\mathcal{L}_{i}(v)$

and therefore $\sum_{\pi\in
S}\pi(\mathcal{K}(v)+\mathcal{J}_{i}(v))=c_{i}\mathcal{L}_{i}(v)+b_{i}\mathcal{K}(v)$.
As the vectors $\mathcal{L}_{i}(v)$ and $\mathcal{K}(v)$ have disjoint
support, by monotonicity of symmetric norm (Lemma B.1) with respect to each
coordinates we can deduce
$\|c_{i}\mathcal{L}_{i}(v)+b_{i}\mathcal{K}(v)\|_{\mathrm{sym}}\geq\|c_{i}(\mathcal{L}_{i}(v)+\mathcal{K}(v))\|_{\mathrm{sym}}$.
By plugging those together,

$\displaystyle c_{i}\|\mathcal{L}_{i}(v)+\mathcal{K}(v)\|_{\mathrm{sym}}\leq$
$\displaystyle~{}\|c_{i}\mathcal{L}_{i}(v)+b_{i}\mathcal{K}(v)\|_{\mathrm{sym}}$
$\displaystyle=$ $\displaystyle~{}\|\sum_{\pi\in
S}\pi(\mathcal{J}_{i}(v)+\mathcal{K}(v))\|_{\mathrm{sym}}$ $\displaystyle\leq$
$\displaystyle~{}\sum_{\pi\in
S}\|\pi(\mathcal{J}_{i}(v)+\mathcal{K}(v))\|_{\mathrm{sym}}$ $\displaystyle=$
$\displaystyle~{}b_{i}\|\pi(\mathcal{J}_{i}(v)+\mathcal{K}(v))\|_{\mathrm{sym}}$

where the first step follows from
$c_{i}\|\mathcal{L}_{i}(v)+\mathcal{K}(v)\|_{\mathrm{sym}}=\|c_{i}(\mathcal{L}_{i}(v)+\mathcal{K}(v))\|_{\mathrm{sym}}$
and the monotonicity of the norm $l$, the second step follows from
$\sum_{\pi\in
S}\pi(\mathcal{J}_{i}(v)+\mathcal{K}(v))=c_{i}\mathcal{L}_{i}(v)+b_{i}\mathcal{K}(v)$,
the third step follows from triangle inequality, and the last step follows
from the property of symmetric norm and $|S|=b_{i}$.

Hence,

$\displaystyle\|\mathcal{J}_{i}(v)+\mathcal{K}(v)\|_{\mathrm{sym}}\geq\frac{c_{i}}{b_{i}}\|\mathcal{L}(v)\|_{\mathrm{sym}}\geq(1-\epsilon)\|\mathcal{L}(v)\|_{\mathrm{sym}},$

Thus, we complete the proof. ∎

###  C.3 Contributing Layers

######  Definition C.5 (Contributing Layers).

For $i\in[P]$, layer $i$ is called $\beta$-contributing if

$\displaystyle\|\mathcal{L}_{i}(v)\|_{\mathrm{sym}}\geq\beta\|\mathcal{L}(v)\|_{\mathrm{sym}}.$

######  Lemma C.6 (Concentration with contributing layers).

Let $\mathcal{L}^{*}(v)$ be the vector obtained from $V$ by removing all
layers that are not $\beta$-contributing. Then

$\displaystyle(1-O(\log_{\alpha}(d))\cdot\beta)\cdot\|\mathcal{L}(v)\|_{\mathrm{sym}}\leq\|\mathcal{L}^{*}(v)\|_{\mathrm{sym}}\leq\|\mathcal{L}(v)\|_{\mathrm{sym}}.$

###### Proof.

Let $i_{1},\dots,i_{k}\in[P]$ be the layers that are not $\beta$\-
contributing.

Then we apply the triangle inequality and have,

$\displaystyle\|\mathcal{L}(v)\|_{\mathrm{sym}}\geq$
$\displaystyle~{}\|\mathcal{L}(v)\|_{\mathrm{sym}}-\|\mathcal{L}_{i_{1}}(v)\|_{\mathrm{sym}}-\dots-\|\mathcal{L}_{i_{k}}(v)\|_{\mathrm{sym}}$
$\displaystyle\geq$
$\displaystyle~{}(1-k_{\beta})\|\mathcal{L}(v)\|_{\mathrm{sym}}$

The proof follows by bounding $k$ by $P=O(\log_{\alpha}(n))$, which is the
total number of non-zero $b_{i}$’s. ∎

###  C.4 Contributing Layers Are Important

In this section, we give two lemmas to show that every $\beta$-contributing
layer (Definition C.5) is $\beta^{\prime}$-important (Definition C.1), where
$\beta^{\prime}$ is depending on $\mathrm{mmc}(l)$ (Definition 1.3). The first
property of the important layer is proved in Lemma C.7, and the second
property is proved in Lemma C.8.

######  Lemma C.7 (Importance of contributing layers (Part 1)).

For $i\in[P]$, if layer $i$ is $\beta$-contributing, then for some absolute
constant $\lambda>0$, we have

$\displaystyle
b_{i}\geq\frac{\lambda\beta^{2}}{\mathrm{mmc}(l)^{2}\log^{2}(d)}\cdot\sum_{j=i+1}^{P}b_{j},$

where $\mathrm{mmc}(l)$ is defined as Definition 1.3.

###### Proof.

We first fix a layer $i$ which is $\beta$-contributing. Let $\mathcal{U}(v)$
be the vector $\mathcal{L}(v)$ after removing buckets $j=0,\dots,i$. By Lemma
B.5, there is an absolute constant $\lambda_{1}>0$ such that

$\displaystyle\|\mathcal{L}_{i}(v)\|_{\mathrm{sym}}=$
$\displaystyle~{}\alpha^{i}\cdot\sqrt{b_{i}}\cdot l(\xi^{(b_{i})})$
$\displaystyle\leq$
$\displaystyle~{}\lambda_{1}\cdot\alpha^{i}\cdot\sqrt{b_{i}}\cdot
M_{l^{(b_{i})}},$

and similarly

$\displaystyle\|\mathcal{U}(v)\|_{\mathrm{sym}}\geq\frac{\lambda_{2}\alpha^{i}}{\sqrt{\log(d)}}\cdot(\sum_{j=i+1}^{P}b_{j})^{1/2}M_{l^{(\sum_{j=i+1}^{P}b_{j})}}.$

With these two inequalities, we can have the following deduction.

First, we have

$\displaystyle\|\mathcal{L}_{i}(v)\|_{\mathrm{sym}}\geq\beta\cdot\|\mathcal{L}(v)\|_{\mathrm{sym}}\geq\beta\cdot\|\mathcal{U}(v)\|_{\mathrm{sym}}.$

Second, we assume that $b_{i}<\sum_{j=i+1}^{P}b_{j}$, as otherwise we are
done:

$\displaystyle
b_{i}\geq\sum_{j=i+1}^{P}b_{j}\geq\frac{\lambda\beta^{2}}{\mathrm{mmc}(l)^{2}\log^{2}(d)}\cdot\sum_{j=i+1}^{P}b_{j}.$

Then, by the monotonicity of the median (Lemma B.6), we have

$\displaystyle
M_{l^{(b_{i})}}\leq\lambda_{3}\cdot\mathrm{mmc}(l)\cdot\sqrt{\log(d)}\cdot
M_{l^{(\sum_{j=i+1}^{P}b_{j})}}$

for some absolute constant $\lambda_{3}>0$.

Putting it all together, we get

$\displaystyle\beta\cdot\frac{\lambda_{2}\alpha^{i}}{\sqrt{\log(d)}}\cdot(\sum_{j=i+1}^{P}b_{j})^{1/2}\leq\lambda_{1}\cdot\alpha^{i}\sqrt{b_{i}}\cdot\lambda_{3}\cdot\mathrm{mmc}(l)\cdot\sqrt{\log(d)}.$

Therefore, we finish the proof. ∎

######  Lemma C.8 (Importance of contributing layers (Part 2)).

For a symmetric $l$, let $\mathrm{mmc}(l)$ be defined as Definition 1.3. If
layer $i\in[P]$ is $\beta$-contributing, then there is an absolute constant
$\lambda>0$ such that

$\displaystyle
b_{i}\alpha^{2i}\geq\frac{\lambda\beta^{2}}{\mathrm{mmc}(l)^{2}\cdot\log_{\alpha}(n)\cdot\log^{2}(n)}\cdot\sum_{j\in[i]}b_{j}\alpha^{2j}.$

###### Proof.

We first fix a layer $i$ which is $\beta$-contributing, and let
$h:=\arg\max_{j\leq i}\sqrt{b_{j}}\alpha^{j}$. We consider the two different
cases as follows.

First, if $b_{i}\geq b_{h}$ then the lemma follows obviously by

$\displaystyle~{}\sum_{j\in[i]}b_{j}\alpha^{2j}$ $\displaystyle\leq$
$\displaystyle~{}t\cdot b_{h}\cdot\alpha^{2h}$ $\displaystyle\leq$
$\displaystyle~{}O(\log_{\alpha}(d))\cdot b_{i}\cdot\alpha^{2i}.$

The second case is when $b_{i}<b_{h}$. With Definition C.5 and Lemma B.5, we
have

$\displaystyle~{}\lambda_{1}\cdot\alpha^{i}\cdot\sqrt{b_{i}}\cdot
M_{l^{(b_{i})}}$ $\displaystyle\geq$
$\displaystyle~{}\|\mathcal{L}_{i}\|_{\mathrm{sym}}$ $\displaystyle\geq$
$\displaystyle~{}\beta\cdot\|\mathcal{L}\|_{\mathrm{sym}}$ $\displaystyle\geq$
$\displaystyle~{}\lambda_{2}\cdot\beta\cdot\alpha^{h}\cdot\sqrt{\frac{b_{h}}{\log(d)}}\cdot
M_{l^{(b_{h})}},$

for some absolute constants $\lambda_{1},\lambda_{2}>0$, where the first step
follows from Lemma B.5, the second step follows from Definition C.5, and the
last step follows from Lemma B.5.

following from monotonicity of the median (Lemma B.6), we can plugging in
$M_{l^{(b_{i})}}\leq\lambda_{3}\cdot\mathrm{mmc}(l)\cdot\sqrt{\log(d)}\cdot
M_{l^{(b_{h})}}$, for some absolute constant $\lambda_{3}>0$, so that we have

$\displaystyle\lambda_{1}\cdot\alpha^{i}\cdot\sqrt{b_{i}}\cdot
M_{l^{(b_{i})}}$
$\displaystyle~{}\geq\frac{\lambda_{2}\cdot\beta\cdot\sqrt{b_{h}}\cdot\alpha^{h}}{\sqrt{\log(d)}}\cdot\frac{M_{l^{(b_{i})}}}{\lambda_{3}\cdot\mathrm{mmc}(l)\cdot\sqrt{\log(d)}},$
$\displaystyle\sqrt{b_{i}}\cdot\alpha^{i}$
$\displaystyle~{}\geq\frac{\lambda_{2}\cdot\beta\cdot\sqrt{b_{h}}\cdot\alpha^{h}}{\lambda_{1}\lambda_{3}\cdot\mathrm{mmc}(l)\cdot\log(d)}.$

Square the above inequality and we can see that
$b_{h}\cdot\alpha^{2h}\geq\frac{1}{O(\log_{\alpha}(d))}\cdot\sum_{j\in[i]}b_{j}\alpha^{2j}$.

Thus we complete the proof. ∎

##  Appendix D Formal Main Result and Algorithms

In this section, we state the formal version of our main theorem and
algorithms. Section D.1 presents our main result: a data structure for
distance estimation with symmetric norm. Section D.2 introduces the sparse
recovery tools for sketching.

###  D.1 Formal Version of Our Main Result

Algorithm 3 Data structure for symmetric norm estimation

1:data structure DistanceOnSymmetricNorm $\triangleright$ Theorem D.1

2:

3:private:

4:procedure LayerVectorApprox($\alpha,b_{1},b_{2},\dots,b_{P},d$)
$\triangleright$ Lemma C.3

5: For each $i\in[P]$, let $\alpha^{i}\cdot{\bf
1}_{b_{i}}\in\mathbb{R}^{b_{i}}$ denote a vector that has length $b_{i}$ and
every entry is $\alpha^{i}$

6: $\mathcal{L}\leftarrow(\alpha^{1}\cdot{\bf
1}_{b_{1}},\cdots,\alpha^{P}\cdot{\bf 1}_{b_{P}},0,\ldots,0)\in\mathbb{R}^{d}$
$\triangleright$ Generate the layer vector

7: return $\|\mathcal{L}\|_{\mathrm{sym}}$ $\triangleright$ Return the norm of
the estimated layer vector

8:end procedure

9:end data structure

Algorithm 4 Data structure for symmetric norm estimation: members, formal
version of Algorithm 1

1:data structure DistanceOnSymmetricNorm $\triangleright$ Theorem D.1

2:members

3: $d,n\in\mathbb{N}_{+}$ $\triangleright$ $n$ is the number of points, $d$ is
dimension

4: $X=\\{x_{i}\in\mathbb{R}^{d}\\}_{i=1}^{n}$ $\triangleright$ Set of points
being queried

5: $L\in\mathbb{N}_{+}$ $\triangleright$ number of layers we subsample

6: $R\in\mathbb{N}_{+}$ $\triangleright$ number of substreams in one layer

7: $\epsilon$, $\delta$

8: $\beta$ $\triangleright$ used to cut important layer

9: $U\in\mathbb{N}_{+}$ $\triangleright$ number of parallel processing

10: BatchHeavyHitter $\\{S_{r,l,u}\\}_{r\in[R],l\in[L],u\in[U]}$

11: $\\{H_{r,l,u}\subset[d]\times\mathbb{R}\\}_{r\in[R],l\in[L],u\in[U]}$
$\triangleright$ each set $H$ has a size of $2/\beta$, and is used to store
the output of BatchHeavyHitter

12: $\gamma$ $\triangleright$ parameter used when cutting layer vector

13: $\mathrm{bmap}\in\\{0,1\\}^{R\times L\times U\times d}$

14: $\overline{x}_{r,l,u}\in\mathbb{R}^{n\times d}$, for each
$r\in[R],l\in[L],u\in[U]$ $\triangleright$ Substreams

15:end members

16:end data structure

Algorithm 5 Data structure for symmetric norm estimation: init, formal version
of Algorithm 1

1:data structure DistanceOnSymmetricNorm $\triangleright$ Theorem D.1

2:public:

3:procedure
Init($\\{x_{1},\cdots,x_{i}\\}\subset\mathbb{R}^{d},n\in\mathbb{N}_{+},d\in\mathbb{N}_{+},\delta\in(0,0.1),\epsilon\in(0,0.1)$)
$\triangleright$ Lemma 4.1

4: $n\leftarrow n$, $d\leftarrow d$, $\delta\leftarrow\delta$,
$\epsilon\leftarrow\epsilon$

5: for $i=1\to n$ do

6: $x_{i}\leftarrow x_{i}$

7: end for

8: $\epsilon_{1}\leftarrow O(\frac{\epsilon^{2}}{\log d})$ $\triangleright$ We
define this notation for purpose of analysis

9: $L\leftarrow\log(d)$,
$R\leftarrow\Theta(\epsilon_{1}^{-2}\log(n/\delta)\log^{2}d)$,
$U\leftarrow\lceil\log(nd^{2}/\delta)\rceil$

10: $\beta\leftarrow O(\frac{\epsilon^{5}}{\mathrm{mmc}(l)^{2}\log^{5}d})$

11: for $r\in[R],l\in[L],u\in[U]$ do

12: $S_{r,l,u}.\textsc{Init}(\sqrt{\beta},n+2,d)$ $\triangleright$ Theorem D.3

13: end for

14: for $r\in[R],u\in[U],j\in[d],l\in[L]$ do

15: Draw $\xi\in[0,1]$

16: if $\xi\in[0,2^{-l}]$ then

17: $\mathrm{bmap}[r,l,u,j]\leftarrow 1$

18: else

19: $\mathrm{bmap}[r,l,u,j]\leftarrow 0$

20: end if

21: end for

22: for $r\in[R],u\in[U],i\in[n],j\in[d],l\in[L]$ do

23: if $\mathrm{bmap}[r,l,u,j]=1$ then

24: $S_{r,l,u}.\textsc{EncodeSingle}(i,j,x_{i,j},d)$ $\triangleright$ Theorem
D.3

25: $[\overline{x}_{r,l,u}]_{i,j}\leftarrow x_{i,j}$ $\triangleright$ Create a
copy of subvectors

26: else

27: $[\overline{x}_{r,l,u}]_{i,j}\leftarrow 0$

28: end if

29: end for

30:end procedure

31:end data structure

Algorithm 6 Data structure for symmetric norm estimation: update

1:data structure DistanceOnSymmetricNorm $\triangleright$ Theorem D.1

2:public:

3:procedure Update($i\in[n],z\in\mathbb{R}^{d}$) $\triangleright$ Lemma 4.2

4: $\triangleright$ You want to replace $x_{i}$ by $z$

5: for $r\in[R],u\in[U],j\in[d],l\in[L]$ do

6: if $\mathrm{bmap}[r,l,u]=1$ then

7: $S_{r,l,u}.\textsc{EncodeSingle}(i,j,z_{j},d)$ $\triangleright$ Theorem D.3

8: $[\overline{x}_{r,l,u}]_{i,j}\leftarrow z_{j}$ $\triangleright$ Create a
copy of subvectors

9: else

10: $[\overline{x}_{r,l,u}]_{i,j}\leftarrow 0$

11: end if

12: end for

13:end procedure

14:end data structure

Algorithm 7 Data structure for symmetric norm estimation: query, formal
version of Algorithm 2

1:data structure DistanceOnSymmetricNorm $\triangleright$ Theorem D.1

2:procedure Query($q\in\mathbb{R}^{d}$) $\triangleright$ Lemma 4.3, 5.1

3: $P\leftarrow O(\log_{\alpha}(d))$ $\triangleright$ $P$ denotes the number
of non-empty layer sets

4: for $r\in[R],l\in[L],u\in[U]$ do

5: $S_{r,l,u}.\textsc{Encode}(n+1,q,d)$ $\triangleright$ Generate Sketch for
$q$

6: end for

7: $\xi\leftarrow$ chosen uniformly at random from $[1/2,1]$

8: $\gamma\leftarrow\Theta(\epsilon)$

9: $\alpha\leftarrow 1+\gamma\cdot\xi$

10: $P\leftarrow O(\log_{\alpha}(d))=O(\log(d)/\epsilon)$ $\triangleright$ $P$
denotes the number of non-empty layer sets

11: for $i\in[n]$ do

12: for $r\in[R],l\in[L],u\in[U]$ do

13: $S_{r,l,u}.\textsc{Subtract}(n+2,n+1,i)$

14: $H_{r,l,u}\leftarrow S_{r,l,u}.\textsc{Decode}(n+2,\sqrt{\beta},d)$
$\triangleright$ This can be done in $\frac{2}{\beta}\operatorname{poly}(\log
d)$

15: $\triangleright$ At this point $H_{r,l,u}$ is a list of index, the value
of each index is reset to $0$

16: for $k\in H_{r,l,u}$ do

17: $\mathrm{value}\leftarrow[\overline{x}_{r,l,u}]_{i,k}$

18: $H_{r,l,u}[k]\leftarrow\mathrm{value}$

19: $w\leftarrow\lceil\log(\mathrm{value})/\log(\alpha)\rceil$

20: if $\alpha^{w-1}\geq\mathrm{value}/(1+\epsilon)$ then

21: $H_{r,l,u}\leftarrow\mathsf{null}$

22: break

23: end if

24: end for

25: if $H_{r,l,u}\not=\mathsf{null}$ then

26: $H_{r,l}\leftarrow H_{r,l,u}$

27: end if

28: end for

29: for $l\in[L],k\in[P]$ do

30: $A^{i}_{l,k}\leftarrow|\\{k~{}|~{}\exists k\in
H_{r,l},\alpha^{k-1}<|H_{r,l}[k]|\leq\alpha^{k}\\}|$

31: end for

32: for $k\in[P]$ do

33:
$q^{i}_{k}\leftarrow\max_{l\in[L]}{\\{l~{}|~{}A^{i}_{l,k}\geq\frac{R\log(1/\delta)}{100\log(d)}\\}}$
$\triangleright$ Definition F.7

34: If $q^{i}_{k}$ does not exist, then $\widehat{\eta}^{i}_{k}\leftarrow 0$;
Else
$\widehat{\eta}^{i}_{k}\leftarrow\frac{A_{q^{i}_{k},k}}{R(1+\epsilon_{1})}$

35: If $\widehat{\eta}^{i}_{k}=0$ then $c^{i}_{k}\leftarrow 0$; Else
$c^{i}_{k}\leftarrow\frac{\log(1-\widehat{\eta}^{i}_{k})}{1-w^{-q_{k}}}$

36: end for

37:
$\mathrm{dst}_{i}\leftarrow\textsc{LayerVetcorApprox}(\alpha,c^{i}_{1},c^{i}_{2},\dots,c^{i}_{P},d)$

38: for $r\in[R],l\in[L],u\in[U]$ do

39: $\\{H_{r,l,u}\\}\leftarrow\\{0\\}$ $\triangleright$ Reset the sets to use
for next point

40: end for

41: end for

42: return $\\{\mathrm{dst}_{i}\\}_{i\in[n]}$

43:end procedure

44:end data structure

Here we divide function Query presented in Theorem 1.4 into two versions. One
takes only the query point $q\in\mathbb{R}^{d}$ as input to ask all the
distances. Another takes a query point $q\in\mathbb{R}^{d}$ and a set
$\mathsf{S}\subset[n]$ to ask for the distance with the specific set of
points. The latter can be viewed as a more general version of the former. In
the former parts, we have proved the correctness of the query (Lemma 5.1), and
the running time of version for all points (Lemma 4.3). Now we state the both
in the following theorem, and the running time analysis for the latter will be
stated in Section E.

######  Theorem D.1 (Main result, formal version of Theorem 1.4).

There is a data structure (Algorithm 4, 5, 7, 6) uses
$O(\epsilon^{-9}n(d+\mathrm{mmc}(l)^{2})\log^{14}(nd/\delta))$ spaces for the
Online Approximate Adaptive Symmetric Norm Distance Estimation Problem
(Definition 1.1) with the following procedures:

  * •

Init$(\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d},\epsilon\in(0,1),\delta\in(0,1))$:
Given $n$ data points $\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d}$, an
accuracy parameter $\epsilon$ and a failure probability $\delta$ as input, the
data structure preprocesses in time
$O(\epsilon^{-9}n(d+\mathrm{mmc}(l)^{2})\log^{14}(nd/\delta))$.

  * •

UpdateX$(z\in\mathbb{R}^{d},i\in[n])$: Given an update vector
$z\in\mathbb{R}^{d}$ and index $i\in[n]$, the UpdateX takes $z$ and $i$ as
input and updates the data structure with the new $i$-th data point in
$O(\epsilon^{-4}d\log^{9}(nd/\delta))$ time.

  * •

Query$(q\in\mathbb{R}^{d})$ (Querying all points): Given a query point
$q\in\mathbb{R}^{d}$, the Query operation takes $q$ as input and approximately
estimates the symmetric norm distances from $q$ to all the data points
$\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d}$ in time

$\displaystyle
O(\epsilon^{-9}(d+n\cdot\mathrm{mmc}(l)^{2})\log^{14}(nd/\delta))$

i.e. it provides a set of estimates $\\{\mathrm{dst}_{i}\\}_{i=1}^{n}$ such
that:

$\displaystyle\forall
i\in[n],(1-\epsilon)\|q-x_{i}\|_{\mathrm{sym}}\leq\mathrm{dst}_{i}\leq(1+\epsilon)\|q-x_{i}\|_{\mathrm{sym}}$

with probability at least $1-\delta$.

  * •

Query$(q\in\mathbb{R}^{d},\mathsf{S}\subseteq[n])$ (Querying a specific set
$\mathsf{S}$ of points). Given a query point $q\in\mathbb{R}^{d}$ and an index
$i\in[n]$, the QueryOne operation takes $q$ and $i$ as input and approximately
estimates the symmetric norm distances from $q$ to the $i$-th point
$x_{i}\in\mathbb{R}^{d}$ in time

$\displaystyle
O(\epsilon^{-9}(d+|\mathsf{S}|\cdot\mathrm{mmc}(l)^{2})\log^{14}(nd/\delta))$

i.e. it provides a estimated distance
$\mathrm{dst}\in\mathbb{R}^{{\mathsf{S}}}$ such that:

$\displaystyle(1-\epsilon)\|q-x_{i}\|_{\mathrm{sym}}\leq\mathrm{dst}_{i}\leq(1+\epsilon)\|q-x_{i}\|_{\mathrm{sym}},\forall
i\in\mathsf{S}$

with probability at least $1-\delta$.

  * •

EstPair$(i,j\in[n])$ Given indices $i,j\in[n]$, the EstPair operation takes
$i$ and $j$ as input and approximately estimates the symmetric norm distances
from $i$-th to the $j$-th point $x_{i},x_{j}\in\mathbb{R}^{d}$ in time

$\displaystyle O(\epsilon^{-9}\cdot\mathrm{mmc}(l)^{2}\log^{14}(nd/\delta))$

i.e. it provides a estimated distance $\mathrm{pair}$ such that:

$\displaystyle(1-\epsilon)\|x_{i}-x_{j}\|_{\mathrm{sym}}\leq\mathrm{pair}\leq(1+\epsilon)\|x_{i}-x_{j}\|_{\mathrm{sym}}$

with probability at least $1-\delta$.

###### Proof.

In Lemma E.3, Lemma E.4, Lemma E.1 and Lemma E.2 we analyze the running time
for Init, Update and Query and EstPair respectively.

Lemma G.1 shows the space complexity.

In Lemma 5.1 we give the correctness of Query, and correctness for EstPair
follows directly.

Thus, putting them all together, we prove the Theorem.

∎

###  D.2 Sparse Recovery tools

We start with describing a data structure problem

######  Definition D.2 (Batch Heavy Hitter).

Given an $n\times d$ matrix, the goal is to design a data structure that
supports the following operations:

  * •

Init$(\epsilon\in(0,0.1),n,d)$. Create a set of Random Hash functions and all
the $n$ copies of sketches share the same hash functions.

  * •

Encode$(i\in[n],z\in\mathbb{R}^{d},d)$. This step encodes $z$ into $i$-th
sketched location and store a size ${\cal S}_{\mathrm{space}}$ linear sketch.

  * •

EncodeSingle$(i\in[n],j\in[d],z\in\mathbb{R},d)$. This step updates one sparse
vector $e_{j}z\in\mathbb{R}^{d}$ into $i$-th sketched location.

  * •

Subtract$(i,j,l\in[n])$. This function updates the sketch at $i$-th location
by $j$-th sketch minus $l$-th sketch.

  * •

Decode$(i\in[n],\epsilon\in(0,0.1),d)$. This function returns a set
$L\subseteq[d]$ of size $|L|=O(\epsilon^{-2})$ containing all $\epsilon$-heavy
hitters $i\in[n]$ under $\ell_{p}$. Here we say $i$ is an $\epsilon$-heavy
hitter under $\ell_{2}$ if
$|x_{i}|\geq\epsilon\cdot\|x_{\overline{[\epsilon^{-2}]}}\|_{2}$ where
$x_{\overline{[k]}}$ denotes the vector $x$ with the largest $k$ entries (in
absolute value) set to zero. Note that the number of heavy hitters never
exceeds $2/\epsilon^{2}$.

The existing work [29, 39] implies the following result. However their proofs
are very decent and complicated. We provide another data structure in Section
I that significantly simplifies the analysis (by only paying some extra log
factors). We believe it is of independent interest.

######  Theorem D.3.

There is (linear sketch) data structure BatchHeavyHitter$(\epsilon,n,d)$ that
uses ${\cal S}_{\mathrm{space}}$ space that support the following operations:

  * •

Init$(\epsilon\in(0,0.1),n,d)$. This step takes ${\cal
T}_{\mathrm{init}}(\epsilon,n,d)$ time.

  * •

Encode$(i\in[n],z\in\mathbb{R}^{d},d)$. This step takes ${\cal
T}_{\mathrm{encode}}(d)$ time.

  * •

EncodeSingle$(i\in[n],j\in[d],z\in\mathbb{R},d)$. This step takes ${\cal
T}_{\mathrm{encodesingle}}(d)$ time.

  * •

Subtract$(i,j,l\in[n])$. This step takes ${\cal T}_{\mathrm{encodesingle}}(d)$
time.

  * •

Decode$(i\in[n],\epsilon\in(0,0.1),d)$. This step takes ${\cal
T}_{\mathrm{decode}}(\epsilon,d)$ time.

The running time of function can be summarize as

  * •

${\cal S}_{\mathrm{space}}(\epsilon,d)=n\cdot O(\epsilon^{-2}\log^{2}d)$

  * •

${\cal T}_{\mathrm{init}}(\epsilon,n,d)=n\cdot O(\epsilon^{-2}\log^{2}d)$

  * •

${\cal T}_{\mathrm{encode}}(d)=O(d\log^{2}(d))$

  * •

${\cal T}_{\mathrm{encodesingle}}(d)=O(\log^{2}(d))$

  * •

${\cal T}_{\mathrm{subtract}}(\epsilon,d)=O(\epsilon^{-2}\log^{2}d)$

  * •

${\cal T}_{\mathrm{decode}}(\epsilon,d)=O(\epsilon^{-2}\log^{2}d)$

Note that the succeed probability is at least $0.99$.

We remark that, to boost the probability from constant to
$1-1/\operatorname{poly}(nd)$ we just need to pay an extra $\log(nd)$ factor.

Algorithm 8 Data structure for symmetric norm estimation: query set

1:data structure DistanceOnSymmetricNorm$\triangleright$ Theorem D.1

2:procedure Query($q\in\mathbb{R}^{d}$, $\mathsf{S}\subseteq[n]$)
$\triangleright$ Lemma 4.3, 5.1

3: $P\leftarrow O(\log_{\alpha}(d))$ $\triangleright$ $P$ denotes the number
of non-empty layer sets

4: for $r\in[R],l\in[L],u\in[U]$ do

5: $S_{r,l,u}.\textsc{Encode}(n+1,q,d)$ $\triangleright$ Generate Sketch for
$q$

6: end for

7: $\xi\leftarrow$ chosen uniformly at random from $[1/2,1]$

8: $\gamma\leftarrow\Theta(\epsilon)$

9: $\alpha\leftarrow 1+\gamma\cdot\xi$

10: $P\leftarrow O(\log_{\alpha}(d))=O(\log(d)/\epsilon)$ $\triangleright$ $P$
denotes the number of non-empty layer sets

11: for $i\in\mathsf{S}$ do

12: for $r\in[R],l\in[L],u\in[U]$ do

13: $S_{r,l,u}.\textsc{Subtract}(n+2,n+1,i)$

14: $H_{r,l,u}\leftarrow S_{r,l,u}.\textsc{Decode}(n+2,\sqrt{\beta},d)$
$\triangleright$ This can be done in $\frac{2}{\beta}\operatorname{poly}(\log
d)$

15: $\triangleright$ At this point $H_{r,l,u}$ is a list of index, the value
of each index is reset to $0$

16: for $k\in H_{r,l,u}$ do

17: $\mathrm{value}\leftarrow[\overline{x}_{r,l,u}]_{i,k}$

18: $H_{r,l,u}[k]\leftarrow\mathrm{value}$

19: $w\leftarrow\lceil\log(\mathrm{value})/\log(\alpha)\rceil$

20: if $\alpha^{w-1}\geq\mathrm{value}/(1+\epsilon)$ then

21: $H_{r,l,u}\leftarrow\mathsf{null}$

22: break

23: end if

24: end for

25: if $H_{r,l,u}\not=\mathsf{null}$ then

26: $H_{r,l}\leftarrow H_{r,l,u}$

27: end if

28: end for

29: for $l\in[L],k\in[P]$ do

30: $A^{i}_{l,k}\leftarrow|\\{k~{}|~{}\exists k\in
H_{r,l},\alpha^{k-1}<|H_{r,l}[k]|\leq\alpha^{k}\\}|$

31: end for

32: for $k\in[P]$ do

33:
$q^{i}_{k}\leftarrow\max_{l\in[L]}{\\{l~{}|~{}A^{i}_{l,k}\geq\frac{R\log(1/\delta)}{100\log(d)}\\}}$

34: If $q^{i}_{k}$ does not exist, then $\widehat{\eta}^{i}_{k}\leftarrow 0$;
Else
$\widehat{\eta}^{i}_{k}\leftarrow\frac{A_{q^{i}_{k},k}}{R(1+\epsilon_{2})}$

35: If $\widehat{\eta}^{i}_{k}=0$ then $c^{i}_{k}\leftarrow 0$; Else
$c^{i}_{k}\leftarrow\frac{\log(1-\widehat{\eta}^{i}_{k})}{1-w^{-q_{k}}}$

36: end for

37:
$\mathrm{dst}_{i}\leftarrow\textsc{LayerVetcorApprox}(\alpha,c^{i}_{1},c^{i}_{2},\dots,c^{i}_{P},d)$

38: for $r\in[R],l\in[L],u\in[U]$ do

39: $\\{H_{r,l,u}\\}\leftarrow\\{0\\}$ $\triangleright$ Reset the sets to use
for next point

40: end for

41: end for

42: return $\\{\mathrm{dst}_{i}\\}_{i\in\mathsf{S}}$

43:end procedure

44:end data structure

Algorithm 9 Data structure for symmetric norm estimation: query pair

1:data structure DistanceOnSymmetricNorm$\triangleright$ Theorem D.1

2:procedure EstPair($i\in[n]$, $j\in[n]$) $\triangleright$ Lemma 4.3, 5.1

3: $P\leftarrow O(\log_{\alpha}(d))$ $\triangleright$ $P$ denotes the number
of non-empty layer sets

4: $\xi\leftarrow$ chosen uniformly at random from $[1/2,1]$

5: $\gamma\leftarrow\Theta(\epsilon)$

6: $\alpha\leftarrow 1+\gamma\cdot\xi$

7: $P\leftarrow O(\log_{\alpha}(d))=O(\log(d)/\epsilon)$ $\triangleright$ $P$
denotes the number of non-empty layer sets

8: for $r\in[R],l\in[L],u\in[U]$ do

9: $S_{r,l,u}.\textsc{Subtract}(n+2,j,i)$

10: $H_{r,l,u}\leftarrow S_{r,l,u}.\textsc{Decode}(n+2,\sqrt{\beta},d)$
$\triangleright$ This can be done in $\frac{2}{\beta}\operatorname{poly}(\log
d)$

11: $\triangleright$ At this point $H_{r,l,u}$ is a list of index, the value
of each index is reset to $0$

12: for $k\in H_{r,l,u}$ do

13: $\mathrm{value}\leftarrow[\overline{x}_{r,l,u}]_{i,k}$

14: $H_{r,l,u}[k]\leftarrow\mathrm{value}$

15: $w\leftarrow\lceil\log(\mathrm{value})/\log(\alpha)\rceil$

16: if $\alpha^{w-1}\geq\mathrm{value}/(1+\epsilon)$ then

17: $H_{r,l,u}\leftarrow\mathsf{null}$

18: break

19: end if

20: end for

21: if $H_{r,l,u}\not=\mathsf{null}$ then

22: $H_{r,l}\leftarrow H_{r,l,u}$

23: end if

24: end for

25: for $l\in[L],k\in[P]$ do

26: $A_{l,k}\leftarrow|\\{k~{}|~{}\exists k\in
H_{r,l},\alpha^{k-1}<|H_{r,l}[k]|\leq\alpha^{k}\\}|$

27: end for

28: for $k\in[P]$ do

29:
$q_{k}\leftarrow\max_{l\in[L]}{\\{l~{}|~{}A_{l,k}\geq\frac{R\log(1/\delta)}{100\log(d)}\\}}$

30: If $q_{k}$ does not exist, then $\widehat{\eta}_{k}\leftarrow 0$; Else
$\widehat{\eta}_{k}\leftarrow\frac{A_{q_{k},k}}{R(1+\epsilon_{2})}$

31: If $\widehat{\eta}_{k}=0$ then $c_{k}\leftarrow 0$; Else
$c_{k}\leftarrow\frac{\log(1-\widehat{\eta}_{k})}{1-w^{-q_{k}}}$

32: end for

33:
$\mathrm{dst}\leftarrow\textsc{LayerVetcorApprox}(\alpha,c_{1},c_{2},\dots,c_{P},d)$

34: return $\mathrm{dst}$

35:end procedure

36:end data structure

##  Appendix E More Details of the Time Complexity

In this section, we analyze the running time of the general version of Query.
Lemma 4.3 is a special case of the following Lemma when $\mathsf{S}=[n]$.

######  Lemma E.1 (Query time for general version).

Given a query point $q\in\mathbb{R}^{d}$ and a set $\mathsf{S}\subseteq[n]$,
the procedure Query (Algorithm 8) runs in time

$\displaystyle
O(\epsilon^{-9}(d+|\mathsf{S}|\cdot\mathrm{mmc}(l)^{2})\log^{14}(nd/\delta)).$

###### Proof.

The Query operation for a stored vector (Algorithm 8) has the following two
parts:

  * •

Part 1: Line 5 takes $O(RLU\cdot\mathcal{T}_{\mathrm{encode}})$ time to call
Encode to generate sketches for $q$.

  * •

Part 2: For each $i\in\mathsf{S}$

    * –

Line 13 takes $O(RLU\cdot\mathcal{T}_{\mathrm{subtract}})$ time to compute
sketch of the difference between $q$ and $x_{i}$, and store the sketch at
index of $n+2$.

    * –

Line 14 takes $O(RLU\cdot\mathcal{T}_{\mathrm{decode}})$ time to decode the
BatchHeavyHitter and get estimated heavy hitters of $q-x_{i}$.

    * –

Line 16 to Line 24 takes $O(RLU\cdot 2/\beta)$ time to analyze the
BatchHeavyHitter and get the set of indices, where $2/\beta$ is the size of
the set.

    * –

Line 30 takes $O(LP\cdot 2/\beta)$ time to compute size of the layer sets cut
by $\alpha$.

    * –

Line 32 to Line 36 takes $O(PL)$ time to compute the estimation of each layer.

The total running time of this part is:

$\displaystyle~{}|\mathsf{S}|\cdot(O(RLU\cdot\mathcal{T}_{\mathrm{subtract}})+O(RLU\cdot\mathcal{T}_{\mathrm{decode}})+O(RLU\cdot
2/\beta)+O(LP\cdot 2/\beta)+O(LP)))$ $\displaystyle=$
$\displaystyle~{}O(|\mathsf{S}|\cdot
L(RU(\mathcal{T}_{\mathrm{subtract}}+\mathcal{T}_{\mathrm{decode}}+\beta^{-1})+P\beta^{-1}))$

time in total.

Taking these two parts together we have the total running time of the Query
procedure:

$\displaystyle~{}O(RLU\cdot\mathcal{T}_{\mathrm{encode}})+O(|\mathsf{S}|\cdot
L(RU(\mathcal{T}_{\mathrm{subtract}}+\mathcal{T}_{\mathrm{decode}}+\beta^{-1})+P\beta^{-1}))$
$\displaystyle=$
$\displaystyle~{}O(RLU(\mathcal{T}_{\mathrm{encode}}+|\mathsf{S}|\cdot(\mathcal{T}_{\mathrm{subtract}}+\mathcal{T}_{\mathrm{decode}}+\beta^{-1}))+|\mathsf{S}|\cdot
LP\beta^{-1})$ $\displaystyle=$
$\displaystyle~{}O(\epsilon^{-4}\log^{6}(nd/\delta)(d\log^{2}(d)\log(nd)+|\mathsf{S}|\cdot\beta^{-1}\log^{2}(d)\log(nd))+|\mathsf{S}|\cdot\epsilon^{-1}\log^{2}(d)\beta^{-1})$
$\displaystyle=$
$\displaystyle~{}O(\epsilon^{-9}(d+|\mathsf{S}|\cdot\mathrm{mmc}(l)^{2})\log^{14}(nd/\delta))$

where the first step follows from the property of big $O$ notation, the second
step follows from the definition of
$R,L,U,\mathcal{T}_{\mathrm{encode}},\mathcal{T}_{\mathrm{encode}},\mathcal{T}_{\mathrm{subtract}},\mathcal{T}_{\mathrm{decode}}$
(Theorem D.3) $,P$, the third step follows from merging the terms.

Thus, we complete the proof.

∎

######  Lemma E.2 (EstPair time).

Given a query point $q\in\mathbb{R}^{d}$, the procedure EstPair (Algorithm 9)
runs in time

$\displaystyle O(\epsilon^{-9}\cdot\mathrm{mmc}(l)^{2}\log^{14}(nd/\delta)).$

###### Proof.

The EstPair operation (Algorithm 9) has the following two parts:

  * •

Line 9 takes $O(RLU\cdot\mathcal{T}_{\mathrm{subtract}})$ time to compute
sketch of the difference between $x_{i}$ and $x_{j}$, and store the sketch at
index of $n+2$.

  * •

Line 10 takes $O(RLU\cdot\mathcal{T}_{\mathrm{decode}})$ time to decode the
BatchHeavyHitter and get estimated heavy hitters of $x_{i}-x_{j}$.

  * •

Line 12 to Line 20 takes $O(RLU\cdot 2/\beta)$ time to analyze the
BatchHeavyHitter and get the set of indices, where $2/\beta$ is the size of
the set.

  * •

Line 26 takes $O(LP\cdot 2/\beta)$ time to compute size of the layer sets cut
by $\alpha$.

  * •

Line 28 to Line 32 takes $O(PL)$ time to compute the estimation of each layer.

The total running time is:

$\displaystyle~{}O(RLU\cdot\mathcal{T}_{\mathrm{subtract}})+O(RLU\cdot\mathcal{T}_{\mathrm{decode}})+O(RLU\cdot
2/\beta)+O(LP\cdot 2/\beta)+O(LP)$ $\displaystyle=$
$\displaystyle~{}O(RLU(\mathcal{T}_{\mathrm{subtract}}+\mathcal{T}_{\mathrm{decode}}+\beta^{-1})+LP\beta^{-1})$
$\displaystyle=$
$\displaystyle~{}O(\epsilon^{-4}\log^{6}(nd/\delta)(\beta^{-1}\log^{2}(d)\log(nd)+\epsilon^{-1}\log^{2}(d)\beta^{-1}\log(nd))$
$\displaystyle=$
$\displaystyle~{}O(\epsilon^{-9}\cdot\mathrm{mmc}(l)^{2}\log^{14}(nd/\delta))$

time in total, where the first step follows from the property of big $O$
notation, the second step follows from the definition of
$R,L,U,\mathcal{T}_{\mathrm{encode}},\mathcal{T}_{\mathrm{encode}},\mathcal{T}_{\mathrm{subtract}},\mathcal{T}_{\mathrm{decode}}$
(Theorem D.3) $,P$, the third step follows from merging the terms.

Thus, we complete the proof.

∎

######  Lemma E.3 (Init time, formal version of Lemma 4.1).

Given data points $\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d}$, an
accuracy parameter $\epsilon>0$, and a failure probability $\delta>0$ as
input, the procedure init (Algorithm 5) runs in time

$\displaystyle O(\epsilon^{-9}n(d+\mathrm{mmc}(l)^{2})\log^{14}(nd/\delta)).$

###### Proof.

The Init time includes these parts:

  * •

Line 12 takes $O(RLU\cdot{\cal T}_{\mathrm{init}}(\sqrt{\beta},n,d))$ to
initialize sketches

  * •

Line 17 to Line 19 takes $O(RUdL)$ to generate the bmap;

  * •

Line 24 takes $O(ndRUL\cdot\mathcal{T}_{\mathrm{encodesingle}}(d))$ to
generate sketches

By Theorems D.3, we have

  * •

$\mathcal{T}_{\mathrm{init}}(\sqrt{\beta},n,d))=n\cdot
O(\beta^{-1}\log^{2}(d)\log(nd))=O(n\cdot\mathrm{mmc}(l)^{2}\log^{7}(d)\log(nd)\epsilon^{-5})$,

  * •

$\mathcal{T}_{\mathrm{encodesingle}}(d)=O(\log^{2}(d)\log(nd))$.

Adding them together we got the time of

$\displaystyle~{}O(RLU{\cal
T}_{\mathrm{init}}(\sqrt{\beta},n,d))+O(RUdL)+O(ndRUL\cdot\mathcal{T}_{\mathrm{encodesingle}}(d))$
$\displaystyle=$ $\displaystyle~{}O(RLU({\cal
T}_{\mathrm{init}}(\sqrt{\beta},n,d)+nd\cdot\mathcal{T}_{\mathrm{encodesingle}}(d)))$
$\displaystyle=$
$\displaystyle~{}O(\epsilon^{-4}\log(d/\delta)\log^{4}(d)\cdot\log(d)\cdot\log(nd^{2}/\delta)\log(nd)(n\cdot\mathrm{mmc}(l)^{2}\log^{7}(d)\epsilon^{-5}+nd\log^{2}(d)))$
$\displaystyle=$
$\displaystyle~{}O(\epsilon^{-9}n(d+\mathrm{mmc}(l)^{2})\log^{14}(nd/\delta)),$

where the first step follows from merging the terms, the second step follows
from the definition of $R,L,U,\mathcal{T}_{\mathrm{encodesingle}}(d),{\cal
T}_{\mathrm{init}}$, the third step follows from merging the terms.

Thus, we complete the proof. ∎

######  Lemma E.4 (Update time, formal version of Lemma 4.2).

Given a new data point $z\in\mathbb{R}^{d}$, and an index $i$ where it should
replace the original data point $x_{i}\in\mathbb{R}^{d}$. The procedure Update
(Algorithm 6) runs in time

$\displaystyle O(\epsilon^{-4}d\log^{9}(nd/\delta)).$

###### Proof.

The Update operation calls BatchHeavyHitter.Encode for $RLU$ times, so it has
the time of

$\displaystyle O(RLU\cdot\mathcal{T}_{\mathrm{encode}}(d))=$
$\displaystyle~{}O(\epsilon^{-4}\log(n/\delta)\log^{4}(d)\cdot\log(d)\cdot\log(nd^{2}/\delta)\cdot
d\log^{2}(d)\log(nd))$ $\displaystyle=$
$\displaystyle~{}O(\epsilon^{-4}d\log^{9}(nd/\delta))$

where the first step follows from the definition of
$R,L,U,\mathcal{T}_{\mathrm{encode}}(d)$, the second step follows from

$\displaystyle~{}\log(n/\delta)\log^{4}(d)\log(d)\log(nd^{2}/\delta)\log^{2}(d)\log(nd)$
$\displaystyle=$ $\displaystyle~{}(\log(n/\delta))(\log^{7}d)(2\log
d+\log(n/\delta))\log(nd)$ $\displaystyle=$
$\displaystyle~{}O(\log^{9}(nd/\delta))$

Thus, we complete the proof. ∎

##  Appendix F More Details of the Correctness Proofs

In this section, we give the complete proofs of the correctness of our
algorithms. In Section F.1 we state and prove the main result of this section,
using the technical lemmas in the following subsections. In Section F.2, we
define the trackable layers and show the connection with important layers
(Definition C.1). In Section F.3, we analyze the sample probability and track
probability of a layer. In Section F.4, we show that a good estimation of
track probability implies a good approximation of the layer size, which
completes the proof of the correctness.

###  F.1 Correctness of Layer Size Estimation

We first show that, the estimation of layer sizes output by our data structure
are good to approximate the exact values.

######  Lemma F.1 (Correctness of layer size approximation).

We first show that, the layer sizes $c^{i}_{1},c^{i}_{2},\dots,c^{i}_{P}$ our
data structure return satisfy

  * •

for all $k\in P$, $c^{i}_{k}\leq b^{i}_{k}$;

  * •

if $k$ is a $\beta$-important layer (Definition C.1) of $q-x_{i}$, then
$c^{i}_{k}\geq(1-\epsilon_{1})b^{i}_{k}$,

with probability at least $1-\delta$, where the $b^{i}_{k}$ is the ground
truth $k$-th layer size of $q-x_{i}$.

###### Proof.

We first define two events as

  * •

$E_{1}$: for all important layers $k\in[P]$, $q_{k}$ is well defined;

  * •

$E_{2}$: for all $k\in[P]$, if $\widehat{\eta}_{k}>0$ then
$(1-O(\epsilon))\eta^{\prime}_{k,q_{k}}\leq\widehat{\eta}_{k}\leq\eta^{\prime}_{k,q_{k}}$.

With Lemma F.6 and Lemma F.8, we have that

$\displaystyle\Pr[E_{1}\cap E_{2}]\geq 1-\delta^{O(\log(d))}.$

When the output of every BatchHeavyHitter is correct, if follows from Lemma
F.5, Lemma F.6 and Lemma F.9 the algorithm outputs an approximation to the
layer vector meeting the two criteria.

The BatchHeavyHitter is used a total of $LR$ times, each with error
probability at most $\delta/\mathrm{d}$. By a union bound over the layers, the
failure probability is at most $(\operatorname{poly}(\log
d))\cdot\delta/d=o(\delta)$. Therefore, the total failure probability of the
algorithm is at most $1-o(\delta)$.

Thus, we complete the proof. ∎

###  F.2 Trackability of Layers

######  Definition F.2 (Trackability of layers).

A layer $k\in[P]$ of a vector $x$ is $\beta$-trackable, if

$\displaystyle\alpha^{2k}\geq\beta\cdot\|x_{\overline{[\beta^{-1}]}}\|_{2}^{2}$

where $x_{\overline{[\kappa]}}$ is defined as Definition A.1.

######  Lemma F.3 (Importance and Trackability).

Let $\alpha$ be some parameter such that $\alpha\in[0,2]$. Suppose subvector
$\widetilde{x}$ is obtained by subsampling the original vector with
probability $p$.

If $k\in[P]$ is a $\beta$-important layer, then for any $\lambda>P$, with
probability at least $1-P\exp(-\frac{\lambda pb_{k}}{P\beta})$, layer $k$ is
$\frac{\beta}{\lambda pb_{k}}$-trackable.

In particular, if $pb_{k}=O(1)$, then with probability at least
$1-P\exp(-\Omega(\frac{\lambda}{P\beta}))$, layer $k$ is
$\frac{\beta}{\lambda}$-trackable.

###### Proof.

Let $(\zeta_{0},\zeta_{1},\dots)$ be the new level sizes of the subvector
$\widetilde{x}$ we sampled. Thus, for $k\in[P]$, we have

$\displaystyle\operatorname*{{\mathbb{E}}}[\zeta_{k}]=p\cdot b_{k}.$

By the definition of important layer (Definition C.1) we have

$\displaystyle\operatorname*{{\mathbb{E}}}[\zeta_{k}]\geq\beta\cdot\operatorname*{{\mathbb{E}}}\Big{[}\sum_{j=k+1}^{P}\zeta_{j}\Big{]}$

and

$\displaystyle\operatorname*{{\mathbb{E}}}[\zeta_{k}\cdot\alpha^{2k}]\geq\beta\cdot\operatorname*{{\mathbb{E}}}\Big{[}\sum_{j\in[k]}\zeta_{j}\cdot\alpha^{2j}\Big{]}.$

To have layer $k$ trackable, it has to be in the top $\lambda pb_{k}/\beta$
elements, so that we have $\sum_{j=k+1}^{P}\zeta_{j}\leq\lambda pb_{k}/\beta$.
By Chernoff bound (Lemma A.2), we can know the probability that this event
does not happen is

$\displaystyle\Pr\Big{[}\sum_{j=k+1}^{P}b_{j}>\frac{\lambda
pb_{k}}{\beta}\Big{]}\leq\exp(-\Omega(\lambda pb_{k}/\beta)).$

On the other hand, for level $k$ to be trackable
$\alpha^{2k}\geq\frac{\beta}{\lambda
pb_{k}}\sum_{j\in[k]}\zeta_{j}\alpha^{2j}$.

Thus, the complement occurs with probability

$\displaystyle\Pr\Big{[}\frac{\beta}{\lambda
pb_{k}}\sum_{j\in[k]}\zeta_{j}\alpha^{2j}>\alpha^{2k}\Big{]}\leq$
$\displaystyle~{}\Pr\Big{[}\exists j,\zeta_{j}\alpha^{2j}\geq\frac{\lambda
pb_{k}\alpha^{2k}}{P\beta}\Big{]}$ $\displaystyle\leq$
$\displaystyle~{}\sum_{j\in[P]}\Pr\Big{[}\zeta_{j}\alpha^{2j}\geq\frac{\lambda
pb_{k}\alpha^{2k}}{P\beta}\Big{]}.$

By Chernoff bound (Lemma A.2) and the fact that
$\operatorname*{{\mathbb{E}}}[\zeta_{j}\alpha^{2j}]\leq pb_{k}\alpha^{2k}$, we
have

$\displaystyle\Pr\Big{[}\frac{\beta}{\lambda
pb_{k}}\sum_{j\in[k]}\zeta_{j}\alpha^{2j}>\alpha^{2k}\Big{]}\leq$
$\displaystyle~{}P\cdot\exp\Big{(}-\Omega(\frac{\lambda
pb_{k}\alpha^{2k}}{\alpha^{2j}P\beta})\Big{)}$ $\displaystyle\leq$
$\displaystyle~{}P\cdot\exp\Big{(}-\Omega(\frac{\lambda
pb_{k}}{\beta})\Big{)}.$

Thus we complete the proof. ∎

###  F.3 Probability Analysis

We first define

######  Definition F.4.

For each $k\in[p]$, $l\in\mathbb{R}^{+}$, we define
$\eta_{k,l}:=1-(1-p_{l})^{b_{k}}$ to be the probability that at least one
element from $B_{k}$ is sampled with the sampling probability of
$p_{l}=2^{-l}$.

Set $\lambda=\Theta(P\log(1/\delta))$. Let $\eta^{*}_{k,l}$ be the probability
that an element from $B_{k}$ is contained in $H_{1,l}$, such that, for
$H_{r,l}$ with any other $r$, the probability is the same as $\eta^{*}_{k,l}$.

######  Lemma F.5 (Sample Probability and Track Probability).

For any layer $k\in[P]$ we have $\eta^{*}_{k,l}<\eta_{k,l}$. Let $\delta$ and
$\epsilon$ denote the two parameters such that $0<\delta<\epsilon<1$. If layer
$k$ is a $\beta$-important layer and $p_{l}b_{k}=O(1)$, then

$\displaystyle\eta^{*}_{k,l}\geq(1-\Theta(\epsilon))\cdot\eta_{k,l}.$

###### Proof.

If one is in $H_{r,l}$, it has to be sampled, so we have
$\eta^{*}_{k,l}\leq\eta_{k,l}$. On the other hand, using Lemma F.3, with
probability at least $1-t\exp(-\Omega(\frac{\lambda pb_{k}}{t\beta}))$, layer
$k$ is $\frac{\beta}{\lambda pb_{k}}$-trackable.

We have

$\displaystyle\frac{\beta}{\lambda
pb_{k}}=\Theta(\frac{\beta}{P\log(1/\delta)})$

where the last step follows from definition of $\lambda$.

Thus with probability at least

$\displaystyle\eta_{k,l}(1-\Theta(\delta))\geq\eta_{k,l}(1-O(\epsilon))$

an element from $B_{k}$ is sampled and the element is reported by
BatchHeavyHitter.

Thus we complete the proof. ∎

######  Lemma F.6 (Probability Approximation).

For $k\in[P]$, let $\widehat{\eta}_{k}$ be defined as in Line 34 in Algorithm
7. With probability at least $1-\delta^{\Omega(\log d)}$, for all $k\in[P]$,
if $\widehat{\eta}_{k}\not=0$ then

$\displaystyle(1-O(\epsilon_{1}))\eta^{*}_{k,q_{k}}\leq\widehat{\eta}_{k}\leq\eta^{*}_{k,q_{k}}.$

###### Proof.

We define

$\displaystyle\gamma:=\frac{R\log(1/\delta)}{100\log d}.$

Recall the condition of Line 34, if $\widehat{\eta}_{k}\not=0$, then we have

$\displaystyle A_{q_{k},k}\geq\gamma.$

For a fixed $k\in[P]$, since the sampling process is independent for each
$r\in[R]$, we can assume that

$\displaystyle\operatorname*{{\mathbb{E}}}[A_{q_{k},k}]=R\eta_{k,q_{k}}\geq\gamma.$

Otherwise, by Chernoff bound (Lemma A.2), we get that

$\displaystyle\Pr[A_{q_{k},k}\geq\gamma]=o(\delta^{\Omega(\log d)}),$

which implies that with probability at least $1-\delta^{\Omega(\log d)}$,
$\widehat{\eta}_{k}=0$ for all $k\in[P]$, and we are done.

Thus, under this assumption, by Chernoff bound (Lemma A.2), we have

$\displaystyle\Pr[|A_{q_{k},k}-R\cdot\eta^{*}_{k,q_{k}}|\geq\epsilon
R\eta_{k,q_{k}}]\leq\exp(-\Omega(\epsilon^{2}\gamma))=\delta^{\Omega(\log
d)}.$

Since $P=\operatorname{poly}\log(d)$, by union bound over the $B_{k}$ , the
event

$\displaystyle(1-\epsilon_{1})\eta_{k,q_{k}}\leq\frac{A_{q_{k},k}}{R_{k}}\leq(1+\epsilon_{1})\eta_{k,q_{k}}$

holds for all $k\in[P]$ with probability at least
$1-\delta^{\Omega(\log(d))}$. Since
$\widehat{\eta}_{k}=\frac{A_{k,q_{k}}}{R(1+\epsilon_{1})}$ by definition, we
get the desired bounds.

Thus we complete the proof. ∎

######  Definition F.7.

We define $q_{k}$ as

$\displaystyle
q_{k}:=\max_{l\in[L]}\Big{\\{}l|A_{l,k}\geq\frac{R\log(1/\delta)}{100\log(d)}\Big{\\}}.$

We say that $q_{k}$ is well-defined if the set in the RHS of the above
definition is non-empty.

At Line 33 in Algorithm 7, we define the $q^{i}_{k}$ for $i$-th vector as the
definition above.

######  Lemma F.8 (Maximizer Probability).

If layer $k\in[P]$ is important (Line 33 in Algorithm 7), then with
probability at least $1-\delta^{\Omega(\log d)}$, the maximizer $q_{k}$ is
well defined.

###### Proof.

Lemma F.5 tells us that, when $p_{k}b_{k}=O(1)$, layer $k$ is at least
$\Omega(\frac{\beta}{P\log(1/\delta)})$-trackable. On the other hand, if
$P_{k}=2^{-l_{0}}=1/b_{k}$, we have $\eta_{k,l_{0}}=1-(1-p_{k})^{b_{k}}\geq
1/e$. Thus we have

$\displaystyle\operatorname*{{\mathbb{E}}}[A_{l_{0},k}]\geq R/e,$

so by Chernoff bound (Lemma A.2),

$\displaystyle\Pr[A_{l_{0},k}\leq$
$\displaystyle~{}\frac{R\log(1/\delta)}{\log
d}]\leq\exp(-\Omega(\frac{R\log(1/\delta)}{\log d}))$ $\displaystyle\leq$
$\displaystyle~{}\delta^{\Omega(\log d)}.$

Thus we show that, there exists one $q_{k}\geq l_{0}$ with probability at
least $1-\delta^{\Omega(\log n)}$.

Since there are at most $P=\operatorname{poly}\log(d)$ important layers, with
probability at least $1-\delta^{\Omega(\log n)}$, the corresponding value of
$q_{k}$ is well defined for all important layers.

Thus we complete the proof. ∎

###  F.4 From Probability Estimation to Layer Size Approximation

The following lemma shows that, if we have a sharp estimate for the track
probability of a layer, then we can obtain a good approximation for its size.

######  Lemma F.9 (Track probability implies layer size approximation).

Suppose $q_{k}\geq 1$, $\epsilon\in(0,1/2)$, and $d$ is sufficiently large.
Define $\epsilon_{1}:=O(\epsilon^{2}/\log(d))$. We have for $k\in[P]$,

  * •

Part 1. If $\widehat{\eta}_{k}\leq\eta_{k,q_{k}}$ then $c_{k}\leq b_{k}$.

  * •

Part 2. If $\widehat{\eta}_{i}\geq(1-\epsilon_{1})\eta_{k,q_{k}}$ then
$c_{k}\geq(1-O(\epsilon_{1}))b_{k}$.

###### Proof.

We know that

$\displaystyle b_{k}=\frac{\log(1-\eta_{k,q_{k}})}{\log(1-2^{-q_{k}})},$

which is a increasing function of $\eta_{k,q_{k}}$.

Part 1. If $\widehat{\eta}_{k}\leq\eta_{k,q_{k}}$, then $c_{k}\leq b_{k}$.

Part 2. If $\widehat{\eta}_{k}\geq(1-O(\epsilon))\eta_{k,q_{k}}$ we have

$\displaystyle c_{k}\geq
b_{k}+\frac{\epsilon_{1}\eta_{k,q_{k}}}{(1-\eta_{k,q_{k}})\log(1-2^{-q_{k}})}\geq
b_{k}-O(\epsilon)b_{k}.$

Thus we complete the proof. ∎

##  Appendix G Space Complexity

In this section, we prove the space complexity of our data structure.

######  Lemma G.1 (Space complexity of our data structure, formal version of
Lemma 4.4).

Our data structure (Algorithm 4 and 5) uses
$O(\epsilon^{-9}n(d+\mathrm{mmc}(l)^{2})\log^{14}(nd/\delta))$ space.

###### Proof.

First, we store the original data,

$\displaystyle\mathrm{space~{}for~{}}x=O(nd).$

Second, we store the sub stream/sample of orignal data

$\displaystyle\mathrm{space~{}for~{}}\overline{x}=$ $\displaystyle~{}O(RLUnd)$
$\displaystyle=$
$\displaystyle~{}O(\epsilon^{-4}\log(n/\delta)\log^{4}(d)\cdot\log(d)\cdot\log(nd^{2}/\delta)\cdot
nd)$ $\displaystyle=$ $\displaystyle~{}O(\epsilon^{-4}nd\log^{6}(nd/\delta)).$

Our data structure holds a set $\\{S_{r,l,u}\\}_{r\in[R],l\in[L],u\in[U]}$
(Line 10). Each $S_{r,l,u}$ has a size of
$\mathcal{S}_{\mathrm{space}}(\sqrt{\beta},d)=O(n\cdot\beta^{-1}\log^{2}(d)\log(nd))$,
which uses the space of

$\displaystyle\mathrm{space~{}for~{}}S=$
$\displaystyle~{}O(RLUn\cdot\beta^{-1}\log^{2}(d)\log(nd))$ $\displaystyle=$
$\displaystyle~{}O(\epsilon^{-4}\log(n/\delta)\log^{4}(d)\cdot\log(d)\cdot\log(nd)\cdot\log(nd^{2}/\delta)\cdot
n\cdot(\epsilon^{-5}\cdot\mathrm{mmc}(l)^{2}\log^{5}(d))\log^{2}(d))$
$\displaystyle=$
$\displaystyle~{}O(\epsilon^{-9}n\cdot\mathrm{mmc}(l)^{2}\log^{14}(nd/\delta))$

where the first step follows from the definition of $R,L,U$, and the second
step follows just simplifying the last step.

We hold a $\mathrm{bmap}$ (Line 17 and Line 19) of size $O(RLUd)$, which uses
the space of

$\displaystyle\mathrm{space~{}for~{}bmap}=$ $\displaystyle~{}O(RLUd)$
$\displaystyle=$
$\displaystyle~{}O(\epsilon^{-4}\log(n/\delta)\log^{4}(d)\cdot\log(d)\cdot\log(nd^{2}/\delta)\cdot
d)$ $\displaystyle=$ $\displaystyle~{}O(\epsilon^{-4}d\log^{6}(nd/\delta)).$

In Query, we generate a set of sets
$\\{H_{r,l,u}\\}_{r\in[R],l\in[L],u\in[U]}$, each of the sets has size of
$O(\beta^{-1})$, so the whole set uses space of

$\displaystyle\mathrm{space~{}for~{}}H=$
$\displaystyle~{}O(RLU\cdot\beta^{-1})$ $\displaystyle=$
$\displaystyle~{}O(\epsilon^{-4}\log(n/\delta)\log^{4}(d)\cdot\log(d)\cdot\log(nd^{2}/\delta)\cdot\epsilon^{-5}\cdot\mathrm{mmc}(l)^{2}\log^{5}(d))$
$\displaystyle=$
$\displaystyle~{}O(\epsilon^{-9}\cdot\mathrm{mmc}(l)^{2}\log^{11}(nd/\delta)).$

By putting them together, we have the total space is

$\displaystyle~{}\mathrm{total~{}space}$ $\displaystyle=$
$\displaystyle~{}\mathrm{space~{}for~{}}x+\mathrm{space~{}for~{}}\overline{x}+\mathrm{space~{}for~{}}S+\mathrm{space~{}for~{}bmap}+\mathrm{space~{}for~{}}H$
$\displaystyle=$
$\displaystyle~{}O(nd)+O(\epsilon^{-4}nd\log^{6}(nd/\delta))+O(\epsilon^{-9}n\cdot\mathrm{mmc}(l)^{2}\log^{13}(nd/\delta))$
$\displaystyle~{}+O(\epsilon^{-4}d\log^{6}(nd/\delta))+O(\epsilon^{-9}\cdot\mathrm{mmc}(l)^{2}\log^{11}(nd/\delta))$
$\displaystyle=$
$\displaystyle~{}O(\epsilon^{-9}n(d+\mathrm{mmc}(l)^{2})\log^{14}(nd/\delta)).$

Thus, we complete the proof.

∎

##  Appendix H Lower Bound From Previous Work

We first define turnstile streaming model (see page 2 of [32] as an example)
as follows

######  Definition H.1 (Turnstile streaming model).

We define two different turnstile streaming models here:

  * •

Strict turnstile: Each update $\Delta$ may be an arbitrary positive or
negative number, but we are promised that $x_{i}\geq 0$ for all $i\in[n]$ at
all points in the stream.

  * •

General turnstile: Each update $\Delta$ may be an arbitrary positive or
negative number, and there is no promise that $x_{i}\geq 0$ always. Entries in
$x$ may be negative.

Under the turnstile model, the _norm estimation problem_ has the following
streaming lower bound:

######  Theorem H.2 (Theorem 1.2 in [10]).

Let $l$ be a symmetric norm on $\mathbb{R}^{n}$. Any turnstile streaming
algorithm (Definition H.1) that outputs, with probability at least $0.99$, a
$(1\pm 1/6)$-approximation for $l(\cdot)$ must use
$\Omega(\mathrm{mmc}(l)^{2})$ bits of space in the worst case.

We note that this problem is a special case of our symmetry norm distance
oracle problem (i.e., with $n=1$ and query vector $q={\bf 0}_{d}$ where ${\bf
0}_{d}$ is a all zeros length-$d$ vector). And in this case, the query time of
our data structure becomes $\widetilde{O}(\mathrm{mmc}(l)^{2})$ for a
constant-approximation, matching the streaming lower bound in Theorem H.2.

##  Appendix I Details About Sparse Recovery Tools

In this section we give an instantiation of the sparse recovery tool we use
(Definition D.2) in Algorithms 10 \- 12. Although the running times of our
data structure are slightly worse (by some log factors) than the result of
[29], it’s enough for our symmetric norm estimation task. In terms of space
requirement, the classical sparse recovery/compressed sensing only sublinear
space is allowed. In our application, we’re allowed to use linear space (e.g.
$d$ per point, $nd$ in total). And more importantly, our instantiation has
much simpler algorithm and analysis than the prior result.

Algorithm 10 Our CountSketch for Batch heavy hitter

1:data structure BasicBatchHeavyHitter $\triangleright$ Definition D.2

2:members

3: $d,n\in\mathbb{N}^{+}$ $\triangleright$ $n$ is the number of vectors, $d$
is the dimension.

4: $\epsilon$ $\triangleright$ We are asking for $\epsilon$-heavy hitters

5: $\delta$ $\triangleright$ $\delta$ is the failure probability

6: $B$ $\triangleright$ $B$ is the multiple number of each counter to take
mean

7: $L$ $\triangleright$ $L$ is the number of number of the level of the binary
tree.

8: $\eta$ $\triangleright$ $\eta$ is the precision for $l_{2}$ norm
estimation.

9: $K$ $\triangleright$ $K$ is the number of hash functions.

10: $\\{h_{l,k}\\}_{l\in\\{0,\dots,L\\},k\in[K]}\subseteq[2^{l}]\times[B]$
$\triangleright$ hash functions.

11: $\\{C^{i}_{l,b}\\}_{i\in[n],l\in\\{0,\dots,L\\},b\in[B]}$ $\triangleright$
The counters we maintain in CountSketch.

12:
$\\{\sigma_{l,k}\\}_{l\in\\{0,\dots,L\\},k\in[K]}\subseteq[d]\times\\{+1,-1\\}$
$\triangleright$ The hash function we use for norm estimation

13: $\mathcal{Q}$ $\triangleright$ A instantiation of LpLpTailEstimation
(Algorithm 13)

14: $\\{\mathcal{D}_{l}\\}_{l\in[L]}$ $\triangleright$ Instantiations of FpEst
(Algorithm 14)

15:end members

16:

17:public:

18:procedure Init($\epsilon,n\in\mathbb{N}^{+},d\in\mathbb{N}^{+},\delta$)

19: $L\leftarrow\log_{2}d$

20: $\delta^{\prime}\leftarrow\epsilon\delta/(12(\log d)+1)$

21: for $l\in\\{0,\dots,L\\}$ do

22: $\mathcal{D}_{l}.\textsc{Init}(n,d,l,1/7,\epsilon,\delta^{\prime})$

23: end for

24: $C_{0}\leftarrow$ greater than $1000$

25: $\mathcal{Q}.\textsc{Init}(n,\epsilon^{-2},2,C_{0},\delta)$

26:end procedure

Algorithm 11 Our CountSketch for Batch heavy hitter

1:data structure BasicBatchHeavyHitter $\triangleright$ Definition D.2

2:procedure EncodeSingle($i\in[n],j\in[d],z\in\mathbb{R},d$)

3: for $l\in\\{0,\dots,L\\}$ do

4: $\mathcal{D}_{l}.\textsc{Update}(i,j,z)$

5: end for

6: $\mathcal{Q}.\textsc{Update}(i,j,z)$

7:end procedure

8:

9:procedure Encode($i\in[n],z\in\mathbb{R}^{d},d$)

10: for $j\in[d]$ do

11: $\textsc{EncodeSingle}(i,j,z_{j},d)$

12: end for

13:end procedure

14:

15:end data structure

Algorithm 12 Our CountSketch for Batch heavy hitter

1:data structure BasicBatchHeavyHitter $\triangleright$ Definition D.2

2:procedure Subtract($i,j,k\in[n]$)

3: for $l\in\\{0,\dots,L\\}$ do

4: $\mathcal{D}_{l}.\textsc{Subtract}(i,j,k)$

5: end for

6: $\mathcal{Q}.\textsc{Subtract}(i,j,k)$

7:end procedure

8:

9:procedure Decode($i\in[n],\epsilon,d$)

10: $\mathrm{EstNorm}\leftarrow\mathcal{Q}.\textsc{Query}(i)$ $\triangleright$
Here the $\mathrm{EstNorm}$ is the estimated tail $l_{2}$-norm of $i$-vector.

11: $S\leftarrow\\{0\\},S^{\prime}\leftarrow\emptyset$

12: for $l\in\\{0,\dots,L\\}$ do $\triangleright$ The dyadic trick.

13: for $\xi\in S$ do

14: $\mathrm{Est}\leftarrow\mathcal{D}.\textsc{Query}(i,\xi)$

15: if $\mathrm{Est}\geq(3/4)\epsilon^{2}\cdot\mathrm{EstNorm}$ then

16: $S^{\prime}\leftarrow S^{\prime}\cup\\{2\xi,2\xi+1\\}$

17: end if

18: end for

19: $S\leftarrow S^{\prime}$, $S^{\prime}\leftarrow\emptyset$

20: end for

21: return $S$

22:end procedure

23:end data structure

The following lemma shows that the sparse recovery data structure satisfies
our requirements in Theorem D.3.

###  I.1 Our Sparse Recovery Tool

Algorithm 13 Batched $\ell_{p}$ tail estimation algorithm, based on [38]

1:data structure LpLpTailEstimation

2:members

3: $m$ $\triangleright$ $m$ is the sketch size

4: $\\{g_{j,t}\\}_{j\in[d],t\in[m]}$ $\triangleright$ random variable that
sampled i.i.d. from distribution $\mathcal{D}_{p}$

5: $\\{\delta_{j,t}\\}_{j\in[d],t\in[m]}$ $\triangleright$ Bernoulli random
variable with $\operatorname*{{\mathbb{E}}}[\delta_{j,t}]=1/(100k)$

6: $\\{y_{i,t}\\}_{i\in[n],t\in[m]}$ $\triangleright$ Counters

7:end members

8:public:

9:procedure Init($n,k,p,C_{0},\delta$)

10: $m\leftarrow O(\log(n/\delta))$

11: Choose $\\{g_{j,t}\\}_{j\in[d],t\in[m]}$ to be random variable that
sampled i.i.d. from distribution $\mathcal{D}_{p}$

12: Choose $\\{\delta_{j,t}\\}_{j\in[d],t\in[m]}$ to be Bernoulli random
variable with $\operatorname*{{\mathbb{E}}}[\delta_{j,t}]=1/(100k)$
$\triangleright$ Matrix $A$ in Lemma I.4 is implicitly constructed based on
$g_{j,t}$ and $\delta_{j,t}$

13: initialize $\\{y_{i,t}\\}_{i\in[n],t\in[m]}=\\{0\\}$

14:end procedure

15:

16:procedure Update($i\in[n],j\in[d],z\in\mathbb{R}$)

17: for $t\in[m]$ do

18: $y_{i,t}\leftarrow y_{i,t}+\delta_{j,t}\cdot g_{jt}\cdot z$

19: end for

20:end procedure

21:

22:procedure Subtract($i,j,k\in[n]$)

23: for $t\in[m]$ do

24: $y_{i,t}\leftarrow y_{j,t}-y_{k,t}$

25: end for

26:end procedure

27:

28:procedure Query($i\in[n]$)

29: $V\leftarrow\operatorname*{median}_{t\in[m]}|y_{i,t}|^{2}$

30: return $V$

31:end procedure

We first state the correctness, the proof follows from framework of [29].

######  Lemma I.1.

The function Decode$(i,\epsilon,d,\delta)$ (Algorithm 12) returns a set
$S\subseteq d$ of size $|S|=O(\epsilon^{-2})$ containing all $\epsilon$-heavy
hitters of the $i$-column of the matrix under $l_{2}$ with probability of
$1-\delta$. Here we say $j$ is an $\epsilon$-heavy hitter under $l_{2}$ if
$|x_{j}|\geq\epsilon\cdot\|x_{\overline{[\epsilon^{-2}]}}\|_{2}$ where
$x_{\overline{[k]}}$ denotes the vector $x$ with the largest $k$ entries (in
absolute value) set to zero. Note that the number of heavy hitters never
exceeds $2/\epsilon^{2}$.

###### Proof.

The correctness follows from the framework of [29], and combining tail
estimation (Lemma I.4) and norm estimation.

∎

We next analyze the running time of our data structure in the following lemma:

######  Lemma I.2.

The time complexity of our data structure (Algorithm 10, Algorithm 11 and
Algorithm 12) is as follows:

  * •

Init takes time of $O(\epsilon^{-1}(n+d)\log^{2}(nd/\delta))$.

  * •

EncodeSingle takes time of $O(\log^{2}(nd/\delta))$.

  * •

Encode takes time of $O(d\log^{2}(nd/\delta))$.

  * •

Subtract takes time of $O(\epsilon^{-1}\log^{2}(nd/\delta))$.

  * •

Decode takes time of $O(\epsilon^{-2}\log^{2}(nd/\delta))$.

###### Proof.

We first notice that $L=\log_{2}d$ and
$\delta^{\prime}=\epsilon\delta/(12(\log(d)+1))$.

For the procedure Init (Algorithm 10), Line 22 takes time

$\displaystyle
O(L\epsilon^{-1}n\log(n/\delta^{\prime}))=O(\epsilon^{-1}n\log^{2}(\delta^{-1}\epsilon^{-1}nd\log(d)).$

Line 25 takes time $O((n+d)\log(n/\delta))$. Taking together, we have the
total running time of Init is
$O(\epsilon^{-1}(n+d)\log^{2}(\delta^{-1}\epsilon^{-1}nd\log(d))$

For the procedure EncodeSingle (Algorithm 11), Line 4 takes time of

$\displaystyle
O(L\log(n/\delta^{\prime}))=O(\log^{2}(\epsilon^{-1}\delta^{-1}nd\log(d))).$

Line 6 takes time of $O(\log(n/\delta))$. Taking together we have the total
running time of EncodeSingle to be
$O(\log^{2}(\epsilon^{-1}\delta^{-1}nd\log(d)))$.

For the procedure Encode (Algorithm 11), it runs EncodeSingle for $d$ times,
so its running time is $O(d\log^{2}(\epsilon^{-1}\delta^{-1}nd\log(d)))$.

For the procedure Subtract (Algorithm 12), Line 4 runs in time

$\displaystyle
O(L\epsilon^{-1}\log(n/\delta^{\prime}))=O(\epsilon^{-1}\log^{2}(\epsilon^{-1}\delta^{-1}nd\log(d))).$

Line 6 runs in time $O(\log(n/\delta))$. So the total running time is
$O(\epsilon^{-1}\log^{2}(\epsilon^{-1}\delta^{-1}nd\log(d)))$.

For the procedure Decode (Algorithm 12), Line 10 runs in time
$O(\log(n/\delta))$. Line 14 runs in time

$\displaystyle
O(L\epsilon^{-2}\log(n/\delta^{\prime}))=O(\epsilon^{-2}\log^{2}(\epsilon^{-1}\delta^{-1}nd\log(d))).$

So the total running time is
$O(\epsilon^{-2}\log^{2}(\epsilon^{-1}\delta^{-1}nd\log(d)))$

Thus we complete the proof. ∎

The space complexity of our data structure is stated in below.

######  Lemma I.3.

Our batch heavy hitter data structure (Algorithm 10, Algorithm 11 and
Algorithm 12) takes the space of

$\displaystyle
O(\epsilon^{-1}(n+d)\log^{2}(\epsilon^{-1}\delta^{-1}nd\log(d))).$

###### Proof.

Our data structure has these two parts to be considered:

  * •

The instantiations of FpEst we maintain.

  * •

The instantiation of LpLpTailEstimation we maintain .

The first part takes the space of

$\displaystyle
O(L\epsilon^{-1}n\log(n/\delta^{\prime}))=O(\epsilon^{-1}n\log^{2}(\epsilon^{-1}\delta^{-1}nd\log(d))).$

And the second part takes the space of $O(d\log(n/\delta))$. Adding them
together we complete the proof. ∎

###  I.2 Lp Tail Estimation

[38] provide a linear data structure LpLpTailEstimation$(x,k,p,C_{0},\delta)$
that can output the estimation of the contribution of non-heavy-hitter
entries. We restate their Lemma as followed.

######  Lemma I.4 (Lemma C.4 of [38]).

Let $C_{0}\geq 1000$ denote some fixed constant. There is an oblivious
construction of matrix $A\in\mathbb{R}^{m\times n}$ with $m=O(\log(1/\delta))$
along with a decoding procedure LpLpTailEstimation$(x,k,p,C_{0},\delta)$ such
that, given $Ax$, it is possible to output a value $V$ in time O(m) such that

$\displaystyle\frac{1}{10k}\|x_{\overline{C_{0}k}}\|_{p}^{p}\leq
V\leq\frac{1}{k}\|x_{\overline{k}}\|_{p}^{p},$

holds with probability $1-\delta$.

######  Lemma I.5.

The running time of the above data structure is

  * •

Init runs in time of $O((n+d)\log(n/\delta))$

  * •

Update runs in time of $O(\log(n/\delta))$

  * •

Subtract runs in time of $O(\log(n/\delta))$

  * •

Query runs in time of $O(\log(n/\delta))$

And its space is $O(d\log(n/\delta))$.

###  I.3 Lp Norm Estimation

Algorithm 14 Batched $\ell_{p}$ norm estimation algorithm, based on [30]

1:data structure LpNormEst

2:members

3: $R,T$ $\triangleright$ parallel parameters

4: $m$ $\triangleright$ Sketch size

5: $\\{y^{i}_{r,t}\\}_{i\in[n],r\in[R],t\in[T]}\subset\mathbb{R}^{m}$
$\triangleright$ Sketch vectors

6: $\\{A\\}_{r,t}\subset\mathbb{R}^{m\times 2^{l}}$ $\triangleright$ Sketch
matrices

7: $\\{h_{t}\\}_{t\in[T]}:\\{0,\dots,2^{l}\\}\rightarrow[R]$ $\triangleright$
hash functions

8:end members

9:

10:public:

11:procedure Init($n,d,l,\phi,\epsilon$)

12: $R\leftarrow\lceil 1/\epsilon\rceil$

13: $T\leftarrow\Theta(\log(n/\delta))$

14: $m\leftarrow O(1/\phi^{2})$

15: for $i\in[n],r\in[R],t\in[T]$ do

16: $y^{i}_{r,t}\leftarrow\textbf{0}$ $\triangleright$ Sketch vectors

17: end for

18: for $i\in[n],r\in[R],t\in[T]$ do

19: generate $A_{r,t}\in\mathbb{R}^{m\times 2^{l}}$ $\triangleright$ See [30]
for details

20: end for

21: initialize $h$

22:end procedure

23:

24:procedure Update($i\in[n],j\in[d],z\in\mathbb{R}$)

25: $\xi\leftarrow j\cdot 2^{l}/d$

26: for $t\in[T]$ do

27: $y^{i}_{h_{t}(\xi),t}\leftarrow
y^{i}_{h_{t}(\xi),t}+A_{h_{t}(\xi),t}\mathbf{i}^{l}_{j,z}$ $\triangleright$
$\mathbf{i}^{l}_{j,z}$ is define to be the $2^{l}$-dimensional vector with
$j$-th entry of $z$ and others to be $0$

28: end for

29:end procedure

30:

31:procedure Subtract($i,j,k\in[n]$)

32: for $r\in[R],t\in[T]$ do

33: $y^{i}_{r,t}\leftarrow y^{j}_{r,t}-y^{k}_{r,t}$

34: end for

35:end procedure

36:

37:procedure Query($i\in[n],\xi\in[2^{l}]$)

38: for $t\in[T]$ do

39:
$V_{h_{t}(\xi),t}\leftarrow\operatorname*{median}_{\zeta\in[m]}y^{i}_{r,t,\zeta}/\operatorname*{median}(|\mathcal{D}_{p}|)$
$\triangleright$ Definition A.5

40: end for

41: $V\leftarrow\operatorname*{median}_{t\in[T]}V_{h_{t}(\xi),t}$

42: return $V$

43:end procedure

Following the work of [30], we provide a linear sketch satisfying the
following requirements.

######  Lemma I.6 ([30]).

There is a linear sketch data structure FpEst using space of

$\displaystyle O(\epsilon^{-1}\phi^{-2}n\log(n/\delta))$

and it provide these functions:

  * •

Init$(n\in\operatorname*{\mathbb{Z}}^{+},d\in\operatorname*{\mathbb{Z}}^{+},l\in\operatorname*{\mathbb{Z}}^{+},\phi,\epsilon,\delta)$:
Initialize the sketches, running in time $O(\epsilon^{-1}n\log(n/\delta))$

  * •

Update$(i\in[n],j\in[d],z\in\mathbb{R})$: Update the sketches, running in time
$O(\log(n/\delta))$

  * •

Subtract$(i,j,k\in[n])$: Subtract the sketches, running in time
$O(\epsilon^{-1}\phi^{-2}\log(n/\delta))$

  * •

Query$(i\in[n],\xi\in[2^{l}])$: This function will output a $V$ satisfying

$\displaystyle(1-\phi)\cdot F_{i}(l,\xi)\leq
V\leq(1+\phi)\cdot(F_{i}(l,\xi)+5\epsilon\|x_{i}\|_{2}^{2}),$

where $F(l,\xi)$ is defined as

$\displaystyle
F_{i}(l,\xi):=\sum_{j=\frac{\xi}{2^{l}}d}^{\frac{\xi+1}{2^{l}}d-1}|x_{i,j}|^{2},$

running in time $O(\phi^{-2}\log(n/\delta))$

We choose $\phi$ to be constant when we use the above Lemma.