Optimal compression of approximate inner products and dimension reduction

Noga Alon, Bo'az Klartag

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations

Abstract

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

Original languageEnglish (US)
Title of host publicationProceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017
PublisherIEEE Computer Society
Pages639-650
Number of pages12
ISBN (Electronic)9781538634646
DOIs
StatePublished - Nov 10 2017
Externally publishedYes
Event58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017 - Berkeley, United States
Duration: Oct 15 2017Oct 17 2017

Publication series

NameAnnual Symposium on Foundations of Computer Science - Proceedings
Volume2017-October
ISSN (Print)0272-5428

Other

Other58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017
CountryUnited States
CityBerkeley
Period10/15/1710/17/17

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Gaussian correlation
  • compression scheme
  • dimension reduction
  • epsilon-net

Fingerprint Dive into the research topics of 'Optimal compression of approximate inner products and dimension reduction'. Together they form a unique fingerprint.

Cite this