
## A. Mean And Variance

Proof [Lemma 2] To compute the expectation we expand

$$\left\langle x,x^{\prime}\right\rangle_{\phi}=\sum_{i,j}\xi(i)\xi(j)x_{i}x_{j}^{\prime}\delta_{h(i),h(j)}.\tag{10}$$

Since Eφ[h**x, x**′iφ
] = Eh[Eξ[h**x, x**′iφ
]], taking expectations over ξ we see that only the terms i = j have nonzero value, which shows the first claim. For the variance we compute Eφ[h**x, x**′i 2 φ
]. Expanding this, we get:

$$\langle x,x^{\prime}\rangle_{\phi}^{2}=\sum_{i,j,k,l}\xi(i)\xi(j)\xi(k)\xi(l)x_{i}x_{j}^{\prime}x_{k}x_{l}^{\prime}\delta_{h(i),h(j)}\delta_{h(k),h(l)}\,.$$

This expression can be simplified by noting that:

Eξ [ξ(i)ξ(j)ξ(k)ξ(l)] = δij δkl + [1 − δ**ijkl**](δikδjl + δilδjk).
Passing the expectation over ξ through the sum, this allows
us to break down the expansion of the variance into two
terms.
Eφ[hx, x′i 2 φ ] = X i,k xix ′ixkx ′k +X i6=j x 2 i x ′j 2Eh-δh(i),h(j)  +X i6=j xix ′ixjx ′jEh-δh(i),h(j)  = hx, x′i 2 + 1 m  X i6=j x 2 i x ′j 2 +X i6=j xix ′ixjx ′j   by noting that Eh-δh(i),h(j) = 1 m for i 6= j. Using the fact
that σ
2 = Eφ[h**x, x**′i
2
φ
]−Eφ[h**x, x**′iφ
]
2 proves the claim.

## B. Concentration Of Measure

We use the concentration result derived by Liberty, Ailon and Singer in (Liberty et al., 2008). Liberty et al. create a Johnson-Lindenstrauss random projection matrix by combining a carefully constructed deterministic matrix A
with random diagonal matrices. For completeness we restate the relevant lemma. Let i range over the hashbuckets. Let m = c **log(1**/δ)/ǫ2for a large enough constant c. For a given vector x, define the diagonal matrix Dx as (Dx)jj = xj . For any matrix A ∈ ℜm×d, define kxkA ≡ maxy:kyk2=1 kADxyk2.

Lemma 2 (Liberty et al., 2008). For any columnnormalized matrix A, vector x *with* kxk2 = 1 *and an* i.i.d. random ±1 diagonal matrix Ds*, the following holds:*
∀x, if kxkA ≤ ǫ 6
√**log(1**/δ)
then, Pr[|kADsxk2−1| > ǫ] ≤
δ. We also need the following form of a weighted balls and bins inequality - the statement of the Lemma, as well as the proof follows that of Lemma 6 (Dasgupta et al., 2010).

We still outline the proof because of some parameter values being different.

Lemma 8 Let m be the size of the hash function range and let η =1 2
√m log(m/δ)
. If x *is such that* kxk2 = 1 and kxk∞ ≤ η*, then define* σ 2
∗ **= max**iPd j=1 x 2 j δih(j) *where* i ranges over all hash-buckets. We have that with probability 1 − δ,

$$\sigma_{*}^{2}\leq{\frac{2}{m}}$$

Proof We outline the proof-steps. Since the buckets have identical distribution, we look only at the 1 st bucket, i.e. at i = 1 and bound Pj:h(j)=1 x 2 j
. Define Xj = x 2 j δ1h(j) −
1 m
. Then Eh[Xj **] = 0** and Eh[X2 j
] = x 4 j 1m − 1 m2≤
x 4 j m ≤
x 2 j η 2 m using kxk∞ ≤
η. Thus, Pj Eh[X2 j
] ≤η 2 m . Also note that Pj Xj = Pj:h(j)=1 x 2 j −
1 m . Plugging this into the Bernstein's inequality, equation 5, we have that

$$\begin{array}{r l}{\operatorname*{Pr}[\sum_{j}X_{j}>{\frac{1}{m}}]\leq\exp\left(-{\frac{1/2m^{2}}{\eta^{2}/m+\eta^{2}/3m}}\right)}\\ {=\exp(-{\frac{3}{8m\eta^{2}}})\leq\exp(-\log(m/\delta))\leq\delta/m}\end{array}$$

By taking union bound over all the m buckets, we get the above result.

Proof [Theorem 3] Given the function φ = (**h, r**), define the matrix A as Aij = δih(j) and Ds as (Ds)jj = rj . Let x be as specified, i.e. kxk2 = 1 and kxk∞ ≤ η. Note that kxkφ = kADsxk2. Let y ∈ ℜd be such that kyk2 = 1.

Thus

$$\begin{split}\|AD_{xy}\|_{2}^{2}&=\sum_{i=1}^{m}\left(\sum_{j=1}^{d}y_{j}\delta_{ih(j)}x_{j}\right)^{2}\\ &\leq\sum_{i=1}^{m}(\sum_{j=1}^{d}y_{j}^{2}\delta_{ih(j)})(\sum_{j=1}^{d}x_{j}^{2}\delta_{ih(j)})\\ &\leq\sum_{i=1}^{m}(\sum_{j=1}^{d}y_{j}^{2}\delta_{ih(j)})\sigma_{*}^{2}\leq\sigma_{*}^{2}.\end{split}$$

by applying the Cauchy-Schwartz inequality, and using the definition of σ∗. Thus, kxkA **= max**y:kyk2=1 kADxyk2 ≤
σ∗ ≤√2m−1/2. If m ≥72 ǫ 2 **log(1**/δ), we have that kxkA ≤ǫ 6
√**log(1**/δ)
, which satisfies the conditions of Lemma 2 from (Liberty et al., 2008). Thus applying the above result from Lemma 2 (Liberty et al., 2008) to x, and