# Dimensionality reduction on complex vector spaces for dynamic weighted
Euclidean distance

Paolo Pellizzoni<EMAIL_ADDRESS>University of Padova and
Francesco Silvestri<EMAIL_ADDRESS>University of Padova

(2018)

###### Abstract.

The weighted Euclidean distance between two vectors is a Euclidean distance
where the contribution of each dimension is scaled by a given non-negative
weight. The Johnson–Lindenstrauss (JL) lemma can be easily adapted to the
weighted Euclidean distance if weights are known at construction time. Given a
set of $n$ vectors with dimension $d$, it suffices to scale each dimension of
the input vectors according to the weights, and then apply any standard JL
reduction: the weighted Euclidean distance between pairs of vectors is
preserved within a multiplicative factor $\varepsilon$ with high probability.

However, this is not the case when weights are provided after the
dimensionality reduction. In this paper, we show that by applying a linear map
from real vectors to a complex vector space, it is possible to update the
compressed vectors so that the weighted Euclidean distances between pairs of
points can be computed within a multiplicative factor $\varepsilon$, even when
weights are provided after the dimensionality reduction. Finally, we consider
the estimation of weighted Euclidean norms in streaming settings: we show how
to estimate the weighted norm when the weights are provided either after or
concurrently with the input vector.

dimensionality reduction, Johnson-Lindestrauss, complex space, streaming

††copyright: none††copyright: acmcopyright††journalyear: 2018††doi:
XXXXXXX.XXXXXXX††conference: Make sure to enter the correct conference title
from your rights confirmation emai; June 03–05, 2018; Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06††ccs: Theory of computation Sketching and
sampling††ccs: Theory of computation Nearest neighbor algorithms††ccs: Theory
of computation Random projections and metric embeddings

##  1\. Introduction

The weighted Euclidean distance between two vectors is a Euclidean distance
where the contribution of each dimension is scaled by a given weight
representing the relevance of the dimension: given a vector
$x\in\mathbb{R}^{d}$ and a weight vector $w\in\mathbb{R}^{d}$ (with $w_{i}\geq
0$ for all $i\in\\{1,\ldots d\\}$), the _weighted norm_ of $x$ with weights
$w$ is defined as $\left\lVert
x\right\rVert_{w}=\sqrt{\sum_{i=1}^{d}w_{i}^{2}x_{i}^{2}}$. The weighted
Euclidean distance between two vectors $x,y$ is then $\left\lVert
x-y\right\rVert_{w}$.

The weighted Euclidean distance is widely used in _feature weighting_ (nino21,
): given a set $S$ of $n$ vectors in $\mathbb{R}^{d}$, the goal of feature
weighting is to estimate a vector of $d$ weights $w$ representing the degree
of relevance that each feature (i.e., dimension) has on the desired output.
Feature weighting is used to improve the quality of several tasks, like
recommendation systems and $k$-NN classifier (see e.g., (WangWY15, ; GuZHS16,
; Amorim16, ; BhattacharyaGC17, ) and the survey (nino21, )). For instance,
feature weighting in collaborative filtering may improve the accuracy of
prediction since it can enhance the role of relevant products while reducing
the impacts of irrelevant products (YuXEK03, ). We observe that, when weights
are known and fixed, a task with weighted Euclidean distances can usually be
solved by algorithms for the unweighted case: it suffices to scale the entire
input set $S$ (i.e., replacing $x\in S$ with $w\odot x$, where $\odot$
represents the element-wise multiplication) and obtain a new input set
$S^{\prime}$; then, the new set is used as input for any algorithm for the
unweighted case. However, this is not the case when the weight vector is not
fixed and unique. For instance, in recommendation systems, user preferences
might dynamically change over time implying a change in feature weights
(BarddalGEPB16, ).

Dimensionality reduction methods are usually adopted to reduce the size of
high-dimensional vectors without significantly losing information: the low-
dimension vectors reduce communication and storage costs and mitigate the
curse of dimensionality in the running time. A well-known result on
dimensionality reduction is provided by the _Johnson–Lindenstrauss (JL) lemma_
(JL84, ): given a set $S$ of $n$ vectors in $\mathbb{R}^{d}$, there exists a
linear map $g(\cdot)$ that approximately maintains pairwise squared Euclidean
distances; that is, for any $x,y\in S$, we have that $|\left\lVert
x-y\right\rVert_{2}^{2}-\left\lVert
g(x)-g(y)\right\rVert_{2}^{2}|\leq\varepsilon\left\lVert
x-y\right\rVert_{2}^{2}$. The JL lemma holds even with weighted Euclidean
distance if weights are known beforehand. Consider one of the several linear
maps $g(x)$ satisfying the JL lemma, for instance $g(x)=Ax$ where $A$ is the
Achlioptas’ matrix (Achlioptas03, ) (i.e., each element is a random value in
$\\{-1,1\\}$): if all input vectors in $S$ are scaled according to the given
weights $w$, the map $g(x^{\prime})$ gives $|\left\lVert
x-y\right\rVert_{w}^{2}-\left\lVert
g(x^{\prime})-g(y^{\prime})\right\rVert_{2}^{2}|\leq\varepsilon\left\lVert
x-y\right\rVert_{w}^{2}$, where $x^{\prime}$ is the scaled version of the
input vector $x\in S$. However, this does not hold if weights are unknown, or
if weights change over time: to the best of our knowledge, there are no
previous works addressing this problem.

##### Our results.

In this paper, we provide the first solution to dimensionality reduction with
dynamic weights. We map vectors in $S$ into a low dimensional complex vector
space with a linear map $g(x)=Ax$ with
$g:\mathbb{R}^{d}\rightarrow\mathbb{C}^{k}$ and $A$ a $k\times d$ random
matrix. When weights are known, we then apply a suitable function on the low-
dimensional vectors to estimate the squared weighted Euclidean norms and the
pairwise distances for any pair of vectors in $S$ and for any weight vector
$w$. The map is done before the weights are revealed and it is hence
independent of weights. More specifically, matrix $A$ is a complex $k\times d$
random matrix, where each entry is an independently and identically
distributed random variable over $\\{+1,-1,+i,-i\\}$, where $i$ is the
imaginary unit (i.e., $i^{2}=-1$) and $k>0$ is a suitable value. Let
$g(x)=Ax/\sqrt{k}$, $h(x,w)=g(x)\odot\sqrt{k}g(w)$, and
$\rho(x,w)=\textnormal{Re}\left(\displaystyle h(x,w)\cdot h(w,x)\right)$,
where $\odot$ is the element-wise multiplication, $\cdot$ is the inner
product, and $\textnormal{Re}\left(\displaystyle\right)$ is the real part. We
claim that the expected value of $\rho(x,w)$ is $\left\lVert
x\right\rVert_{w}^{2}$. Let $\Delta$ be a given parameter named _distortion
threshold_ ; if
$k=\Omega\left(\varepsilon^{-2}\Delta^{4}\ln(1/\delta)\right)$, we also claim
that the following statement holds with probability at least $1-\delta$ for
any given $x$ and $w$:

  * •

(Multiplicative error) If $\Delta\geq\left\lVert x\right\rVert_{2}\left\lVert
w\right\rVert_{2}/\left\lVert x\right\rVert_{w}$, then

$(1-\varepsilon)\left\lVert
x\right\rVert_{w}^{2}\leq\rho(x,w)\leq(1+\varepsilon)\left\lVert
x\right\rVert_{w}^{2}.$

  * •

(Additive error) If $\Delta<\left\lVert x\right\rVert_{2}\left\lVert
w\right\rVert_{2}/\left\lVert x\right\rVert_{w}$, then

$\left\lVert x\right\rVert_{w}^{2}-\varepsilon\frac{\left\lVert
x\right\rVert_{2}^{2}\left\lVert
w\right\rVert_{2}^{2}}{\Delta^{2}}\leq\rho(x,w)\leq\left\lVert
x\right\rVert_{w}^{2}+\varepsilon\frac{\left\lVert
x\right\rVert_{2}^{2}\left\lVert w\right\rVert_{2}^{2}}{\Delta^{2}}.$

In other words, if the given weights create a _distortion_
$\Delta(x,w)=\left\lVert x\right\rVert_{2}\left\lVert
w\right\rVert_{2}/\left\lVert x\right\rVert_{w}$ lower than the given
distortion threshold $\Delta$, then we have an $\varepsilon$ approximation as
in the JL lemma; otherwise, we get a bounded additive error
$\varepsilon\frac{\left\lVert x\right\rVert_{2}^{2}\left\lVert
w\right\rVert_{2}^{2}}{\Delta^{2}}$. The results are provided in Section 3.
Note that function $\rho(x,w)$ is not a norm: the function can indeed returns
a negative value; however its expected behavior is as the weighted squared
Euclidean distance.

We remark that the above dimensionality reduction method allows us to estimate
pairwise weighted Euclidean distances. Specifically, given a set $S$ of $n$
vectors and let $S^{\prime}=\\{g(x),\forall x\in S\\}$, we have that
$\rho(x-y)$ is a good estimate of $\left\lVert x-y\right\rVert_{w}^{2}$. Note
that $\rho(x-y)$ can be computed from the embeddings of $g(x)$ and $g(y)$
since $g(\cdot)$ is a linear function. We observe that the real function
$B(x\odot x)\odot B(w\odot w)$, where $B$ is a real random matrix with entries
in $\\{-1,1\\}$, gives a simpler and unbiased estimator of $\left\lVert
x\right\rVert_{w}^{2}$: however, it cannot be used for estimating pairwise
weighted distances since the operation is not linear in $x$.

In Section 4, we show that the proposed approach with complex numbers can also
be used in the streaming settings to estimate $\left\lVert
x\right\rVert_{w}^{2}$ when both $x$ and $w$ are provided in the stream in
arbitrary order. We recall that, in the streaming model of computation, data
are generated continuously, and they have to be processed on-the-fly while
maintaining in memory only a small (i.e. sublinear) portion of the data. We
construct an AMS-like sketch that, by leveraging on random complex values in
$\\{+1,-1,+i,-i\\}$, allows us to estimate $\left\lVert x\right\rVert_{w}^{2}$
with a multiplicative error $\varepsilon$ and space
${O}\left(\varepsilon^{-2}(\left\lVert x\right\rVert_{2}\left\lVert
w\right\rVert_{2}/\left\lVert x\right\rVert_{w})^{4}\log(1/\delta)\right)$.
The constants in these results are better than those obtained for the above
result on dimensionality reduction. Furthermore, the sketch just requires
8-independent hash functions, and not full independence as in the previoius
result. However, the sketch is not linear and cannot be used for computing
pairwise weighted distances.

Finally, we provide a preliminary experimental evaluation of our
dimensionality reduction technique to validate our theoretical contributions.
This result and some of the following proofs are reported in the Appendix.

##### Previous work.

Recently, (LeiHKT19, ; HuL21, ) have studied the $r$-near neighbor search for
the weighted Euclidean distance when the weights are given at query time:
given a set $S$ of $n$ vectors, construct a data structure that, for any query
vector $x$ and weight vector $w$, returns a vector $y$ in $S$ such that
$\left\lVert x-y\right\rVert_{w}\leq r$. The papers leverage an asymmetric
Locality Sensitive Hashing approach that uses a dimensionality expansion built
with trigonometric functions. The result (LeiHKT19, ) focuses on the weighted
Euclidean distance, while (HuL21, ) on the Manhattan or $\ell_{1}$ distance.

In (HS17, ), the authors have proposed a variant of the nearest neighbor
search problem allowing for some coordinates of the dataset to be arbitrarily
corrupted or unknown. The goal is to preprocess the input set, such that given
a query point $q$, it is possible to efficiently find a point $x\in S$ such
that the distance of the query $q$ to the point $x$ is minimized when removing
the noisiest $k$ coordinates (i.e., coordinates are chosen so that deleting
them from both vectors minimizes their distance). The paper provides a
$(1+\varepsilon)$-approximation to the optimal solution. We observe that in
this work the coordinates to be removed are selected by the maximization
procedure, and not specified in input.

##  2\. Preliminaries

###  2.1. Basic concepts

Given a value $p>0$, the _$p$ -norm_ of a vector $x\in\mathbb{R}^{d}$ is
defined as $\left\lVert
x\right\rVert_{p}=\left(\sum_{i=1}^{d}|x|^{p}_{i}\right)^{1/p}$. Given a
_weight vector_ $w$ in $\mathbb{R}_{+}^{d}$, the _weighted $p$-norm_ of $x$ is
$\left\lVert
x\right\rVert_{w,p}=\left(\sum_{i=1}^{d}w^{p}|x|^{p}_{i}\right)^{1/p}$. When
$p=2$, we have the Euclidean norm and we simply denote the norm and the
weighted norms of $x$ as $\left\lVert x\right\rVert$ and $\left\lVert
x\right\rVert_{w}$.

