nucleation

LIT-1151: Optimal compression of approximate inner products and dimension reduction

3 min read

Properties6
StatusActive — read 2026-10-16 (NOTE-929) in full; worth reading as the paper that turns the Johnson–Lindenstrauss lower bound into a bit count, determining how many bits it takes to store every inner product of n points of the unit ball to additive ε, and so extending Larsen and Nelson's dimension lower bound to every ε ≥ 2/√n with log(2 + ε²n)/ε² in place of log n/ε². Read it knowing that its dimension statements are for additive error on squared distances, the relative form being stated only for ε ≥ 1/n^0.49; that the step from bits to dimension is a short remark; that constants are unstated; and that its small-ε upper bound is bipartite, keeps only cross inner products and does not bound norms, so the one-set JL lemma at log(2 + ε²n)/ε² stays open. Filed as THEORY-399 and THEORY-393.
Version2
Tagsmathematics, information-theory
ExtendsLIT-1154 — Optimality of the Johnson-Lindenstrauss Lemma
Cited as “paper” byNOTE-929 — Alon & Klartag — optimal compression of approximate inner products
Cited as “source” byTHEORY-393 — Any two families of n vectors of norm at most 1 have images in ⌊C log(2 + ε²n)/ε²⌋ dimensions whose cross inner products ⟨x_i, y_j⟩ are each within an additive ε of the originals, found by a randomized polynomial-time algorithm, which for small ε is below the log n/ε² of the Johnson–Lindenstrauss lemma; only cross products are kept, the new vectors' norms are not bounded, and whether one set can be embedded that small is open, THEORY-399 — Storing every inner product of n points of the unit ball of R^k to additive error ε takes Θ(n log n/ε²) bits once k ≥ log n/ε² and Θ(nk log(2 + log n/(ε²k))) below, for 1/n^0.49 ≤ ε ≤ 0.1, and comparing these counts across dimensions shows that some n such points cannot be mapped into fewer than Ω(min{k, log(2 + ε²n)/ε²}) dimensions with additive error ε for every ε ≥ 2/√n; this is a worst-case lower bound with unstated constants, the small-ε bit count is open for k above that dimension, and no one-family embedding that small is proved

Graph View

Noga Alon and Bo’az Klartag (2017), “Optimal compression of approximate inner products and dimension reduction”, FOCS 2017: 639–650 — ARXIV-1610.00239

Key takeaways

From the reading, NOTE-929.

  • Bits (Theorem 1.1). For 1/n^0.49 ≤ ε ≤ 0.1, an additive ε-sketch of n points of the unit ball of R^k needs Θ(n log n/ε²) bits for k ≥ log n/ε², Θ(nk log(2 + log n/(ε²k))) for log n ≤ k ≤ log n/ε², and Θ(nk log(1/ε)) for k ≤ log n. Upper bound by a volume count of ε-separated Gram matrices; lower bound by n/2 random probes against n/2 net points.
  • An efficient sketch (Theorem 4.1). JL into 40 log n/ε² dimensions, then unbiased randomized rounding, O(1) bits per coordinate, with norms stored apart.
  • Dimension (Corollaries 2.1, 2.3). For every ε ≥ 2/√n, some n points in R^k cannot be mapped into ℓ ≤ ck dimensions with additive error ε on squared distances unless ℓ = Ω(log(2 + ε²n)/ε²). For ε ≥ 1/n^0.49 this is Larsen and Nelson’s bound, also stated for relative error.
  • Small ε (Theorem 2.2). The count is Θ(nk log(2 + t/k)) for k ≤ t = log(2 + ε²n)/ε²; above t only Ω(nt) to O(n log n/ε²) is known. The union bound is replaced by the Gaussian correlation inequality.
  • Bipartite JL (Theorem 1.2). Two families of n vectors of norm at most 1 have images in ⌊C log(2 + ε²n)/ε²⌋ dimensions with every ⟨x_i, y_j⟩ within ε, by a randomized polynomial algorithm. Norms are not bounded; bounding them is Conjecture 2.4, proved only for t of order n (Theorem 2.5).
  • Scope. Additive error, worst-case sets, unstated constants; the relative-error sketch problem keeps a log gap.

Standing in the record

Filed on 2026-10-16 as later work flagged by NOTE-925, and read the same day in NOTE-929. The registration said the paper proves the lower bound of Larsen and Nelson’s Conjecture 1 “for all parameters”. The reading qualifies that. The paper proves it for every ε ≥ 2/√n, smaller ε being the trivial case, in additive form on squared distances of points of norm at most 1, with the step from bits to dimension given as a short remark. The relative form follows for small ε but is not stated. The upper half of the conjecture is proved only in a bipartite form without norm bounds, so the one-set JL lemma at log(2 + ε²n)/ε² is still open.

For QUESTION-120 it extends THEORY-395’s lower bound to the whole range of ε, filed as THEORY-399, and gives the bipartite upper bound, filed as THEORY-393. On the distances thread its count is the log of a family’s size, but for small ε that log is of 2 + ε²n, not of the n² pairs a union bound counts. On superposition it says nothing directly. information-theory is for its question, the bits needed to store approximate inner products. It carries no instruction for machine-learning practice.

Backlinks