UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Spectral graph matching

PDE and Applied Math Seminar

Speaker: Dr. Yosi Keller, Bar Ilan University (Israel)
Location: 1147 MSB
Start time: Thu, Sep 25 2008, 11:00AM

The representation and analysis of data by graphs is ubiquitous nowadays, as a myriad of graph based approaches were shown to provide efficient means to various data analysis problems, such as dimensionality reduction and classification, to name a few. In this talk we suggest to cast the graph matching problem as quadratic binary optimization (QBO), which can be efficiently solved by way of spectral relaxation. Our first goal is the alignment of point sets in R^n, and apply it to ensemble matching for speech recognition and shape matching and recognition. We then consider the symmetric case, and its spectral properties, paving the way to novel symmetry detection and analysis scheme. Last, we show how to apply the QBO to the optimization of state machines. For that we present numerical schemes for the solution of least squares over finite groups and apply them to the decoding of MIMO channels. Joint work with Michael Chertok, Amir Egozi and Amit Leshem