Funding: NWO Physical Sciences, Free Competition
Running Period: 2011-2015
Staff: Bodo Manthey
Ph.D. student: Kamiel Cornelissen
Abstract
Belief propagation is a heuristic approach for solving large-scale statistical inference problems. It is an easy-to-implement heuristic has become very popular in a wide range of applications.
Its success in practice, however, is at sharp contrast to the lack of theoretical understanding of its performance. To provide a more realistic analysis of algorithms, the concept of smoothed analysis has been developed. In smoothed analysis, performance is not measured in terms of worst-case instances. Instead, an adversary specifies an instance, and then the expected performance is measured when this instance is slightly randomly perturbed. Smoothed analysis takes into account that practical data is often noisy, e.g., due to measurement errors.
The aim of this project is smoothed analysis of belief propagation. The goal is to get a deeper understanding of its performance and to bridge the gap between theoretical and practical performance of belief propagation.
The project has meanwhile been finished, and PhD student Kamiel Cornelissen has defended his PhD thesis.