We define a quantity that will be used later in the paper. Let
$x,w\in\mathbb{R}^{d}$; we define the _distortion_ of $x$ and $w$ as
$\Delta(x,w)=\frac{\left\lVert x\right\rVert_{2}\left\lVert
w\right\rVert_{2}}{\left\lVert x\right\rVert_{w}}$. Note that the distortion
of $x$ and $w$ is invariant to scaling for both the arguments, i.e.
$\Delta(ax,w)=\Delta(x,w)$ and $\Delta(x,aw)=\Delta(x,w)$ for any $a>0$.

We state some commonly known inequalities that will be used in the subsequent
sections.

###### Lemma 0 (Cauchy-Schwarz inequality).

For any $x,y\in\mathbb{R}^{d}$, we have

$\left(\sum_{i=1}^{d}x_{i}y_{i}\right)^{2}\leq\left(\sum_{i=1}^{d}x_{i}^{2}\right)\left(\sum_{i=1}^{d}y_{i}^{2}\right)=\left\lVert
x\right\rVert^{2}_{2}\left\lVert y\right\rVert^{2}_{2}.$

###### Lemma 0 (Monotonicity of $p$-norm).

For any $x\in\mathbb{R}^{d}$ and any $0<p<q<+\infty$, we have $\left\lVert
x\right\rVert_{q}\leq\left\lVert x\right\rVert_{p}$

###### Proof.

If $x=0$ the claim holds trivially. Else, let $y_{i}=|x_{i}|/\left\lVert
x\right\rVert_{q}\leq 1$. Then we have

$\begin{split}\left\lVert
x\right\rVert_{p}^{p}&=\sum_{i=1}^{d}|x_{i}|^{p}=\sum_{i=1}^{d}|y_{i}|^{p}\left\lVert
x\right\rVert_{q}^{p}\\\ &\geq\sum_{i=1}^{d}|y_{i}|^{q}\left\lVert
x\right\rVert_{q}^{p}=\left\lVert
x\right\rVert_{q}^{p}\sum_{i=1}^{d}|x_{i}|^{q}/\left\lVert
x\right\rVert_{q}^{q}=\left\lVert x\right\rVert_{q}^{p}\end{split}$

∎

###### Lemma 0.

For any $p\geq 1$ and any $x,y\in\mathbb{R}^{d}$, we have
$\sum_{i=1}^{d}|x_{i}|^{p}|y_{i}|^{p}\leq\left\lVert
x\right\rVert_{2}^{p}\left\lVert y\right\rVert_{2}^{p}$

###### Proof.

By applying Lemmas 1 and 2, we get:

$\begin{split}\sum_{i=1}^{d}x_{i}^{p}y_{i}^{p}&\leq\left(\sum_{i=1}^{d}|x_{i}|^{2p}\right)^{1/2}\left(\sum_{i=1}^{d}|y_{i}|^{2p}\right)^{1/2}\\\
&\leq\left\lVert x\right\rVert_{2p}^{p}\left\lVert
y\right\rVert_{2p}^{p}\leq\left\lVert x\right\rVert_{2}^{p}\left\lVert
y\right\rVert_{2}^{p}.\end{split}$

∎

###  2.2. Johnson-Lindenstrauss (JL) lemma

Let $X=\\{x_{1},\ldots x_{n}\\}$ be a set of $n$ vectors in $d>0$ dimensions.
For any $\varepsilon>0$, the Johnson-Lindenstrauss lemma claims that, if
$k=\Omega\left(\varepsilon^{-2}\log n\right)$, there exists a linear function
$g:\mathbb{R}^{d}\rightarrow\mathbb{R}^{k}$ that maintains pairwise distances
up to a multiplicative error $\varepsilon$. That is, for any $x,y\in X$, we
have

$(1-\varepsilon)\left\lVert x-y\right\rVert^{2}_{2}\leq\left\lVert
g(x)-g(y)\right\rVert^{2}_{2}\leq(1+\varepsilon)\left\lVert
x-y\right\rVert^{2}_{2}.$

The JL lemma has been proved to provide tight bounds (LarsenN16, ). There are
several constructions for $g(\cdot)$, for instance, those by Achlioptas
(Achlioptas03, ). Let $g(x)=Ax$ for a suitable $k\cdot d$ matrix; if
$k={\Theta}\left(\varepsilon^{-2}\log n\right)$ and each entry of $A$ is an
independent and even distributed Rademacher random variable $\\{-1,1\\}$, then
$A$ satisfies the JL lemma with high probability. The property holds even if
an entry of $A$ is 0 with probability 2/3 and in $\\{-1,1\\}$ otherwise.

###  2.3. Decoupling results and Rademacher chaos

We introduce here some results on the decoupling theory for chaos. Let
$I_{\gamma,n}\subseteq\\{1,\ldots n\\}^{\gamma}$, and let
$I^{\prime}_{\gamma,n}=\\{(i_{1},\ldots,i_{\gamma}):i_{j}\in\\{1,\ldots
n\\},i_{j}\neq i_{\gamma}\text{ if }j\neq\gamma\\}$ be a set of ordered
sequences of $\gamma$ distinct values from $\\{1,\dots,n\\}$; when $n$ is
clear from the context, we drop the subscript $n$. In the paper, we leverage a
decoupling result in (PenaGine99, ) for decoupling $U$-processes. We state
here the result in the special case of Rademacher variables, for notational
convenience.

###### Theorem 4 (Theorem $3.1.1$ (PenaGine99, )).

For natural numbers $n\geq\gamma$, let $\\{{X}_{i}\\}_{i=1}^{n}$ be a sequence
of $n$ independent Rademacher random variables, and let
$\\{{X}_{i}^{(j)}\\}_{i=1}^{n}$, with $j=1\ldots\gamma$, be $\gamma$
independent copies of this sequence. Let $I^{\prime}_{\gamma,n}$ be a set of
ordered sequences of distinct values, let $h_{(i_{1},\ldots
i_{\gamma})}:\\{-1,+1\\}^{\gamma}\rightarrow\mathbb{R}$ be a function such
that $\mathbb{E}\left[\displaystyle|h_{(i_{1},\ldots
i_{\gamma})}(X_{i_{1}},\ldots X_{i_{\gamma}})|\right]<+\infty$ for each
$(i_{1},\ldots i_{\gamma})\in I^{\prime}_{\gamma,n}$. Let also
$\Phi:\mathbb{R}^{+}_{0}\rightarrow\mathbb{R}^{+}_{0}$ be a convex non-
decreasing function such that
$\mathbb{E}\left[\displaystyle|\Phi(X_{i_{1}},\ldots,X_{i_{\gamma}})|\right]<+\infty$
for any $(i_{1},\ldots i_{\gamma})\in I_{\gamma}$. Then, there exists a value
$C_{\gamma}$ depending only on $\gamma$ such that:

$\displaystyle\begin{split}\mathbb{E}\left[\displaystyle\Phi\left(\left|\sum_{(i_{1},\ldots
i_{\gamma})\in I^{\prime}_{\gamma}}h_{(i_{1},\ldots
i_{\gamma})}\left(X_{i_{1}},\ldots
X_{i_{\gamma}}\right)\right|\right)\right]\leq\\\ \leq
C_{\gamma}\mathbb{E}\left[\displaystyle\Phi\left(\left|\sum_{(i_{1},\ldots
i_{\gamma})\in I^{\prime}_{\gamma}}h_{(i_{1},\ldots
i_{\gamma})}\left(X^{(1)}_{i_{1}},\ldots
X^{(\gamma)}_{i_{\gamma}}\right)\right|\right)\right]\end{split}$

Let $X_{1},\ldots X_{n}$ be $n$ independent Rademacher random variables. Then,
a _Rademacher chaos_ $S$ is defined as:

$\displaystyle S=\sum_{(i_{1},\ldots i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots i_{\gamma})}X_{i_{1}}\ldots
X_{i_{\gamma}}.$

In the following parts of the paper, we will build on Theorem 4 for decoupling
Rademacher chaos. We observe that the book (Vershynin18, , Section 6.1)
provides some bounds on Rademacher chaos but only for the special case of
$\gamma=2$.

##  3\. Complex dimensionality reduction

In this section we analyze the properties of the dimensionality reduction onto
the complex vector space described in the introduction. We recall that
$A\in\mathbb{C}^{k\times d}$ denotes a random matrix where each entry in an
independent and identically distributed random variable in $\\{1,-1,i,-i\\}$,
and we define $g(x)=Ax/\sqrt{k}$ and $h(x,w)=g(x)\odot\sqrt{k}g(w)$ for any
$x,w\in\mathbb{R}^{d}$. The linear reduction is given by function $g(x)$ and,
for a set $S$ of vectors, we define $S^{\prime}=\\{g(x),\forall x\in S\\}$. We
claim that $\rho(x,w)=\textnormal{Re}\left(\displaystyle h(x,w)\cdot
h(x,w)\right)$ is our estimate of $\left\lVert x\right\rVert_{w}^{2}$.
Although $\rho(x,w)$ is expressed as a function of $x$, it can be computed
from the reduced vector $g(x)$: we indeed get that
$\rho(x,w)=\textnormal{Re}\left(\displaystyle
k\sum_{i=1}^{k}\left(g(x)_{i}g(w)_{i}\right)^{2}\right)$.

We initially propose some decoupling results in Section 3.1 that extend
Theorem 4 from (PenaGine99, ), and which might be of independent interest.
Then, in Section 3.2, we prove that the expected value of $\rho(x,w)$ is
$\left\lVert x\right\rVert_{w}^{2}$, and that $\rho(x,w)$ is an
$\varepsilon$-approximation of $\left\lVert x\right\rVert_{w}^{2}$ with high
probability for a sufficiently large value of $k$.

###  3.1. Decoupling results

In this section, we will prove the following decoupling bound for Rademacher
chaos:

###### Theorem 1.

For natural numbers $n\geq\gamma$, let $\mathcal{X}=\\{{X}_{i}\\}_{i=1}^{n}$
be a sequence of $n$ independent Rademacher random variables. Let
$I^{\prime}_{\gamma,n}\subseteq\\{1,\ldots n\\}^{\gamma}$ be a set of
sequences of distinct values , and let $a_{(i_{1},\ldots i_{\gamma})}$ denote
an arbitrary real value for any $(i_{1},\ldots i_{\gamma})\in
I^{\prime}_{\gamma,n}$. Let $t>0$ be an arbitrary value, then there exists a
value $C_{\gamma}$ depending only on $\gamma$ such that

$\displaystyle\textnormal{Pr}\left[\displaystyle\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}\geq
t\right]\leq C_{\gamma}e^{-\frac{t^{2}}{4\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a^{2}_{(i_{1},\ldots,i_{\gamma})}}}$

To prove the theorem, we first introduce the following lemmas:

###### Lemma 0.

For natural numbers $n\geq\gamma$, let $\mathcal{X}=\\{{X}_{i}\\}_{i=1}^{n}$
be a sequence of $n$ independent Rademacher random variables, and let
$\mathcal{X}^{(j)}=\\{X_{i}^{(j)}\\}_{i=1}^{n}$ with $j=1,\ldots,\gamma$, be
$\gamma$ independent copies of this sequence. Let
$I^{\prime}_{\gamma,n}\subseteq\\{1,\ldots n\\}^{\gamma}$ be a set of
sequences of distinct values, and let $a_{(i_{1},\ldots i_{\gamma})}$ denote
an arbitrary real value for any $(i_{1},\ldots i_{\gamma})\in
I^{\prime}_{\gamma,n}$. Let $t,u>0$ be two arbitrary values, then there exists
a value $C_{\gamma}$ depending only on $\gamma$ such that, for any $u>0$, we
have

$\displaystyle\textnormal{Pr}\left[\displaystyle\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}\geq
t\right]$ $\displaystyle\qquad\leq C_{\gamma}\mathbb{E}\left[\displaystyle
e^{u\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}}\right]e^{-u\cdot
t}$

###### Proof.

Let $\Delta=\max_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}|a_{(i_{1},\ldots,i_{\gamma})}|$. Then we have that
$\Delta+a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}$ is always
non negative since $X_{i_{j}}$ can assume only values in $\\{-1,+1\\}$. Let
$u>0$ be an arbitrary value. Since the summation has $|I^{\prime}_{\gamma,n}|$
terms and by applying Markov’s inequality, it then follows that:

$\displaystyle\textnormal{Pr}\left[\displaystyle\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}\geq
t\right]$
$\displaystyle=\textnormal{Pr}\left[\displaystyle\Delta|I^{\prime}_{\gamma,n}|+\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}\geq\Delta|I^{\prime}_{\gamma,n}|+{t}\right]$
$\displaystyle=\textnormal{Pr}\left[\displaystyle
e^{u\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}\left(\Delta+a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}\right)}\geq
e^{u(t+\Delta|I^{\prime}_{\gamma,n}|)}\right]$
$\displaystyle\leq\mathbb{E}\left[\displaystyle
e^{u\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}\left(\Delta+a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}\right)}\right]{e^{-u(t+\Delta|I^{\prime}_{\gamma,n}|)})}$
$\displaystyle\leq\mathbb{E}\left[\displaystyle
e^{\left|u\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}\Delta+a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}\right|}\right]{e^{-u(t+\Delta|I^{\prime}_{\gamma,n}|)}}$

