Year: 2025
Author: Lingyi Chen, Shitong Wu, Wenhao Ye, Huihui Wu, Wenyi Zhang, Hao Wu, Bo Bai
CSIAM Transactions on Applied Mathematics, Vol. 6 (2025), Iss. 2 : pp. 350–379
Abstract
The Blahut-Arimoto (BA) algorithm has played a fundamental role in the numerical computation of rate-distortion (RD) functions. This algorithm possesses a desirable monotonic convergence property by alternatively minimizing its Lagrangian with a fixed multiplier. In this paper, we propose a novel modification of the BA 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 RD curve as in the original BA algorithm. Moreover, this modification presents a versatile framework, applicable to a wide range of problems, including the computation of distortion-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. Numerical experiments demonstrate that the modified algorithms exhibit significant acceleration compared with the original BA algorithms and showcase commendable performance across classical source distributions such as discretized Gaussian, Laplacian and uniform sources.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/csiam-am.SO-2024-0002
CSIAM Transactions on Applied Mathematics, Vol. 6 (2025), Iss. 2 : pp. 350–379
Published online: 2025-01
AMS Subject Headings: Global Science Press
Copyright: COPYRIGHT: © Global Science Press
Pages: 30
Keywords: Alternating minimization Blahut-Arimoto algorithm convergence analysis constrained optimization rate-distortion function.