Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Conference article › Research
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 language | English |
---|---|
Journal | Leibniz International Proceedings in Informatics |
Volume | 55 |
Pages (from-to) | 82:1 - 82:11 |
Number of pages | 11 |
ISSN | 1868-8969 |
DOIs | |
Publication status | Published - 2016 |
Event | ICALP 2016 : 43RD INTERNATIONAL COLLOQUIUM ON AUTOMATA, LANGUAGES, AND PROGRAMMING - Rome, Italy Duration: 12 Jul 2016 → 15 Jul 2016 http://www.easyconferences.eu/icalp2016/index.html |
Conference | ICALP 2016 |
---|---|
Country | Italy |
City | Rome |
Period | 12/07/2016 → 15/07/2016 |
Internet address |
See relations at Aarhus University Citationformats
ID: 108067714