where the last step follows since $u>0$ and
$\Delta+a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}$ is always
non negative. We now apply Theorem 4 with $\Phi(x)=e^{x}$ and
$h_{(i_{1},\ldots i_{\gamma})}\left(X_{i_{1}},\ldots
X_{i_{\gamma}}\right)=u\left(\Delta+a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}\right)$,
which gives:

$\displaystyle\textnormal{Pr}\left[\displaystyle\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}\geq
t\right]$ $\displaystyle\leq C_{\gamma}\mathbb{E}\left[\displaystyle
e^{\left|u\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}\Delta+a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}^{(j)}\right|}\right]{e^{-u(t+\Delta|I^{\prime}_{\gamma,n}|)}}$
$\displaystyle\leq C_{\gamma}\mathbb{E}\left[\displaystyle
e^{u\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}\Delta+a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}^{(j)}}\right]{e^{-u(t+\Delta|I^{\prime}_{\gamma,n}|)}}$
$\displaystyle\leq C_{\gamma}\mathbb{E}\left[\displaystyle
e^{u\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}^{(j)}}\right]{e^{-ut}}$

∎

###### Lemma 0.

For natural numbers $n\geq\gamma$, let
$\mathcal{X}^{(j)}=\\{X_{i}^{(j)}\\}_{i=1}^{n}$ be $\gamma$ independent
sequences of $n$ independent Rademacher random variables. Let
$I^{\prime}_{\gamma,n}\subseteq\\{1,\ldots n\\}^{\gamma}$ be a set of
sequences of distinct values, and let $a_{(i_{1},\ldots i_{\gamma})}$ denote
an arbitrary real value for any $(i_{1},\ldots i_{\gamma})\in
I^{\prime}_{\gamma,n}$. Then, for any $u>0$, we have

$\displaystyle\mathbb{E}\left[\displaystyle
e^{u\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}^{(j)}}\right]\leq
e^{u^{2}\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}^{2}}$

###### Proof.

By the series expansion of the exponential, we get:

(1) $\begin{split}&\mathbb{E}\left[\displaystyle
e^{u\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}^{(j)}}\right]\\\
&=\sum_{\ell=0}^{+\infty}{u^{\ell}\mathbb{E}\left[\displaystyle\left(\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}^{(j)}\right)^{\ell}\right]}{(\ell!)^{-1}}\end{split}$

Let $H=\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}^{(j)}$.
By computing the polynomial expansion of $H^{\ell}$, we obtain a sum of
products: each product has degree $\gamma\ell$, and hence it contains $\ell$
random variables from $\mathcal{X}^{(j)}$, possibly with repetitions, for each
value of $j$. More formally, denote with $\tau_{i,j}$ the $j$-th position of a
sequence $\tau_{i}$ in $I^{\prime}_{\gamma,n}$; we have:

$\begin{split}\mathbb{E}\left[\displaystyle
H^{\ell}\right]&=\sum_{\tau_{1},\ldots\tau_{\ell}\in(I^{\prime}_{\gamma,n})^{\ell}}\left(\left(\prod_{w=1}^{\ell}a_{\tau_{w}}\right)\mathbb{E}\left[\displaystyle\prod_{j=1}^{\gamma}\prod_{w=1}^{\ell}X^{(j)}_{\tau_{w,j}}\right]\right)\\\
&=\sum_{\tau_{1},\ldots\tau_{\ell}\in(I^{\prime}_{\gamma,n})^{\ell}}\left(\left(\prod_{w=1}^{\ell}a_{\tau_{w}}\right)\prod_{j=1}^{\gamma}\mathbb{E}\left[\displaystyle\prod_{w=1}^{\ell}X^{(j)}_{\tau_{w,j}}\right]\right)\end{split}$

where the last step follows by the independence among the $\mathcal{X}^{(j)}$
sequences.

Consider the case when $\ell$ is odd, that is $\ell=2\ell^{\prime}+1$. We
claim that $\mathbb{E}\left[\displaystyle H^{\ell}\right]=0$: each product in
the expansion of $H^{\ell}$ contains $\ell$ terms from the sequence
$\mathcal{X}^{(1)}$, and hence there must exist a random variable
$X_{i}^{(1)}$, for some $i$, appearing an odd number $\ell^{\prime\prime}$ of
times in $\prod_{w=1}^{\ell}X^{(1)}_{\tau_{w,j}}$ (otherwise the number of
terms from the first sequence in the product would be even); since
$\mathbb{E}\left[\displaystyle(X_{i_{j}}^{(1)})^{\ell^{\prime\prime}}\right]=0$
for any odd value $\ell^{\prime\prime}$ and by the independence among all
random variables in $\mathcal{X}^{(1)}$, we get the claim.

Consider now an even exponent $\ell=2\ell^{\prime}$. Similarly to the previous
case, the expected value of a product in the expansion of $H^{\ell}$ is 0 if
the product contains at least a random variable appearing an odd number of
times. It then follows that $\mathbb{E}\left[\displaystyle H^{\ell}\right]$ is
given by the sum of the expected values of the remaining products, where all
terms $X_{i_{j}}$ have even exponent. $\mathbb{E}\left[\displaystyle H\right]$
can then be rewritten as

$\begin{split}\mathbb{E}\left[\displaystyle
H^{\ell}\right]&=\sum_{\tau^{\prime}_{1},\ldots\tau^{\prime}_{\ell^{\prime}}\in(I^{\prime}_{\gamma,n})^{\ell}}\left(\left(\prod_{w=1}^{\ell^{\prime}}a_{\tau^{\prime}_{w}}^{2}\right)\prod_{j=1}^{\gamma}\mathbb{E}\left[\displaystyle\prod_{w=1}^{\ell^{\prime}}(X^{(j)}_{\tau_{w,j}})^{2}\right]\right)\\\
&=\sum_{\tau^{\prime}_{1},\ldots\tau^{\prime}_{\ell^{\prime}}\in(I^{\prime}_{\gamma,n})^{\ell}}\prod_{w=1}^{\ell^{\prime}}a_{\tau^{\prime}_{w}}^{2}=\left(\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}^{2}\right)^{\ell^{\prime}}\end{split}$

where the second equality follows since $\mathbb{E}\left[\displaystyle
X^{2}\right]=1$ for any Rademacher random variable. By replacing the above
bounds for the odd and even cases in Equation 1, we get:

$\displaystyle\mathbb{E}\left[\displaystyle
e^{u\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}^{(j)}}\right]$
$\displaystyle=\sum_{\ell^{\prime}=0}^{+\infty}{u^{2\ell^{\prime}}\left(\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}^{2}\right)^{\ell^{\prime}}}{((2\ell^{\prime})!)^{-1}}$
$\displaystyle\leq\sum_{\ell^{\prime}=0}^{+\infty}{\left(u^{2}\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}^{2}\right)^{\ell^{\prime}}}{(\ell^{\prime}!)^{-1}}$
$\displaystyle\leq e^{u^{2}\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}^{2}}$

∎

We are now ready to prove Theorem 1.

###### Proof of Theorem 1.

By Lemma 2, we have

$\displaystyle\textnormal{Pr}\left[\displaystyle\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}\geq
t\right]$ $\displaystyle\qquad\leq C_{\gamma}\mathbb{E}\left[\displaystyle
e^{u\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}\prod_{j=1}^{\gamma}a_{i_{j},j}X_{i_{j}}^{(j)}}\right]e^{-u\cdot
t}$

where $\\{X_{i}^{(j)}\\}_{i=1}^{n}$ denote $\gamma$ independent copies of the
$n$ Rademacher random variables. By Lemma 3, we then get

$\displaystyle\textnormal{Pr}\left[\displaystyle\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}\geq
t\right]\leq C_{\gamma}\frac{e^{u^{2}\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}^{2}}}{e^{-u\cdot t}}$

By setting $u=t/\left(2\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}^{2}\right)$, we get the
stated result. ∎

We now state a version of the above theorem that will be used in the
subsequent proofs. The corollary provides some guarantees on the average of
$\kappa$ independent Rademacher chaoses.

###### Corollary 0.

Let $\\{X_{l,i}\\}_{l=1,\dots,\kappa\ i=1,\dots,n}$ be a sequence of
independent Rademacher random variables, for natural numbers $n\geq\gamma$ and
$\kappa\geq 1$. Let $I^{\prime}_{\gamma,n}$ be the set of ordered sequences of
$\gamma$ distinct values from $\\{1,\dots,n\\}$. Let $a_{(i_{1},\ldots
i_{n})}$ be an arbitrary real value for any $(i_{1},\ldots i_{n})\in
I^{\prime}_{\gamma,n}$. Then there exists a value $C_{\gamma}$ depending only
on $\gamma$ such that

$\begin{split}&\textnormal{Pr}\left[\displaystyle\left|\sum_{l=1}^{\kappa}\sum_{(i_{1},\dots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{l,i_{j}}\right|>t\right]\\\
&\leq C_{\gamma}e^{-t^{2}/(4\kappa\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}^{2})}\end{split}$

###### Proof.

We first observe, that by setting
$a^{\prime}_{(i_{1},\ldots,i_{\gamma})}=-a_{(i_{1},\ldots,i_{\gamma})}$,
Theorem 1 gives

$\displaystyle\textnormal{Pr}\left[\displaystyle\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,\kappa
n}}a^{\prime}_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}\geq
t\right]\leq C_{\gamma}e^{-\frac{t^{2}}{4\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a^{2}_{(i_{1},\ldots,i_{\gamma})}}}$

which then implies that

(2)
$\displaystyle\begin{split}&\textnormal{Pr}\left[\displaystyle\left|\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,\kappa
n}}a^{\prime}_{(i_{1},\ldots,i_{\gamma}),\ell}\prod_{j=1}^{\gamma}X_{i_{j}}\right|\geq
t\right]\\\ &\leq
2C_{\gamma}e^{-\frac{t^{2}}{4\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,\kappa n}}a^{2}_{(i_{1},\ldots,i_{\gamma})}}}.\end{split}$

Since the $\\{X_{l,i}\\}_{l=1,\dots,\kappa\ i=1,\dots,n}$ represents $n\kappa$
independent and distinct Rademacher random variables, we can replace
$I^{\prime}_{\gamma,n}$ with a suitable set $I^{\prime}_{\gamma,\kappa n}$ and
relabel variables $a_{(i_{1},\ldots,i_{\gamma})}$ in order to transform the
the double summation $\sum_{l=1}^{\kappa}\sum_{(i_{1},\dots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{l,i_{j}}$
into $\sum_{(i_{1},\dots,i_{\gamma})\in I^{\prime}_{\gamma,\kappa
n}}a^{\prime}_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{l,i_{j}}$. We
can then apply the above Equation 2 and get

$\displaystyle\begin{split}&\textnormal{Pr}\left[\displaystyle\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,\kappa
n}}a^{\prime}_{(i_{1},\ldots,i_{\gamma})}\prod_{j=1}^{\gamma}X_{i_{j}}\geq
t\right]\\\ &\leq
2C_{\gamma}e^{-\frac{t^{2}}{4\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,\kappa n}}a^{\prime
2}_{(i_{1},\ldots,i_{\gamma})}}}\end{split}$

Since $\sum_{(i_{1},\ldots,i_{\gamma})\in I^{\prime}_{\gamma,\kappa
n}}a^{\prime
2}_{(i_{1},\ldots,i_{\gamma})}=\kappa\sum_{(i_{1},\ldots,i_{\gamma})\in
I^{\prime}_{\gamma,n}}a^{2}_{(i_{1},\ldots,i_{\gamma})}$, we get the
statement. ∎

###  3.2. Dimensionality reduction with complex numbers

We are now ready to analyze $\rho(x,w)$ in expectation and in high
probability. By using a simple bound based on Hoeffding’s inequality, we get
that $\rho(x,w)$ is an $\varepsilon$-approximation in high probability if
$k>\frac{1}{\varepsilon^{2}}\left(\frac{\left\lVert
x\right\rVert_{1}\left\lVert w\right\rVert_{1}}{\left\lVert
x\right\rVert_{w}}\right)^{4}\ln(2/\delta)$. Note that $1$-norms are very
sensitive on the number $\ell$ of nonzero entries in the vector, as in the
worst case $\left\lVert x\right\rVert_{1}=\left\lVert
x\right\rVert_{2}\sqrt{\ell}$. We then highlight a dependency on 2-norms using
a more articulated proof based on the previous results on decoupling
Rademacher chaos, and we get a lower bound on $k$ that depends on $2$-norms:
specifically, $k=\Omega\left(\frac{1}{\varepsilon^{2}}\left(\frac{\left\lVert
x\right\rVert_{1}\left\lVert w\right\rVert_{1}}{\left\lVert
x\right\rVert_{w}}\right)^{4}\ln(1/\delta)\right)$.

####  3.2.1. Results in expectation

###### Theorem 5.

