A Constrained BA Algorithm for Rate-Distortion and Distortion-Rate Functions (CSIAM Transactions on Applied Mathematics, 2025)
The Blahut-Arimoto (BA) algorithm has played a fundamental role in thenumerical computation of rate-distortion (RD) functions. This algorithm possessesa desirable monotonic convergence property by alternatively minimizing its Lagrangian with a fixed multiplier. In this paper, we propose a novel modification of theBA algorithm, wherein the multiplier is updated through a one-dimensional root-finding step using a monotonic univariate function, efficiently implemented by Newton’s method in each iteration. Consequently, the modified algorithm directly computes the RD function for a given target distortion, without exploring the entire RDcurve as in the original BA algorithm. Moreover, this modification presents a versatile framework, applicable to a wide range of problems, including the computation ofdistortion-rate (DR) functions. Theoretical analysis shows that the outputs of the modified algorithms still converge to the solutions of the RD and DR functions with rate $\mathcal{O}(1/n),$ where $n$ is the number of iterations. Additionally, these algorithms provide $ε$-approximation solutions with $\mathcal{O}((MN{\rm {\rm log}}N/ε)(1+{\rm log}|{\rm log}ε|))$ arithmetic operations,where $M,$ $N$ are the sizes of source and reproduced alphabets respectively. Numericalexperiments demonstrate that the modified algorithms exhibit significant accelerationcompared with the original BA algorithms and showcase commendable performanceacross classical source distributions such as discretized Gaussian, Laplacian and uniform sources.