Annealing and the rate distortion problem

Unformatted text preview:

Annealing and the rate distortion problem Albert E Parker Department of Mathematical Sciences Montana State University Bozeman MT 59771 parker math montana edu Toma s Gedeon Department of Mathematical Sciences Montana State University gedeon 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 Deterministic Annealing Information Distortion and the Information Bottleneck Method We also introduce a numerical algorithm which uses the explicit form of the bifurcating branches to find optima at a bifurcation point 1 Introduction This paper analyzes a class of optimization problems max G q D q q 1 where is a linear constraint space G and D are continuous real valued functions of q smooth in the interior of and maxq G q is known Furthermore G and D are invariant under the group of symmetries SN The goal is to solve 1 for B 0 This type of problem which appears to be N P 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 B Algorithm 1 Let q0 be the maximizer of max G q q 2 and let 0 0 For k 0 let qk k be a solution to 1 Iterate the following steps until B for some 1 Perform step Let k 1 k dk where dk 0 0 2 Take qk 1 qk where is a small perturbation as an initial guess for the solution qk 1 at k 1 3 Optimization solve max G q k 1 D q q 0 to get the maximizer qk 1 using initial guess qk 1 We introduce methodology to efficiently perform algorithm 1 Specifically we implement numerical continuation techniques 9 10 to effect steps 1 and 2 We show how to detect bifurcation and we rely on bifurcation theory with symmetries 11 12 13 to search for the desired