Ragesh Jaiswal (Theory Seminar)

"D^2-Sampling and k-Means Clustering" 
Ragesh Jaiswal (IIT Delhi)
Wednesday, January 22, 2020, 4:00pm
EBU3B, Room 4258

Abstract:The k-means/median problem is to find good representative points (called centers) for a given set of points X in R^d. The D^2-sampling technique is to iteratively pick points from X as centres, where the probability of picking a point as a centre in an iteration is proportional to the (squared) Euclidean distance of the point from the closest centre chosen in one of the earlier iterations. In this talk, we will discuss the effectiveness of the D^2-sampling technique in the context of k-means/median problem.