Aarhus University Seal

The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearch

For any n > 1, 0 < ϵ < 1/2, and N > n C for some constant C > 0, we show the existence of an N-point subset X of ℓ 2 n such that any linear map from X to ℓ 2 m with distortion at most 1 + ϵ must have m = Ω (min{n, ϵ -2 lgN}). This improves a lower bound of Alon [Alon, Discre. Mathem., 1999], in the linear setting, by a lg(1/ϵ) factor. Our lower bound matches the upper bounds provided by the identity matrix and the Johnson-Lindenstrauss lemma [Johnson and Lindenstrauss, Contem. Mathem., 1984].

Original languageEnglish
JournalLeibniz International Proceedings in Informatics
Volume55
Pages (from-to)82:1 - 82:11
Number of pages11
ISSN1868-8969
DOIs
Publication statusPublished - 2016
EventICALP 2016 : 43RD INTERNATIONAL COLLOQUIUM ON AUTOMATA, LANGUAGES, AND PROGRAMMING - Rome, Italy
Duration: 12 Jul 201615 Jul 2016
http://www.easyconferences.eu/icalp2016/index.html

Conference

ConferenceICALP 2016
CountryItaly
CityRome
Period12/07/201615/07/2016
Internet address

    Research areas

  • Dimensionality reduction, Johnson-Lindenstrauss, Lower bounds

See relations at Aarhus University Citationformats

ID: 108067714