The Information Bottleneck is NP-hard

Given a joint distribution $P_{XY}$ on a finite alphabet, the information bottleneck method seeks a representation $T$ of $X$ that is as informative as possible about $Y$ while compressing $X$, where $T$ and $Y$ are conditionally independent given $X$. We show that computing the optimal value $\mathrm{I}\mathrm{B}(P_{XY},R)={\sup }_T\{I(Y;T):I(X;T)\le R\}$ of the information bottleneck problem, as well as its Lagrangian relaxation $L_{\beta }(P_{XY})={\sup }_T[I(Y;T)-\beta I(X;T)]$, is NP-hard. Moreover, unless $\mathrm{P}=\mathrm{N}\mathrm{P}$, neither $\mathrm{I}\mathrm{B}(P_{XY},R)$ nor $L_{\beta }(P_{XY})$ can be approximated in polynomial time within an additive error of order $\mathrm{\mid }\mathcal{X}{\mathrm{\mid }}^{-3\mathrm{/}2}$.