using Lemma 8, we have that Pr[|kADsxk 2 − 1| ≥ ǫ] ≤ δ and hence

$$\Pr[|\|x\|_{\phi}^{2}-1|\geq\epsilon]\leq\delta$$

by taking union over the two error probabilities of Lemma 2 and Lemma 8, we have the result.

## C. Inner Product

Proof [Corollary 4] We have that 2 h**x, x**′iφ = kxk 2 φ +
kx′k 2 φ − kx − x′k 2 φ
. Taking expectations, we have the standard inner product inequality. Thus,

$\left|2\left\langle x,x^{\prime}\right\rangle_{\phi}-2\left\langle x,x^{\prime}\right\rangle\right|\leq\left|\left|\left|x\right|\right|_{\phi}^{2}-\left|\left|x\right|\right|^{2}\right|$  $+\left|\left|\left|x^{\prime}\right|\right|_{\phi}^{2}-\left|\left|x^{\prime}\right|\right|^{2}\right|+\left|\left|\left|x-x^{\prime}\right|\right|_{\phi}^{2}-\left|\left|x-x^{\prime}\right|\right|^{2}\right|$
Using union bound, with probability 1 − 3δ, each of the terms above is bounded using Theorem 3. Thus, putting the bounds together, we have that, with probability 1 − 3δ,

$2\left\langle\phi_{u}(x),\phi_{u}(x)\right\rangle-2\left\langle x,x\right\rangle|\leq\epsilon(\left\|x\right\|^{2}+\left\|x^{\prime}\right\|^{2}+\left\|x-x^{\prime}\right\|^{2})$.  

## D. Refutation Of The Previous Incorrect Proof

There were a few bugs in the previous version of the paper (Weinberger et al., 2009). We now detail each of them and illustrate why it was an error. The current result shows that the using hashing we can create a projection matrix that can preserve distances to a factor of (1 ± ǫ) for vectors with a bounded kxk∞/kxk2 ratio. The constraint on input vectors can be circumvented by multiple hashing, as outlined in Section 3.2, but that would require hashing O(
1 ǫ 2 )
times. Recent work (Dasgupta et al., 2010) suggests that better theoretical bounds can be shown for this construction. We thank Tamas Sarlos and Ravi Kumar for the following writeup on the errors and for suggestion the new proof in Appendix B.

1. The statement of the main theorem in Weinberger et al. (Weinberger et al., 2009, Theorem 3) is false as it contradicts the lower bound of Alon (Alon, 2003). The flaw lies in the probability of error in (Weinberger et al., 2009, Theorem 3), which was claimed to be exp(−
√ǫ 4η
). This error can be made arbitrarily small without increasing the embedding dimensionality m but by decreasing η =
||x||∞
||x||2
, which in turn can be achieved by preprocessing the input vectors x. However, this contradicts Alon's lower bound on the em-
bedding dimensionality. The details of this contradiction are best presented through (Weinberger et al.,
2009, Corollary 5) as follows.

Set m **= 128** and δ = 1/2 and consider the vertices of the n-simplex in ℜ
n+1, i.e., x1 = (1, 0**, ...,** 0),
x2 = (0, 1, 0**, ...,** 0), . . . . Let P ∈ ℜ(n+1)c×(n+1)
be the naive, replication based preconditioner, with replication parameter c **= 512 log**2n as defined in Section 2 of our submission or (Weinberger et al.,
2009, Section 3.2). Therefore for all pairs i 6= j we have that ||P xi − P xj ||∞ = 1/
√c and that ||P xi − P xj ||2 =
√2. Hence we can apply (Weinberger et al., 2009, Corollary 5) to the set of vectors P xi with η = 1/
√2c = 1/**(32 log** n); then the claimed approximation error is q2m +64η 2log2 n 2δ =
1 8+ 1 16 ≤ 14
. If Corollary 5 were true, then it would follow that with probability at least 1/2, the linear transformation A = φ · P : ℜ
n+1 → ℜm distorts the pairwise distances of the above n + 1 vectors by at most a 1 ± 1/4 multiplicative factor. On the other hand, the lower bound of Alon shows that any such transformation A must map to **Ω(log** n) dimensions; see the remarks following Theorem 9.3 in (Alon, 2003) and set ǫ = 1/4 there. This clearly contradicts m **= 128**
above.

2. The proof of the Theorem 3 contained a fatal, unfixable error. Recall that δij denotes the usual Kronecker symbol, and h and h′are hash functions. Weinberger et al. make the following observation after equation (13) of their proof on page 8 in Appendix B.

"First note that Pi Pj δh(j)i + δh′(j)iis at most 2t, where t = |{j : h(j) 6= h′(j)}|."
The quoted observation is false. Let d denote the dimension of the input. Then, Pi Pj δh(j)i + δh′ P
(j)i =
j
(Pi δh(j)i + δh′(j)i) = Pj 2 = 2d, independent of the choice of the hash function. Note that t played a crucial role in the proof of (Weinberger et al., 2009)
relating the Euclidean approximation error of the dimensionality reduction to Talagrand's convex distance defined over the set of hash functions. Albeit the error is elementary, we do not see how to rectify its consequences in (Weinberger et al., 2009) even if the claim were of the right form.

3. The proof of Theorem 3 in (Weinberger et al., 2009)
also contains a minor and fixable error. To see this, consider the sentence towards the end of the proof Theorem 3 in (Weinberger et al., 2009) where 0 <
ǫ < 1 and β = β(x) ≥ 1.

"Noting that s 2 = (pβ 2 + ǫ −
β)/4||x||∞ ≥
√ǫ/4||x||∞, ..."