For any $x,w\in\mathbb{R}^{d}$, we have that
$\mathbb{E}[\rho(x,w)]=\left\lVert x\right\rVert^{2}_{w}$.

###### Proof.

We have that $\rho(x,w)=\sum_{i=1}^{k}\textnormal{Re}\left(\displaystyle
h_{i}(x,w)^{2}\right)$, and thus
$\mathbb{E}\left[\displaystyle\rho(x,w)\right]=\sum_{i=1}^{k}\mathbb{E}\left[\displaystyle\textnormal{Re}\left(\displaystyle
h_{i}(x,w)^{2}\right)\right]$. By the definition of the vector $h(\cdot)$, we
get:

$\begin{split}h_{i}(x,w)^{2}&=k^{-1}\left(\sum_{j=1}^{d}A_{i,j}x_{j}\right)^{2}\left(\sum_{j=1}^{d}A_{i,j}w_{j}\right)^{2}\\\
&=k^{-1}\sum_{(j_{1},j_{2},j_{3},j_{4})\in
I_{4,d}}A_{i,j_{1}}A_{i,j_{2}}A_{i,j_{3}}A_{i,j_{4}}x_{j_{1}}x_{j_{2}}w_{j_{3}}w_{j_{4}}\end{split}$

Consider now the expectation of the term $\mathbb{E}\left[\displaystyle
A_{i,j_{1}}A_{i,j_{2}}A_{i,j_{3}}A_{i,j_{4}}\right]$ for a given value $i$.
Since $\mathbb{E}\left[\displaystyle
A_{i,j}\right]=\mathbb{E}\left[\displaystyle
A_{i,j}^{2}\right]=\mathbb{E}\left[\displaystyle A_{i,j}^{3}\right]=0$ for any
$i,j$ and the terms in $A$ are independent, we have that
$\mathbb{E}\left[\displaystyle\textnormal{Re}\left(\displaystyle
A_{i,j_{1}}A_{i,j_{2}}A_{i,j_{3}}A_{i,j_{4}}\right)\right]=1$ if
$j_{1}=j_{2}=j_{3}=j_{4}$, and 0 otherwise. Then, we get:

$\begin{split}\mathbb{E}\left[\displaystyle{h_{i}(x,w)^{2}}\right]&=k^{-1}\sum_{(j_{1},j_{2},j_{3},j_{4})\in
I_{4,d}}\mathbb{E}\left[\displaystyle{A_{i,j_{1}}A_{i,j_{2}}A_{i,j_{3}}A_{i,j_{4}}}\right]x_{j_{1}}x_{j_{2}}w_{j_{3}}w_{j_{4}}\\\
&=k^{-1}\sum_{j=1}^{d}x^{2}_{j}w^{2}_{j}=\left\lVert
x\right\rVert^{2}_{w}/k\end{split}$

Similarly, we can prove that
$\mathbb{E}\left[\displaystyle{(h_{i}(x,w)^{2})^{*}}\right]=\left\lVert
x\right\rVert^{2}_{w}/k$, where $*$ denotes the complex conjugate. The theorem
follows since $\rho(x,w)=\sum_{i=1}^{k}\textnormal{Re}\left(\displaystyle
h_{i}(x,w)^{2}\right)$ and

$\begin{split}\mathbb{E}\left[\displaystyle\textnormal{Re}\left(\displaystyle
h_{i}(x,w)^{2}\right)\right]&=\mathbb{E}\left[\displaystyle(h_{i}(x,w)^{2}+(h_{i}(x,w)^{2})^{*})/2\right]\\\
&=(\mathbb{E}\left[\displaystyle
h_{i}(x,w)^{2}\right]+\mathbb{E}\left[\displaystyle(h_{i}(x,w)^{2})^{*}\right])/2.\end{split}$

∎

####  3.2.2. Results in high probability with Hoeffding’s inequality

We exploit the fact that each term $h_{i}^{2}$ is bounded to use Hoeffding’s
inequality to obtain a first concentration result.

###### Theorem 6.

For any given $x,w\in\mathbb{R}^{d}$ and for any $\varepsilon,\delta>0$,
setting $k>\frac{1}{\varepsilon^{2}}\left(\frac{\left\lVert
x\right\rVert_{1}\left\lVert w\right\rVert_{1}}{\left\lVert
x\right\rVert_{w}}\right)^{4}\ln(2/\delta)$ yields

$(1+\varepsilon)\left\lVert
x\right\rVert_{w}^{2}<\rho(x,w)<(1+\varepsilon)\left\lVert
x\right\rVert_{w}^{2}$

with probability at least $1-\delta$.

###### Proof.

We have that

$\begin{split}|\textnormal{Re}\left(\displaystyle h_{i}^{2}(x,w)\right)|&\leq
k^{-1}\sum_{(j_{1},j_{2},j_{3},j_{4})\in
I_{4,d}}|x_{j_{1}}||x_{j_{2}}||w_{j_{3}}||w_{j_{4}}|\\\ &\leq\left\lVert
x\right\rVert_{1}^{2}\left\lVert w\right\rVert_{1}^{2}/k\end{split}$

with probability 1. Then, by Hoeffding’s inequality we have

$\mathbb{P}\left[\left|\sum_{j=1}^{d}\textnormal{Re}\left(\displaystyle
h_{i}^{2}(x,w)\right)\ -\left\lVert
x\right\rVert_{w}\right|>\varepsilon\left\lVert
x\right\rVert_{w}^{2}\right]\leq 2e^{-k\frac{\varepsilon^{2}\left\lVert
x\right\rVert_{w}^{4}}{4\left\lVert x\right\rVert_{1}^{4}\left\lVert
w\right\rVert_{1}^{4}}}$

Then if we take $k>\frac{1}{\varepsilon^{2}}\frac{4\left\lVert
x\right\rVert_{1}^{4}\left\lVert w\right\rVert_{1}^{4}}{\left\lVert
x\right\rVert_{w}^{4}}\ln(2/\delta)$, we have the claim. ∎

####  3.2.3. Results in high probability with Rademacher chaos concentration
bounds

Since the results of Corollary 4 apply only to pairwise distinct indices, we
split $\rho(x,w)=\sum_{i=1}^{k}\textnormal{Re}\left(\displaystyle
h_{i}(x,w)^{2}\right)$ into 5 sums, each over a set of pairwise distinct
indices, and bound each term individually. Here we assume that
$I_{\gamma,d}=\\{1,\ldots,d\\}^{\gamma}$ and
$I^{\prime}_{\gamma,d}=\\{(j_{1},\ldots,j_{d}):j_{p}\neq j_{q}\quad\forall
p,q\in\\{1,\ldots d\\},p\neq q\\}$.

$\displaystyle\rho(x,w)=\sum_{i=1}^{k}\sum_{(j_{1},\dots,j_{4})\in
I_{4,d}}\textnormal{Re}\left(\displaystyle
A_{i,j_{1}}A_{i,j_{2}}A_{i,j_{3}}A_{i,j_{4}}\right)w_{j_{1}}w_{j_{2}}x_{j_{3}}x_{j_{4}}=$
$\displaystyle=\quad\sum_{i=1}^{k}\sum_{(j_{1},\dots,j_{4})\in
I^{\prime}_{4,d}}\textnormal{Re}\left(\displaystyle
A_{i,j_{1}}A_{i,j_{2}}A_{i,j_{3}}A_{i,j_{4}}\right)w_{j_{1}}w_{j_{2}}x_{j_{3}}x_{j_{4}}$
$\displaystyle+\sum_{i=1}^{k}\sum_{(j_{1},j_{2},j_{3})\in
I^{\prime}_{3,d}}\textnormal{Re}\left(\displaystyle
A_{i,j_{1}}^{2}A_{i,j_{2}}A_{i,j_{3}}\right)\Bigl{(}w_{j_{1}}^{2}x_{j_{2}}x_{j_{3}}+4w_{j_{1}}x_{j_{1}}w_{j_{2}}x_{j_{3}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad+x_{j_{1}}^{2}w_{j_{2}}w_{j_{3}}\Bigr{)}$
$\displaystyle+2\sum_{i=1}^{k}\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,d}}\textnormal{Re}\left(\displaystyle
A_{i,j_{1}}^{3}A_{i,j_{2}}\right)\left(w_{j_{1}}^{2}x_{j_{1}}x_{j_{2}}+x_{j_{1}}^{2}w_{j_{1}}w_{j_{2}}\right)$
$\displaystyle+\sum_{i=1}^{k}\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,d}}\textnormal{Re}\left(\displaystyle
A_{i,j_{1}}^{2}A_{i,j_{2}}^{2}\right)\left(w_{j_{1}}^{2}x_{j_{2}}^{2}+2x_{j_{1}}w_{j_{1}}x_{j_{2}}w_{j_{2}}\right)$
$\displaystyle+\sum_{i=1}^{k}\sum_{j=1}^{d}w_{j}^{2}x_{j}^{2}$
$\displaystyle=H_{1}+H_{2}+H_{3}+H_{4}+k\left\lVert x\right\rVert_{w}^{2}$

Note that each $A_{i,j}$ can be written as $s(1-r+i(1+r))/2$, with $s$ and $r$
independent Rademacher random variables. Then we have that

$\begin{split}&\textnormal{Re}\left(\displaystyle
A_{i,j_{1}}A_{i,j_{2}}A_{i,j_{3}}A_{i,j_{4}}\right)\\\
&=\left(-1-r_{i,j_{1}}r_{i,j_{2}}r_{i,j_{3}}r_{i,j_{4}}+\sum_{p=1}^{4}\sum_{q=p+1}^{4}r_{i,j_{p}}r_{i,j_{q}}\right)s_{i,j_{1}}s_{i,j_{2}}s_{i,j_{3}}s_{i,j_{4}}/4\end{split}$

We now bound the tail probabilities of the individual terms $H_{\ell}$ by
expanding them into sums of Rademacher chaoses and using Corollary 4.

###### Lemma 0.

We have that $\mathbb{P}[|H_{2}|>t]\leq 2C_{4}e^{-t^{2}/(36k\left\lVert
w\right\rVert_{2}^{4}\left\lVert x\right\rVert_{2}^{4})}$

###### Proof.

By setting
$\tau_{j_{1},j_{2},j_{3}}=w_{j_{1}}^{2}x_{j_{2}}x_{j_{3}}+4w_{j_{1}}x_{j_{1}}w_{j_{2}}x_{j_{3}}+x_{j_{1}}^{2}w_{j_{2}}w_{j_{3}}$,
we rewrite $H_{2}$ as

$\displaystyle H_{2}$
$\displaystyle=\sum_{i=1}^{k}\sum_{(j_{1},j_{2},j_{3})\in
I^{\prime}_{3,d}}\textnormal{Re}\left(\displaystyle
A_{i,j_{1}}^{2}A_{i,j_{2}}A_{i,j_{3}}\right)\tau_{j_{1},j_{2},j_{3}}$
$\displaystyle=\sum_{i=1}^{k}\sum_{(j_{1},j_{2},j_{3})\in
I^{\prime}_{3,d}}(s_{i,j_{2}}s_{i,j_{3}}r_{i,j_{1}}r_{i,j_{2}}+s_{i,j_{2}}s_{i,j_{3}}r_{i,j_{1}}r_{i,j_{3}})\tau_{j_{1},j_{2},j_{3}}/4$
$\displaystyle=\sum_{i=1}^{k}\sum_{(j_{1},j_{2},j_{3})\in
I^{\prime}_{3,d}}s_{i,j_{2}}s_{i,j_{3}}r_{i,j_{1}}r_{i,j_{2}}\tau_{j_{1},j_{2},j_{3}}/4$
$\displaystyle\quad+\sum_{i=1}^{k}\sum_{(j_{1},j_{2},j_{3})\in
I^{\prime}_{3,d}}s_{i,j_{2}}s_{i,j_{3}}r_{i,j_{1}}r_{i,j_{3}}\tau_{j_{1},j_{2},j_{3}}/4$
$\displaystyle=H_{2,1}/4+H_{2,2}/4$

Since $H_{2,1}$ and $H_{2,2}$ have the same distribution, we focus on the
first one.

Let $\hat{\tau}:I^{\prime}_{4,2d}\rightarrow\mathbb{R}$ be

$\hat{\tau}_{j_{1},j_{2},j^{\prime}_{2},j_{3}}=\begin{cases}\tau_{j_{1},j_{2},j_{3}}&\text{if
}j^{\prime}_{2}=j_{2}+d,j_{1}\leq d,j_{3}>d\\\ 0&\text{otherwise.}\\\
\end{cases}$

Let also $X_{i,:}=(r_{i,1},\dots,r_{i,d},s_{i,1},\dots,s_{i,d})$. Note that
the components of $X$ are independent. Then, we can rewrite $H_{2,1}$ as

$H_{2,1}=\sum_{i=1}^{k}\sum_{(j_{1},j_{2},j^{\prime}_{2},j_{3})\in
I^{\prime}_{4,2d}}X_{i,j^{\prime}_{2}}X_{i,j_{3}}X_{i,j_{1}}X_{i,j_{2}}\hat{\tau}_{j_{1},j_{2},j^{\prime}_{2},j_{3}}.$

