Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Bartal, Yair; Gottlieb, Lee-Ad License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-59081


Dimension Reduction Techniques for l_p (1<p<2), with Applications



For Euclidean space (l_2), there exists the powerful dimension reduction transform of Johnson and Lindenstrauss [Conf. in modern analysis and probability, AMS 1984], with a host of known applications. Here, we consider the problem of dimension reduction for all l_p spaces 1<p<2. Although strong lower bounds are known for dimension reduction in l_1, Ostrovsky and Rabani [JACM 2002] successfully circumvented these by presenting an l_1 embedding that maintains fidelity in only a bounded distance range, with applications to clustering and nearest neighbor search. However, their embedding techniques are specific to l_1 and do not naturally extend to other norms. In this paper, we apply a range of advanced techniques and produce bounded range dimension reduction embeddings for all of 1<p<2, thereby demonstrating that the approach initiated by Ostrovsky and Rabani for l_1 can be extended to a much more general framework. We also obtain improved bounds in terms of the intrinsic dimensionality. As a result we achieve improved bounds for proximity problems including snowflake embeddings and clustering.

BibTeX - Entry

  author =	{Yair Bartal and Lee-Ad Gottlieb},
  title =	{{Dimension Reduction Techniques for l_p (1

Keywords: Dimension reduction, embeddings
Seminar: 32nd International Symposium on Computational Geometry (SoCG 2016)
Issue date: 2016
Date of publication: 2016

DROPS-Home | Fulltext Search | Imprint Published by LZI