Learned Universal Entropy Coding With Tensor Networks
TL;DR
Experimental results demonstrate that the proposed TN-based universal entropy coding method consistently outperforms existing universal approaches and is comparable to task-specific approaches in the tasks of lossless graph and image compression and learned lossy image compression.
Abstract
Existing methods for universal entropy coding suffer from the dilemma between versatility to general data sources and ability in exploiting complex structured statistics. They usually rely on presumed structural and statistical assumptions to decompose joint probability distribution for tractable entropy modeling. To address this problem, in this paper, we propose the first learned universal entropy coding method that leverages tensor networks (TNs) to learn joint probability distribution of diverse data sources without presuming distribution priors or context structures. Specifically, we resort to the tensor network formulation based on matrix product states (MPS) to learn the tractable low-order tensor approximation for high-order tensor representation of joint probability distribution. Entropy encoding and decoding are achieved in a sequential fashion by constructing cumulative distribution functions with marginal probabilities of sources on top of the probabilistic modeling. We demonstrate in theory that the proposed entropy model converges to stationary distribution, guarantees upper and lower bounds of entropy rates, and exponentially decays in truncation error of entropy rate with truncation order and correlation length. Furthermore, TN-based practical coding framework is designed with unified Gray-code bit-plane decomposition to mitigate numerical overflow. Experimental results demonstrate that the proposed method consistently outperforms existing universal approaches and is comparable to task-specific approaches in the tasks of lossless graph and image compression and learned lossy image compression.