View Full Document

Annealing and the rate distortion problem



View the full content.
View Full Document
View Full Document

3 views

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



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Annealing and the rate distortion problem and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Annealing and the rate distortion problem and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?