AnnealingandtheRateDistortionProblem-NIPS.PDFVIP

Annealing and the Rate Distortion Problem ´ˇ Albert E. Parker Tomas Gedeon Department of Mathematical Sciences Department of Mathematical Sciences Montana State University Montana State University Bozeman, MT 59771 gedeon@math.montana.edu parker@math.montana.edu Alexander G. Dimitrov Center for Computational Biology Montana State University alex@nervana.montana.edu Abstract In this paper we introduce methodology to determine the bifurcation structure of optima for a class of similar cost functions from Rate Distortion Theory, Determin- istic Annealing, Information Distortion and the Information Bottleneck Method. We also introduce a numerical algorithm which uses the explicit form of the bifur- cating branches to find optima at a bifurcation point. 1 Introduction This paper analyzes a class of optimization problems (1) where is a linear constraint space, and are continuous, real valued functions of , smooth in the interior of , and is known. Furthermore, and are invariant under the group of symmetries . The goal is to solve (1) for . This type of problem, which appears to be hard, arises in Rate Distortion Theory [1, 2], Deterministic Annealing [3], Information Distortion [4, 5, 6] and the Information Bottleneck Method [7, 8]. The following basic algorithm, various forms of which have appeared in [3, 4, 6, 7, 8], can be used to solve (1) for . Algorithm 1 Let be the maximizer of