2026-09-10T08:21:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5908 2026-09-04T17:38:28Z ddc:004 open_access

Dimension Reduction Techniques for l_p (1<p<2), with Applications Bartal, Yair Gottlieb, Lee-Ad Dimension reduction embeddings 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yair Bartal and Lee-Ad Gottlieb 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.16 urn:nbn:de:0030-drops-59081 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.16 eng https://creativecommons.org/licenses/by/3.0/legalcode