k-means and k-medians under Dimension Reduction
Talkat Robust and High-Dimensional Statistics (Simons Institute workshop, 2018) · 2018-10-29..11-02·
summary
Shows that projecting by a random orthogonal or Gaussian map to dimension about d = Θ((log K)/ε^2) preserves the cost of every k‑means clustering up to 1+ε (and gives a similar bound for k‑medians with an extra ε loss), matching the Ω(log K/ε^2) lower bound up to that ε. Key tools are Johnson–Lindenstrauss style maps, a distortion graph analysis that routes distorted pairwise terms, removing a small random set of outliers via a combinatorial measure lemma, and a robust Kirszbraun extension to handle k‑medians.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:37Euclidean k-means and k-medians
- 4:44k-means under dimension reduction
- 9:13k-medians under dimension reduction
- 10:35Plan
- 12:09Out result for k-means
- 14:42Challenges
- 16:10Warm-up
- 19:38Problem & Notation
- 21:08Distortion graph
- 23:23Cost of a cluster
- 24:52Everywhere-sparse edges
- 29:56(1-0) non-distorted core
- 31:25All clusters are large
- 34:14Main Combinatorial lemma
- 35:43Edges Incident on Outliers
- 39:55Summary
related talks
01h 00mStreaming Euclidean k-median and k-means with o(log n) Space
01h 34mAlgorithmic High-Dimensional Geometry I
28mCertified Sub-Linear Lower Bounds for K-Means Clustering
01h 07mRecent Progress in High-Dimensional Learning
44mConcentration Inequalites in Learning with Kernels
01h 02mTheory and Big Data
01h 00mAlgorithmic High Dimensional Robust Statistics I
40mMonte Carlo Approximation Certificates for K-Means Clustering