The Department of Mathematics & Statistics would like to welcome:
Dr. Rachel Ward on Wednesday, April 22 at 11:00am in SCP 229.
Title: Geometric Clustering: Efficient Algorithm and Guaranteed Optimality
Abstract: k-means clustering aims to partition a set of n points into k clusters in such a way that each observation belongs to the cluster with the nearest mean, and such that the sum of squared distances from each point to its nearest mean is minimal. In general, this is a hard optimization problem, requiring an exhaustive search over all possible partitions of the data into k clusters in order to find the optimal clustering. At the same time, fast heuristic algorithms for the k-means optimization problem are often applied in many data processing applications, despite having few guarantees on the clusters they produce. In this talk, we will introduce an efficient algorithm for solving the k-means optimization problem, along with geometric conditions on a set of data such that the algorithm is guaranteed to find the optimal k-means clustering for the data. For points drawn from separated balls, the important quantities are the distances between the centers of the balls compa
red to the relative densities of points within them. We will also discuss connections to spectral clustering and the question of partitioning data arising from nonlinear shapes such as concentric circles. We will conclude by discussing several open questions related to this work. This is joint work with P. Awasthi, A. Bandeira, M. Charikar, R. Krishnaswamy, and S. Villar.
Dr. Rachel Ward received her PhD at Princeton University’s Program of Applied and Computational Mathematics. She is currently an assistant professor at The University of Texas at Austin. Before joining UT Austin, Dr. Ward was an NSF Postdoctoral Fellow at Courant Institute, New York University. Her research interests include mathematical signal processing, applied harmonic analysis, compressed sensing, theoretical computer science, and machine learning. Dr. Ward is the recipient of several prestigous awards including Barry M. Goldwater, NSF Graduate Fellowship, Alfred P. Sloan Fellowship, and an NSF Career Award to name a few.