  In rate-distortion (RD) problems one seeks reduced representations of a
source that meet a target distortion constraint. Such optimal representations
undergo topological transitions at some critical rate values, when their
cardinality or dimensionality change. We study the convergence time of the
Arimoto-Blahut alternating projection algorithms, used to solve such problems,
near those critical points, both for the rate-distortion and information
bottleneck settings. We argue that they suffer from critical slowing down -- a
diverging number of iterations for convergence -- near the critical points.
This phenomenon can have theoretical and practical implications for both
machine learning and data compression problems.
