A Multilinear Johnson–Lindenstrauss Transform
Loading...
Access rights
openAccess
CC BY
CC BY
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2025
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
8th SIAM Symposium on Simplicity of Algorithms, SOSA 2025, pp. 108-118
Abstract
The Johnson-Lindenstrauss family of transforms constitutes a key algorithmic tool for reducing the dimensionality of a Euclidean space with low distortion of distances. Rephrased from geometry to linear algebra, one seeks to reduce the dimension of a vector space while approximately preserving inner products. We present a multilinear generalization of this bilinear (inner product) setting that admits both an elementary randomized algorithm as well as a short proof of correctness using Orlicz quasinorms.Description
Keywords
Other note
Citation
Kaski, P, Mannila, H & Matakos, A 2025, A Multilinear Johnson–Lindenstrauss Transform . in I-O Bercea & R Pagh (eds), 8th SIAM Symposium on Simplicity of Algorithms, SOSA 2025 . Society for Industrial and Applied Mathematics, pp. 108-118, Symposium on Simplicity in Algorithms, New Orleans, Louisiana, United States, 13/01/2025 . https://doi.org/10.1137/1.9781611978315.8