K-Means and K-Medians Under Dimension Reduction

Explore the intricacies of k-means and k-medians clustering algorithms under dimension reduction in this 42-minute lecture by Yury Makarychev from Toyota Technological Institute at Chicago. Delve into the Euclidean k-means and k-medians concepts, examining their behavior under dimension reduction. Investigate the challenges, warm-up exercises, and problem notation associated with these clustering techniques. Analyze the distortion graph, cost of clusters, and the concept of everywhere-sparse edges. Understand the (1-0) non-distorted core and the importance of large clusters. Examine the main combinatorial lemma and edges incident on outliers. Gain valuable insights into robust and high-dimensional statistics through this comprehensive talk presented at the Simons Institute.