By applying Corollary 4, we get:

$\begin{split}\mathbb{P}[|H_{2,1}|>t]&=\mathbb{P}\left[\sum_{i=1}^{k}\sum_{(j_{1},j_{2},j^{\prime}_{2},j_{3})\in
I^{\prime}_{4,2d}}X_{i,j^{\prime}_{2}}X_{i,j_{3}}X_{i,j_{1}}X_{i,j_{2}}\hat{\tau}_{j_{1},j_{2},j^{\prime}_{2},j_{3}}\
>t\right]\\\ &\leq C_{4}e^{-t^{2}/(4k\Phi)}\end{split}$

where $\Phi=\sum_{(j_{1},j_{2},j^{\prime}_{2},j_{3})\in
I^{\prime}_{4,2d}}\hat{\tau}^{2}_{j_{1},j_{2},j^{\prime}_{2},j_{3}}=\sum_{(j_{1},j_{2},j_{3})\in
I^{\prime}_{3,d}}\tau_{j_{1},j_{2},j_{3}}^{2}$. With some standard arguments,
we get:

$\begin{split}\Phi&=\sum_{(j_{1},j_{2},j_{3})\in
I^{\prime}_{3,d}}\left(w_{j_{1}}^{2}x_{j_{2}}x_{j_{3}}+4w_{j_{1}}x_{j_{1}}w_{j_{2}}x_{j_{3}}+x_{j_{1}}^{2}w_{j_{2}}w_{j_{3}}\right)^{2}\\\
&=\sum_{(j_{1},j_{2},j_{3})\in
I^{\prime}_{3,d}}w_{j_{1}}^{4}x_{j_{2}}^{2}x_{j_{3}}^{2}+16w_{j_{1}}^{2}x_{j_{1}}^{2}w_{j_{2}}^{2}x_{j_{3}}^{2}+x_{j_{1}}^{4}w_{j_{2}}^{2}w_{j_{3}}^{2}\\\
&\quad+8w_{j_{1}}^{3}x_{j_{1}}w_{j_{2}}x_{j_{2}}x_{j_{3}}^{2}+8w_{j_{1}}x_{j_{1}}^{3}w_{j_{2}}^{2}w_{j_{3}}x_{j_{3}}+2w_{j_{1}}^{2}x_{j_{1}}^{2}w_{j_{2}}x_{j_{2}}x_{j_{3}}w_{j_{3}}\\\
&\leq 36\left\lVert w\right\rVert_{2}^{4}\left\lVert
x\right\rVert_{2}^{4}.\end{split}$

The final inequality follows since each term of the summation can upper
bounded by the product of three sums to which we can apply Lemma 3. For
instance,

$\begin{split}\sum_{(j_{1},j_{2},j_{3})\in
I^{\prime}_{3,d}}&8w_{j_{1}}^{3}x_{j_{1}}w_{j_{2}}x_{j_{2}}x_{j_{3}}^{2}\leq
8\sum_{(j_{1},j_{2},j_{3})\in
I_{3,d}}|w_{j_{1}}^{3}x_{j_{1}}w_{j_{2}}x_{j_{2}}x_{j_{3}}^{2}|\\\ &\leq
8\left(\sum_{j_{1}\in
I_{1,d}}|w_{j_{1}}|^{3}|x_{j_{1}}|\right)\left(\sum_{j_{2}\in
I_{1,d}}|w_{j_{2}}||x_{j_{2}}|\right)\left(\sum_{j_{3}\in
I_{1,d}}|x_{j_{3}}|^{2}\right)\\\ &\leq\left\lVert
w\right\rVert_{2}^{3}\left\lVert x\right\rVert_{2}\left\lVert
w\right\rVert_{2}\left\lVert x\right\rVert_{2}\left\lVert
x\right\rVert_{2}^{2}.\end{split}$

We hence get that $\mathbb{P}[|H_{2,1}|>t]\leq C_{4}e^{-t^{2}/(144k\left\lVert
w\right\rVert_{2}^{4}\left\lVert x\right\rVert_{2}^{4})}$. Then, by using an
union bound, we finally get

$\begin{split}\mathbb{P}[|H_{2}|>t]&=\mathbb{P}[|H_{2,1}+H_{2,2}|>4t]\\\
&\leq\mathbb{P}[|H_{2,1}|>2t]+\mathbb{P}[|H_{2,2}|>2t]\\\ &\leq
2C_{4}e^{-t^{2}/(36k\left\lVert w\right\rVert_{2}^{4}\left\lVert
x\right\rVert_{2}^{4})}.\end{split}$

∎

The following two lemmas state the tail bounds for $H_{3}$ and $H_{4}$.

###### Lemma 0.

We have that $\mathbb{P}[|H_{3}|>t]\leq C_{2}e^{-t^{2}/(32k\left\lVert
w\right\rVert_{2}^{4}\left\lVert x\right\rVert_{2}^{4})}$

###### Proof.

By setting
$\tau_{j_{1},j_{2}}=w_{j_{1}}^{2}x_{j_{1}}x_{j_{2}}+x_{j_{1}}^{2}w_{j_{1}}w_{j_{2}}$,
we rewrite $H_{3}$ as

$\begin{split}H_{3}&=2\sum_{i=1}^{k}\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,d}}\textnormal{Re}\left(\displaystyle
A_{i,j_{1}}^{3}A_{i,j_{2}}\right)\tau_{j_{1},j_{2}}\\\
&=2\sum_{i=1}^{k}\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,d}}s_{j_{1}}s_{j_{2}}(1+r_{j_{1}}r_{j_{2}})\tau_{j_{1},j_{2}}/2\\\
&=\sum_{i=1}^{k}\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,d}}s_{j_{1}}s_{j_{2}}\tau_{j_{1},j_{2}}+\sum_{i=1}^{k}\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,d}}s^{\prime}_{j_{1}}s^{\prime}_{j_{2}}\tau_{j_{1},j_{2}}\\\
\end{split}$

where $s^{\prime}_{j}=s_{j}r_{j}$ and has the same distribution of a
Rademacher random variable.

Let $\hat{\tau}:I^{\prime}_{2,2d}\rightarrow\mathbb{R}$ be

$\hat{\tau}_{j_{1},j_{2}}=\begin{cases}\tau_{j_{1},j_{2}}&\text{if }j_{1}\leq
d,j_{2}\leq d\\\ \tau_{j_{1}-d,j_{2}-d}&\text{if }j_{1}>d,j_{2}>d\\\
0&\text{otherwise.}\end{cases}$

Let also
$X_{i,:}=(s_{i,1},\dots,s_{i,d},s^{\prime}_{i,1},\dots,s^{\prime}_{i,d},)$.
Note that the components of $X$ are independent.

Then, we can rewrite $H_{3}$ as

$H_{3}=\sum_{i=1}^{k}\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,2d}}X_{i,j_{1}}X_{i,j_{2}}\hat{\tau}_{j_{1},j_{2}}.$

By applying Corollary 4, we get:

$\begin{split}\mathbb{P}[|H_{3}|>t]&=\mathbb{P}\left[\sum_{i=1}^{k}\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,2d}}X_{i,j_{1}}X_{i,j_{2}}\hat{\tau}_{j_{1},j_{2}}\ >t\right]\\\
&\leq C_{2}e^{-t^{2}/(4k\Phi)}\end{split}$

where $\Phi=\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,2d}}\hat{\tau}^{2}_{j_{1},j_{2}}=2\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,d}}\tau_{j_{1},j_{2},j_{3}}^{2}$.

Then, we get that:

$\begin{split}\Phi&=2\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,d}}\left(w_{j_{1}}^{2}x_{j_{1}}x_{j_{2}}+x_{j_{1}}^{2}w_{j_{1}}w_{j_{2}}\right)^{2}\\\
&=2\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,d}}\left(w_{j_{1}}^{4}x_{j_{1}}^{2}x_{j_{2}}^{2}+x_{j_{1}}^{4}w_{j_{1}}^{2}w_{j_{2}}^{2}+2w_{j_{1}}^{3}x_{j_{1}}^{3}w_{j_{2}}x_{j_{2}}\right)\\\
&\leq 8\left\lVert w\right\rVert_{2}^{4}\left\lVert
x\right\rVert_{2}^{4},\end{split}$

and the claim follows. ∎

###### Lemma 0.

We have that $\mathbb{P}[|H_{4}|>t]\leq C_{2}e^{-t^{2}/(16k\left\lVert
w\right\rVert_{2}^{4}\left\lVert x\right\rVert_{2}^{4})}$

###### Proof.

By setting
$\tau_{j_{1},j_{2}}=w_{j_{1}}^{2}x_{j_{2}}^{2}+2x_{j_{1}}w_{j_{1}}x_{j_{2}}w_{j_{2}}$,
we rewrite $H_{3}$ as

$\begin{split}H_{4}&=\sum_{i=1}^{k}\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,d}}\textnormal{Re}\left(\displaystyle
A_{i,j_{1}}^{2}A_{i,j_{2}}^{2}\right)\tau_{j_{1},j_{2}}\\\
&=\sum_{i=1}^{k}\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,d}}r_{j_{1}}r_{j_{2}}\tau_{j_{1},j_{2}}\end{split}$

Then we can apply Corollary 4 with $X_{i,:}=(r_{i,1},\dots,r_{i,d})$, which
yields

$\begin{split}\mathbb{P}[|H_{4}|>t]&=\mathbb{P}\left[\sum_{i=1}^{k}\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,d}}X_{j_{1}}X_{j_{2}}\tau_{j_{1},j_{2}}>t\right]\leq
C_{2}e^{-t^{2}/(4k\Phi)},\end{split}$

where $\Phi=\sum_{(j_{1},j_{2})\in I^{\prime}_{2,d}}\tau_{j_{1},j_{2}}^{2}$.
Then, by mimicing the approach used for $H_{2}$, we get:

$\begin{split}\Phi&=\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,d}}\left(w_{j_{1}}^{2}x_{j_{1}}x_{j_{2}}+x_{j_{1}}^{2}w_{j_{1}}w_{j_{2}}\right)^{2}\\\
&=\sum_{(j_{1},j_{2})\in
I^{\prime}_{2,d}}\left(w_{j_{1}}^{4}x_{j_{1}}^{2}x_{j_{2}}^{2}+x_{j_{1}}^{4}w_{j_{1}}^{2}w_{j_{2}}^{2}+2w_{j_{1}}^{3}x_{j_{1}}^{3}w_{j_{2}}x_{j_{2}}\right)\\\
&\leq 4\left\lVert w\right\rVert_{2}^{4}\left\lVert
x\right\rVert_{2}^{4},\end{split}$

and the lemma follows. ∎

Lastly, we bound $H_{1}$, which has the most complex expansion into Rademacher
chaoses.

###### Lemma 0.

We have that $\mathbb{P}[|H_{1}|>t]\leq 8C_{4}e^{-t^{2}/(16k\left\lVert
w\right\rVert_{2}^{4}\left\lVert x\right\rVert_{2}^{4})}$

###### Proof.

By setting
$\tau_{j_{1},j_{2},j_{3},j_{4}}=w_{j_{1}}w_{j_{2}}x_{j_{3}}x_{j_{4}}$, we
rewrite $H_{4}$ as

$\begin{split}4H_{1}&=\sum_{i=1}^{k}\sum_{(j_{1},\dots,j_{4})\in
I^{\prime}_{4,d}}\textnormal{Re}\left(\displaystyle
A_{i,j_{1}}A_{i,j_{2}}A_{i,j_{3}}A_{i,j_{4}}\right)\tau_{j_{1},j_{2},j_{3},j_{4}}\\\
&=\sum_{i=1}^{k}\sum_{(j_{1},\dots,j_{4})\in
I^{\prime}_{4,d}}\left(-1-r_{i,j_{1}}r_{i,j_{2}}r_{i,j_{3}}r_{i,j_{4}}+\sum_{p=1}^{4}\sum_{q=p+1}^{4}r_{i,j_{p}}r_{i,j_{q}}\right)\cdot\\\
&\qquad\qquad\qquad\quad\cdot
s_{j_{1}}s_{j_{2}}s_{j_{3}}s_{j_{4}}\tau_{j_{1},j_{2},j_{3},j_{4}}\\\
&=-H_{1,1}-H_{1,2}+H_{1,12}+H_{1,13}+H_{1,14}+H_{1,23}+H_{1,24}+H_{1,34}\end{split}$

By relabelling the $r$ and $s$ Rademacher variables, it is possible to rewrite
each term as a chaos of degree four. It follows that the eight terms have the
same distribution. We hence bound the tail probabilities of only $H_{1,1}$. We
can apply Corollary 4 with $X_{i,:}=(s_{i,1},\dots,s_{i,d})$, which yields

