TY - GEN

T1 - Optimal compression of approximate inner products and dimension reduction

AU - Alon, Noga

AU - Klartag, Bo'az

PY - 2017/11/10

Y1 - 2017/11/10

N2 - 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

AB - 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

KW - Gaussian correlation

KW - compression scheme

KW - dimension reduction

KW - epsilon-net

UR - http://www.scopus.com/inward/record.url?scp=85040679242&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85040679242&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2017.65

DO - 10.1109/FOCS.2017.65

M3 - Conference contribution

AN - SCOPUS:85040679242

T3 - Annual Symposium on Foundations of Computer Science - Proceedings

SP - 639

EP - 650

BT - Proceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017

PB - IEEE Computer Society

T2 - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017

Y2 - 15 October 2017 through 17 October 2017

ER -