Rate-Distortion in Non-Convex Families

Iterative constrained optimization often requires convexity conditions about the argument set in order to converge to the global optimum. One such instant is the parametric version of the Blahut algorithm for rate-distortion function computation. However, there are many interesting cases for which the parametric set is not convex, e.g a discrete reproduction alphabet at unknown (parametric) locations for a continuous source. In this paper we show examples of non-convex families for which the parametric Blahut algorithm does not converge to the global optimum, and suggest a combined parametric Blahut and random annealing (A) method to overcome this problem.