$\begin{split}\mathbb{P}[|H_{1,1}|>t]&=\mathbb{P}\left[\sum_{i=1}^{k}\sum_{(j_{1},\dots,j_{4})\in
I^{\prime}_{4,d}}X_{j_{1}}X_{j_{2}}X_{j_{3}}X_{j_{4}}\tau_{j_{1},j_{2},j_{3},j_{4}}>t\right]\\\
&\leq C_{4}e^{-t^{2}/(4k\Phi)},\end{split}$

where $\Phi=\sum_{(j_{1},\dots,j_{4})\in
I^{\prime}_{4,d}}\tau_{j_{1},j_{2},j_{3},j_{4}}^{2}\leq\left\lVert
w\right\rVert_{2}^{4}\left\lVert x\right\rVert_{2}^{4}$.

Then by union bound we have $\mathbb{P}[|H_{1}|>t]=\mathbb{P}[|4H_{1}|>4t]\leq
8\mathbb{P}[|H_{1,1}|>t/2]\leq 8C_{4}e^{-t^{2}/(16k\left\lVert
w\right\rVert_{2}^{4}\left\lVert x\right\rVert_{2}^{4})}$ ∎

We are then ready to prove the main lemma.

###### Lemma 0.

For any given $x,w\in\mathbb{R}^{d}$, there exists an universal constant $C$
such that

$\mathbb{P}\left[\left|\rho(x,w)\ -\left\lVert
x\right\rVert_{w}^{2}\right|>t\right]\leq 12Ce^{-k\cdot t^{2}/(576\left\lVert
w\right\rVert_{2}^{4}\left\lVert x\right\rVert_{2}^{4}))}.$

###### Proof.

We have $\sum_{i=1}^{k}kh_{i}^{2}-\ k\left\lVert
x\right\rVert_{w}^{2}=H_{1}+H_{2}+H_{3}+H_{4}.$ This in turn implies, by union
bound, that

$\begin{split}&\mathbb{P}\left[\left|\rho(x,w)-k\left\lVert
x\right\rVert_{w}^{2}\right|>t\right]=\mathbb{P}\left[\left|H_{1}+H_{2}+H_{3}+H_{4}\right|>t\right]\\\
&\leq\mathbb{P}[|H_{1}|>t/4]+\mathbb{P}[|H_{2}|>t/4]+\mathbb{P}[|H_{3}|>t/4]+\mathbb{P}[|H_{4}|>t/4]\\\
&\leq 8Ce^{-t^{2}/(256k\left\lVert w\right\rVert_{2}^{4}\left\lVert
x\right\rVert_{2}^{4})}+2Ce^{-t^{2}/(576k\left\lVert
w\right\rVert_{2}^{4}\left\lVert x\right\rVert_{2}^{4})}\\\
&\quad+Ce^{-t^{2}/(512k\left\lVert w\right\rVert_{2}^{4}\left\lVert
x\right\rVert_{2}^{4})}+Ce^{-t^{2}/(256k\left\lVert
w\right\rVert_{2}^{4}\left\lVert x\right\rVert_{2}^{4})}\\\ &\leq
12Ce^{-t^{2}/(576k\left\lVert w\right\rVert_{2}^{4}\left\lVert
x\right\rVert_{2}^{4}))},\end{split}$

where $C=\max\\{C_{4},C_{3},C_{2}\\}=C_{4}$. ∎

By setting $k\geq\left\lVert x\right\rVert^{4}_{2}\left\lVert
w\right\rVert^{4}_{2}\varepsilon^{-2}\left\lVert
x\right\rVert_{w}^{-4}\ln{(12C/\delta)}$, the above lemma gives an
$\varepsilon$-approximation on $\left\lVert x\right\rVert_{w}^{2}$. However,
matrix $A$ should have a size that does not depend on a specific input vector:
we then state the main theorem as a function of a parameter $\Delta$ which
represents the maximum tolerated distortion: if the actual distortion
$\Delta(x,w)$ is not larger than $\Delta$, we get a multiplicative error
$\varepsilon$; otherwise, we get an additive error
$\varepsilon\frac{\left\lVert x\right\rVert_{2}^{2}\left\lVert
w\right\rVert_{2}^{2}}{\Delta^{2}}$.

###### Theorem 12.

Let $k=\frac{c\Delta^{4}}{\varepsilon^{2}}\ln(1/\delta)$ for a suitable
constant $c$. Then, for any given $x,w\in\mathbb{R}^{d}$ we have

$\left\lVert x\right\rVert_{w}^{2}-\varepsilon\frac{\left\lVert
x\right\rVert_{2}^{2}\left\lVert
w\right\rVert_{2}^{2}}{\Delta^{2}}<\rho(x,w)<\left\lVert
x\right\rVert_{w}^{2}+\varepsilon\frac{\left\lVert
x\right\rVert_{2}^{2}\left\lVert w\right\rVert_{2}^{2}}{\Delta^{2}}$

with probability at least $1-\delta$. In particular if $\Delta\geq\left\lVert
x\right\rVert_{2}\left\lVert w\right\rVert_{2}/\left\lVert x\right\rVert_{w}$,
we get:

$(1-\varepsilon)\left\lVert
x\right\rVert_{w}^{2}<\rho(x,w)<(1+\varepsilon)\left\lVert
x\right\rVert_{w}^{2}$

###### Proof.

Set $\varepsilon^{\prime}=\varepsilon\left\lVert
x\right\rVert^{2}_{2}\left\lVert w\right\rVert^{2}_{2}/(\Delta^{2}\left\lVert
x\right\rVert_{w}^{2})$ and by applying Lemma 11 with $\varepsilon^{\prime}$,
we have that

$\mathbb{P}\left[\left|\rho(x,w)\ -\left\lVert
x\right\rVert_{w}^{2}\right|>\varepsilon^{\prime}\left\lVert
x\right\rVert_{w}^{2}\right]\leq 12Ce^{-k\cdot\varepsilon^{\prime
2}\left\lVert x\right\rVert_{w}^{4}/(576\left\lVert
w\right\rVert_{2}^{4}\left\lVert x\right\rVert_{2}^{4}))}$

So, if we take $k=\frac{576}{\varepsilon^{\prime 2}}\left(\frac{\left\lVert
x\right\rVert_{2}\left\lVert w\right\rVert_{2}}{\left\lVert
x\right\rVert_{w}}\right)^{4}\ln(12C/\delta)={\Theta}\left(\frac{\Delta^{4}}{\varepsilon^{2}}\ln(1/\delta)\right)$,
we get the claim. ∎

Finally, we restate the above theorem to prove that the proposed reduction
maintains pairwise distances in a set $S$ of $n$ vectors and for a set of
weights $W$ with a bounded relative error. We remark that $\rho(x-y,w)$ can be
computed from the reduced vector $g(x)$ and $g(y)$: we indeed have

$\begin{split}\rho(x-y,w)&=k\textnormal{Re}\left(\displaystyle\sum_{i=1}^{k}\left((g(x)_{i}-g(y)_{i})g(w)_{i}\right)^{2}\right)\end{split}$

###### Corollary 0.

Let $S=(x_{1},\dots,x_{n})$, $x_{i}\in\mathbb{R}^{d}$ be a dataset of $n$
vectors. Let $W\subset\mathbb{R}^{d}$ be the set of the weights of interest,
with $|W|={O}\left(n\right)$. For any given $\varepsilon>0$ and
$k>\frac{c}{\varepsilon^{2}}\Delta^{4}\ln(n)$ where $c$ is an universal
constant, we have with high probability that, for any $x,y\in S$ and $w\in W$:

$\left\lVert x-y\right\rVert_{w}^{2}-\varepsilon\frac{\left\lVert
x-y\right\rVert_{2}^{2}\left\lVert
w\right\rVert_{2}^{2}}{\Delta^{2}}<\rho(x-y,w)<\left\lVert
x-y\right\rVert_{w}^{2}+\varepsilon\frac{\left\lVert
x\right\rVert_{2}^{2}\left\lVert w\right\rVert_{2}^{2}}{\Delta^{2}}.$

###### Proof.

It suffices to apply Theorem 12 with $x^{\prime}=x-y$ and
$\delta=1/(|W|n^{2})$. The claim follows by an union bound. ∎

We comment the behavior of the theorem for a special case. Let $\left\lVert
x\right\rVert=1$ and assumes that the smallest (in absolute value) entry in
$x$ is $\omega$, let $w$ contain $\ell$ entries equal to 1 and the remaining
to 0 (i.e., $w$ denotes only the desired positions). Let also assume that the
intersection of non zero positions between $x$ and $w$ is non empty. Then, it
suffices to set $k={O}\left(\varepsilon^{-2}(\ell/\omega)^{2}\log n\right)$:
that is, the low dimension depends on the ratio between the number $\ell$ of
non zero entries in $w$ and the smallest non zero entry $\omega$ in the input
set.

Finally, we carried out some proof-of-concept experiments, which are reported
in Section 5, to validate our theoretical contributions. The experiments
indeed show that the weighted squared norms estimates are centered around the
true weighted squared norms, and that the concentration around the mean
increases with $k$. Moreover, they show that the estimation quality degrades
as the distortion $\Delta(x,w)$ increases, suggesting that its presence in the
results is not a mere artifact of our analysis.

##  4\. Streaming estimation of weighted norms

In the streaming model of computation, data is generated continuously and has
to be processed on-the-fly while maintaining in memory only a sublinear
portion of it. We focus on the following problem. A vector
$x=(x_{1},\dots,x_{d})^{\intercal}\in\mathbb{R}^{d}$ is provided to the
machine via a stream one dimension at a time (e.g. at timestep 1 $x_{1}$ is
provided, at timestep 2 $x_{2}$, and so on) and the goal is to compute
$\left\lVert x\right\rVert^{2}_{w}$ while using $o(d)$ memory. If $w$ is
provided in the stream simultaneously to $x$ then it is easy to compute the
weighted norm just by updating the estimate as $\left\lVert
x\right\rVert^{2}_{w}\leftarrow\left\lVert
x\right\rVert^{2}_{w}+x^{2}_{i}w^{2}_{i}$ for each timestep $i$.111We claim
that the result also holds if the vectors $x$ and $w$ are given as a sequence
of updates $(i,h,x)$ (resp., $(i,h,w)$) meaning that entry $x_{i}$ of vector
$x$ (resp., $w_{i}$ of vector $w$) should be increased by a quantity $h$. In
this case, the hash functions should depend on index $i$ and not on the
timestep. Moreover, $x_{i}$ and $w_{i}$ in the proofs denote the final value
of entry $x_{i}$. We now detail a streaming algorithm for computing weighted
norms when the weight vector is provided separately, or for when one wants to
compute the norm for a vector $x$ with respect to multiple weights $w$. Our
algorithm is inspired by the AMS sketch (AlonMS96, ) and exploits the same
ideas that we developed in the previous sections.

We maintain an array of $r\times m$ counters $C[i,j]$, as well as $r\times m$
independent hash functions
$h_{ij}:\mathbb{N}^{+}\longrightarrow\\{1,-1,i,-i\\}$ that map timesteps to
$\pm 1$ and $\pm i$. These hash functions shall each produce 8-independent
uniform random variables over $\\{1,-1,i,-i\\}$, which can be achieved using
k-independent hashing (Wegman1981New, ) using a degree-7 polynomial, whose
coefficients can be stored with ${O}\left(1\right)$ memory. Note that the
linear transformation described in Section 3 required storing in memory the
entire matrix $A$, which takes ${O}\left(kd\right)$ bits. Upon the arrival of
a value $x_{t}$ at timestep $t$ we update, for each $i$ and $j$, the counter
as $C_{x}[i,j]+=x_{t}h_{ij}(t)$. At the end of the stream, the array $C_{x}$
is the compressed representation of $x$. We do the same for the weight $w$
using the same family of hash functions, and we obtain the array $C_{w}$. Let
$\hat{x}^{(ij)}=C_{x}[i,j]^{2}C_{w}[i,j]^{2}$. We then define
$\hat{x}^{(i)}=\frac{1}{m}\sum_{j=1}^{m}\hat{x}^{(ij)}$ and
$\tilde{x}^{(i)}=\textnormal{Re}\left(\displaystyle\hat{x}^{(i)}\right)$.
Finally, our estimate for the squared weighted norm is $\rho(x,w)$, defined as
the median of the $r$ values of the $\tilde{x}^{(i)}$’s.

While in the dimensionality reduction technique described in Section 3,
exponential tail bounds are obtained by the average of
${O}\left(\varepsilon^{-2}\log(1/\delta)\right)$ independent estimates, the
weaker k-independence, which is necessary to avoid using ${O}\left(kd\right)$
memory to store the matrix $A$, is not enough to get exponential tail bounds
just by averaging. We show that by first averaging and then taking the median
is enough to get the desired exponential tail bounds. First of all, we
establish the expected value of the $\tilde{x}^{(i)}$’s.

###### Lemma 0.

We have that $\mathbb{E}\left[\displaystyle\tilde{x}^{(i)}\right]=\left\lVert
x\right\rVert^{2}_{w}$, for $i=1,\dots,r$.

###### Proof.

By definition of $\hat{x}^{(ij)}$, we get

