November 28, 2012
Mathematics Colloquium today
At 2:30 p.m. today, Brendan Ames from the Institute for Mathematics and Its Applications will present "Clique and Cluster Identification Using Convex Optimization" in 122 Cardwell Hall.
Identifying clusters of similar objects in data plays a significant role in a wide range of applications such as information retrieval, pattern recognition, computational biology and image processing. A classical approach to clustering is to model a given data set as a graph whose nodes correspond to items in the data and edges indicate similarity between the corresponding endpoints and try to decompose the graph into dense subgraphs. Unfortunately, finding such a decomposition usually requires solving an intractable combinatorial optimization problem.
In this talk, Ames will discuss a convex relaxation approach to identifying these dense subgraphs with surprising recovery properties: if the data is randomly sampled from a distribution of "clusterable" data, then the correct partition of the data into clusters can be exactly recovered from the optimal solution of our convex relaxation with high probability.