# A Constrained BA Algorithm for Rate-Distortion and Distortion-Rate Functions

arXiv: https://arxiv.org/abs/2305.02650 · HTML: https://mlsanity.com/paper/2305.02650/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 34 references that are in the map.
- First posted on arXiv 4 May 2023.

## Builds on (most cited first, 4 of 4)

- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [End-to-end Optimized Image Compression](https://mlsanity.com/paper/1611.01704/) (2016)
- [Neonatal Bowel Sound Detection Using Convolutional Neural Network and Laplace Hidden Semi-Markov Model](https://mlsanity.com/paper/2108.07467/) (2021)
- [The Double Regularization Method for Capacity Constrained Optimal Transport](https://mlsanity.com/paper/2212.00354/) (2022)

## Built on by (most cited first, 1 of 1)

- [Forget BIT, It is All about TOKEN: Towards Semantic Information Theory for LLMs](https://mlsanity.com/paper/2511.01202/) (2025)

## Abstract (arXiv)

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 O(1/n), where n is the number of iterations. Additionally, these algorithms provide varepsilon-approximation solutions with Oleft(fracMNlog Nvarepsilon(1+log |log varepsilon|)right) 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.