The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors

• p. 11 Running time paragraph

  This number is distributed B(nk, q).

• p. 11 Running time

  This number is distributed B(nk, q)

• p. 6 Section 2, definition of P

  P is a k-by-d matrix

Judge's note: p.307 defines P as k-by-d with each entry nonzero independently with probability q; p.312 prints B(nk,q). The claimed E|P| = O(ε^{p−4}log^{p+1} n) follows from dkq with q = Θ(ε^{p−2}log^p n/d) and k = cε^{−2}log n; nkq would carry an extra factor n/d (n ≥ d is assumed).

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 19 Section 5, Achlioptas paragraph

  as 0 with probability 1 −q and uniformly ±1 (instead of a normal distribution) with probability 1 −q

• p. 19 Section 5, paragraph on combining FJLT with Achlioptas

  uniformly ±1 (instead of a normal distribution) with probability 1 −q

• p. 19 Concluding remarks

  0 with probability 1 −q and uniformly ±1 (instead of a normal distribution) with probability 1 −q

• p. 6 Section 2, definition of P

  With probability 1 −q set Pij as 0, and otherwise (with the remaining prob-

Judge's note: Page 19 image confirms the text. The definition of P on page 6 says 'With probability 1 − q set P_ij as 0, and otherwise (with the remaining probability q)'. As printed, the two probabilities sum to 2 − 2q.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 7 Lemma 1, part 1

  α1 = k√2π−1 and α2 = k

• p. 11 ℓ2 case conclusion

  Pr [ Σ y2 i > (1 + ε)k ] ≤ e−Ω(ε2k)

• p. 7 Lemma 1, part 1

  where α1 = k√2π−1 and α2 = k

• p. 11 Proof, ℓ2 case

  Pr[ Σ y_i^2 > (1 + ε)k ] ≤ e−Ω(ε2k)

Only the authors can say what is right here.

Judge's note: Reworked from p.312 image: conditioned on Z_i, E[y_i^2] = Z_i/q, and Lemma 3 gives ΣZ_i ≈ kq, so Σy_i^2 ≈ k; the conclusion printed is Pr[Σy_i^2 > (1+ε)k] ≤ e^{−Ω(ε^2 k)}, i.e. a statement about the squared norm. With ||x||_2 = 1 the lemma as printed requires ||Φx||_2 ≈ k, which fails for k ≥ 2 (e.g. q=1: ||Φx||_2^2 ~ χ^2_k). α_1 = k√(2/π) is consistent with the unsquared ℓ1 norm, so the ℓ2 statement needs α_2 = √k or a squared norm. No statement in the paper says p=2 refers to the squared norm.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 13 Fig. 3 pseudocode, query loop

  else if DT (x, p′) > (1 + 1 2)k (failure)

• p. 15 Section 3.4

  If DT (x, p′) ≤(1 + 1 2ε)k, then

• p. 13 Fig. 3 pseudocode

  else if DT (x, p′) > (1 + 1/2)k (failure)

• p. 16 Section 3.4

  DT (x, p′) > (1 + 1/2ε)k, then we conclude that all points p ∈Px satisfy

Judge's note: Fig. 3 crop (p.314) shows (1+½)k with no ε; p.316–317 text shows D_T(x,p′) ≤ (1+½ε)k for success and > (1+½ε)k for failure. The pseudocode as printed implements a fixed 1.5k threshold, contradicting the described algorithm; evident fix is to insert ε.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 16 Section 4, definition of R^{l,j}

  with the probability of a 1 being 1/2l

• p. 17 Section 4, definition of μ(l)

  μ(l) def = 1 2 ( 1 − ( 1 − 1 2l ) l )

• p. 17 Section 4, definition of μ(l)

  μ(l) def= 1/2 (1 − (1 − 1/2l)^l)

Only the authors can say what is right here.

Judge's note: Pages 16–18 checked. If row entries are Bernoulli(β), then for a vector with l ones r·v mod 2 is 1 with probability ½(1 − (1−2β)^l). With β = 1/(2l) this is ½(1 − (1 − 1/l)^l). Counterexample at l = 1: β = 1/2, so every bit of R(x+p) is 1 with probability 1/2 and the expected distance is k/2. The printed μ(1) = 1/4, and the ball radius k(1/4 + ε′/3) is below k/2 for small ε′, so Lemma 5(ii) fails with the parameters as printed. Sections 4.1 and 4.2 consistently use 1/2l, i.e. 1/(2l). Either the entry probability or μ(l) needs changing. Lemma 5 is attributed to [33], which is not among the files, so the authors should say which parameter is intended.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 19 Section 5, Achlioptas paragraph

  for the (ℓ1 →ℓ1) case (also affecting the ε-ANN application)

Only the authors can say what is right here.

Judge's note: Page 19. Fig. 3 and Section 3.2 (pages 13 and 15) use a 'random (ℓ2 → ℓ1) FJLT matrix', and the parallel case in the same sentence is (ℓ2 → ℓ2). No ℓ1 → ℓ1 embedding appears anywhere in the paper. What Matoušek [36] actually covers rests on outside knowledge, so this is filed as a query.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 20 Reference [19]

  in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1990, pp. 128–137.

• p. 20 Reference [19]

  in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1990

• p. 21 Reference [29]

  Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1998

• p. 20 Reference [19]

  Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1990

Only the authors can say what is right here.

Judge's note: Rests on outside knowledge: STOC numbering, with the 22nd STOC held in 1990. Within the paper itself, [32] 29th/1997, [29] 30th/1998, [9] 31st/1999 and [41] Thirty-Second/2000 all follow ordinal = year − 1968. On that pattern 1990 would be the 22nd, so either '20th' or '1990' is wrong. Only the authors can say which.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 2 Section 1.1, description of the JL matrix

  The resulting matrix is a projection onto a random k-dimensional subspace of Rn

• p. 2 Section 1.1, end of construction paragraph

  projection onto a random k-dimensional subspace of Rn

• p. 2 Section 1.1, last paragraph

  a projection onto a random k-dimensional subspace of Rn

• p. 2 section 1.1

  random k-dimensional subspace of Rn

Judge's note: Crop of p.2 shows R^n. The same sentence group defines Φ as a k×d matrix with rows in S^{d−1} ⊂ R^d, and n is used throughout for the number of points. No other interpretation makes R^n correct.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 6 Section 2, paragraph after definition of D

  The Walsh–Hadamard matrix encodes the discrete Fourier transform over the additive group GF (2)d

• p. 6 Section 2, after definition of D

  discrete Fourier transform over the additive group GF (2)d

Judge's note: Crop shows superscript d. H_ij is defined via the mod-2 dot product of m-bit vectors, and d = 2^m (p.306), so the group has 2^m = d elements; GF(2)^d would have 2^d elements.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 7 Proof of Lemma 1, after eq. (5)

  plugging t = sd into (5)

• p. 7 Proof of Lemma 1, after eq. (5)

  (plugging t = sd into (5))

Only the authors can say what is right here.

Judge's note: Reworked on p.308 image: (5) reads E[e^{tdu_1}] ≤ e^{t^2 d||x||_2^2/2}. Setting t = s gives E[e^{sdu_1}] ≤ e^{s^2 d/2}, exactly the bound used in the chain; t = sd would give E[e^{sd^2u_1}] ≤ e^{s^2 d^3/2}, which is not what is used. The substitution is misstated but the chain and bound (4) hold with t = s.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 9 Proof of Lemma 2, second paragraph

  maximum at a vertex of P, namely, when u = v

• p. 9 Proof of Lemma 2, lower-bound part

  minimum when u = v

• p. 9 Proof of Lemma 2

  maximum at a vertex of P, namely, when u = v.

• p. 9 Proof of Lemma 2

  namely, when u = v.

Judge's note: Page 9 (p.310) image shows 'u = v' twice; p.309 defines u* and Z* as the extremal case, and the proof proceeds with Z*. v does not appear in Section 2. The fix is to read u = u*; the argument is otherwise unaffected.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 11 ℓ2 case, display before 'and hence'

  eλ k i=1(Zi/q+ξλ2 k i=1(Zi/q)2)

• p. 11 ℓ2 case, display after 'Therefore, by independence'

  E [eλ k i=1 y2 i ] ≤eλ k i=1(Zi/q+ξλ2 k i=1(Zi/q)2)

Only the authors can say what is right here.

Judge's note: Page 11 (p.312) image shows the printed exponent. Multiplying the per-coordinate bounds e^{λZ_i/q+ξλ^2(Z_i/q)^2} gives e^{λΣZ_i/q+ξλ^2Σ(Z_i/q)^2}; the printed form expands to λΣZ_i/q + kξλ^3Σ(Z_i/q)^2, which is not the product. Eq. (10) uses the correct form, so the stated result is unaffected.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 13 Fig. 3 pseudocode

  set l ←l + 2−t

• p. 14 Section 3.2, item 1

  lt−1 −2−t+1l1

• p. 19 Section 5, Matousek [36] sentence

  for the (ℓ1 →ℓ1) case (also affecting the ε-ANN application)

• p. 13 Fig. 3

  set Φ ←random (ℓ2 →ℓ1) FJLT matrix

Judge's note: Looked at page 13 (Fig. 3) and page 14 (Section 3.2). The pseudocode sets l ← R(P_x), and its caption says the variables p, l 'correspond to p_t, l_t in section 3.2'. The step is still the unscaled 2^{−t}. The exponent fits if the update in iteration t produces l_{t+1}, since 2^{−(t+1)+1} = 2^{−t}, so the only discrepancy is the missing scale factor l_1 = R(P_x). This cluster covers the pseudocode issue (reviewer note 1). The (ℓ1 → ℓ1) wording raised in notes 2–5 is judged under C023.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 14 Section 3.2, item 2

  pt is updated as the witness point of distance at most (1 + ε)l1

• p. 14 Section 3.2, item 2

  witness point of distance at most (1 + ε)l1

Only the authors can say what is right here.

Judge's note: The page 14 image shows the subscript 1. By item 1, success at step t−1 means a point within (1+ε)l_{t−1}. My own check: two successes give l_3 = l_1 − l_1/2 − l_1/4 = l_1/4, so the invariant needs ‖x−p_3‖ ≤ l_1/2. A bound of (1+ε)l_1 does not deliver that. The printed statement is true but cannot carry the invariant used for (12), so l_{t−1} looks intended. The stated result stands once the subscript is corrected.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send