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

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

34 Downloads (Pure)

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.

Original language	English
Title of host publication	8th SIAM Symposium on Simplicity of Algorithms, SOSA 2025
Editors	Ioana-Oriana Bercea, Rasmus Pagh
Publisher	Society for Industrial and Applied Mathematics
Pages	108-118
ISBN (Electronic)	978-1-61197-831-5
DOIs	https://doi.org/10.1137/1.9781611978315.8
Publication status	Published - 2025
MoE publication type	A4 Conference publication
Event	Symposium on Simplicity in Algorithms - New Orleans, United States Duration: 13 Jan 2025 → 15 Jan 2025 Conference number: 8

Conference

Conference	Symposium on Simplicity in Algorithms
Abbreviated title	SOSA
Country/Territory	United States
City	New Orleans
Period	13/01/2025 → 15/01/2025

Access to Document

10.1137/1.9781611978315.8

SCI_Kaski_etal_SOSA_2025Final published version, 400 KBLicence: CC BY

Cite this

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

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

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

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 - http://www.scopus.com/inward/record.url?scp=85217043692&partnerID=8YFLogxK

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

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this