TY - GEN
T1 - Optimal compression of approximate inner products and dimension reduction
AU - Alon, Noga
AU - Klartag, Bo'az
N1 - Publisher Copyright:
© 2017 IEEE.
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.
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.
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 -