A Multilinear Johnson–Lindenstrauss Transform

Simple item page
dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorKaski, Petteri
dc.contributor.authorMannila, Heikki
dc.contributor.authorMatakos, Antonis
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.editorBercea, Ioana-Oriana
dc.contributor.editorPagh, Rasmus
dc.contributor.groupauthorComputer Science Professorsen
dc.contributor.groupauthorComputer Science - Algorithms and Theoretical Computer Science (TCS) - Research areaen
dc.contributor.groupauthorHelsinki Institute for Information Technology (HIIT)en
dc.contributor.groupauthorProfessorship Kaski Petterien
dc.contributor.groupauthorProfessorship Mannila Heikkien
dc.contributor.groupauthorGionis Aris groupen
dc.date.accessioned2025-01-15T06:29:11Z
dc.date.available2025-01-15T06:29:11Z
dc.date.issued2025
dc.description.abstractThe 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.en
dc.description.versionPeer revieweden
dc.format.mimetypeapplication/pdf
dc.identifier.citationKaski, 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.8en
dc.identifier.doi10.1137/1.9781611978315.8
dc.identifier.isbn978-1-61197-831-5
dc.identifier.otherPURE UUID: 5ffcf3fd-0c83-4b1f-9f2f-bc91d31b3b15
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/5ffcf3fd-0c83-4b1f-9f2f-bc91d31b3b15
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/170552981/SCI_Kaski_etal_SOSA_2025.pdf
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/132914
dc.identifier.urnURN:NBN:fi:aalto-202501151207
dc.language.isoenen
dc.relation.fundinginfoWe thank Aristides Gionis and the anonymous reviewers for their useful comments that helped us to improve the paper.
dc.relation.ispartofSymposium on Simplicity in Algorithmsen
dc.relation.ispartofseries8th SIAM Symposium on Simplicity of Algorithms, SOSA 2025en
dc.relation.ispartofseriespp. 108-118en
dc.rightsopenAccessen
dc.rightsCC BY
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.titleA Multilinear Johnson–Lindenstrauss Transformen
dc.typeA4 Artikkeli konferenssijulkaisussafi
dc.type.versionpublishedVersion

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
SCI_Kaski_etal_SOSA_2025.pdf
Size:
722.29 KB
Format:
Adobe Portable Document Format
Download

Collections

[article-cris] Perustieteiden korkeakoulu / SCI