Analyzing brain signals by combinatorial optimization

Justin Dauwels, François Vialatte, Theophane Weber, Andrzej Cichocki

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


We present a new method to determine the similarity (or synchrony) of a collection of multi-dimensional signals. The signals are first converted into point processes, where each event of a point process corresponds to a burst of activity of the corresponding signal in an appropriate feature space. The similarity of signals is then computed by adaptively aligning the events from the different point processes. If the point processes are similar, clusters containing one point from each time serie will naturally appear. Synchrony is then measured as a function of the size of the clusters and the distance between points within one cluster. The alignment of events is defined in a natural statistical model; the optimal clustering is obtained through maximum a posteriori inference and can be cast as a combinatorial optimization problem. As the dimension and the number of signals increase, so does the complexity of the inference task. In particular, the inference task corresponds to: a) a dynamic program when comparing two 1-dimensional signals b) A maximum weighted matching on a bipartite graph when comparing two d-dimensional signals c) A NP-hard integer program that can be reduced to N-dimensional matching when comparing N ≥ 2 signals We show the applicability of the method by predicting the onset of Mild Cognitive Impairment (MCI) from EEG signals.

Original languageEnglish
Title of host publication46th Annual Allerton Conference on Communication, Control, and Computing
Number of pages8
Publication statusPublished - 2008
Externally publishedYes
Event46th Annual Allerton Conference on Communication, Control, and Computing - Monticello, IL, United States
Duration: 24 Sep 200826 Sep 2008

Publication series

Name46th Annual Allerton Conference on Communication, Control, and Computing


Conference46th Annual Allerton Conference on Communication, Control, and Computing
Country/TerritoryUnited States
CityMonticello, IL


Dive into the research topics of 'Analyzing brain signals by combinatorial optimization'. Together they form a unique fingerprint.

Cite this