Skip to main content

Near Linear Lower Bound for Dimension Reduction in L1

Author(s): Andoni, Alexandr; Charikar, Mosese S; Neiman, Ofer; Nguyen, Huy L

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1c80j
Full metadata record
DC FieldValueLanguage
dc.contributor.authorAndoni, Alexandr-
dc.contributor.authorCharikar, Mosese S-
dc.contributor.authorNeiman, Ofer-
dc.contributor.authorNguyen, Huy L-
dc.date.accessioned2021-10-08T19:44:42Z-
dc.date.available2021-10-08T19:44:42Z-
dc.date.issued2011en_US
dc.identifier.citationAndoni, Alexandr, Moses S. Charikar, Ofer Neiman, and Huy L. Nguyen. "Near Linear Lower Bound for Dimension Reduction in L1." 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (2011): pp. 315-323. doi:10.1109/FOCS.2011.87en_US
dc.identifier.issn0272-5428-
dc.identifier.urihttp://web.mit.edu/andoni/www/papers/dim2-focs.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1c80j-
dc.description.abstractGiven a set of n points in ℓ 1 , how many dimensions are needed to represent all pair wise distances within a specific distortion? This dimension-distortion tradeoff question is well understood for the ℓ 2 norm, where O((log n)/ϵ 2 ) dimensions suffice to achieve 1+ϵ distortion. In sharp contrast, there is a significant gap between upper and lower bounds for dimension reduction in ℓ 1 . A recent result shows that distortion 1+ϵ can be achieved with n/ϵ 2 dimensions. On the other hand, the only lower bounds known are that distortion δ requires n Ω(1/δ 2 ) dimensions and that distortion 1+ϵ requires n 1/2-O(ϵ log(1/ϵ)) dimensions. In this work, we show the first near linear lower bounds for dimension reduction in ℓ 1 . In particular, we show that 1+ϵ distortion requires at least n 1-O(1 / log(1/ϵ)) dimensions. Our proofs are combinatorial, but inspired by linear programming. In fact, our techniques lead to a simple combinatorial argument that is equivalent to the LP based proof of Brinkman-Charikar for lower bounds on dimension reduction in ℓ 1 .en_US
dc.format.extent315 - 323en_US
dc.language.isoen_USen_US
dc.relation.ispartofIEEE 52nd Annual Symposium on Foundations of Computer Scienceen_US
dc.rightsAuthor's manuscripten_US
dc.titleNear Linear Lower Bound for Dimension Reduction in L1en_US
dc.typeConference Articleen_US
dc.identifier.doi10.1109/FOCS.2011.87-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
NearLinearLowerBoundDimensionReduction.pdf287.23 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.