Performance of Johnson--Lindenstrauss Transform for k-Means and k-Medians Clustering

DOI10.1137/20M1330701MaRDI QIDQ5067443zbMATH OpenOpenAlexFDO

Authors Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn

Publication date 1 April 2022

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/20m1330701

zbMATH Keywords

\(k\)-meansclusteringdimension reduction

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Metric embeddings as related to computational problems and algorithms (68R12) Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• Performance of Johnson-Lindenstrauss transform for \(k\)-means and \(k\)-medians clustering
• \(k\)-median clustering under discrete Fréchet and Hausdorff distances
• Near-optimal large-scale k-medoids clustering
• On coresets for k-means and k-median clustering
• A new clustering preserving transformation for \(k\)-means algorithm output
• On variants of k-means clustering
• K-medoids clustering algorithm based on distance inequality

Cites work

• A sparse Johnson-Lindenstrauss transform
• Adaptive estimation of a quadratic functional by model selection.
• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
• An elementary proof of a theorem of Johnson and Lindenstrauss
• An improved approximation algorithm for the column subset selection problem
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Deterministic Feature Selection for K-Means Clustering
• Dimensionality reduction for k-means clustering and low rank approximation
• Empirical processes and random projections
• Extensions of Lipschitz mappings into a Hilbert space
• Fast dimension reduction using Rademacher series on dual BCH codes
• High-dimensional probability. An introduction with applications in data science
• scientific article; zbMATH DE number 1305418 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• Least squares quantization in PCM
• Metric dimension reduction: a snapshot of the Ribe program
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• New constructions of RIP matrices with fast multiplication and fewer rows
• Oblivious dimension reduction for \(k\)-means: beyond subspaces and the Johnson-Lindenstrauss lemma
• On general minimax theorems
• Optimal Approximate Matrix Product in Terms of Stable Rank
• Probability in Banach spaces. Isoperimetry and processes
• Problems and results in extremal combinatorics. I.
• Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
• Sparser Johnson-Lindenstrauss transforms
• Turning big data into tiny data: constant-size coresets for k-means, PCA and projective clustering

Cited in

(6)

• Dimensionality reduction for k-means clustering and low rank approximation
• Polynomial-time approximation schemes for geometric min-sum median clustering
• On the Performance of Clustering in Hilbert Spaces
• Performance of Johnson-Lindenstrauss transform for \(k\)-means and \(k\)-medians clustering
• Oblivious dimension reduction for \(k\)-means: beyond subspaces and the Johnson-Lindenstrauss lemma
• Randomly projected convex clustering model: motivation, realization, and cluster recovery guarantees

This page was built for publication: Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5067443)