$\begin{split}\mathbb{E}\left[\displaystyle\hat{x}^{(ij)}\right]&=\left(\sum_{t=1}^{d}x_{t}h_{ij}(t)\right)^{2}\left(\sum_{t=1}^{d}w_{t}h_{ij}(t)\right)^{2}\\\
&=\sum_{t_{1},t_{2},t_{3},t_{4}}x_{t_{1}}x_{t_{2}}w_{t_{3}}w_{t_{4}}\mathbb{E}\left[\displaystyle
h_{ij}(t_{1})h_{ij}(t_{2})h_{ij}(t_{3})h_{ij}(t_{4})\right]\end{split}$

Since the $h_{ij}(t)$’s are 4-independent, we have
$\mathbb{E}\left[\displaystyle\hat{x}^{(ij)}\right]=\sum_{t=1}^{d}x_{t}^{2}w_{t}^{2}$.
Then, taking the average of the $\hat{x}^{(ij)}$’s and the real part preserves
the expected value. ∎

The following Lemma bounds the variance of $\hat{x}^{(i)}$ by using the
8-independence of the random variables. Recall that the variance of a complex-
valued random variable is a real number defined as
$Var\left[Z\right]=\mathbb{E}\left[\displaystyle|Z-\mathbb{E}\left[\displaystyle
Z\right]|^{2}\right]=\mathbb{E}\left[\displaystyle|Z|^{2}\right]-|\mathbb{E}\left[\displaystyle
Z\right]|^{2}=\mathbb{E}\left[\displaystyle|Z^{2}|\right]-|\mathbb{E}\left[\displaystyle
Z\right]|^{2}$.

###### Lemma 0.

We have that $Var\left[\hat{x}^{(i)}\right]\leq\frac{34}{m}\left\lVert
x\right\rVert^{4}\left\lVert w\right\rVert^{4}$.

###### Proof.

We have that

$\begin{split}\mathbb{E}\left[\displaystyle\hat{x}^{(ij)\
2}\right]&=\left(\sum_{t=1}^{d}x_{t}h(t)\right)^{4}\left(\sum_{t=1}^{d}w_{t}h(t)\right)^{4}\\\
&=\sum_{t_{1},\dots,t_{8}}x_{t_{1}}\dots
w_{t_{8}}\mathbb{E}\left[\displaystyle h(t_{1})\dots
h(t_{8})\right].\end{split}$

By 8-independence of the hash function, and recalling that
$\mathbb{E}\left[\displaystyle h(t)\right]=\mathbb{E}\left[\displaystyle
h(t)^{2}\right]=\mathbb{E}\left[\displaystyle h(t)^{3}\right]=0$, while
$\mathbb{E}\left[\displaystyle h(t)^{4}\right]=1$, we have that the only terms
of the above sum that are not 0 are the terms with 8 equal indexes and the
ones with 2 distinct quadruplets of equal indices. In the former case, for
each index $t\in\\{1,\dots,d\\}$, we have a single contribution to the sum. In
the latter case, for each pair of distinct indexes, we have five possible
configurations. The configuration
$x^{2}_{t_{1}}w^{2}_{t_{1}}x^{2}_{t_{2}}w^{2}_{t_{2}}$ appears
$\left(\frac{4!}{2!2!}\right)^{2}=36$ times, the configurations
$x^{3}_{t_{1}}w_{t_{1}}x_{t_{2}}w^{3}_{t_{2}}$ and
$x_{t_{1}}w^{3}_{t_{1}}x^{3}_{t_{2}}w_{t_{2}}$ appear
$\left(\frac{4!}{3!1!}\right)^{2}=16$ times each and the configurations
$x^{4}_{t_{1}}w^{4}_{t_{2}}$ and $x^{4}_{t_{2}}w^{4}_{t_{1}}$ appear
$\left(\frac{4!}{4!0!}\right)^{2}=1$ time each.

We then get

$\begin{split}\mathbb{E}\left[\displaystyle\hat{x}^{(ij)\
2}\right]=&\sum_{t=1}^{d}x_{t}^{4}w_{t}^{4}+36\sum_{1\leq t_{1}<t_{2}\leq
d}x^{2}_{t_{1}}w^{2}_{t_{1}}x^{2}_{t_{2}}w^{2}_{t_{2}}\\\ &+16\sum_{1\leq
t_{1}<t_{2}\leq
d}(x^{3}_{t_{1}}w_{t_{1}}x_{t_{2}}w^{3}_{t_{2}}+x_{t_{1}}w^{3}_{t_{1}}x^{3}_{t_{2}}w_{t_{2}})\\\
&+\sum_{1\leq t_{1}<t_{2}\leq
d}(x^{4}_{t_{1}}w^{4}_{t_{2}}+x^{4}_{t_{2}}w^{4}_{t_{1}}).\end{split}$

Then, we have

$\begin{split}Var[&\hat{x}^{(ij)}]=\mathbb{E}\left[\displaystyle\hat{x}^{(ij)\
2}\right]-\mathbb{E}\left[\displaystyle\hat{x}^{(ij)}\right]^{2}=\\\
&=\sum_{t=1}^{d}x_{t}^{4}w_{t}^{4}+36\sum_{1\leq t_{1}<t_{2}\leq
d}x^{2}_{t_{1}}w^{2}_{t_{1}}x^{2}_{t_{2}}w^{2}_{t_{2}}\\\ &+16\sum_{1\leq
t_{1}<t_{2}\leq
d}(x^{3}_{t_{1}}w_{t_{1}}x_{t_{2}}w^{3}_{t_{2}}+x_{t_{1}}w^{3}_{t_{1}}x^{3}_{t_{2}}w_{t_{2}})\\\
&+\sum_{1\leq t_{1}<t_{2}\leq
d}(x^{4}_{t_{1}}w^{4}_{t_{2}}+x^{4}_{t_{2}}w^{4}_{t_{1}})-\left(\sum_{t=1}^{d}x_{t}^{2}w_{t}^{2}\right)^{2}=\\\
&=\sum_{t=1}^{d}x_{t}^{4}w_{t}^{4}+36\sum_{t_{1}<t_{2}}x^{2}_{t_{1}}w^{2}_{t_{1}}x^{2}_{t_{2}}w^{2}_{t_{2}}\\\
&+16\sum_{t_{1}<t_{2}}(x^{3}_{t_{1}}w_{t_{1}}x_{t_{2}}w^{3}_{t_{2}}+x_{t_{1}}w^{3}_{t_{1}}x^{3}_{t_{2}}w_{t_{2}})\\\
&+\sum_{t_{1}<t_{2}}(x^{4}_{t_{1}}w^{4}_{t_{2}}+x^{4}_{t_{2}}w^{4}_{t_{1}})-\sum_{t=1}^{d}x_{t}^{4}w_{t}^{4}-2\sum_{t_{1}<t_{2}}x^{2}_{t_{1}}w^{2}_{t_{1}}x^{2}_{t_{2}}w^{2}_{t_{2}}=\\\
&=34\sum_{t_{1}<t_{2}}x^{2}_{t_{1}}w^{2}_{t_{1}}x^{2}_{t_{2}}w^{2}_{t_{2}}+16\sum_{t_{1}<t_{2}}(x^{3}_{t_{1}}w_{t_{1}}x_{t_{2}}w^{3}_{t_{2}}+x_{t_{1}}w^{3}_{t_{1}}x^{3}_{t_{2}}w_{t_{2}})\\\
&+\sum_{t_{1}<t_{2}}(x^{4}_{t_{1}}w^{4}_{t_{2}}+x^{4}_{t_{2}}w^{4}_{t_{1}}).\end{split}$

We bound each of the three terms individually, using a combination of Lemma 1
and Lemma 2:

$\begin{split}2\sum_{1\leq t_{1}<t_{2}\leq
d}x^{2}_{t_{1}}w^{2}_{t_{1}}x^{2}_{t_{2}}w^{2}_{t_{2}}&\leq\left(\sum_{t}x^{2}_{t}w^{2}_{t}\right)^{2}\leq\left(\sum_{t}x_{t}^{4}\right)\left(\sum_{t}w^{4}_{t}\right)\\\
&=\left\lVert x\right\rVert_{4}^{4}\left\lVert
w\right\rVert_{4}^{4}\leq\left\lVert x\right\rVert_{2}^{4}\left\lVert
w\right\rVert_{2}^{4}\end{split}$ $\begin{split}\sum_{1\leq t_{1}<t_{2}\leq
d}&(x^{3}_{t_{1}}w_{t_{1}}x_{t_{2}}w^{3}_{t_{2}}+x_{t_{1}}w^{3}_{t_{1}}x^{3}_{t_{2}}w_{t_{2}})\leq\left(\sum_{t}x^{3}_{t}w_{t}\right)\left(\sum_{t}x_{t}w^{3}_{t}\right)\\\
&\leq\left(\sum_{t}x_{t}^{6}\right)^{1/2}\left(\sum_{t}w^{2}_{t}\right)^{1/2}\left(\sum_{t}x_{t}\right)^{1/2}\left(\sum_{t}w^{6}_{t}\right)^{1/2}\\\
&=\left\lVert x\right\rVert_{6}^{3}\left\lVert w\right\rVert_{2}\left\lVert
x\right\rVert_{2}\left\lVert w\right\rVert_{6}^{3}\leq\left\lVert
x\right\rVert_{2}^{4}\left\lVert w\right\rVert_{2}^{4}\end{split}$
$\begin{split}\sum_{1\leq t_{1}<t_{2}\leq
d}(x^{4}_{t_{1}}w^{4}_{t_{2}}+x^{4}_{t_{2}}w^{4}_{t_{1}})&\leq\left(\sum_{t}x_{t}^{4}\right)\left(\sum_{t}w^{4}_{t}\right)=\left\lVert
x\right\rVert_{4}^{4}\left\lVert w\right\rVert_{4}^{4}\\\ &\leq\left\lVert
x\right\rVert_{2}^{4}\left\lVert w\right\rVert_{2}^{4}.\end{split}$

Then we have that

$Var[\hat{x}^{(ij)}]\leq 17\left\lVert x\right\rVert_{2}^{4}\left\lVert
w\right\rVert_{2}^{4}+16\left\lVert x\right\rVert_{2}^{4}\left\lVert
w\right\rVert_{2}^{4}+\left\lVert x\right\rVert_{2}^{4}\left\lVert
w\right\rVert_{2}^{4}.$

Since the $\hat{x}^{(ij)}$, $j=1,\dots,m$ are all independent, we have that

$Var[\hat{x}^{(i)}]=\frac{1}{m^{2}}\sum_{j=1}^{m}Var[\hat{x}^{(ij)}]\leq\frac{34}{m}\left\lVert
x\right\rVert^{4}_{w}.$

∎

###### Theorem 3.

For any $x,w\in\mathbb{R}^{d}$ and for any $\varepsilon,\delta>0$, choosing
$m>\frac{136}{\varepsilon^{2}}\Delta(x,w)^{4}$ and $r>12\ln(1/\delta)$ yields

$(1-\varepsilon)\left\lVert
x\right\rVert^{2}_{w}<\rho(x,w)<(1+\varepsilon)\left\lVert
x\right\rVert^{2}_{w}$

with probability at least $1-\delta$.

###### Proof.

We first show that Chebychev’s inequality holds for complex random variables.
Indeed, let $Z$ be a complex random variable and $Var[Z]$ its variance. Let
also $U=|Z-\mathbb{E}\left[\displaystyle Z\right]|^{2}$. Then $U$ is a real-
valued random variable. Then we have

$\textnormal{Pr}\left[\displaystyle|Z-\mathbb{E}\left[\displaystyle
Z\right]|>a\right]=\textnormal{Pr}\left[\displaystyle
U>a^{2}\right]\leq\frac{\mathbb{E}\left[\displaystyle
U\right]}{a^{2}}=\frac{Var[Z]}{a^{2}}.$

By Chebychev’s inequality, we then have that

$\begin{split}\textnormal{Pr}\left[\displaystyle\left|\hat{x}^{(i)}-\left\lVert
x\right\rVert_{w}^{2}\right|>\varepsilon\left\lVert
x\right\rVert_{w}^{2}\right]&\leq\frac{Var[\hat{x}^{(i)}]}{\varepsilon^{2}\left\lVert
x\right\rVert_{w}^{4}}\leq\frac{\frac{34}{m}\left\lVert
x\right\rVert^{4}\left\lVert w\right\rVert^{4}}{\varepsilon^{2}\left\lVert
x\right\rVert^{4}_{w}}\\\
&\leq\frac{34}{\varepsilon^{2}m}\Delta(x,w)^{4}\leq\frac{1}{4}.\end{split}$

Recalling that

$\begin{split}\left|\hat{x}^{(i)}-\left\lVert
x\right\rVert_{w}^{2}\right|^{2}&=\left(\textnormal{Re}\left(\displaystyle\hat{x}^{(i)}\right)-\left\lVert
x\right\rVert_{w}^{2}\right)^{2}+\textnormal{Im}\left(\displaystyle\hat{x}^{(i)}\right)^{2}\\\
&=\left(\tilde{x}^{(i)}-\left\lVert
x\right\rVert_{w}^{2}\right)^{2}+Im(\hat{x}^{(i)})^{2}\geq\left(\tilde{x}^{(i)}-\left\lVert
x\right\rVert_{w}^{2}\right)^{2},\end{split}$

