|WEDNESDAY Nov. 28 :|| COLLOQUIUM |
|Title:||Clique and Cluster Identification Using Convex Optimization|
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|