Events Calendar - Viewing Details

Events Calendar - Viewing Details

WEDNESDAY Nov. 28 : COLLOQUIUM
Title: Clique and Cluster Identification Using Convex Optimization
Brendan Ames
Institute for Mathematics and Its Applications

Abstract: 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, I 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.
Time and Place: 2:30 PM CW 122