we have that
$\textnormal{Pr}\left[\displaystyle\left|\tilde{x}^{(i)}-\left\lVert
x\right\rVert_{w}^{2}\right|>\varepsilon\left\lVert
x\right\rVert_{w}^{2}\right]\leq\frac{1}{4}.$ For each $i=1,\dots,r$, let then
$X_{i}$ be $1$ if the event $\left|\tilde{x}^{(i)}-\left\lVert
x\right\rVert_{w}^{2}\right|\leq\varepsilon\left\lVert x\right\rVert_{w}^{2}$
happens and $0$ otherwise. By letting $\rho(x,w)$ be the median of the
$\tilde{x}^{(i)}$’s, we have that if $\sum_{i=1}^{r}X_{i}>r/2$, then the event
$\left|\rho(x,x)-\left\lVert
x\right\rVert_{w}^{2}\right|\leq\varepsilon\left\lVert x\right\rVert_{w}^{2}$
is true. We can bound such a probability using Chernoff’s bound:

$\textnormal{Pr}\left[\displaystyle\sum_{i=1}^{r}X_{i}>r/2\right]=\textnormal{Pr}\left[\displaystyle\sum_{i=1}^{r}X_{i}>2\cdot\mathbb{E}\left[\displaystyle\sum_{i=1}^{r}X_{i}\right]\right]\leq\exp\left(-\frac{r}{12}\right)<\delta.$

∎

We remark that the dimensionality reduction described in this section uses
only ${O}\left(\varepsilon^{-2}\log(1/\delta)\right)$ memory. On the other
hand, this transformation is not linear in $x$, and hence it would not
maintain pairwise distances between vectors, while the one described in
Section 3 is.

##  5\. Experiments

In this section, we present some proof-of-concept experiments to validate our
theoretical contributions. The main goals of the experiments are (i) to show
that the weighted squared norms estimates derived from the compressed vectors
are centered around the true weighted squared norms and that the concentration
around the mean increases with $k$, and (ii) investigate the degradation of
the estimation quality as the distortion $\Delta(x,w)$ increases. We
implemented the linear transformation described in Section 3 in Python and run
our experiments on a Linux server equipped with an Intel Xeon W-2245
processor.

###  5.1. Concentration of estimates

In the first set of experiments, we show the concentration of the norm
estimates across different realizations of the algorithm. Towards this end, we
fix $d=2\cdot 10^{5}$ and generate a single random sparse vector
$x\in\mathbb{R}^{d}$, with $\ell_{x}=\ell=10$ nonzero entries and with
(Euclidean) norm $1$, and a single sparse weight vector $w\in\mathbb{R}^{d}$
with $\ell_{w}=\ell=10$ entries set to $1$. The dimensions in which both $x$
and $w$ have nonzero entries are fixed to be $\ell_{\rm overlap}=8$ and chosen
at random. This setting illustrates a quite general case, where the user is
interested in only some of the dimensions of the vector, and not all of them
correspond to nonzero entries in the vector, leading to a weighted norm
smaller than the euclidean norm. While in these experiments we keep the
overlap between the nonzero entries fixed, we investigate how different
choices of $w$, and consequently of $\Delta(x,w)$, influence the performance
in Section 5.2.

Then, we generate $250$ random matrices $A$, as described in Section 3, and
for each of them, we perform the dimensionality reduction and norm estimation
for $x$ and $w$. Figure 1 reports the histograms of the estimated squared
weighted norm for the different generated matrices, for
$k\in\\{10^{2},10^{3},10^{4},10^{5}\\}$.

Figure 1. Histograms for estimated squared weighted norms for fixed $x$ and
$w$ over $250$ different realizations of the random matrix $A$, for
$k\in\\{10^{2},10^{3},10^{4},10^{5}\\}$. We fix $\ell=10$ and $\ell_{\rm
overlap}=8$.

As one can see from the plots, the estimates for $\left\lVert
x\right\rVert^{2}_{w}$ are centered around the true value and get more
concentrated as $k$ increases.

Moreover, we investigate the concentration of the norm estimates across
different random vectors $x$, keeping $A$ fixed. Towards this end, we generate
a single random matrix $A$ and a fixed sparse weight vector $w$ with
$\ell_{w}=\ell=10$ nonzero entries. We then generate $250$ sparse random
vectors $x_{i}$, each with $\ell_{x}=\ell=10$ nonzero entries, again such that
the overlap between the nonzero entries of $w$ and the $x_{i}$’s is fixed to
$\ell_{\rm overlap}=8$.

Figure 2. Histograms for the ratio between estimated squared weighted norms
and true squared weighted norms, for fixed $A$ and $w$ over $250$ different
random vectors $x$, for $k\in\\{10^{2},10^{3},10^{4},10^{5}\\}$. We fix
$\ell=10$ and $\ell_{\rm overlap}=8$.

Figure 2 reports the results of the experiments. Since the weighted norms of
the vectors are all different, we report the histograms for the ratio between
the estimated and the true norms, i.e. $\rho(x,w)/\left\lVert
x\right\rVert^{2}_{w}$. Overall, we observe that the estimates are generally
centered around the true values, and that the concentration increases wit $k$,
as expected.

###  5.2. Dependence on distortion

In this second set of experiments, we investigate the dependence of the
quality of the estimates on the distortion $\Delta(x,w)$.

First, we keep $\left\lVert x\right\rVert$ and $\left\lVert w\right\rVert$
fixed, using again sparse random vectors generated as described in Section
5.1, with $\ell_{x}=\ell_{w}=10$, and we vary the value of $\left\lVert
x\right\rVert_{w}$. This can be easily achieved by varying the number
$\ell_{\rm overlap}$ of nonzero entries overlapping between $x$ and $w$.
Indeed, the lower $\ell_{\rm overlap}$, the lower $\left\lVert
x\right\rVert_{w}$ gets.

Figure 3 reports the histograms for the estimated squared weighted norms for
$250$ different realizations of the random matrix $A$ for both $\ell_{\rm
overlap}=2$ and $\ell_{\rm overlap}=10$. In the former case, $\left\lVert
x\right\rVert_{w}$ is much smaller than $\left\lVert x\right\rVert$ while in
the latter case the two norms coincide.

As expected from our theoretical analysis, the concentration of the estimates
in absolute terms is roughly the same in the two scenarios, since it depends
only on $\left\lVert x\right\rVert\left\lVert w\right\rVert$. On the other
hand, since $\left\lVert x\right\rVert_{w}$ in the former case is smaller than
in the latter case, this corresponds to a worse error in relative terms, as
described by Theorem 12.

Figure 3. Histograms for estimated squared weighted norms for fixed $x$ and
$w$ over $250$ different realizations of the random matrix $A$, for $\ell_{\rm
overlap}\in\\{2,10\\}$. We fix $k=10^{5}$ and $\ell_{x}=\ell_{w}=10$.

As a second way to vary $\Delta(x,w)$, we increase the density of the vectors
$x$ and $w$. Indeed, we have that $\Delta(x,w)\in
O\left(\frac{\ell_{x}\ell_{w}}{\min(\ell_{x},\ell_{w})}\right)$, which for
$\ell_{x}=\ell_{w}=\ell$ grows linearly with $\ell$.

As before, for each experiment, we generated a random vector $x$ and a random
weight vector $w$, each with $\ell$ nonzero entries and with an overlap of
$\ell_{\rm overlap}=0.8\ell$ nonzero entries. We tested
$\ell\in\\{10,30,100\\}$, and for each value we repeated the experiment for
$250$ different realizations of the random matrix $A$.

Figure 4. Histograms for estimated squared weighted norms for fixed $x$ and
$w$ over $250$ different realizations of the random matrix $A$, for
$\ell\in{30,100}$. We fix $k=10^{5}$ and $\ell_{\rm overlap}=0.8\ell$.

Figure 4 reports the histograms for the estimated squared weighted norms for
the various values of $\ell$. We omitted $\ell=10$ since it is reported in
Figure 1. As shown by the plots, while the estimates are centered around the
true values, the concentration significantly worsens as $\ell$ increases. This
suggests that the term $\Delta(x,w)$ in Theorem 12 is not an artifact of our
analysis, but is indeed present also in practice.

##  6\. Conclusion

In this paper we provided the first dimensionality reduction techniques that
are able to cope with dynamically-weighted Euclidean distances. First, we
introduced a JL-type linear transformation that maps vectors to a lower-
dimensional complex vector space. The estimated weighted norms obtained from
the compressed vectors are an $\varepsilon$-approximation for the true
weighted norms with high probability. Moreover, the AMS-like sketch provides
an alternative dimensionality reduction approach that allows for a
significantly lower memory footprint, at the cost of giving up linearity. An
interesting open question is to provide a fast method for dimensionality
reductions in the complex vector space similar to the Fast JL transform
(AilonC09, ). Finally, we believe that our constructions can be of interest
for privacy preserving similarity search: suppose that an user wants to search
similar vectors using its own weights; the low dimension vectors represent a
noisy variant of the original vectors that can be shared with this user, but
without revealing the original vectors.

## References

  * [1] Dimitris Achlioptas.  Database-friendly random projections: Johnson-lindenstrauss with binary coins.  Journal of Computer and System Sciences, 66(4):671–687, 2003.
  * [2] Nir Ailon and Bernard Chazelle.  The fast johnson–lindenstrauss transform and approximate nearest neighbors.  SIAM J. Comput., 39(1):302–322, 2009.
  * [3] Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  In Gary L. Miller, editor, Proc. 28th Annual ACM Symposium on the Theory of Computing (STOC), pages 20–29. ACM, 1996.
  * [4] Jean Paul Barddal, Heitor Murilo Gomes, Fabrício Enembreck, Bernhard Pfahringer, and Albert Bifet.  On dynamic feature weighting for feature drifting data streams.  In Proc. European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD), volume 9852 of LNCS, pages 129–144, 2016.
  * [5] Gautam Bhattacharya, Koushik Ghosh, and Ananda S. Chowdhury.  Granger causality driven AHP for feature weighted knn.  Pattern Recognit., 66:425–436, 2017.
  * [6] Renato Cordeiro de Amorim.  A survey on feature weighting based k-means algorithms.  J. Classif., 33(2):210–242, 2016.
  * [7] V. de la Peña and E. Giné.  Decoupling: From Dependence to Independence.  Probability and Its Applications. Springer New York, 2012.
  * [8] Yupeng Gu, Bo Zhao, David Hardtke, and Yizhou Sun.  Learning global term weights for content-based recommender systems.  In Proc. 25th ACM International Conference on World Wide Web (WWW), pages 391–400, 2016.
  * [9] Sariel Har-Peled and Sepideh Mahabadi.  Proximity in the age of distraction: Robust approximate nearest neighbor search.  In Proc. 28 ACM-SIAM Symposium on Discrete Algorithms (SODA), SODA ’17, page 1–15. Society for Industrial and Applied Mathematics, 2017.
  * [10] Huan Hu and Jianzhong Li.  Sublinear time nearest neighbor search over generalized weighted manhattan distance.  CoRR, abs/2104.04902, 2021.
  * [11] William Johnson and Joram Lindenstrauss.  Extensions of lipschitz maps into a hilbert space.  Contemporary Mathematics, 26:189–206, 01 1984.
  * [12] Kasper Green Larsen and Jelani Nelson.  The johnson-lindenstrauss lemma is optimal for linear dimensionality reduction.  In Proc. 43rd International Colloquium on Automata, Languages, and Programming (ICALP), volume 55 of LIPIcs, pages 82:1–82:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
  * [13] Yifan Lei, Qiang Huang, Mohan S. Kankanhalli, and Anthony K. H. Tung.  Sublinear time nearest neighbor search over generalized weighted space.  In Proc. 36th International Conference on Machine Learning, (ICML), volume 97, pages 3773–3781, 2019.
  * [14] Iratxe Niño-Adan, Diana Manjarres, Itziar Landa-Torres, and Eva Portillo.  Feature weighting methods: A review.  Expert Systems with Applications, 184:115424, 2021.
  * [15] Roman Vershynin.  High-Dimensional Probability: An Introduction with Applications in Data Science.  Cambridge University Press, 2018.
  * [16] Hao Wang, Naiyan Wang, and Dit-Yan Yeung.  Collaborative deep learning for recommender systems.  In Proc. 21th ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD), pages 1235–1244, 2015.
  * [17] Mark N. Wegman and J.Lawrence Carter.  New hash functions and their use in authentication and set equality.  Journal of Computer and System Sciences, 22(3):265–279, 1981.
  * [18] Kai Yu, Xiaowei Xu, Martin Ester, and Hans-Peter Kriegel.  Feature weighting and instance selection for collaborative filtering: An information-theoretic approach*.  Knowl. Inf. Syst., 5(2):201–224, 2003.