Computing Rate-Distortion Functions of Continuous Memoryless Sources via Discrete Algorithms: An Integrated Scheme...

Numerical computation of the rate-distortion (RD) function is a key problem in RD theory. Thus far, efficient algorithms have been well studied for discrete sources, but for continuous sources, there is still lack of a rigorously developed solution. In this article, an integrated approach is conducted that bridges RD problems of continuous memoryless sources and discrete numerical algorithms. First, we analyze and establish the theoretical convergence guarantee when progressively approaching the continuous RD problem via a sequence of discrete problems. Next, discrete algorithms including the Blahut-Arimoto (BA) and constrained BA algorithms are reviewed, and estimates of their required amount of arithmetic operations to attain ε-accuracy in solving the continuous RD problem are derived. Finally, acceleration techniques that exploit structures of special distortion measures (i.e., squared-error and absolute-error) are developed.