Algorithms for optimization over noisy data

Claire Mathieu , Researcher at Brown University, Providence, RI, U.S.A

To deal with NP-hard reconstruction problems, one natural possibility consists in assuming that the input data is a noisy version of some unknown ground truth. We present two such examples: correlation clustering, and transitive tournaments. In correlation clustering, the goal is to partition data given pairwise similarity and dissimilarity information, and sometimes semi-definite programming can, with high probability, reconstruct the optimal (maximum likelihood) underlying clustering...

Published on : Friday 24 October 2014