DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2016.16

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

Authors: Yair Bartal and Lee-Ad Gottlieb

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract

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.

Cite as

Yair Bartal and Lee-Ad Gottlieb. Dimension Reduction Techniques for l_p (1<p<2), with Applications. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bartal_et_al:LIPIcs.SoCG.2016.16,
  author =	{Bartal, Yair and Gottlieb, Lee-Ad},
  title =	{{Dimension Reduction Techniques for l\underlinep (1\langlep\langle2), with Applications}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.16},
  URN =		{urn:nbn:de:0030-drops-59081},
  doi =		{10.4230/LIPIcs.SoCG.2016.16},
  annote =	{Keywords: Dimension reduction, embeddings}
}

Search Results

Documents authored by Gottlieb, Lee-Ad

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

Abstract

Cite as

Thanks for your feedback!

Could not send message