Blahut–Arimoto algorithm

From formulasearchengine
Jump to navigation Jump to search


The Blahut–Arimoto algorithm, co-invented by Richard Blahut, is an elegant iterative technique for numerically obtaining rate–distortion functions of arbitrary finite input/output alphabet sources. Much work has been done to extend it to more general problem instances.[1][2]


Suppose we have a source with probability of any given symbol. We wish to find an encoding that generates a compressed signal from the original signal while minimizing the expected distortion , where the expectation is taken over the joint probability of and . We can find an encoding that minimizes the rate-distortion functional locally by repeating the following iteration until convergence:

where is an inverse temperature parameter that controls how much we favor compression versus distortion (higher means less compression). It should be noted that the above algorithm only converges locally to an optimal point on the rate-distortion curve. Finding the global optimum is a computationally hard problem.