Optimal Compression of Approximate Inner Products and Dimension Reduction

Let X be a set of n points of norm at most 1 in the Euclidean space R^k, and suppose ≥0. An ≥-distance sketch for X is a data structure that, given any two points of X enables one to recover the square of the (Euclidean) distance between them up to an additive} error of ≥. Let f(n,k,≥) denote the minimum possible number of bits of such a sketch. Here we determine f(n,k,≥) up to a constant factor for all n ≥ k ≥ 1 and all ≥ ≥ \frac{1}{n^{0.49}}. Our proof is algorithmic, and provides an efficient algorithm for computing a sketch of size O(f(n,k,≥)/n) for each point, so that the square of the distance between any two points can be computed from their sketches up to an additive error of ≥ in time linear in the length of the sketches. We also discuss the case of smaller ≥2/√ n and obtain some new results about dimension reduction in this range. In particular, we show that for any such ≥ and any k ≤ t=\frac{\log (2+≥^2 n)}{≥^2} there are configurations of n points in R^k that cannot be embedded in R^{ℓ} for ℓ