A Multilinear Johnson–Lindenstrauss Transform

Petteri Kaski; Heikki Mannila; Antonis Matakos

doi:10.1137/1.9781611978315.8

A Multilinear Johnson–Lindenstrauss Transform

Petteri Kaski
, Heikki Mannila
, Antonis Matakos

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference article in proceedings › Scientific › vertaisarvioitu

1 Sitaatiot (Scopus)

180 Lataukset (Pure)

Abstrakti

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.

Alkuperäiskieli	Englanti
Otsikko	8th SIAM Symposium on Simplicity of Algorithms, SOSA 2025
Toimittajat	Ioana-Oriana Bercea, Rasmus Pagh
Kustantaja	Society for Industrial and Applied Mathematics
Sivut	108-118
ISBN (elektroninen)	978-1-61197-831-5
DOI - pysyväislinkit	https://doi.org/10.1137/1.9781611978315.8
Tila	Julkaistu - 2025
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisussa
Tapahtuma	Symposium on Simplicity in Algorithms - New Orleans, Yhdysvallat Kesto: 13 tammik. 2025 → 15 tammik. 2025 Konferenssinumero: 8

Conference

Conference	Symposium on Simplicity in Algorithms
Lyhennettä	SOSA
Maa/Alue	Yhdysvallat
Kaupunki	New Orleans
Ajanjakso	13/01/2025 → 15/01/2025

Rahoitus

We thank Aristides Gionis and the anonymous reviewers for their useful comments that helped us to improve the paper.

Pääsy asiakirjaan

10.1137/1.9781611978315.8

SCI_Kaski_etal_SOSA_2025Final published version, 400 KBLisenssi: CC BY

Muut tiedostot ja linkit

Linkki julkaisuun Scopuksessa

Siteeraa tätä

@inproceedings{5ffcf3fd0c834b1f9f2fbc91d31b3b15,

title = "A Multilinear Johnson–Lindenstrauss Transform",

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.",

author = "Petteri Kaski and Heikki Mannila and Antonis Matakos",

year = "2025",

doi = "10.1137/1.9781611978315.8",

language = "English",

pages = "108--118",

editor = "Ioana-Oriana Bercea and Rasmus Pagh",

booktitle = "8th SIAM Symposium on Simplicity of Algorithms, SOSA 2025",

publisher = "Society for Industrial and Applied Mathematics",

address = "United States",

note = "Symposium on Simplicity in Algorithms, SOSA ; Conference date: 13-01-2025 Through 15-01-2025",

}

Kaski, P , Mannila, H & Matakos, A 2025, A Multilinear Johnson–Lindenstrauss Transform. julkaisussa I-O Bercea & R Pagh (toim), 8th SIAM Symposium on Simplicity of Algorithms, SOSA 2025. Society for Industrial and Applied Mathematics, Sivut 108-118, Symposium on Simplicity in Algorithms, New Orleans, Louisiana, Yhdysvallat, 13/01/2025. https://doi.org/10.1137/1.9781611978315.8

A Multilinear Johnson–Lindenstrauss Transform. / Kaski, Petteri ; Mannila, Heikki; Matakos, Antonis.
8th SIAM Symposium on Simplicity of Algorithms, SOSA 2025. toim. / Ioana-Oriana Bercea; Rasmus Pagh. Society for Industrial and Applied Mathematics, 2025. s. 108-118.

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference article in proceedings › Scientific › vertaisarvioitu

TY - GEN

T1 - A Multilinear Johnson–Lindenstrauss Transform

AU - Kaski, Petteri

AU - Mannila, Heikki

AU - Matakos, Antonis

N1 - Conference code: 8

PY - 2025

Y1 - 2025

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85217043692

U2 - 10.1137/1.9781611978315.8

DO - 10.1137/1.9781611978315.8

M3 - Conference article in proceedings

SP - 108

EP - 118

BT - 8th SIAM Symposium on Simplicity of Algorithms, SOSA 2025

A2 - Bercea, Ioana-Oriana

A2 - Pagh, Rasmus

PB - Society for Industrial and Applied Mathematics

T2 - Symposium on Simplicity in Algorithms

Y2 - 13 January 2025 through 15 January 2025

ER -

A Multilinear Johnson–Lindenstrauss Transform

Abstrakti

Conference

Rahoitus

Pääsy asiakirjaan

Muut tiedostot ja linkit

Sormenjälki

Siteeraa tätä