• If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!


Scribe Note 7-1

This version was saved 12 years, 7 months ago View current version     Page history
Saved by lt010@...
on December 9, 2011 at 3:24:12 pm


a)We have defined the information rate distortion function as 



where the minimization is over all conditional distributions  Formula  for which the joint distribution Formula  satisfies the expected distortion constraint. This is a standard minimization problem of a convex function over the convex set of all Formula satisfying Formula for all Formula and Formula

We can use the method of Lagrange multipliers to find the solution.  We set up the functional

Differentiating with respect to Formula , setting Formula, we obtain

Since Formula , we must have Formula  or

for all Formula. We can combine these Formula equations with the equation defining the distortion and calculate λ and the  Formula unknowns Formula. We can  find the optimum conditional distribution.

The above analysis is valid if  Formula  is unconstrained. The inequality condition Formula is covered by the Kuhn–Tucker conditions, which reduce to

Substituting the value of the derivative, we obtain the conditions for the minimum as

This characterization will enable us to check if a given Formula is a solution to the minimization problem. However, it is not easy to solve for the optimum output distribution from these equations. In the next section we provide an iterative algorithm for computing the rate distortion function. This algorithm is a special case of a general algorithm for finding the minimum relative entropy distance between two convex sets of probability densities.




Comments (0)

You don't have permission to comment on this page.