rdot

Rate Distortion Optimization Tools

Introduction

RDOT (Rate Distortion Optimization Tools) is a software library that aims to provide efficient, unified tools for numerically computing rate distortion functions from data.

For low cardinalities, the solutions to rate distortion (Shannon, 1959), information bottleneck (IB) (Tishby et al., 1999) and related objectives are feasible to solve with Blahut-Arimoto (BA) style algorithms. This library unifies several different variants on the rate distortion objective and provides solvers using BA and reverse deterministic annealing. Implementation is inspired by the libraries embo and dit. This library was created to overcome two shortcomings of these existing libraries:

• embo is a fast implementation of generalized IB, but has no support for getting solution encoders, or using deterministic annealing, which is useful for preserving some structure between nearby optima.

• dit is a more general library supporting discrete information theory but (anecdotally) it has been found to be slow and its build and tests are not always passing. In contrast, rdot is a fast and focused implementation of rate-distortion objectives that yields all relevant components of fixed-point solutions.

Installing RDOT

First, set up a virtual environment (e.g. via miniconda, conda create -n rdot python=3, and conda activate rdot).

Method 1. Install via pypi

Install RDOT via pypi (We recommend doing this inside a virtual environment)

pip install rdot

Method 2. Install locally

• Download or clone this repository and navigate to the root folder.

• Install RDOT (inside a virtual environment)

  pip install -e .

Getting started

• Check out the examples, which contains a notebook walking through rate distortion problems, and a comparison of IB solutions for rdot and embo.

Modules

The main module is rdot.optimizers, which includes a unified hierarchy of optimizer classes that use Blahut-Arimoto algorithms for defining and solving rate distortion objectives.

There are several auxiliary modules, including:

• rdot.distortions for defining distortion functions,
• rdot.information helper functions for working with distributions and information-theoretic quantities,
• rdot.probability helper functions for working with distributions,
• rdot.postprocessing helper functions for ensuring the quality of solutions computed from rdot.optimizers.

Testing

Unit tests are written using pytest in the test_rd.py file and executed via running pytest from the root folder.

References:

Shannon, C.E. (1959). Coding theorems for a discrete source with a fidelity criterion. Institute of Radio Engineers, National Convention Record 4:142–163.

Tishby, N., Pereira F.C., & Bialek, W. (1999). The information bottleneck method. Proceedings of the 37th Annual Allerton Conference on Communication, Control and Computing, eds Hajek B, Sreenivas RS (Univ of Illinois, Urbana, IL), pp 368– 377.