APPLIED MATH SEMINAR
Abstract:
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 fields and a QBO-based Sudoku solver.
Joint work with Michael Chertok and Amir Egozi