Aarhus Universitets segl

English

Du er her: AU » Om AU » Organisation » Barriers for Faster Dimensionality Reduction

Om AU

Barriers for Faster Dimensionality Reduction

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

DOI

The Johnson-Lindenstrauss transform allows one to embed a dataset of n points in Rd into Rm, while preserving the pairwise distance between any pair of points up to a factor (1 ± ε), provided that m = Ω(ε−2 lg n). The transform has found an overwhelming number of algorithmic applications, allowing to speed up algorithms and reducing memory consumption at the price of a small loss in accuracy. A central line of research on such transforms, focus on developing fast embedding algorithms, with the classic example being the Fast JL transform by Ailon and Chazelle. All known such algorithms have an embedding time of Ω(d lg d), but no lower bounds rule out a clean O(d) embedding time. In this work, we establish the first non-trivial lower bounds (of magnitude Ω(m lg m)) for a large class of embedding algorithms, including in particular most known upper bounds.

OriginalsprogEngelsk
Titel40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023
RedaktørerPetra Berenbrink, Patricia Bouyer, Anuj Dawar, Mamadou Moustapha Kante
Antal sider15
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Udgivelsesårmar. 2023
Artikelnummer31
ISBN (Elektronisk)9783959772662
DOI
StatusUdgivet - mar. 2023
Begivenhed40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023 - Hamburg, Tyskland
Varighed: 7 mar. 2023 → 9 mar. 2023

Konference

Konference40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023
LandTyskland
ByHamburg
Periode07/03/2023 → 09/03/2023
SerietitelLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind254
ISSN1868-8969

Bibliografisk note

Funding Information:
Funding Ora Nova Fandina: Independent Research Fund Denmark (DFF) Sapere Aude Research Leader grant No 9064-00068B. Mikael Møller Høgsgaard: Independent Research Fund Denmark (DFF) Sapere Aude Research Leader grant No 9064-00068B. Kasper Green Larsen: Independent Research Fund Denmark (DFF) Sapere Aude Research Leader grant No 9064-00068B.

Publisher Copyright:
© Ora Nova Fandina, Mikael Møller Høgsgaard, and Kasper Green Larsen.

Se relationer på Aarhus Universitet Citationsformater

ID: 322540097