| 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 |