# iFlow: Numerically Invertible Flows for Efficient Lossless Compression via a
Uniform Coder

Shifeng Zhang, Ning Kang, Tom Ryder, Zhenguo Li
Huawei Noah’s Ark Lab
{zhangshifeng4, kang.ning2, tom.ryder1, li.zhenguo}.huawei.com

###### Abstract

It was estimated that the world produced $59ZB$ ($5.9\times 10^{13}GB$) of
data in 2020, resulting in the enormous costs of both data storage and
transmission. Fortunately, recent advances in deep generative models have
spearheaded a new class of so-called "neural compression" algorithms, which
significantly outperform traditional codecs in terms of compression ratio.
Unfortunately, the application of neural compression garners little commercial
interest due to its limited bandwidth; therefore, developing highly efficient
frameworks is of critical practical importance. In this paper, we discuss
lossless compression using normalizing flows which have demonstrated a great
capacity for achieving high compression ratios. As such, we introduce iFlow, a
new method for achieving efficient lossless compression. We first propose
Modular Scale Transform (MST) and a novel family of numerically invertible
flow transformations based on MST. Then we introduce the Uniform Base
Conversion System (UBCS), a fast uniform-distribution codec incorporated into
iFlow, enabling efficient compression. iFlow achieves state-of-the-art
compression ratios and is $5\times$ quicker than other high-performance
schemes. Furthermore, the techniques presented in this paper can be used to
accelerate coding time for a broad class of flow-based algorithms.

##  1 Introduction

The volume of data, measured in terms of IP traffic, is currently witnessing
an exponential year-on-year growth [13]. Consequently, the cost of
transmitting and storing data is rapidly becoming prohibitive for service
providers, such as cloud and streaming platforms. These challenges
increasingly necessitate the need for the development of high-performance
lossless compression codecs.

One promising solution to this problem has been the development of a new class
of so-called “neural compression” algorithms [30, 38, 18, 4, 17, 37, 26, 31,
6, 41]. These methods typically posit a deep probabilistic model of the data
distribution, which, in combination with entropy coders, can be used to
compress data with the minimal codelength bounded by the negative log-
likelihood [29]. However, despite reliably improved compression performance
compared to traditional codecs [14, 33, 9, 34], meaningful commercial
applications have been limited by impractically slow coding speed.

Figure 1: Illustration of IDF(++), iVPF, LBB and the proposed iFlow method.
Flow layers with darker color denote higher expressive power. The top-right of
each model illustration shows the key procedure of exact bijections between
$\bar{x}$ and $\bar{z}$. The compression ratio and bandwidth are listed below.

In this paper, we focus on developing approaches with deep probabilistic
models based on normalizing flows [11, 25, 32, 27, 7, 28, 23]. A normalizing
flow admits a learnable bijective mapping between input data and a latent
variable representation. In this paradigm, inputs can be compressed by first
transforming data to latent variables, with the resulting output encoded by a
prior distribution. Compared to other classes of generative models,
normalizing flows typically perform best in both tasks of probability density
estimation (as compared with variational autoencoders [24, 15, 8]) and
inference speed (as compared with autoregressive factorizations [35, 39, 22]).
This suggests that compression with flows can jointly achieve high compression
ratios along with fast coding times.

Unfortunately, lossless compression requires discrete data for entropy coding,
and the continuous bijections of normalizing flows would not guarantee
discrete latent variables. As such, transformations would require
discretization, resulting in a loss of information [41, 3]. To resolve this
issue, Integer Discrete Flows (IDF) [18, 4] (Fig. 1, left) proposed an
invertible mapping between discrete data and latent variables. Similarly, iVPF
[41] achieves a discrete-space bijection using volume-preserving flows.
However, the above models must introduce constraints on flow layers to ensure
a discrete-space bijection, which limits the expressivity of the
transformation. Local Bits-Back Coding (LBB) [17] (Fig. 1, middle) was the
first approach to succeed in lossless coding with the flexible family of
continuous flows. It resolves the information loss by coding numerical errors
with the rANS coder [12]. However, the coder is extraordinarily slow, making
the method impractical.

In this paper, we introduce iFlow: a numerically invertible flow-based neural
compression codec that bridges the gap between high-fidelity density
estimators and practical coding speed. To achieve this we introduce two
novelties: Modular Scale Transform (MST) and Uniform Base Conversion Systems
(UBCS). MST presents a flexible family of bijections in discrete space,
deriving an invertible class of flows suitable for lossless compression. UBCS,
built on the uniform distribution, permits a highly efficient entropy coding
compatible with MST. The main ideas are illustrated in Fig. 1(right). We test
our approach across a range of image datasets against both traditional and
neural compression techniques. Experimentally we demonstrate that our method
achieves state-of-the-art compression ratios, with coding time $5\times$
quicker than that of the next-best scheme, LBB.

##  2 Numerically Invertible Flows and Lossless Compression

Let $f:\mathcal{X}\to\mathcal{Z}$ be our normalizing flow, which we build as a
composition of layers such that $f=f_{L}\circ...\circ f_{2}\circ f_{1}$.
Defining $d$-dimensional $\mathbf{y}_{0}=\mathbf{x}\in\mathcal{X}$ and
$\mathbf{y}_{L}=\mathbf{z}\in\mathcal{Z}$, the latents can be computed as
$\mathbf{y}_{l}=f_{l}(\mathbf{y}_{l-1})$, with $p_{X}(\mathbf{x})$ calculated
according to

$\log p_{X}(\mathbf{x})=\log p_{Z}(\mathbf{z})+\sum_{l=1}^{L}\log|\det
J_{f_{l}}(\mathbf{y}_{l-1})|,$ (1)

where $J_{f_{l}}(\mathbf{x})$ is the Jocabian matrix of the transformation
$f_{l}$ at $\mathbf{y}_{l-1}$. In this paper, we use $\log$ to denote base 2
logarithms. Training the flow should minimize the negative log-likelihood
$-\log p_{X}(\mathbf{x})$. The inverse flow is defined as
$f^{-1}=f^{-1}_{1}\circ...\circ f^{-1}_{L}$, such that
$f^{-1}(\mathbf{z})=\mathbf{x}$. There are many types of invertible
bijections, $f_{l}$. Popular choices include element-wise, autoregressive
(e.g. coupling layers) [41] and $1\times 1$ convolution transformations [25].

To perform lossless compression with normalizing flows, the input data should
be transformed to latent variables, which are then encoded with a prior
distribution. As data and encoded bits should be in binary format,
$\mathbf{x}$ and $\mathbf{z}$ must be discrete, with a bijection between
discrete inputs and outputs established. However, as discussed, this operation
is usually intractable with popular classes of transformations used in
continuous flows due to the numerical errors induced by discretization.

In this section, we introduce a novel algorithm derived from continuous flows
that allows us to achieve an exact bijiective mapping between discrete
$\mathbf{x}$ and discrete $\mathbf{z}$. We present the general idea of a flow
layer’s numerical invertibility in discrete space in Sec. 2.1. We then
introduce our flow layers in Sec. 2.2 and 2.3, with their application to
compression discussed in Sec. 2.4 and 2.5.

###  2.1 Invertibility of Flows in Discrete Space

To discretize the data, we follow [41] and adopt $k$-precision quantization to
assign floating points to discretization bins such that

$\bar{x}=\frac{\lfloor 2^{k}\cdot x\rfloor}{2^{k}},$ (2)

where $\lfloor\cdot\rfloor$ is the floor function. The associated quantization
error is bounded by $|\bar{x}-x|<2^{-k}$. Any $d$-dimensional $\mathbf{x}$ can
be quantized into bins with volume $\delta=2^{-kd}$. The probability mass of
$\bar{\mathbf{x}}$ can then be approximated by
$P(\bar{\mathbf{x}})=p(\bar{\mathbf{x}})\delta$, such that the theoretical
codelength is $-\log(p(\bar{\mathbf{x}})\delta)$.

Denote our proposed numerically invertible flow (iFlow) according to
$\bar{f}=\bar{f}_{L}\circ...\circ\bar{f}_{1}$. The input and output should be
subject to $k$-precision quantization, where each layer should be
appropriately invertible such that
$\bar{\mathbf{y}}_{l-1}\equiv\bar{f}_{l}^{-1}(\bar{f}_{l}(\bar{\mathbf{y}}_{l-1}))$.
Denoting $\bar{\mathbf{y}}_{0}=\mathbf{x}$ and
$\bar{\mathbf{z}}=\bar{\mathbf{y}}_{L}$, it is further expected that
$\bar{\mathbf{z}}=\bar{f}(\mathbf{x})$ and
$\mathbf{x}\equiv\bar{f}^{-1}(\bar{\mathbf{z}})$. We will show in the
following subsections that $\bar{f}$ can be derived from any continuous flow
$f$ in such a way that the error between $\bar{f}(\mathbf{x})$ and
$f(\mathbf{x})$ is negligible.

###  2.2 Numerically Invertible Element-Wise Flows

We begin by describing our approach for element-wise flows
$\mathbf{z}=f(\mathbf{x})$, where $f$ is a monotonic element-wise
transformation. For notation simplicity, we assume that the flow contains just
one layer. In most cases, $f$ does not present a unique inverse in discrete
space, such that $f^{-1}(\bar{\mathbf{z}})\neq\mathbf{x}$. In what follows, we
introduce an approach to derive an invertible, discrete-space operation from
any element-wise flow transformation. For simplicity, we denote the inputs and
output pairs of a continuous flow as $x$ and $z=f(x)$; and we denote the
$k$-precision quantized input-output pairs of iFlow as $\bar{x}$ and
$\bar{z}=\bar{f}(\bar{x})$.

####  2.2.1 Scale Flow

Algorithm 1 Modular Scale Transform (MST): Numerically Invertible Scale Flow
$f(x)=R/S\cdot x$.

Forward MST: $\bar{z}=\bar{f}(\bar{x})$.

1: $\hat{x}\leftarrow 2^{k}\cdot\bar{x}$;

2: Decode $r_{d}$ using $U(0,R)$; $\hat{y}\leftarrow R\cdot\hat{x}+r_{d}$;

3: $\hat{z}\leftarrow\lfloor\hat{y}/S\rfloor,r_{e}\leftarrow\hat{y}\mod S$;

4: Encode $r_{e}$ using $U(0,S)$;

5: return $\bar{z}\leftarrow\hat{z}/2^{k}$.

Inverse MST: $\bar{x}=\bar{f}^{-1}(\bar{z})$.

1: $\hat{z}\leftarrow 2^{k}\cdot\bar{z}$;

2: Decode $r_{e}$ using $U(0,S)$; $\hat{y}\leftarrow S\cdot\hat{z}+r_{e}$;

3: $\hat{x}\leftarrow\lfloor\hat{y}/R\rfloor,r_{d}\leftarrow\hat{y}\mod R$;

4: Encode $r_{d}$ using $U(0,R)$;

5: return $\bar{x}\leftarrow\hat{x}/2^{k}$.

We begin with the scale transformation defined as $z=f(x)=a\cdot x,\,(a>0)$,
from which we are able to build more complex flow layers. The input can be
converted to an integer with $\hat{x}=2^{k}\cdot\bar{x}$, and the latent
variable $\bar{z}$ can be recovered from integer $\hat{z}$ by
$\bar{z}=\hat{z}/2^{k}$. Inspired by MAT in iVPF [41], we first approximate
$a$ with a fractional such that $a\approx\frac{R}{S},$ where
$R,S\in\mathbb{N}$. Denote $\hat{y}=R\cdot\hat{x}+r_{d}$ where $r_{d}$ is
sampled uniformly from $\\{0,1,...,R-1\\}$, we can obtain $\hat{z}$ with
$\hat{z}=\lfloor\hat{y}/S\rfloor$, and the remainder $r_{e}=\hat{y}\mod R$ can
be encoded to eliminate the error. It is clear that
$(\hat{x},r_{d})\leftrightarrow\hat{y}\leftrightarrow(\hat{z},r_{e})$ are
bijections.

Let $U(0,A)$ be the uniform distribution such that
$P(s)=\frac{1}{A},\,s\in\\{0,1,...,A-1\\}$. The numerically invertible scale
flow $\bar{f}$ is displayed in Alg. 1. As the modular operation is essential
to Alg. 1, we name it the Modular Scale Transform (MST). Setting $S$ and
$R=\mathrm{round}(S\cdot a)$ to be large, we observe that the following
propositions hold.

######  Proposition 1.

[41] $|\bar{z}-f(\bar{x})|<O(S^{-1},2^{-k})$.

######  Proposition 2.

The codelength of MST is $L_{f}(\bar{x},\bar{z})=\log S-\log
R\approx-\log|a|=-\log|f^{\prime}(\bar{x})|$.

Proposition 1 establishes that the error is small if $S$ and $k$ are large.
Proposition 2 demonstrates that the codelength is almost exactly the log-
Jocabian of $f$. The above properties and the correctness of the algorithm are
discussed in the Appendix. Further note that, with the exception of the usual
encoding and decoding processes, MST’s operations can be parallelized,
resulting in minimal additional overhead. In contrast, MAT’s operation in iVPF
[41] only deals with volume-preserving affine transform and is performed
sequentially along dimensions, limiting its usage and efficiency.

####  2.2.2 General Element-wise Flow

Algorithm 2 Numerically Invertible Element-wise Flows

Forward: $\bar{z}=\bar{f}(\bar{x})$.

1: Get $\bar{x}_{l},\bar{x}_{h},\bar{z}_{l},\bar{z}_{h}$ given $\bar{x}$, so
that $\bar{x}\in[\bar{x}_{l},\bar{x}_{h})$;

2: Set large $S$; get $R$ with Eq. (4);
$\bar{x}^{\prime}\leftarrow\bar{x}-\bar{x}_{l}$;

3: Get $\bar{z}^{\prime}$ with forward MST in Alg. 1, given input
$\bar{x}^{\prime}$ and coefficients $R,S$;

4: return $\bar{z}=\bar{z}^{\prime}+\bar{z}_{l}$.
$\qquad\quad\triangleright~{}\bar{z}\in[\bar{z}_{l},\bar{z}_{h}).$

Inverse: $\bar{x}=\bar{f}^{-1}(\bar{z})$.

1: Get $\bar{x}_{l},\bar{x}_{h},\bar{z}_{l},\bar{z}_{h}$ given $\bar{z}$, so
that $\bar{z}\in[\bar{z}_{l},\bar{z}_{h})$;

2: Set large $S$; get $R$ with Eq. (4);
$\bar{z}^{\prime}\leftarrow\bar{z}-\bar{z}_{l}$;

3: Get $\bar{x}^{\prime}$ with inverse MST in Alg. 1, given input
$\bar{z}^{\prime}$ and coefficients $R,S$;

4: return $\bar{x}=\bar{x}^{\prime}+\bar{x}_{l}$.
$\qquad\quad\triangleright~{}\bar{x}\in[\bar{x}_{l},\bar{x}_{h}).$

For simplicity, we assume the non-linear $f$ is monotonically increasing. For
a monotonically decreasing $f$, we simply invert the sign: $-f$.

MST in Alg. 1 works with linear transformations, and is incompatible with non-
linear functions. Motivated by linear interpolation, we can approximate the
non-linear flow with a piecewise linear function. In general, consider input
$\bar{x}$ to be within an interval $\bar{x}\in[\bar{x}_{l},\bar{x}_{h})$111All
intervals must partition the domain of $f$. and
$\bar{z}_{l}=\overline{f(\bar{x}_{l})},\bar{z}_{h}=\overline{f(\bar{x}_{h})}$.
The linear interpolation of $f$ is then

$f_{inp}(x)=\frac{\bar{z}_{h}-\bar{z}_{l}}{\bar{x}_{h}-\bar{x}_{l}}(\bar{x}-\bar{x}_{l})+\bar{z}_{l}.$
(3)

It follows that $\bar{z}$ can be derived from MST with input
$\bar{x}-\bar{x}_{l}$ followed by adding $\bar{z}_{l}$. Furthermore, $\bar{z}$
and $\bar{x}$ can be recovered with the corresponding inverse transformation.
To preserve monotonicity, $\bar{z}$ must be within interval
$\bar{z}\in[\bar{z}_{l},\bar{z}_{h})$. Denoting the invertible linear flow
derived from $f_{inp}$ as $\bar{f}_{inp}$, it must hold that
$\bar{f}_{inp}(\bar{x}_{l})\geq\bar{z}_{l},\bar{f}_{inp}(\bar{x}_{h}-2^{-k})\leq\bar{z}_{h}-2^{-k}$.
As we use MST in Alg. 1, we observe that when
$\frac{\bar{z}_{h}-\bar{z}_{l}}{\bar{x}_{h}-\bar{x}_{l}}$ is approximated with
$R/S$, the minimum possible value of $\bar{f}_{inp}(\bar{x}_{l})$ is
$\bar{z}_{l}$ (when $r_{d}=0$ in Line 2) and the maximum possible value of
$\bar{f}_{inp}(\bar{x}_{h}-2^{-k})$ is $\lfloor(R\cdot
2^{k}(\bar{x}_{h}-\bar{x}_{l}-2^{-k})+R-1)/(S\cdot 2^{k})\rfloor+\bar{z}_{l}$
(when $r_{d}=R-1$ in Line 2). Given large $S$, the largest possible value of
$R$ should be

$R=\big{\lfloor}\frac{(2^{k}\cdot(\bar{z}_{h}-\bar{z}_{l})-1)\cdot
S+1}{2^{k}\cdot(\bar{x}_{h}-\bar{x}_{l})}\big{\rfloor}.$ (4)

Another difficulty is in determining the correct interpolation interval
$[\bar{x}_{l},\bar{x}_{h})$. One simple solution is to split the input domain
into uniform intervals with length $2^{-h}$ such that
$\bar{x}_{l}=\lfloor(2^{h}\cdot\bar{x})/2^{h}\rfloor,\bar{x}_{h}=\bar{x}_{l}+2^{-h}$.
However, for the inverse computation given $\bar{z}$, it is not easy to
recover the interpolation interval as $f^{-1}(\bar{z})$ may not be within
$[\bar{x}_{l},\bar{x}_{h})$. Instead, as
$\bar{z}\in[\bar{z}_{h},\bar{z}_{l})$, the interval
$[\bar{x}_{l},\bar{x}_{h})$ can be obtained via a binary search in which
$\bar{x}_{l}$ is obtained with
$\bar{z}\in[\overline{f(\bar{x}_{l})},\overline{f(\bar{x}_{h})})$. Another
approach is to split the co-domain into uniform intervals such that
$\bar{z}_{l}=\lfloor(2^{h}\cdot\bar{z})/2^{h}\rfloor,\bar{z}_{h}=\bar{z}_{l}+2^{-h}$,
with
$\bar{x}_{l}=\overline{f^{-1}(\bar{z}_{l})},\bar{x}_{h}=\overline{f^{-1}(\bar{z}_{h})}$.
In this case, determining $[\bar{z}_{l},\bar{z}_{h})$ during the inverse
computation is simple. While for the forward pass, $[\bar{z}_{l},\bar{z}_{h})$
should be determined with a binary search such that
$\bar{x}\in[\overline{f^{-1}(\bar{z}_{l})},\overline{f^{-1}(\bar{z}_{h})})$.
In practice, we have simpler tricks to determine the correct interval
$[\bar{x}_{l},\bar{x}_{h}),[\bar{z}_{l},\bar{x}_{h})$ for both the forward and
inverse computation, which can be found in the Appendix.

The general idea of the non-linear flow adaptations are summarized in Alg. 2.
Note that Alg. 2 can be used in any element-wise flow including linear flow.
In Alg. 2, Proposition 2 holds such that
$L_{f}(\bar{x},\bar{z})=-\log(R/S)\approx-\log\frac{\bar{z}_{h}-\bar{z}_{l}}{\bar{x}_{h}-\bar{x}_{l}}\approx-\log|f^{\prime}(\bar{x})|$.
It is possible to arrive at a similar conclusion in Proposition 1 where the
corresponding error is $|\bar{z}-f(\bar{x})|<O(S^{-1},2^{-k},2^{-2h})$.

###  2.3 Practical Numerically Invertible Flow Layers

Whilst one can use many types of complex transformations to build richly
expressive flow-based models, to ensure the existence and uniqueness of the
inverse computation, these layers are generally constructed with element-wise
transformations. In this subsection, we demonstrate the invertibility of
discretized analogs to some of the most widely used flow layers using the
operators as described in Sec. 2.2. Such flows include autoregressive flows
[20] (including coupling flows [10, 11, 16]) and $1\times 1$ convolutional
flows [25].

####  2.3.1 Autoregressive and Coupling Flows

Algorithm 3 Numerically Invertible Autoregressive Flow

Forward: $\bar{\mathbf{z}}=\bar{f}(\bar{\mathbf{x}})$.

1: for $i=m,...,1$ do

2:
$\bar{\mathbf{z}}_{i}\leftarrow\bar{f}_{i}(\bar{\mathbf{x}}_{i},\bar{\mathbf{x}}_{<i})$
with Alg. 2 (forward);

3: end for

4: return
$\bar{\mathbf{z}}=[\bar{\mathbf{z}}_{1},...,\bar{\mathbf{z}}_{m}]^{\top}$.

Inverse: $\bar{\mathbf{x}}=\bar{f}^{-1}(\bar{\mathbf{z}})$.

1: for $i=1,...,m$ do

2:
$\bar{\mathbf{x}}_{i}\leftarrow\bar{f}^{-1}_{i}(\bar{\mathbf{z}}_{i},\bar{\mathbf{x}}_{<i})$
with Alg. 2 (inverse);

3: end for

4: return
$\bar{\mathbf{z}}=[\bar{\mathbf{z}}_{1},...,\bar{\mathbf{z}}_{m}]^{\top}$.

Supposing that the inputs and outputs, $\mathbf{x}$ and $\mathbf{z}$, are
split into $m$ parts
$\mathbf{x}=[\mathbf{x}_{1},...,\mathbf{x}_{m}]^{\top},\mathbf{z}=[\mathbf{z}_{1},...,\mathbf{z}_{m}]^{\top}$,
the autoregressive flow $\mathbf{z}=f(\mathbf{x})$ can be represented as
$\mathbf{z}_{i}=f_{i}(\mathbf{x}_{i};\mathbf{x}_{<i})$, where
$f_{i}(\cdot;\mathbf{x}_{<i})$ is the element-wise flow (discussed in Sec.
2.2), conditioned on $\mathbf{x}_{<i}$. Now let
$\bar{f}_{i}(\cdot;\mathbf{x}_{<i})$ denote the invertible element-wise flow
transformation as discussed in Alg. 1-2. Alg. 3 then illustrates the details
of an invertible autoregressive flow $\bar{f}$.

Propositions 1 and 2 hold in our discretized autoregressive transformation. In
fact, the log-determinant of Jacobian is given by $\log|\det
J_{f}(\mathbf{x})|=\sum_{i=1}^{m}\log|\det
J_{f_{i}}(\mathbf{x}_{i};\mathbf{x}_{<i})|$, and the expected codelength is
simply
$L_{f}(\bar{\mathbf{x}},\bar{\mathbf{z}})=\sum_{i=1}^{m}L_{f}(\bar{\mathbf{x}}_{i},\bar{\mathbf{z}}_{i})\approx-\sum_{i=1}^{m}\log|\det
J_{f_{i}}(\bar{\mathbf{x}}_{i};\bar{\mathbf{x}}_{<i})|=-\log|\det
J_{f}(\bar{\mathbf{x}})|$.

When $m=2$ and $f_{1}(\mathbf{x}_{1})=\mathbf{x}_{1}$, the autoregressive flow
is reduced to a coupling flow, which is widely used in flow-based models [10,
11, 16]. It is therefore trivially clear that the coupling flow is
additionally compatible with Alg. 3.

####  2.3.2 $1\times 1$ Convolutional Flow

$1\times 1$ convolutional layers can be viewed as a matrix multiplication
along a channel dimension [25]. Let
$\bar{\mathbf{x}},\bar{\mathbf{z}}\in\mathbb{R}^{c}$ be inputs and outputs
along channels, and $\mathbf{W}\in\mathbb{R}^{c\times c}$ the weights of our
network. The objective is to obtain
$\bar{\mathbf{z}}=\bar{f}(\bar{\mathbf{x}})$ where
$f(\mathbf{x})=\mathbf{W}\mathbf{x}$.

We use the ideas of iVPF [41] to achieve a numerically invertible $1\times 1$
convolutional transformation. In particular, we begin by performing an LU
decomposition such that
$\mathbf{W}=\mathbf{P}\mathbf{L}\mathbf{\Lambda}\mathbf{U}$. It then follows
that the $1\times 1$ convolution is performed with successive matrix
multiplications with $\mathbf{U},\mathbf{\Lambda},\mathbf{L}$ and
$\mathbf{P}$. In iVPF, the authors extensively discussed matrix
multiplications with factors $\mathbf{U},\mathbf{L}$ and $\mathbf{P}$ [41].
Meanwhile, one can view the matrix multiplication with $\mathbf{\Lambda}$ as a
scale transform, such that $f(\mathbf{x})=\bm{\lambda}\odot\mathbf{x}$, where
$\odot$ is an element-wise multiplication and $\bm{\lambda}$ are the diagonal
elements of $\mathbf{\Lambda}$. MST in Alg. 1 can then be applied. In such a
case, it is clear that Proposition 1 and 2 hold for a $1\times 1$
convolutional flow. For Proposition 2, it is observed that
$L_{f}(\bar{\mathbf{x}},\bar{\mathbf{z}})\approx-\mathrm{sum}(\log\bm{\lambda})=-\log|\det\bm{\Lambda}|=-\log|\det\mathbf{W}|=-\log|\det
J_{f}(\bar{\mathbf{x}})|$.

###  2.4 Building Numerically Invertible Flows

Our flow model is constructed as a composition of layers $f=f_{L}\circ...\circ
f_{2}\circ f_{1}$, where each layer is a transformation of the type discussed
in Sec. 2.2 and 2.3. Let us represent the resulting flow as
$\bar{f}=\bar{f}_{L}\circ...\circ\bar{f}_{1}$, where $\bar{f}_{l}$ is a
discretized transformation derived from the corresponding continuous $f$. It
is clear that the quantized input $\bar{\mathbf{x}}(=\bar{\mathbf{y}}_{0})$
and latent $\bar{\mathbf{z}}(=\bar{\mathbf{y}}_{L})$ establish a bijection
with successive transformations between discrete inputs and outputs. For the
forward pass, $\bar{\mathbf{z}}$ is computed with
$\bar{\mathbf{y}}_{l}=\bar{f}(\bar{\mathbf{y}}_{l-1}),l=1,2,...,L$; for the
inverse pass, $\bar{\mathbf{x}}$ is recovered with the inverse flow
$\bar{f}^{-1}=\bar{f}^{-1}_{1}\circ...\circ\bar{f}^{-1}_{L}$ such that
$\bar{\mathbf{y}}_{l-1}=f^{-1}_{l}(\bar{\mathbf{y}}_{l})$.

For our resultant flow model, we can draw similar conclusions as in
Propositions 1 and 2. Firstly, the error of
$\bar{\mathbf{z}}=\bar{f}(\bar{\mathbf{x}})$ and
$\mathbf{z}=f(\bar{\mathbf{x}})$ is small, bounded by
$|\bar{\mathbf{z}}-\mathbf{z}|<O(LS^{-1},L2^{-k},L2^{-2h})$. Secondly, the
codelength is approximately
$L_{f}(\bar{\mathbf{x}},\bar{\mathbf{z}})=\sum_{l=1}^{L}L_{f_{l}}(\bar{\mathbf{y}}_{l-1},\bar{\mathbf{y}}_{l})\approx-\sum_{l=1}^{L}\log|\det
J_{f_{l}}(\bar{\mathbf{y}}_{l-1})|$.

###  2.5 Lossless Compression with Flows via Bits-back Dequantization

Armed with our flow model $\bar{f}$, performing lossless compression is
straight-forward. For the encoding process, the latent is generated according
to $\bar{\mathbf{z}}=\bar{f}(\bar{\mathbf{x}})$. We then encode
$\bar{\mathbf{z}}$ with probability $p_{Z}(\bar{\mathbf{z}})\delta$. For the
decoding process, $\bar{\mathbf{z}}$ is decoded with
$p_{Z}(\bar{\mathbf{z}})\delta$, and $\bar{\mathbf{x}}$ is recovered with
$\bar{f}^{-1}(\bar{\mathbf{z}})$. The expected codelength is approximately
$-\log(p_{X}(\bar{\mathbf{x}})\delta)$ such that

$L(\bar{\mathbf{x}})\approx-\log(p_{Z}(\bar{\mathbf{z}})\delta)-\sum_{l=1}^{L}\log|\det
J_{f_{l}}(\bar{\mathbf{y}}_{l-1})|\approx-\log(p_{X}(\bar{\mathbf{x}})\delta).$
(5)

However, we note that if $k$ is large, $-\log\delta=kd$ and the codelengths
will also be large, resulting in a waste of bits. For what follows, we adopt
the bits-back trick in LBB [17] to reduce the codelength. In particular,
consider coding with input data $\mathbf{x}^{\circ}\in\mathbb{Z}^{d}$, where a
$k$-precision noise vector $\bar{\mathbf{u}}\in[0,1)^{d}$ is decoded with
$q(\bar{\mathbf{u}}|\mathbf{x}^{\circ})\delta$ and added to input data such
that $\bar{\mathbf{x}}=\mathbf{x}^{\circ}+\bar{\mathbf{u}}$. In this way,
$\bar{\mathbf{x}}$ is then encoded with our flow $\bar{f}$. For the decoding
process, $\mathbf{x}^{\circ}$ is recovered by applying the inverse
transformation. We name this coding process Bits-back Dequantization, which is
summarized in Alg. 4.

Algorithm 4 Lossless Compression with iFlow.

Encode $\mathbf{x}^{\circ}$.

1: Decode $\bar{\mathbf{u}}$ using
$q(\bar{\mathbf{u}}|\mathbf{x}^{\circ})\delta$;

2: $\bar{\mathbf{z}}\leftarrow\bar{f}(\mathbf{x}^{\circ}+\bar{\mathbf{u}})$;

3: Encode $\bar{\mathbf{z}}$ using $p_{Z}(\bar{\mathbf{z}})\delta$.

Decode.

1: Decode $\bar{\mathbf{z}}$ using $p_{Z}(\bar{\mathbf{z}})\delta$;

2:
$\bar{\mathbf{x}}\leftarrow\bar{f}^{-1}(\bar{\mathbf{z}}),\mathbf{x}^{\circ}\leftarrow\lfloor\bar{\mathbf{x}}\rfloor$;

3: Encode $\bar{\mathbf{u}}=\bar{\mathbf{x}}-\mathbf{x}^{\circ}$ using
$q(\bar{\mathbf{u}}|\mathbf{x}^{\circ})\delta$;

4: return $\mathbf{x}^{\circ}$.

In practice, $q(\mathbf{u}|\mathbf{x}^{\circ})$ is constructed with a flow
model such that $\mathbf{u}=g(\bm{\epsilon};\mathbf{x}^{\circ})$ where
$\bm{\epsilon}\sim p(\bm{\epsilon})$. $\bar{\mathbf{u}}$ is decoded by first
decoding $\bar{\bm{\epsilon}}$ with $p(\bar{\bm{\epsilon}})\delta$, and then
applying $\bar{\mathbf{u}}=\bar{g}(\bar{\bm{\epsilon}};\mathbf{x}^{\circ})$.
Thus decoding $\bar{\mathbf{u}}$ involves
$-\log(q(\bar{\mathbf{u}}|\mathbf{x}^{\circ})\delta)$ bits. Overall, the
expected codelength is exactly the dequantization lower bound [19] such that

$\begin{split}L(\mathbf{x}^{\circ})&\approx\sum_{\bar{\mathbf{u}}}q(\bar{\mathbf{u}}|\mathbf{x}^{\circ})\delta[\log(q(\bar{\mathbf{u}}|\mathbf{x}^{\circ})\delta)-\log(p(\mathbf{x}^{\circ}+\bar{\mathbf{u}})\delta)]\\\
&\approx\mathbb{E}_{q(\bar{\mathbf{u}}|\mathbf{x}^{\circ})}[\log
q(\bar{\mathbf{u}}|\mathbf{x}^{\circ})-\log
p(\mathbf{x}^{\circ}+\bar{\mathbf{u}})].\end{split}$ (6)

###  2.6 Extensions

With novel modifications, flow models can be applied to the generation of
various data types, obtaining superior performance [7, 28, 23]. These models
can be used for improved lossless compression. In general, given input data
$\mathbf{x}^{\circ}$, these models generate intermediate data $\mathbf{v}$
with $q(\mathbf{v}|\mathbf{x}^{\circ})$, and the density of $\mathbf{v}$ is
modelled with flow model $\mathbf{z}=f(\mathbf{v})$. For generation, when
$\mathbf{v}$ is generated with the inverse flow, $\mathbf{x}$ is generated
with $p(\mathbf{x}^{\circ}|\mathbf{v})$. It is clear that $p(\mathbf{x})$ can
be estimated with variational lower bound such that $\log
p(\mathbf{x}^{\circ})\geq\mathbb{E}_{q(\mathbf{v}|\mathbf{x}^{\circ})}[\log
P(\mathbf{x}^{\circ}|\mathbf{v})+\log p(\mathbf{v})-\log
q(\mathbf{v}|\mathbf{x}^{\circ})]$. For lossless compression,
$\mathbf{x}^{\circ}$ can be coded with bits-back coding, which is similar with
Alg. 4. In the encoding process, we first decode $\bar{\mathbf{v}}$ with
$q(\bar{\mathbf{v}}|\mathbf{x}^{\circ})\delta$ and then encode
$\mathbf{x}^{\circ}$ with $P(\mathbf{x}^{\circ}|\bar{\mathbf{v}})$ (similar
with Line 1 in Alg. 4-Encode). We then obtain the prior
$\bar{\mathbf{z}}=\bar{f}(\bar{\mathbf{v}})$ (Line 2), before finally encoding
$\bar{\mathbf{z}}$ with $p_{Z}(\bar{\mathbf{z}})\delta$ (Line 3). In the
decoding process, $\bar{\mathbf{z}}$ is firstly decoded with
$p_{Z}(\bar{\mathbf{z}})\delta$ (similar to Line 1 in Alg. 4-Decode), and then
recovered $\bar{\mathbf{v}}$ and decoded $\mathbf{x}^{\circ}$ with
$P(\mathbf{x}^{\circ}|\bar{\mathbf{v}})$ (Line 2). Finally, we encode using
$\bar{\mathbf{v}}$ with $q(\bar{\mathbf{v}}|\mathbf{x}^{\circ})$ [38]. The
expected codelength is approximately

$L(\mathbf{x}^{\circ})\approx\mathbb{E}_{q(\bar{\mathbf{v}}|\mathbf{x}^{\circ})}[\log
q(\bar{\mathbf{v}}|\mathbf{x}^{\circ})-\log
P(\mathbf{x}^{\circ}|\bar{\mathbf{v}})-\log p(\bar{\mathbf{v}})].$ (7)

We introduce a selection of recent, state-of-the-art flow-based models
modified according to the above. Each model corresponds to a certain coding
algorithm.

VFlow [7]. VFlow expands the input data dimension with variational data
augmentation to resolve the bottleneck problem in the flow model. In VFlow,
$\mathbf{v}=[\mathbf{x}^{\circ}+\mathbf{u},\mathbf{r}](\mathbf{u}\in[0,1)^{d})$,
where $\mathbf{u}\sim q_{u}(\mathbf{u}|\mathbf{x}^{\circ}),\mathbf{r}\sim
q_{r}(\mathbf{r}|\mathbf{x}^{\circ}+\mathbf{u})$, is modelled with flows
$g_{u},g_{r}$ such that
$\mathbf{u}=g_{u}(\bm{\epsilon}_{u};\mathbf{x}^{\circ}),\mathbf{r}=g_{r}(\bm{\epsilon}_{r};\mathbf{x}^{\circ}+\mathbf{u})$
($\bm{\epsilon}_{u},\bm{\epsilon}_{r}$ are priors). Then we have
$q(\mathbf{v}|\mathbf{x}^{\circ})=q_{u}(\mathbf{u}|\mathbf{x}^{\circ})q_{r}(\mathbf{r}|\mathbf{x}^{\circ}+\mathbf{u}),P(\mathbf{x}^{\circ}|\mathbf{v})=1$
(as $\mathbf{v}\to(\mathbf{x}^{\circ}+\mathbf{u})\to\mathbf{x}^{\circ}$). Thus
for the encoding process, $\bar{\bm{\epsilon}}_{u},\bar{\bm{\epsilon}}_{r}$
are decoded. To construct $\bar{\mathbf{v}}$ we have
$\bar{\mathbf{u}}=\bar{g}_{u}(\bar{\bm{\epsilon}}_{u};\mathbf{x}^{\circ}),\bar{\mathbf{r}}=\bar{g}_{r}(\bar{\bm{\epsilon}}_{r};\mathbf{x}^{\circ}+\bar{\mathbf{u}})$;
and then $\bar{\mathbf{v}}$ is encoded with iFlow. For the decoding process,
$\bar{\mathbf{v}}$ is decoded with the inverse iFlow, and then
$\mathbf{x}^{\circ},\bar{\mathbf{u}},\bar{\mathbf{r}}$ is recovered with
$\bar{\mathbf{v}}$. Here $\bar{\mathbf{u}},\bar{\mathbf{r}}$ is encoded and
$\mathbf{x}^{\circ}$ is the decoded output. As VFlow achieves better
generation results compared with general flows, one would expect a better
compression ratio with VFlow.

Categorical Normalizing Flow [28]. Categorical Normalizing Flows (CNF) succeed
in modelling categorical data such as text, graphs, etc. Given categorical
data $\mathbf{x}^{\circ}=[x_{1},...,x_{n}],x_{i}\in\\{1,2,...,C\\}^{n}$,
$\mathbf{v}=[\mathbf{v}_{1},...,\mathbf{v}_{n}]$ is represented with word
embeddings such that
$q(\mathbf{v}_{i}|x_{i})=q_{e}(\mathbf{v}_{i}|\bm{\mu}(x_{i}),\bm{\sigma}(x_{i}))$,
in which $q_{e}$ could be a Gaussian or logistic distribution. Then
$P(x_{i}|\mathbf{v}_{i})=\frac{\tilde{p}(x_{i})q(\mathbf{v}_{i}|x_{i})}{\sum_{c=1}^{C}\tilde{p}(c)q(\mathbf{v}_{i}|c)}$
with $\tilde{p}$ being the prior over categories. Thus
$q(\mathbf{v}|\mathbf{x}^{\circ})=\prod_{i=1}^{n}q(\mathbf{v}_{i}|x_{i}),P(\mathbf{x}^{\circ}|\mathbf{v})=\prod_{i=1}^{n}P(x_{i}|\mathbf{v}_{i})$,
and $\mathbf{x}^{\circ}$ can be coded with Alg. 8 given
$q(\mathbf{v}|\mathbf{x}^{\circ}),P(\mathbf{x}^{\circ}|\mathbf{v})$ and the
iFlow.

##  3 Uniform Base Conversion Systems

Algorithm 5 Uniform Base Conversion Systems

ENCODE $s$ using $U(0,R)(R<2^{K})$.

Input: symbol $s$, state $c$, bit-stream bs.

Output: new state $c$ and bit-stream bs.

1: $c\leftarrow c\cdot R+s$;

2: if $c\geq 2^{M+K}$ then

3: bs.push_back($c\mod 2^{K}$); $\triangleright~{}$ push $K$ bits to bit-
stream.

4: $c\leftarrow\lfloor\frac{c}{2^{K}}\rfloor$;

5: end if

6: return $c$, bs.

DECODE with $U(0,R)(R<2^{K})$.

Input: state $c$, bit-stream bs.

Output: decoded $s$, new state $c$ and bit-stream bs.

1: if $c<2^{M}\cdot R$ then

2: $c\leftarrow 2^{K}\cdot c+$bs.pop_back(); $\triangleright~{}$ get last $K$
bits from bit-stream and pop them.

3: end if

4: $s\leftarrow c\mod R$;

5: $c\leftarrow\lfloor c/R\rfloor$;

6: return $s$, $c$, bs.

The previous section demonstrates that coding with a uniform distribution is
central to our algorithm. Note that the distribution varies in each coding
process, thus dynamic entropy coder is expected. Compared to the Gaussian
distribution used in LBB [17], a uniform distribution is simpler, yielding
improved coding speed. As follows, we introduce our Uniform Base Conversion
Systems (UBCS), which is easy to implement and the coding bandwidth is much
greater than that of rANS [12].

UBCS is implemented based on a number-base conversion. The code state $c$ is
represented as an integer. For coding some symbol $s\in\\{0,1,...,R-1\\}$ with
a uniform distribution $U(0,R)$, the new state $c^{\prime}$ is obtained by
converting an $R$-base digit $s$ to an integer such that

$c^{\prime}=E(c,s)=c\cdot R+s.$ (8)

For decoding with $U(0,R)$, given state $c^{\prime}$, the symbol $s$ and state
$c$ are recovered by converting the integer to an $R$-base digit such that

$s=c^{\prime}\mod R,\qquad
c=D(c^{\prime},s)=\lfloor\frac{c^{\prime}}{R}\rfloor.$ (9)

We note, however, that $c$ will become large when more symbols are encoded,
and computing Eq. (8-9) with large $c$ will be inefficient. Similar to rANS,
we define a “normalized interval” which bounds the state $c$ such that
$c\in[2^{M},2^{K+M})$ ($K,M$ are some integers values) after coding each
symbol. For the encoding process, if $c\geq 2^{K+M}$, the lower $K$ bits are
written to disk, and the remaining bits are reserved such that
$c\leftarrow\lfloor\frac{c}{2^{K}}\rfloor$. For the decoding process, if
$c<2^{M}\cdot R$, the stored $K$ bits should be read and appended to the state
before decoding. In this way, the decoded state is contained within the
interval $[2^{M},2^{K+M})$. The initial state can be set such that $c=2^{M}$.
We illustrate this idea in Alg. 5.

The correctness of Alg. 5 is illustrated in the following theorem. P1
demonstrates that the symbols can be correctly decoded with a UBCS coder, with
coding performed in a first-in-last-out (FILO) fashion. P2 shows that the
codelength closely approximates the entropy of a uniform distribution, subject
to a large $M$ and $K$. The proof of the theorem is in the Appendix.

Table 1: Coding bandwidth (M symbol/s) of UBCS and rANS coder on different threads(thrd). We use the implementations in [17] for evaluating rANS. | # thrd | rANS | UBCS
---|---|---|---
Encoder | 1 |  5.1$\pm$0.3 | 380$\pm$5
16 |  21.6$\pm$1.1 | 2075$\pm$353
Decoder | 1 |  0.8$\pm$0.02 | 66.2$\pm$1.7
16 |  7.4$\pm$0.5 | 552$\pm$50

######  Theorem 3.

Consider coding symbols $s_{1},...s_{n}$ with $s_{i}\sim
U(0,R_{i}),(i=1,2,...,n,R_{i}<2^{K})$ using Alg. 5, and then decode
$s^{\prime}_{n},s^{\prime}_{n-1},...,s^{\prime}_{1}$ sequentially. Suppose (1)
the initial state and bit-stream are
$c_{0}=2^{M},\texttt{bs}_{0}=\texttt{empty}$ respectively; (2) After coding
$s_{i}$, the state is $c_{i}$ and the bit-stream is $\texttt{bs}_{i}$; (3)
After decoding $s^{\prime}_{i+1}$, the state is $c^{\prime}_{i}$ and the bit-
stream is $\texttt{bs}^{\prime}_{i}$. We have

P1:
$s^{\prime}_{i}=s_{i+1},c^{\prime}_{i}=c_{i},\texttt{bs}^{\prime}_{i}=\texttt{bs}_{i}$
for all $i=0,...,n-1$.

P2: Denote by the codelength $l_{i}=\lceil\log
c_{i}\rceil+\texttt{len(bs}_{i}\texttt{)}$ where len is the total number of
bits in the bit-stream. Then $l_{n}-l_{0}<\frac{1}{1-1/(\ln 2\cdot 2^{M}\cdot
K)}\big{[}\sum_{i=1}^{n}R_{i}+1+(\ln 2\cdot 2^{M})^{-1}\big{]}$.

In practice, we set $K=32$ and $M=4$. Compared to rANS [12] and Arithmetric
Coding (AC) [40], UBCS is of greater efficiency as it necessitates fewer
operations (more discussions are shown in the Appendix). UBCS can achieve
greater computational efficiency via instantiating multiple UBCS coders in
parallel with multi-threading. Table 1 demonstrates that UBCS achieves coding
bandwidths in excess of giga-symbol/s – speed significantly greater than rANS.

##  4 Experiments

In this section, we perform a number of experiments to establish the
effectiveness of iFlow. We will investigate: (1) how closely the codelength
matches the theoretical bound; (2) the efficiency of iFlow as compared with
the LBB [17] baseline; (3) the compression performance of iFlow on a series
low and high-resolution images.

###  4.1 Flow Architectures and Datasets

We adopt two types of flow architectures for evaluation: Flow++ [16] and iVPF
[41]. Flow++ is a state-of-the-art model using complex non-linear coupling
layers and variational dequantizations [19]. iVPF is derived from a volume-
preserving flow in which numerically invertible discrete-space operations are
introduced. The models are re-implemented or directly taken from the
corresponding authors. Unless specified, we use $h=12,k=28$ and set large $S$
– around $2^{16}$, which we analyse further in the Appendix. To reduce the
auxiliary bits in the bits-back coding scheme, we partition the
$d$-dimensional data into $b$ splits and perform MST (in Alg. 1 and 2) for
each split sequentially. In this case, the auxiliary bits can be reduced to
$1/b$ in MST. We use $b=4$ in this experiment.

Following the lossless compression community [16, 4, 18, 37, 41], we perform
evaluation using toy datasets CIFAR10, ImageNet32 and ImageNet64. Results for
alternate methods are obtained via re-implementation or taken directly from
the corresponding papers, where available. We further test the generalization
capabilities of iFlow in which all toy datasets are compressed with a model
trained on ImageNet32. For benchmarking our performance on high-resolution
images, we evaluate iFlow using CLIC.mobile,
CLIC.pro222https://www.compression.cc/challenge/ and DIV2k [1]. For this
purpose, we adopt our ImageNet32/64 model for evaluation, and process an image
in terms of $32\times 32$ or $64\times 64$ patches, respectively. The
experiment is conducted with PyTorch framework with one Tesla P100 GPU.

Table 2: Coding performance of iFlow, LBB and iVPF on CIFAR10 dataset. We use batch size 64. flow | compression |  |  |  | encoding time (ms) | decoding time (ms)
---|---|---|---|---|---|---
arch. | technique | nll | bpd | aux. bits | inference | coding | inference | coding
Flow++ |  LBB [17] | 3.116 | 3.118 | 39.86 | 16.2$\pm$0.3 |  116$\pm$1.0 | 32.4$\pm$0.2 |  112$\pm$1.5
iFlow (Ours) | 3.118 | 34.28 | 21.0$\pm$0.5 | 37.7$\pm$0.5
iVPF |  iVPF [41] | 3.195 | 3.201 | 6.00 | 5.5$\pm$0.1 |  11.4$\pm$0.2 | 5.2$\pm$0.1 |  13.5$\pm$0.3
iFlow (Ours) | 3.196 | 7.00 |  7.1$\pm$0.2 | 9.7$\pm$0.2

###  4.2 Compression Performance

For our experiments, we use the evaluation protocols of codelength and
compression bandwidth. The codelength is defined in terms of the average bits
per dimension (bpd). For no compression, the bpd is assumed to be 8. The
compression bandwidth evaluates coding efficiency, which we define in terms of
symbols compressed per unit time.

Table 2 demonstrates the compression results on CIFAR10. Note that we only
report the encoding time (results on decoding time are similar, and are
available in the Appendix). For iVPF, we use settings almost identical to the
original paper [41] such that $k=14$.

Firstly, we observe that, when using both the Flow++ and iVPF architectures,
iFlow achieves a bpd very close to theoretically minimal codelength. When
using Flow++, iFlow achieves identical performance as that of LBB. For the
iVPF architecture, iFlow outperforms the underlying iVPF as it avoids the need
to store $16$ bits for each data sample.

Secondly, the coding latency highlights the main advantage of iFlow: we
achieve encoding $5\times$ faster than that of LBB and over $1.5\times$ that
of iVPF. In fact, the use of UBCS only represents $20\%$ of the total coding
time for all symbols (4.8ms in Flow++ and 1.6ms in iVPF). In contrast, the
rANS coder of LBB commands over $85\%$ of the total coding latency, which is
the principal cause of LBB’s impracticality. Indeed, Table 1 demonstrates that
our UBCS coder achieves a speed-up in excess of $50\times$ that of rANS (which
results in a coder latency of 4.8ms in iFlow vs. 99.8ms in LBB).

Lastly, compared with LBB, iFlow necessitates fewer auxiliary bits. In fact,
LBB requires crica $2k+\log\sigma$ bits per dimension (for $\delta=2^{-k}$ and
small $\sigma$ in [17]). Meanwhile, iFlow requires approximately
$k+\frac{1}{b}\log S$, and $\frac{1}{b}\log S$ is usually small with large
$b$.

Table 3: Compression performance in bpd on benchmarking datasets. † denotes the generation performance in which the models are trained on ImageNet32 and tested on other datasets. ‡ denotes compression of high-resolution datasets with our ImageNet64-trained model. | ImageNet32 | ImageNet64 | CIFAR10 | CLIC.mobile | CLIC.pro | DIV2K
---|---|---|---|---|---|---
PNG [5] | 6.39 | 5.71 | 5.87 | 3.90 | 4.00 | 3.09
FLIF [36] | 4.52 | 4.19 | 4.19 | 2.49 | 2.78 | 2.91
JPEG-XL [2] | 6.39 | 5.74 | 5.89 | 2.36 | 2.63 | 2.79
L3C [30] | 4.76 | 4.42 | - | 2.64 | 2.94 | 3.09
RC [31] | - | - | - | 2.54 | 2.93 | 3.08
Bit-Swap [26] | 4.50 | - | 3.82 | - | - | -
IDF [18] | 4.18 | 3.90 | 3.34 | - | - | -
IDF++ [4] | 4.12 | 3.81 | 3.26 | - | - | -
iVPF [41] | 4.03 | 3.75 | 3.20 | - | - | -
LBB [17] | 3.88 | 3.70 | 3.12 | - | - | -
iFlow (Ours) | 3.88 | 3.70 | 3.12 | - | - | -
HiLLoC [37]† | 4.20 | 3.90 | 3.56 | - | - | -
IDF [18]† | 4.18 | 3.94 | 3.60 | - | - | -
iVPF† [41] | 4.03 | 3.79 | 3.49 |  2.47/2.39‡ |  2.63/2.54‡ |  2.77/2.68‡
iFlow (Ours)† | 3.88 | 3.65 | 3.36 | 2.26/2.26‡ | 2.45/2.44‡ | 2.60/2.57‡

###  4.3 Comparison with the State-of-the-Art

To further demonstrate the effectiveness of iFlow, we compare the compression
performance on benchmarking datasets against a variety of neural compression
techniques. These include, L3C [30], Bit-swap [26], HilLoc [37], and flow-
based models IDF [18], IDF++ [4], iVPF [41], LBB [17]. We additionally include
a number of conventional methods, such as PNG [5], FLIF [36] and JPEG-XL [2].

Experiments on Low Resolution Images. Compression results on our described
selection of datasets are available in left three columns of Table 3. Here we
observe that iFlow obtains improved compression performance over all
approaches with the exception of LBB on low-resolution images, for which we
achieve identical results.

Generalization. The last four rows in Table 3 demonstrate the literature-
standard test of generalization, in which ImageNet32 trained model are used
for testing. From these results, it is clear that iFlow achieves the best
generalization performance in this test. It is worth noting that we obtain an
improved performance on ImageNet64 when using our ImageNet32-trained model.

Experiments on High Resolution Images. Finally, we test iFlow across a number
of high-resolution image datasets. Here images are processed into non-
overlapping $32\times 32$ and $64\times 64$ patches for our ImageNet32 and
ImageNet64-trained models. The right three columns in Table 3 display the
results, which is observed that iFlow outperforms all compression methods
across all available benchmarks. Note that as we crop patches for compression,
the compression bandwidth is the same as that in small images like CIFAR10,
i.e., 5 times faster than LBB and 30% speedup compared with iVPF.

##  5 Related Work

Dynamic Entropy coders, such as Arithmetic Coding (AC) [40] and Asymmetric
Numerical Systems (ANS) [12], form the basis of lossless compression. However,
the binary search protocol required at decode time and their comparatively
high number of numerical operations make them both relatively time-consuming.
The term dynamic means that the data symbols are in different distributions,
in this case, efficient entropy coders like Huffman coding [21] and tANS [12]
are incompatible. Our proposed UBCS is dynamic coder, which requires only two
operations per symbol, producing an faster algorithm than AC and ANS.

In order to utilise entropy coders, one must estimate the data distribution.
For this purpose, the wider community has employed a variety of density
estimators. One of the most popular, autoregressive models [35], estimates the
joint density with per-pixel autoregressive factorizations. Whilst commonly
achieving state-of-the-art compression ratios, the sequential pixel-by-pixel
nature of encoding and/or decoding makes them impractically time-consuming.
Alternatively, variational autoencoders (VAEs) [24, 26, 37] maximise a lower
bound on the marginal data likelihood (otherwise known as the ELBO). With the
bits-back coding framework [38], the theoretical codelength is exactly equal
to the ELBO. However, in most cases, VAE formulations typically produce
inferior compression ratios as there exists a gap between the ELBO and the
true data likelihood.

As discussed, flow-based models [16, 25, 11], which admit exact likelihood
computation, represent an alternative route for density estimation. IDF [18]
and IDF++ [4] proposed the titular integer discrete flow to preserve the
existence and uniqueness of an invertible mapping between discrete data and
latent variables. In a similar vein, iVPF [41] achieved a mapping with volume-
preserving flows. Here the remainders of a division operation are stored as
auxiliary states to eliminate the numerical error arising from discretizing
latent variables. However, all of these models must introduce constraints on
the underlying transform, limiting their representational power. LBB [17] was
the first flow-based lossless compression approach to admit a broad class of
invertible flows based on continuous transforms. LBB established this family
of flexible bijections by introducing local bits-back coding techniques to
encode numerical errors. However, LBB typical requires the coding of many such
errors and does so with the ANS scheme, posing obvious challenges to
computational efficiency.

##  6 Conclusions and Discussions

In this paper, we have proposed iFlow, a numerically invertible flow-based
model for achieving efficient lossless compression with state-of-the-art
compression ratios. To achieve this, we have introduced the Modular Scale
Transform and Uniform Base Conversion Systems, which jointly permit an
efficient bijection between discrete data and latent variables. Experiments
demonstrate that the codelength comes extremely close to the theoretically
minimal value, with compression achieved much faster than the next-best high-
performance scheme. Moreover, iFlow is able to achieve state-of-the-art
compression ratios on real-word image benchmarks.

We additionally consider the potential for extending iFlow. That is, recent
advances in normalizing flows have achieved improved generation performance
across various data types [28, 7, 23]. We have discussed the possible
extension to incorporate these advancements in Sec. 2.6, and consider its
application as future work. We further recognise that compression aproaches,
of which iFlow is one, present significant data privacy issues. That is, the
generative model used for compression may induce data leakage; therefore, the
codec should be treated carefully as to observe data-privacy laws.

## References

  * Agustsson and Timofte [2017] Eirikur Agustsson and Radu Timofte.  Ntire 2017 challenge on single image super-resolution: Dataset and study.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops_ , pages 126–135, 2017.
  * Alakuijala et al. [2019] Jyrki Alakuijala, Ruud van Asseldonk, Sami Boukortt, Martin Bruse, Iulia-Maria Comsa, Moritz Firsching, Thomas Fischbacher, Evgenii Kliuchnikov, Sebastian Gomez, Robert Obryk, et al.  Jpeg xl next-generation image compression architecture and coding tools.  In _Applications of Digital Image Processing XLII_ , volume 11137, page 111370K. International Society for Optics and Photonics, 2019.
  * Behrmann et al. [2020] Jens Behrmann, Paul Vicol, Kuan-Chieh Wang, Roger Grosse, and Jörn-Henrik Jacobsen.  Understanding and mitigating exploding inverses in invertible neural networks.  _arXiv preprint arXiv:2006.09347_ , 2020.
  * Berg et al. [2020] Rianne van den Berg, Alexey A Gritsenko, Mostafa Dehghani, Casper Kaae Sønderby, and Tim Salimans.  Idf++: Analyzing and improving integer discrete flows for lossless compression.  _arXiv preprint arXiv:2006.12459_ , 2020.
  * Boutell and Lane [1997] Thomas Boutell and T Lane.  Png (portable network graphics) specification version 1.0.  _Network Working Group_ , pages 1–102, 1997.
  * Cao et al. [2020] Sheng Cao, Chao-Yuan Wu, and Philipp Krähenbühl.  Lossless image compression through super-resolution.  _arXiv preprint arXiv:2004.02872_ , 2020.
  * Chen et al. [2020] Jianfei Chen, Cheng Lu, Biqi Chenli, Jun Zhu, and Tian Tian.  Vflow: More expressive generative flows with variational data augmentation.  In _International Conference on Machine Learning_ , pages 1660–1669. PMLR, 2020.
  * Child [2020] Rewon Child.  Very deep vaes generalize autoregressive models and can outperform them on images.  _arXiv preprint arXiv:2011.10650_ , 2020.
  * Collet and Turner [2016] Yann Collet and Chip Turner.  Smaller and faster data compression with zstandard.  _Facebook Code [online]_ , 2016.
  * Dinh et al. [2014] Laurent Dinh, David Krueger, and Yoshua Bengio.  Nice: Non-linear independent components estimation.  _arXiv preprint arXiv:1410.8516_ , 2014.
  * Dinh et al. [2016] Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio.  Density estimation using real nvp.  _arXiv preprint arXiv:1605.08803_ , 2016.
  * Duda [2013] Jarek Duda.  Asymmetric numeral systems: entropy coding combining speed of huffman coding with compression rate of arithmetic coding.  _arXiv preprint arXiv:1311.2540_ , 2013.
  * Forecast [2010] GMDT Forecast.  Cisco visual networking index: global mobile data traffic forecast update, 2018–2023.  _Update_ , 2018:2023, 2010.
  * Gage [1994] Philip Gage.  A new algorithm for data compression.  _C Users Journal_ , 12(2):23–38, 1994.
  * Higgins et al. [2016] Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner.  beta-vae: Learning basic visual concepts with a constrained variational framework.  2016\.
  * Ho et al. [2019a] Jonathan Ho, Xi Chen, Aravind Srinivas, Yan Duan, and Pieter Abbeel.  Flow++: Improving flow-based generative models with variational dequantization and architecture design.  _arXiv preprint arXiv:1902.00275_ , 2019a.
  * Ho et al. [2019b] Jonathan Ho, Evan Lohn, and Pieter Abbeel.  Compression with flows via local bits-back coding.  In _Advances in Neural Information Processing Systems_ , pages 3879–3888, 2019b.
  * Hoogeboom et al. [2019] Emiel Hoogeboom, Jorn Peters, Rianne van den Berg, and Max Welling.  Integer discrete flows and lossless compression.  In _Advances in Neural Information Processing Systems_ , pages 12134–12144, 2019.
  * Hoogeboom et al. [2020] Emiel Hoogeboom, Taco S Cohen, and Jakub M Tomczak.  Learning discrete distributions by dequantization.  _arXiv preprint arXiv:2001.11235_ , 2020.
  * Huang et al. [2018] Chin-Wei Huang, David Krueger, Alexandre Lacoste, and Aaron Courville.  Neural autoregressive flows.  In _Proceedings of the 35th International Conference on Machine Learning_ , volume 80, pages 2078–2087. PMLR, 2018.
  * Huffman [1952] David A Huffman.  A method for the construction of minimum-redundancy codes.  _Proceedings of the IRE_ , 40(9):1098–1101, 1952\.
  * Jun et al. [2020] Heewoo Jun, Rewon Child, Mark Chen, John Schulman, Aditya Ramesh, Alec Radford, and Ilya Sutskever.  Distribution augmentation for generative modeling.  In _International Conference on Machine Learning_ , pages 5006–5019. PMLR, 2020.
  * Kim et al. [2020] Hyeongju Kim, Hyeonseung Lee, Woo Hyun Kang, Joun Yeop Lee, and Nam Soo Kim.  Softflow: Probabilistic framework for normalizing flow on manifolds.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Kingma and Welling [2013] Diederik P Kingma and Max Welling.  Auto-encoding variational bayes.  _arXiv preprint arXiv:1312.6114_ , 2013.
  * Kingma and Dhariwal [2018] Durk P Kingma and Prafulla Dhariwal.  Glow: Generative flow with invertible 1x1 convolutions.  In _Advances in neural information processing systems_ , pages 10215–10224, 2018.
  * Kingma et al. [2019] Friso H Kingma, Pieter Abbeel, and Jonathan Ho.  Bit-swap: Recursive bits-back coding for lossless compression with hierarchical latent variables.  _arXiv preprint arXiv:1905.06845_ , 2019.
  * Kumar et al. [2019] Manoj Kumar, Mohammad Babaeizadeh, Dumitru Erhan, Chelsea Finn, Sergey Levine, Laurent Dinh, and Durk Kingma.  Videoflow: A flow-based generative model for video.  _arXiv preprint arXiv:1903.01434_ , 2(5), 2019.
  * Lippe and Gavves [2020] Phillip Lippe and Efstratios Gavves.  Categorical normalizing flows via continuous transformations.  _arXiv preprint arXiv:2006.09790_ , 2020.
  * MacKay and Mac Kay [2003] David JC MacKay and David JC Mac Kay.  _Information theory, inference and learning algorithms_.  Cambridge university press, 2003.
  * Mentzer et al. [2019] Fabian Mentzer, Eirikur Agustsson, Michael Tschannen, Radu Timofte, and Luc Van Gool.  Practical full resolution learned lossless image compression.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 10629–10638, 2019.
  * Mentzer et al. [2020] Fabian Mentzer, Luc Van Gool, and Michael Tschannen.  Learning better lossless compression using lossy compression.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 6638–6647, 2020.
  * Prenger et al. [2019] Ryan Prenger, Rafael Valle, and Bryan Catanzaro.  Waveglow: A flow-based generative network for speech synthesis.  In _ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 3617–3621. IEEE, 2019.
  * Rabbani [2002] Majid Rabbani.  Jpeg2000: Image compression fundamentals, standards and practice.  _Journal of Electronic Imaging_ , 11(2):286, 2002\.
  * Roelofs and Koman [1999] Greg Roelofs and Richard Koman.  _PNG: the definitive guide_.  O’Reilly & Associates, Inc., 1999.
  * Salimans et al. [2017] Tim Salimans, Andrej Karpathy, Xi Chen, and Diederik P Kingma.  Pixelcnn++: Improving the pixelcnn with discretized logistic mixture likelihood and other modifications.  _arXiv preprint arXiv:1701.05517_ , 2017.
  * Sneyers and Wuille [2016] Jon Sneyers and Pieter Wuille.  Flif: Free lossless image format based on maniac compression.  In _2016 IEEE International Conference on Image Processing (ICIP)_ , pages 66–70. IEEE, 2016.
  * Townsend et al. [2019a] James Townsend, Thomas Bird, Julius Kunze, and David Barber.  Hilloc: Lossless image compression with hierarchical latent variable models.  _arXiv preprint arXiv:1912.09953_ , 2019a.
  * Townsend et al. [2019b] James Townsend, Tom Bird, and David Barber.  Practical lossless compression with latent variables using bits back coding.  _arXiv preprint arXiv:1901.04866_ , 2019b.
  * Van den Oord et al. [2016] Aaron Van den Oord, Nal Kalchbrenner, Lasse Espeholt, Oriol Vinyals, Alex Graves, et al.  Conditional image generation with pixelcnn decoders.  In _Advances in neural information processing systems_ , pages 4790–4798, 2016.
  * Witten et al. [1987] Ian H Witten, Radford M Neal, and John G Cleary.  Arithmetic coding for data compression.  _Communications of the ACM_ , 30(6):520–540, 1987\.
  * Zhang et al. [2021] Shifeng Zhang, Chen Zhang, Ning Kang, and Zhenguo Li.  ivpf: Numerical invertible volume preserving flow for efficient lossless compression.  _arXiv preprint arXiv:2103.16211_ , 2021.

##  Appendix A Proofs

###  A.1 Correctness of MST (Alg. 1)

As $\bar{x},\bar{z}$ are quantized to $k$-precision, $\hat{x}$ and $\bar{x}$
form a bijection, and so do $\hat{z}$ and $\bar{z}$. Thus MST is correct if
and only if $\hat{x}$ and $\hat{z}$ are valid bijections. In particular,
denoting
$\hat{x}^{d}=\lfloor(S\cdot\hat{z}+r_{e})/R\rfloor,r_{d}^{d}=(S\cdot\hat{z}+r_{e})\mod
R$, we will show $\hat{x}^{d}\equiv\hat{x},r_{d}^{d}\equiv r_{d}$.

In fact, according to forward MST,
$\hat{z}=\lfloor(R\cdot\hat{x}+r_{d})/S\rfloor,r_{e}=(R\cdot\hat{x}+r_{d})\mod
S$, thus $S\cdot\hat{z}+r_{e}=R\cdot\hat{x}+r_{d}$. Considering $r_{e}$ is
first accurately decoded by inverse MST (in Line 2), it is clear that
$\hat{x}^{d}=\lfloor(S\cdot\hat{z}+r_{e})/R\rfloor=\lfloor(R\cdot\hat{x}+r_{d})/R\rfloor=\hat{x}$,
and $r_{d}^{d}=(S\cdot\hat{z}+r_{e})\mod R=(R\cdot\hat{x}+r_{d})\mod R=r_{d}$.
Thus the correctness of MST is proven.

###  A.2 Propositions 1-2 in MST (Alg. 1)

Firstly, as $S\cdot a-0.5\leq R<S\cdot a+0.5$, we have
$|a-\frac{R}{S}|\leq\frac{0.5}{S}=O(S^{-1})$. Secondly, as
$\bar{z}=\lfloor(R\cdot 2^{k}\cdot\bar{x}+r_{d})/S\rfloor/2^{k}$ where
$r_{d}\in[0,R)$, we have $\bar{z}<(R\cdot 2^{k}\cdot\bar{x}+R)/(S\cdot
2^{k})=R/S\cdot\bar{x}+(R-1)/(S\cdot 2^{k})$ and $\bar{z}>(R\cdot
2^{k}\cdot\bar{x}/S-1)/2^{k}=R/S\cdot\bar{x}-2^{-k}$, thus
$|\bar{z}-R/S\cdot\bar{x}|<O(2^{-k})$. Then the error between $\bar{z}$ and
$f(\bar{x})$ is
$|\bar{z}-a\cdot\bar{x}|\leq|\bar{z}-R/S\cdot\bar{x}|+|(a-R/S)\cdot\bar{x}|=O(S^{-1},2^{-k})$;
therefore, Proposition 1 holds.

For Proposition 2, decoding from $U(0,R)$ involves $-\log R$ bits, and
encoding $U(0,S)$ involves $\log S$ bits. As $|a-R/S|<O(S^{-1})$ and
$f^{\prime}(\bar{x})=a$, the codelength of MST is $L_{f}(\bar{x},\bar{z})=\log
S-\log
R=-\log|a+O(S^{-1})|=-\log|f^{\prime}(\bar{x})|+O(S^{-1})\approx-\log|f^{\prime}(\bar{x})|$.
Thus Proposition 2 holds.

###  A.3 Correctness of our Invertible Non-linear Flows (Alg. 2)

If the interpolation interval $[\bar{x}_{l},\bar{x}_{h})$ and
$[\bar{z}_{l},\bar{z}_{h})(\bar{z}_{l}=\overline{f(\bar{x}_{l})},\bar{z}_{l}=\overline{f(\bar{x}_{h})})$
are identical in both the forward and inverse processes, $f_{inp}$ is
additionally identical in both the forward and inverse processes.
Consequently, an exact bijection with MST algorithm is trivially achieved.
Thus we principally seek to show that the interpolation interval can be
correctly determined. Before the proof, it must be emphasised that the
interpolation interval should demonstrate the following properties:

  1. 1.

The interpolation interval is counted and covers the domain/co-domain.
$\bar{x}_{l},\bar{x}_{h}$ must be within the discretized set such that
$\bar{x}_{l},\bar{x}_{h}\in\mathcal{X}_{inp}$ (e.g.
$\mathcal{X}_{inp}=\\{2^{-h}\cdot n,n\in\mathbb{Z}\\}$);

  2. 2.

The interpolation interval must be not intersected. There does not exist $x$
such that $x\in[\bar{x}_{l},\bar{x}_{h})$ and
$x\in\mathcal{X}_{inp}\setminus\\{\bar{x}_{l}\\}$.

Firstly, we show that in the forward computation, $\bar{z}$ will always be
within $[\bar{z}_{l},\bar{z}_{h})$. In fact, $\bar{z}=\lfloor\frac{R\cdot
2^{k}(\bar{x}-\bar{x}_{l})+r_{d}}{S}\rfloor/2^{k}+\bar{z}_{l}$ where
$r_{d}\in[0,R)$. As $\bar{x}\geq\bar{x}_{l}$, $\bar{z}\geq\lfloor\frac{R\cdot
0+0}{S}\rfloor/2^{k}+\bar{z}_{l}=\bar{z}_{l}$. As
$\bar{x}\leq\bar{x}_{h}-2^{-k}$, $\bar{z}\leq\lfloor\frac{R\cdot
2^{k}(\bar{x}_{h}-\bar{x}_{l}-2^{-k})+R-1}{S}\rfloor/2^{k}+\bar{z}_{l}$,
following from Eq. (4) it is clear that $\bar{z}\leq\bar{z}_{h}-2^{-k}$.
Therefore, it holds that $\bar{z}\in[\bar{z}_{l},\bar{z}_{h})$.

Secondly, we show that during the inverse computation, the interpolation
intervals $[\bar{x}_{l},\bar{x}_{h})$ and $[\bar{z}_{l},\bar{z}_{h})$ are the
same as that in the forward process. In other words, if the interpolation
interval is
$[\bar{x}_{l}^{d},\bar{x}_{h}^{d}),[\bar{z}_{l}^{d},\bar{z}_{h}^{d})$ given
$\bar{z}$, it holds that
$\bar{x}_{l}^{d}\equiv\bar{x}_{l},\bar{x}_{h}^{d}\equiv\bar{x}_{h}$. In fact,
$\bar{x}_{l}^{d}\geq\bar{x}_{h}$ is not preserved, as
$\overline{f(\bar{x}_{l}^{d})}\geq\bar{z}$. It then follows that $\bar{z}$
could not be in $[\bar{z}_{l}^{d},\bar{z}_{h}^{d})$. Similarly,
$\bar{x}_{h}\leq\bar{x}_{l}$ is not preserved – otherwise
$\overline{f(\bar{x}_{h}^{d})}\leq\bar{z}$ and $\bar{z}$ could not be in
$[\bar{z}_{l}^{d},\bar{z}_{h}^{d})$. Overall, $\bar{x}_{l}^{d}<\bar{x}_{h}$
and $\bar{x}_{h}^{d}>\bar{x}_{l}$, such that only
$\bar{x}_{l}^{d}=\bar{x}_{l},\bar{x}_{h}^{d}=\bar{x}_{h}$ satisfy this
condition.

###  A.4 Propositions 1-2 in Invertible Non-linear Flows (Alg. 2)

In general, $f^{\prime}(x),f^{\prime\prime}(x)$ is bounded for all $x$.
Consider $f(\bar{x})$ in the small interval such that
$\bar{x}_{h}-\bar{x}_{l}\leq 2^{-h}$ or $\bar{z}_{h}-\bar{z}_{l}\leq 2^{-h}$
($k\gg h$). We first prove the following two propositions in
$[\bar{x}_{l},\bar{x}_{h})$:

  1. 1.

$|f^{\prime}(\bar{x})-\frac{\bar{z}_{h}-\bar{z}_{l}}{\bar{x}_{h}-\bar{x}_{l}}|<O(2^{-h},2^{h-k})$;

  2. 2.

$|f_{inp}(\bar{x})-f(\bar{x})|<O(2^{-2h},2^{-k})$

In fact, by performing the Taylor expansion at $\bar{x}$, we have
$f(\bar{x}_{l})=f(\bar{x})+(\bar{x}_{l}-\bar{x})\cdot
f^{\prime}(\bar{x})+\frac{(\bar{x}_{l}-\bar{x})^{2}}{2}\cdot
f^{\prime\prime}(\xi_{l})$ and
$f(\bar{x}_{h})=f(\bar{x})+(\bar{x}_{h}-\bar{x})\cdot
f^{\prime}(\bar{x})+\frac{(\bar{x}_{h}-\bar{x})^{2}}{2}\cdot
f^{\prime\prime}(\xi_{h})$, where
$\xi_{h},\xi_{l}\in(\bar{x}_{l},\bar{x}_{h})$.

Firstly, $f(\bar{x}_{h})-f(\bar{x}_{l})=(\bar{x}_{h}-\bar{x}_{l})\cdot
f^{\prime}(x)+[\frac{(\bar{x}_{h}-\bar{x})^{2}}{2}\cdot
f^{\prime\prime}(\xi_{h})-\frac{(\bar{x}_{l}-\bar{x})^{2}}{2}\cdot
f^{\prime\prime}(\xi_{l})]$. As $f^{\prime}(x),f^{\prime\prime}(x)$ are
bounded, $\bar{x}_{h}-\bar{x}_{l}\leq O(2^{-h})$, and we have
$f(\bar{x}_{h})-f(\bar{x}_{l})=(\bar{x}_{h}-\bar{x}_{l})\cdot
f^{\prime}(x)+O(2^{-2h})$. As
$|\bar{z}_{l}-f(\bar{x}_{l})|<2^{-k},|\bar{z}_{l}-f(\bar{x}_{l})|<2^{-k}$,
then $|\bar{z}_{h}-\bar{z}_{l}-(\bar{x}_{h}-\bar{x}_{l})\cdot
f^{\prime}(x)|<O(2^{-k},2^{-2h})$. Finally,
$|f^{\prime}(\bar{x})-\frac{\bar{z}_{h}-\bar{z}_{l}}{\bar{x}_{h}-\bar{x}_{l}}|<O(2^{-h},2^{h-k})$.

Secondly, by denoting
$g(\bar{x})=\frac{f(\bar{x}_{h})-f(\bar{x}_{l})}{\bar{x}_{h}-\bar{x}_{l}}(\bar{x}-\bar{x}_{l})+f(\bar{x}_{l})$
and replacing $f(\bar{x}_{l}),f(\bar{x}_{h})$ with its Taylor expansion, we
have
$g(\bar{x})=f(\bar{x})+\frac{1}{2(\bar{x}_{h}-\bar{x}_{l})}(\bar{x}_{h}-\bar{x})(\bar{x}-\bar{x}_{l})[(\bar{x}_{h}-\bar{x})f^{\prime\prime}(\xi_{h})+(\bar{x}-\bar{x}_{l})f^{\prime\prime}(\xi_{l})]$.
As $f^{\prime\prime}(x)$ is bounded, $|g(\bar{x})-f(\bar{x})|<O(2^{-2h})$.
Moreover, it is clear that $|f_{inp}(\bar{x})-g(\bar{x})|<O(2^{-k})$, and as
such it finally holds that $|f_{inp}(\bar{x})-f(\bar{x})|<O(2^{-2h},2^{-k})$.

For Proposition 1, with MST, we have $\bar{z}-\bar{z}_{l}=\lfloor\frac{R\cdot
2^{k}\cdot(\bar{x}-\bar{x}_{l})+r_{d}}{S}\rfloor/2^{k}$ where $r_{d}\in[0,R)$,
thus $|\bar{z}-\bar{z}_{l}-\frac{R}{S}\cdot(\bar{x}-\bar{x}_{l})|<O(2^{-k})$.
Moreover, with Eq. (4), it is easy to arrive at that
$\frac{\bar{z}_{h}-\bar{z}_{l}-2^{-k}(1-S^{-1})}{\bar{x}_{h}-\bar{x}_{l}}-S^{-1}<\frac{R}{S}\leq\frac{\bar{z}_{h}-\bar{z}_{l}-2^{-k}(1-S^{-1})}{\bar{x}_{h}-\bar{x}_{l}}$,
and therefore
$|\frac{R}{S}-\frac{\bar{z}_{h}-\bar{z}_{l}}{\bar{x}_{h}-\bar{x}_{l}}|<O(S^{-1},2^{h-k})$.
Overall,
$|\bar{z}-f_{inp}(\bar{x})|=|(\bar{z}-\bar{z}_{l}-\frac{R}{S}\cdot(\bar{x}-\bar{x}_{l}))+((\frac{R}{S}-\frac{\bar{z}_{h}-\bar{z}_{l}}{\bar{x}_{h}-\bar{x}_{l}})\cdot(\bar{x}-\bar{x}_{l}))|<O(S^{-1},2^{-k})$,
and finally
$|\bar{z}-f(\bar{x})|\leq|\bar{z}-f_{inp}(\bar{x})|+|f_{inp}(\bar{x})-f(\bar{x})|<O(S^{-1},2^{-k},2^{-2h})$.

For Proposition 2, with
$|\frac{R}{S}-\frac{\bar{z}_{h}-\bar{z}_{l}}{\bar{x}_{h}-\bar{x}_{l}}|<O(S^{-1},2^{h-k})$,
it is clear that the expected codelength is
$L_{f}(\bar{x},\bar{z})=-\log(R/S)=-\log\frac{\bar{z}_{h}-\bar{z}_{l}}{\bar{x}_{h}-\bar{x}_{l}}+O(S^{-1},2^{h-k})=-\log|f^{\prime}(\bar{x})|+O(S^{-1},2^{h-k},2^{-h})$.
Overall, $L_{f}(\bar{x},\bar{z})\approx-\log|f^{\prime}(\bar{x})|$ if $S,k,h$
are large and $k\gg h$.

###  A.5 Theorem 3 in UBCS (Alg. 5)

P1. We begin by showing that $c_{i}\in[2^{M},2^{K+M)}$ for all $i=0,...,n$
with mathematical induction. In fact, when $i=0$,
$c_{0}=2^{M}\in[2^{M},2^{K+M})$. When $i=k$ and $c_{k}\in[2^{M},2^{K+M})$,
denote $c_{k+1}^{\circ}=c_{k}\cdot R_{k+1}+s_{k+1}$. It is therefore clear
that $c_{k+1}^{\circ}=[2^{M}\cdot R_{k+1},2^{M+K}\cdot R_{k+1})$. Note that
$R_{k+1}<2^{K}$ and therefore $2^{M}\cdot R_{k+1}<2^{M+K}$. If
$c_{k+1}^{\circ}<2^{K+M}$, $c_{k+1}=c_{k+1}^{\circ}\in[2^{M}\cdot
R_{k+1},2^{M+K})$, it follows that $c_{k+1}^{\circ}\geq 2^{K+M}$,
$c_{k+1}=\lfloor c_{k+1}^{\circ}/2^{K}\rfloor\in[2^{M},2^{K}\cdot R_{k+1})$.
Overall, $c_{k+1}\in[2^{M},2^{K+M})$. Thus $c_{i}\in[2^{M},2^{K+M})$ for all
$i=1,...,n$ such that

$c_{i}=\begin{cases}c_{i-1}\cdot R_{i}+s_{i}\in[2^{M}\cdot
R_{i},2^{K+M}),&c_{i-1}\cdot R_{i}+s_{i}<2^{K+M}\\\ \lfloor\frac{c_{i-1}\cdot
R_{i}+s_{i}}{2^{K}}\rfloor\in[2^{M},2^{M}\cdot R_{i}),&c_{i-1}\cdot
R_{i}+s_{i}\geq 2^{K+M}\\\ \end{cases}$ (10)

We will now demonstrate that
$s^{\prime}_{i}=s_{i+1},c^{\prime}_{i}=c_{i},\texttt{bs}^{\prime}_{i}=\texttt{bs}_{i}$
for all $i=0,...,n-1$. Denote $c_{i}^{\circ}=c_{i-1}\cdot R_{i}+s_{i}$.

(i) Consider $i=n-1$. (a) If $c_{n}<2^{M}\cdot R_{n}$, the last $K$ bits
(denoted by $r_{n}$) will be popped from $\texttt{bs}_{n}$ and added to
$c_{n}$. In this case, according to Eq. (10), $r_{n}=\lfloor c_{n}^{\circ}\mod
2^{K}\rfloor$ must be encoded to form $\texttt{bs}_{n}$. Thus in the decoding
process, $r_{n}$ is popped from $\texttt{bs}_{n}$, and therefore
$\texttt{bs}^{\prime}_{n-1}=\texttt{bs}_{n-1}$,
$c^{\prime}_{n-1}=\lfloor(2^{K}\cdot c_{n}+r_{n})/R_{n}\rfloor=\lfloor
c_{n-1}^{\circ}/R_{n}\rfloor=\lfloor(c_{n-1}\cdot
R_{n}+s_{n-1})/R_{n}\rfloor=c_{n-1}$, and $s^{\prime}_{n-1}=(2^{K}\cdot
c_{n}+r_{n})\mod R_{n}=(c_{n-1}\cdot R_{n}+s_{n-1})\mod R_{n}=s_{n-1}$. (b) If
$c_{n}\geq 2^{M}\cdot R$, no bits are popped from $\texttt{bs}_{n}$ such that
$\texttt{bs}^{\prime}_{n-1}=\texttt{bs}_{n}$. In this case, according to Eq.
(10), no bits are pushed to $\texttt{bs}_{n-1}$ and therefore
$\texttt{bs}_{n-1}=\texttt{bs}_{n}=\texttt{bs}^{\prime}_{n-1}$. In the
decoding process, $c^{\prime}_{n-1}=\lfloor
c_{n-1}^{\circ}/R_{n}\rfloor=c_{n-1},s^{\prime}_{n-1}=c_{n-1}^{\circ}\mod
R_{n}=s^{\prime}_{n-1}$. Overall, P1 holds for $i=n-1$.

(ii) If P1 holds for $i=k$, we will prove that P1 holds for $i=k-1$. (a) If
$c^{\prime}_{k}<2^{M}\cdot R_{k}$, the last $K$ bits will be popped from
$\texttt{bs}^{\prime}_{k}$ and added to $c^{\prime}_{k}$. In this case, in the
encoding process, as $c_{k}=c^{\prime}_{k}$, according to Eq. (10),
$r_{k}=\lfloor c_{k}^{\circ}\mod 2^{K}\rfloor$ must be encoded to form
$\texttt{bs}_{k}$ to obtain $c_{k}$. In the decoding process, as
$\texttt{bs}^{\prime}_{k}=\texttt{bs}_{k}$, $r_{k}$ is popped from
$\texttt{bs}^{\prime}_{k}$ in the decoding process, it is therefore seen that
$\texttt{bs}^{\prime}_{k-1}=\texttt{bs}_{k-1}$. Finally we obtain
$c^{\prime}_{k-1}=\lfloor(2^{K}\cdot
c^{\prime}_{k}+r_{k})/R_{k}\rfloor=\lfloor(2^{K}\cdot
c_{k}+r_{k})/R_{k}\rfloor=\lfloor c_{k-1}^{\circ}/R_{k}\rfloor=c_{k-1}$, and
$s^{\prime}_{k-1}=(2^{K}\cdot c^{\prime}_{k}+r_{k})\mod R_{k}=(c_{k-1}\cdot
R_{n}+s_{k-1})\mod R_{n}=s_{k-1}$. (b) If $c^{\prime}_{k}\geq 2^{M}\cdot R$,
no bits are popped from $\texttt{bs}^{\prime}_{k}$ such that
$\texttt{bs}^{\prime}_{k-1}=\texttt{bs}^{\prime}_{k}$. In this case, in the
encoding process, as $c^{\prime}_{k}=c_{k}$, according to Eq. (10), no bits
are pushed to $\texttt{bs}_{k-1}$ to obtain $c_{k}$ and therefore
$\texttt{bs}_{k-1}=\texttt{bs}_{k}=\texttt{bs}^{\prime}_{k}=\texttt{bs}^{\prime}_{k-1}$.
In the decoding process, we have
$c^{\prime}_{k-1}=\lfloor(c^{\prime}_{k-1}\cdot
R_{k}+s_{k-1})/R_{k}\rfloor=\lfloor
c_{k-1}^{\circ}/R_{k}\rfloor=c_{k-1},s^{\prime}_{k-1}=(c^{\prime}_{k-1}\cdot
R_{k}+s_{k-1})\mod R_{k}=s_{k-1}$. Overall, P1 holds for $i=k-1$.

From (i)(ii), it is concluded that P1 holds by proof of mathematical
induction.

P2. Denote that the lower $K$ bits of $c_{i}$ need to be push to
$\texttt{bs}_{i}$ at $i=m_{1},...,m_{T}$
$(m_{t}<m_{t+1},m_{t}\in\\{1,...,n-1\\}$ for all $t=1,...,T-1$). In other
words, we have

$c_{i}=\begin{cases}\lfloor\frac{c_{i-1}\cdot
R_{i}+s_{i}}{2^{K}}\rfloor,&i\in\\{m_{1},...,m_{T}\\}\\\ c_{i-1}\cdot
R_{i}+s_{i},&otherwise\\\ \end{cases}$ (11)

Firstly, it is clear that
$\texttt{len(bs}_{m_{t+1}}\texttt{)}=\texttt{len(bs}_{m_{t}}\texttt{)}+K$.
Secondly, for any $i\in\\{m_{t}+1,...,m_{t+1}-1\\}$, as $c_{i}=c_{i-1}\cdot
R_{i}+s_{i},s_{i}\in[0,R_{i})$, it is clear that $c_{i-1}\cdot R_{i}\leq
c_{i}\leq c_{i-1}\cdot R_{i}+R_{i}-1$. Thus
$c_{m_{t}}\cdot\prod_{i=m_{t}+1}^{m_{t+1}-1}R_{i}\leq
c_{m_{t+1}-1}\leq(c_{m_{t}}+1)\cdot\prod_{i=m_{t}+1}^{m_{t+1}-1}R_{i}-1$, and
therefore

$\big{\lfloor}\frac{c_{m_{t}}\cdot\prod_{i=m_{t}+1}^{m_{t+1}}R_{i}}{2^{K}}\big{\rfloor}\leq
c_{m_{t+1}}\leq\big{\lfloor}\frac{(c_{m_{t}}+1)\cdot\prod_{i=m_{t}+1}^{m_{t+1}}R_{i}-1}{2^{K}}\big{\rfloor}.$
(12)

Note that the above inequality also holds for $t=0$ in which $m_{0}=0$. With
Eq. (12), $\log
c_{m_{t+1}}\leq\log\big{\lfloor}\frac{(c_{m_{t}}+1)\cdot\prod_{i=m_{t}+1}^{m_{t+1}}R_{i}-1}{2^{K}}\big{\rfloor}<\log\big{(}\frac{(c_{m_{t}}+1)\cdot\prod_{i=m_{t}+1}^{m_{t+1}}R_{i}}{2^{K}}\big{)}=\log
c_{m_{t}}+\sum_{i=m_{t}+1}^{m_{t+1}}\log R_{i}+\log(1+c_{m_{t}}^{-1})-K<\log
c_{m_{t}}+\sum_{i=m_{t}+1}^{m_{t+1}}\log R_{i}+(\ln 2\cdot c_{m_{t}})^{-1}-K$.
As $c_{m_{t}}\in[2^{M},2^{M}\cdot R_{m_{t}})$, it holds that

$\log c_{m_{t+1}}+\texttt{len(bs}_{m_{t+1}}\texttt{)}<\log
c_{m_{t}}+\texttt{len(bs}_{m_{t}}\texttt{)}+\sum_{i=m_{i}+1}^{m_{t+1}}\log
R_{i}+(\ln 2\cdot 2^{M})^{-1}$ (13)

If $m_{T}=n$, $\log c_{n}+\texttt{len(bs}_{n}\texttt{)}=\log
c_{m_{T}}+\texttt{len(bs}_{m_{T}}\texttt{)}$; otherwise,
$\texttt{len(bs}_{n}\texttt{)}=\texttt{len(bs}_{m_{T}}\texttt{)}$ and $\log
c_{n}\leq\log(c_{m_{T}}+1)+\sum_{i=m_{T}+1}^{n}R_{i}<\log
c_{m_{T}}+\sum_{i=m_{T}+1}^{n}R_{i}+(\ln 2\cdot 2^{M})^{-1}$. Overall, we
finally obtain

$\log c_{n}+\texttt{len(bs}_{n}\texttt{)}<\log
c_{0}+\texttt{len(bs}_{0}\texttt{)}+\sum_{i=1}^{n}\log R_{i}+(T+1)\cdot(\ln
2\cdot 2^{M})^{-1}$ (14)

Note that as $c_{n}\geq 2^{M}=c_{0},\texttt{len(bs}_{n}\texttt{)}=TK$ and
$l_{0}=M=\log c_{0}+\texttt{len(bs}_{0}\texttt{)}$, it is clear that $\log
c_{n}+\texttt{len(bs}_{n}\texttt{)}>TK+l_{0}$. With Eq. (14), the codelength
is finally computed as

$l_{n}-l_{0}\leq\log
c_{n}+\texttt{len(bs}_{n}\texttt{)}-l_{0}+1<\frac{1}{1-1/(\ln 2\cdot
2^{M}\cdot K)}\big{[}\sum_{i=1}^{n}R_{i}+1+(\ln 2\cdot 2^{M})^{-1}\big{]}$
(15)

which completes the proof.

##  Appendix B Details of Alg. 2 in iFlow

The main difficulty is in determining the interpolation interval
$[\bar{x}_{l},\bar{x}_{h}),[\bar{z}_{l},\bar{z}_{h})$ given $\bar{x}$ or
$\bar{z}$. The main paper discusses two interpolation tricks: (1)
interpolating uniform intervals in domain $x$ and (2) interpolating uniform
intervals in co-domain $z$.

Algorithm 6 Uniform interpolating interval $x$ in numerically invertible
element-wise flows.

Determine $\bar{x}_{l},\bar{x}_{h},\bar{z}_{l},\bar{z}_{h}$ given $\bar{x}$.

1:
$\bar{x}_{l}=\lfloor(2^{h}\cdot\bar{x})/2^{h}\rfloor,\bar{x}_{h}=\bar{x}_{l}+2^{-h}$;

2:
$\bar{z}_{l}=\overline{f(\bar{x}_{l})},\bar{z}_{h}=\overline{f(\bar{x}_{h})}$;

3: return $\bar{x}_{l},\bar{x}_{h},\bar{z}_{l},\bar{z}_{h}$.

Determine $\bar{x}_{l},\bar{x}_{h},\bar{z}_{l},\bar{z}_{h}$ given $\bar{z}$.

1: $x^{\prime}=f^{-1}(\bar{z})$;

2: $\bar{x}^{\prime}_{m}=\mathrm{round}(2^{h}\cdot
x^{\prime})/2^{h},\bar{x}^{\prime}_{l}=\bar{x}^{\prime}_{m}-2^{-h},\bar{x}^{\prime}_{h}=\bar{x}^{\prime}_{m}+2^{-h}$;

3:
$\bar{z}^{\prime}_{\\{l,m,h\\}}=\overline{f(\bar{x}^{\prime}_{\\{l,m,h\\}})}$;

4: if $\bar{z}<\bar{z}^{\prime}_{m}$ then

5:
$\bar{x}_{l}=\bar{x}^{\prime}_{l},\bar{x}_{h}=\bar{x}^{\prime}_{m},\bar{z}_{l}=\bar{z}^{\prime}_{l},\bar{z}_{h}=\bar{z}^{\prime}_{m}$;

6: else

7:
$\bar{x}_{l}=\bar{x}^{\prime}_{m},\bar{x}_{h}=\bar{x}^{\prime}_{h},\bar{z}_{l}=\bar{z}^{\prime}_{m},\bar{z}_{h}=\bar{z}^{\prime}_{h}$

8: end if

9: return $\bar{x}_{l},\bar{x}_{h},\bar{z}_{l},\bar{z}_{h}$.

Interpolating uniform intervals in $x$. This usually applies in the case that
$f^{\prime}$ is large (e.g. inverse sigmoid). The uniform interval in domain
$x$ is defined as
$\bar{x}_{l}=\lfloor(2^{h}\cdot\bar{x})/2^{h}\rfloor,\bar{x}_{h}=\bar{x}_{l}+2^{-h}$.
The corresponding interval in the co-domain is
$\bar{z}_{l}=\overline{f(\bar{x}_{l})},\bar{z}_{h}=\overline{f(\bar{x}_{h})}$.
For the forward pass, given $\bar{x}$, the interval can be obtained as above.
For the inverse pass, we first compute $x^{\prime}=f^{-1}(\bar{z})$ and then
compute $\bar{x}^{\prime}_{m}=\mathrm{round}(2^{h}\cdot
x^{\prime})/2^{h},\bar{x}^{\prime}_{l}=\bar{x}^{\prime}_{m}-2^{-h},\bar{x}^{\prime}_{h}=\bar{x}^{\prime}_{m}+2^{-h}$.
Finally, we have
$\bar{z}_{\\{l,m,h\\}}=\overline{f(\bar{x}^{\prime}_{\\{l,m,h\\}})}$. If
$\bar{z}<\bar{z}_{m}$, we set the interval
$\bar{x}_{l}=\bar{x}^{\prime}_{l},\bar{x}_{h}=\bar{x}^{\prime}_{m}$; otherwise
$\bar{x}_{l}=\bar{x}^{\prime}_{m},\bar{x}_{h}=\bar{x}^{\prime}_{h}$. The
method is summarized in Alg. 6.

The correctness of the algorithm is guaranteed provided that $f$ is Lipchitz
continuous and the numerical error between $f^{-1}(f(\bar{x}))$ and $x$ is
limited. Let $|f^{-1}(f(x))-x|<\epsilon$ for all $x$ and
$|f^{-1}(x_{1})-f^{-1}(x_{2})|<\mu|x_{1}-x_{2}|$ for all $x_{1},x_{2}$. We
will show that Alg. 6 is correct if $\varepsilon=2^{-k}\mu+\epsilon<2^{-h-1}$.
In fact, it is clear that
$|f^{-1}(\bar{z}_{l})-\bar{x}_{l}|\leq|f^{-1}(\bar{z}_{l})-f^{-1}(f(\bar{x}_{l}))|+|\bar{x}_{l}-f^{-1}(f(\bar{x}_{l}))|<2^{-k}\mu+\epsilon=\varepsilon$.
Similarly, $|f^{-1}(\bar{z}_{h})-\bar{x}_{h}|<\varepsilon$. As $f^{-1}$ is
monotonically increasing and $\bar{z}\in(\bar{z}_{l},\bar{z}_{h})$, it is
clear that
$x^{\prime}=f^{-1}(\bar{z})\in[\bar{x}_{l}-\varepsilon,\bar{x}_{h}+\varepsilon)$.
As $|\bar{x}^{\prime}_{m}-x^{\prime}|\leq 2^{-h-1}$, we have
$\bar{x}^{\prime}_{m}\in(\bar{x}_{l}-\varepsilon-2^{-h-1},\bar{x}_{h}+\varepsilon+2^{-h-1})$.
(i) When $\bar{z}<\bar{z}^{\prime}_{m}$, it corresponds to
$\bar{x}<\bar{x}^{\prime}_{m}$. As $\bar{x}\in[\bar{x}_{l},\bar{x}_{h})$, it
is clear that
$\bar{x}^{\prime}_{m}\in(\bar{x}_{l},\bar{x}_{h}+\varepsilon+2^{-h-1})=(\bar{x}_{h}-2^{-h},\bar{x}_{h}+\varepsilon+2^{-h-1})$.
Note that $\bar{x}^{\prime}_{m},\bar{x}_{h}\in\\{2^{-h}\cdot
n,n\in\mathbb{Z}\\}$ when $\varepsilon<2^{-h-1}$; therefore, it must hold that
$\bar{x}^{\prime}_{m}=\bar{x}_{h}$. (ii) When
$\bar{z}\geq\bar{z}^{\prime}_{m}$, it corresponds to
$\bar{x}\geq\bar{x}^{\prime}_{m}$. It is clear that
$\bar{x}^{\prime}_{m}\in(\bar{x}_{l}-\varepsilon-2^{-h-1},\bar{x}_{h})=(\bar{x}_{l}-\varepsilon-2^{-h-1},\bar{x}_{l}+2^{-h})$
– thus it must hold that $\bar{x}^{\prime}_{m}=\bar{x}_{l}$. In fact, as $h\ll
k$, $\mu$ is bounded and $\epsilon$ is rather small, such that
$\varepsilon<2^{-h-1}$, the correctness of Alg. 6 follows.

Algorithm 7 Uniform interpolating interval $z$ in numerically invertible
element-wise flows.

Determine $\bar{x}_{l},\bar{x}_{h},\bar{z}_{l},\bar{z}_{h}$ given $\bar{x}$.

1: $z=f(\bar{z})$;

2: $\bar{z}^{\prime}_{m}=\mathrm{round}(2^{h}\cdot
z^{\prime})/2^{h},\bar{z}^{\prime}_{l}=\bar{z}^{\prime}_{m}-2^{-h},\bar{z}^{\prime}_{h}=\bar{z}^{\prime}_{m}+2^{-h}$;

3:
$\bar{x}^{\prime}_{\\{l,m,h\\}}=\overline{f^{-1}(\bar{z}^{\prime}_{\\{l,m,h\\}})}$;

4: if $\bar{x}<\bar{x}^{\prime}_{m}$ then

5:
$\bar{x}_{l}=\bar{x}^{\prime}_{l},\bar{x}_{h}=\bar{x}^{\prime}_{m},\bar{z}_{l}=\bar{z}^{\prime}_{l},\bar{z}_{h}=\bar{z}^{\prime}_{m}$;

6: else

7:
$\bar{x}_{l}=\bar{x}^{\prime}_{m},\bar{x}_{h}=\bar{x}^{\prime}_{h},\bar{z}_{l}=\bar{z}^{\prime}_{m},\bar{z}_{h}=\bar{z}^{\prime}_{h}$

8: end if

9: return $\bar{x}_{l},\bar{x}_{h},\bar{z}_{l},\bar{z}_{h}$.

Determine $\bar{x}_{l},\bar{x}_{h},\bar{z}_{l},\bar{z}_{h}$ given $\bar{z}$.

1:
$\bar{z}_{l}=\lfloor(2^{h}\cdot\bar{z})/2^{h}\rfloor,\bar{z}_{h}=\bar{z}_{l}+2^{-h}$;

2:
$\bar{x}_{l}=\overline{f^{-1}(\bar{x}_{l})},\bar{x}_{h}=\overline{f^{-1}(\bar{z}_{h})}$;

3: return $\bar{x}_{l},\bar{x}_{h},\bar{z}_{l},\bar{z}_{h}$.

Interpolating uniform intervals in $z$. This usually applies in the case that
$f^{\prime}$ is small (e.g. sigmoid). The uniform interval in co-domain $z$ is
defined as
$\bar{z}_{l}=\lfloor(2^{h}\cdot\bar{z})/2^{h}\rfloor,\bar{z}_{h}=\bar{z}_{l}+2^{-h}$.
The corresponding interval in the domain is
$\bar{x}_{l}=\overline{f^{-1}(\bar{z}_{l})},\bar{x}_{h}=\overline{f^{-1}(\bar{z}_{h})}$.
For the inverse pass given $\bar{z}$, the interval can be obtained as above.
For the forward pass, we first compute $z^{\prime}=f(\bar{x})$, and then
compute $\bar{z}^{\prime}_{m}=\mathrm{round}(2^{h}\cdot
z^{\prime})/2^{h},\bar{z}^{\prime}_{l}=\bar{z}^{\prime}_{m}-2^{-h},\bar{z}^{\prime}_{h}=\bar{z}^{\prime}_{m}+2^{-h}$,
and $\bar{x}_{\\{l,m,h\\}}=\overline{f^{-1}(\bar{z}^{\prime}_{\\{l,m,h\\}})}$.
If $\bar{x}<\bar{x}_{m}$, we set the interval
$\bar{z}_{l}=\bar{z}^{\prime}_{l},\bar{z}_{h}=\bar{z}^{\prime}_{m}$; otherwise
$\bar{z}_{l}=\bar{z}^{\prime}_{m},\bar{z}_{h}=\bar{z}^{\prime}_{h}$. The
method is summarized in Alg. 7.

Similarly as in Alg. 6, the correctness of Alg. 7 is ensured by $h\ll k$ and
the limited numerical errors. The proof is very similar as to that of Alg. 6.

##  Appendix C Extensions of iFlow

Algorithm 8 Lossless Compression with Flows.

Encode $\mathbf{x}^{\circ}$.

1: Decode $\bar{\mathbf{v}}$ using
$q(\bar{\mathbf{v}}|\mathbf{x}^{\circ})\delta$;

2: $\bar{\mathbf{z}}\leftarrow\bar{f}(\bar{\mathbf{v}})$;

3: Encode $\bar{\mathbf{z}}$ using $p_{Z}(\bar{\mathbf{z}})\delta$;

4: Encode $\mathbf{x}^{\circ}$ using $P(\mathbf{x}^{\circ}|\bar{\mathbf{v}})$.

Decode.

1: Decode $\bar{\mathbf{z}}$ using $p_{Z}(\bar{\mathbf{z}})\delta$;

2: $\bar{\mathbf{v}}\leftarrow\bar{f}^{-1}(\bar{\mathbf{z}})$;

3: Decode $\mathbf{x}^{\circ}$ using $P(\mathbf{x}^{\circ}|\bar{\mathbf{v}})$;

4: Encode $\bar{\mathbf{v}}$ using
$q(\bar{\mathbf{v}}|\mathbf{x}^{\circ})\delta$;

5: return $\mathbf{x}^{\circ}$.

The extension of iFlow for lossless compression is summarized in Alg. 8. Note
that for Variational Dequantization Flow [19, 17] (Alg. 4),
$\mathbf{v}=\mathbf{x}^{\circ}+\mathbf{u}(\mathbf{u}\in[0,1)^{d}),q(\mathbf{v}|\mathbf{x}^{\circ})=q(\mathbf{u}|\mathbf{x}^{\circ}),P(\mathbf{x}^{\circ}|\mathbf{v})=1$.
Thus the above coding procedure reduces to Alg. 4.

##  Appendix D Dynamic Uniform Entropy Coder in AC, ANS and UBCS

In this section we will demonstrate the effectiveness of UBCS compared with AC
and ANS. Both AC and ANS use probability mass function (PMF) and cumulative
distribution function (CDF) for encoding and inverse CDF for decoding. For
ease of coding, the PMF and CDF are all mapped to integers in $[0,m)$. For
uniform distribution $U(0,R)$ in which $P(s)=1/R,s\in\\{0,1,...,R-1\\}$, the
most simple way to compute PMF and CDF are

$\begin{split}l_{s}&=\mathrm{PMF}(s)=\begin{cases}\lfloor m/R\rfloor,&\quad
s<R-1\\\ m-(R-1)\cdot\lfloor m/R\rfloor,&\quad s=R-1\end{cases},\\\
b_{s}&=\mathrm{CDF}(s-1)=\lfloor m/R\rfloor\cdot s\end{split}$ (16)

Given $b\in[0,m)$, the output of inverse CDF $s=\mathrm{CDF}^{-1}(b)$, should
be exactly $b\in[b_{s},b_{s}+l_{s})$. The general way to determine
$\mathrm{CDF}^{-1}$ is binary search. But for uniform distribution, we can
directly obtain the inverse CDF such that

$s=\mathrm{CDF}^{-1}(b)=\min(\lfloor b/l\rfloor,R-1),\quad l=\lfloor
m/R\rfloor$ (17)

We summarize uniform entropy coder AC, rANS and UBCS as follows:

For AC:

  * •

Initial state: interval $[lo,hi)$;

  * •

Encoding: get $m=hi-ho$, get $l_{s},b_{s}$ with Eq. (16), update interval
$[lo^{\prime},hi^{\prime})$ such that
$lo^{\prime}=lo+b_{s},hi^{\prime}=lo^{\prime}+l_{s}$, get
$c^{\prime}\in[lo^{\prime},hi^{\prime})$ as the encoded bits;

  * •

Decoding: for encoded bits $c^{\prime}\in[lo,hi)$ and current interval
$[lo,hi)$, get $m=hi-lo,b=c^{\prime}-lo$, decode $s=\mathrm{CDF}^{-1}(b)$ with
Eq. (17), update interval $[lo^{\prime},hi^{\prime})$ such that
$lo^{\prime}=lo+b_{s},hi^{\prime}=lo^{\prime}+l_{s}$;

  * •

Number of atom operations in encoding: one division, one multiplication333We
omit add/sub operations as they are negligible compared with
multiplication/division.;

  * •

Number of atom operations in decoding: two divisions, one multiplication.
Binary search may involve if Eq. (17) is not used.

For rANS:

  * •

Initial state: number $c$;

  * •

Encoding: set $m=2^{K}$, get $l_{s},b_{s}$ with Eq. (16), update
$c^{\prime}=\lfloor c/l_{s}\rfloor\cdot m+(c\mod l_{s})+b_{s}$;

  * •

Decoding: set $m=2^{K}$, for encoded bits $c^{\prime}$, get $b=c^{\prime}\mod
m$, decode $s=\mathrm{CDF}^{-1}(b)$ with Eq. (17), update $c=l_{s}\cdot\lfloor
c^{\prime}/m\rfloor+(c^{\prime}\mod m)-b_{s}$;

  * •

Number of atom operations in encoding: two divisions, two
multiplications444The multiplication/division/mod with $m=2^{K}$ only involve
bit operations. With the result of $\lfloor c/l_{s}\rfloor$, $c\mod l_{s}$
only involve one multiplication.;

  * •

Number of atom operations in decoding: two divisions, one multiplication.
Binary search may involve if Eq. (17) is not used.

For UBCS:

  * •

Initial state: number $c$;

  * •

Encoding: update $c^{\prime}=c\cdot R+s$;

  * •

Decoding: for encoded bits $c^{\prime}$, decode $s=c^{\prime}\mod R$, update
$c=\lfloor c^{\prime}/R\rfloor$;

  * •

Number of atom operations in encoding: one multiplication;

  * •

Number of atom operations in decoding: one division with remainder.

Overall, UBCS uses the least number of atom operations, which conveys that
UBCS performs the best. Moreover, with PMF and CDF in Eq. (16), the optimal
entropy coder cannot be guaranteed.

##  Appendix E More Experiments

In this section we will demonstrate our performance attributes across more
benchmarking datasets. All experiments are conducted in PyTorch framework on
one NVIDIA Tesla P100 GPU and Intel(R) Xeon(R) CPU E5-2690 @ 2.60GHz CPU. The
code for LBB and the Flow++ model is directly taken from the original paper
under MIT license.

###  E.1 Coding Efficiency of UBCS

Table 4: More results on coding bandwidth (M symbol/s) of UBCS and rANS coder. We use the implementations in [17] for evaluating rANS. | # threads | rANS | UBCS
---|---|---|---
Encoder | 1 |  5.1$\pm$0.3 | 380$\pm$5
4 |  10.8$\pm$1.9 | 709$\pm$56
8 |  15.9$\pm$1.4 | 1297$\pm$137
16 |  21.6$\pm$1.1 | 2075$\pm$353
Decoder | 1 |  0.80$\pm$0.02 | 66.2$\pm$1.7
4 |  2.8$\pm$0.1 | 248$\pm$8
8 |  5.5$\pm$0.2 | 460$\pm$16
16 |  7.4$\pm$0.5 | 552$\pm$50
Table 5: Detailed results on the coding performance of iFlow and LBB on ImageNet32. We use a batch size of 64. flow | compression |  |  |  | encoding time (ms) | decoding time (ms)
---|---|---|---|---|---|---
arch. | technique | nll | bpd | aux. bits | inference | coding | inference | coding
Flow++ |  LBB [17] | 3.871 | 3.875 | 45.96 | 58.7$\pm$0.1 |  176$\pm$2.8 | 83.2$\pm$0.4 |  172$\pm$4.7
iFlow (Ours) | 3.873 | 34.40 | 66.6$\pm$0.3 | 95.3$\pm$0.3
Table 6: Detailed results on the coding performance of iFlow and LBB on ImageNet64. We use a batch size of 64. flow | compression |  |  |  | encoding time (ms) | decoding time (ms)
---|---|---|---|---|---|---
arch. | technique | nll | bpd | aux. bits | inference | coding | inference | coding
Flow++ |  LBB [17] | 3.701 | 3.703 | 38.00 | 24.4$\pm$0.0 |  284$\pm$2.5 | 35.7$\pm$0.1 |  281$\pm$2.2
iFlow (Ours) | 3.703 | 34.42 | 45.0$\pm$1.7 | 57.0$\pm$1.4

The detailed experiments is shown in Table 4.

###  E.2 Compression Performance

Detailed experimental results on ImageNet32 and ImageNet64 datasets are
displayed in Tables 5 and 6. Note that we further report the decoding time,
which we observe is close to the model inference time.

###  E.3 Hyper-parameters

As discussed in Sec. 2.4, the codelength will be affected by the choices of
$h,k$ and $S$. As $S$ is set to a large value – and will minimally affect the
codelength resulting from MST – we mainly discuss $h$ and $k$. Tables 7, 8 and
9 illustrate the codelength and auxiliary bits (in bpd) for differing choices
of $h$ and $k$. It is clear that, for large $k$, the codelength decreases with
a larger $h$. This is expected as larger $h$ corresponds to a greater
numerical precision of our linear interpolation. On the other hand, for a
fixed $h$, the codelength becomes larger with a smaller $k$, as a smaller $k$
corresponds to a greater quantization error. A smaller $k$ may even lead to
the failure of iFlow entirely – especially if $k$ is close to $h$, which would
result in the potential of a zero-valued $R$ in Eq. (4) for sufficiently small
$|f^{\prime}(\bar{x})|$. On the other hand, the auxiliary bits are principally
affected by $k$ and not $h$. Therefore we note that a smaller $k$ is
preferred. To conclude, we can nonetheless achieve a near-optimal codelength
with a considered choice of hyper-parameters. Thus we set $k=28$ and $h=12$
for the experiments.

Table 7: Codelengths in terms of bpd and auxiliary length on different $h$ and $k$ on the CIFAR10 dataset. N/A denotes the failure of the compression procedure. The theoretical bpd (nll) is 3.116. |  | $h$
---|---|---
|  | 6 | 8 | 10 | 12 | 14
bpd
$k$ | 18 |  3.229$\pm$0.000 | N/A | N/A | N/A | N/A
20 |  3.225$\pm$0.000 |  3.152$\pm$0.000 | N/A | N/A | N/A
22 |  3.224$\pm$0.000 |  3.147$\pm$0.000 |  3.130$\pm$0.000 | N/A | N/A
24 |  3.224$\pm$0.000 |  3.146$\pm$0.000 |  3.126$\pm$0.000 |  3.124$\pm$0.000 | N/A
26 |  3.224$\pm$0.000 |  3.146$\pm$0.000 |  3.125$\pm$0.000 |  3.119$\pm$0.000 |  3.122$\pm$0.000
28 |  3.224$\pm$0.000 |  3.146$\pm$0.000 |  3.124$\pm$0.000 |  3.118$\pm$0.000 |  3.118$\pm$0.000
30 |  3.224$\pm$0.000 |  3.146$\pm$0.000 |  3.124$\pm$0.000 |  3.118$\pm$0.000 |  3.116$\pm$0.000
32 |  3.224$\pm$0.000 |  3.146$\pm$0.000 |  3.124$\pm$0.000 |  3.118$\pm$0.000 |  3.116$\pm$0.000
auxiliary length
$k$ | 18 |  24.25$\pm$0.01 | N/A | N/A | N/A | N/A
20 |  26.25$\pm$0.01 |  26.27$\pm$0.01 | N/A | N/A | N/A
22 |  28.26$\pm$0.01 |  28.27$\pm$0.01 |  28.27$\pm$0.01 | N/A | N/A
24 |  30.25$\pm$0.01 |  30.27$\pm$0.01 |  30.27$\pm$0.01 |  30.27$\pm$0.01 | N/A
26 |  32.25$\pm$0.01 |  32.27$\pm$0.01 |  32.27$\pm$0.01 |  32.27$\pm$0.01 |  32.27$\pm$0.01
28 |  34.25$\pm$0.01 |  34.27$\pm$0.01 |  34.27$\pm$0.01 |  34.27$\pm$0.01 |  34.27$\pm$0.01
30 |  36.25$\pm$0.01 |  36.26$\pm$0.01 |  36.27$\pm$0.01 |  36.27$\pm$0.01 |  36.27$\pm$0.01
32 |  38.25$\pm$0.01 |  38.26$\pm$0.01 |  38.27$\pm$0.01 |  38.27$\pm$0.01 |  38.27$\pm$0.01
Table 8: Codelengths in terms of bpd and auxiliary length on different $h$ and $k$ on a SUBSET of ImageNet32 dataset. N/A denotes the failure of the compression procedure. The theoretical bpd (nll) is 3.883. |  | $h$
---|---|---
|  | 6 | 8 | 10 | 12 | 14
bpd
$k$ | 18 |  3.994$\pm$0.000 |  3.953$\pm$0.000 | N/A | N/A | N/A
20 |  3.985$\pm$0.000 |  3.919$\pm$0.000 | N/A | N/A | N/A
22 |  3.983$\pm$0.000 |  3.910$\pm$0.000 |  3.900$\pm$0.000 | N/A | N/A
24 |  3.983$\pm$0.000 |  3.908$\pm$0.000 |  3.892$\pm$0.000 |  3.896$\pm$0.000 |  3.928$\pm$0.000
26 |  3.983$\pm$0.000 |  3.908$\pm$0.000 |  3.890$\pm$0.000 |  3.887$\pm$0.000 |  3.894$\pm$0.000
28 |  3.983$\pm$0.000 |  3.908$\pm$0.000 |  3.889$\pm$0.000 |  3.885$\pm$0.000 |  3.886$\pm$0.000
30 |  3.982$\pm$0.000 |  3.908$\pm$0.000 |  3.889$\pm$0.000 |  3.885$\pm$0.000 |  3.884$\pm$0.000
32 |  3.983$\pm$0.000 |  3.908$\pm$0.000 |  3.889$\pm$0.000 |  3.885$\pm$0.000 |  3.884$\pm$0.000
auxiliary length
$k$ | 18 |  24.37$\pm$0.01 |  24.37$\pm$0.01 | N/A | N/A | N/A
20 |  26.38$\pm$0.01 |  26.39$\pm$0.01 | N/A | N/A | N/A
22 |  28.38$\pm$0.01 |  28.39$\pm$0.01 |  28.39$\pm$0.01 | N/A | N/A
24 |  30.38$\pm$0.01 |  30.39$\pm$0.01 |  30.40$\pm$0.01 |  30.39$\pm$0.01 |  30.38$\pm$0.01
26 |  32.38$\pm$0.01 |  32.39$\pm$0.01 |  32.40$\pm$0.01 |  32.40$\pm$0.01 |  32.39$\pm$0.01
28 |  34.38$\pm$0.01 |  34.39$\pm$0.01 |  34.40$\pm$0.01 |  34.40$\pm$0.01 |  34.40$\pm$0.01
30 |  36.38$\pm$0.01 |  36.39$\pm$0.01 |  36.39$\pm$0.01 |  36.40$\pm$0.01 |  36.40$\pm$0.01
32 |  38.38$\pm$0.01 |  38.39$\pm$0.01 |  38.39$\pm$0.01 |  38.39$\pm$0.01 |  38.39$\pm$0.01
Table 9: Codelengths in terms of bpd and auxiliary length on different $h$ and $k$ on a SUBSET of ImageNet64 dataset. N/A denotes the failure of the compression procedure. The theoretical bpd (nll) is 3.718. |  | $h$
---|---|---
|  | 6 | 8 | 10 | 12 | 14
bpd
$k$ | 18 |  3.829$\pm$0.000 |  3.779$\pm$0.000 |  3.867$\pm$0.000 | N/A | N/A
20 |  3.823$\pm$0.000 |  3.753$\pm$0.000 |  3.760$\pm$0.000 |  3.863$\pm$0.000 | N/A
22 |  3.821$\pm$0.000 |  3.746$\pm$0.000 |  3.733$\pm$0.000 |  3.755$\pm$0.000 |  3.861$\pm$0.000
24 |  3.821$\pm$0.000 |  3.744$\pm$0.000 |  3.727$\pm$0.000 |  3.729$\pm$0.000 |  3.754$\pm$0.000
26 |  3.821$\pm$0.000 |  3.744$\pm$0.000 |  3.725$\pm$0.000 |  3.722$\pm$0.000 |  3.727$\pm$0.000
28 |  3.821$\pm$0.000 |  3.744$\pm$0.000 |  3.725$\pm$0.000 |  3.720$\pm$0.000 |  3.721$\pm$0.000
30 |  3.821$\pm$0.000 |  3.744$\pm$0.000 |  3.725$\pm$0.000 |  3.720$\pm$0.000 |  3.719$\pm$0.000
32 |  3.821$\pm$0.000 |  3.744$\pm$0.000 |  3.725$\pm$0.000 |  3.720$\pm$0.000 |  3.719$\pm$0.000
auxiliary length
$k$ | 18 |  24.40$\pm$0.01 |  24.41$\pm$0.01 |  24.39$\pm$0.01 | N/A | N/A
20 |  26.40$\pm$0.01 |  26.41$\pm$0.01 |  26.41$\pm$0.01 |  26.39$\pm$0.01 | N/A
22 |  28.40$\pm$0.01 |  28.42$\pm$0.01 |  28.42$\pm$0.01 |  28.41$\pm$0.01 |  28.39$\pm$0.01
24 |  30.40$\pm$0.01 |  30.42$\pm$0.01 |  30.42$\pm$0.01 |  30.42$\pm$0.01 |  30.41$\pm$0.01
26 |  32.40$\pm$0.01 |  32.42$\pm$0.01 |  32.42$\pm$0.01 |  32.42$\pm$0.01 |  32.42$\pm$0.01
28 |  34.40$\pm$0.01 |  34.42$\pm$0.01 |  34.42$\pm$0.01 |  34.42$\pm$0.01 |  34.42$\pm$0.01
30 |  36.40$\pm$0.01 |  36.42$\pm$0.01 |  36.42$\pm$0.01 |  36.42$\pm$0.01 |  36.42$\pm$0.01
32 |  38.40$\pm$0.01 |  38.42$\pm$0.01 |  38.42$\pm$0.01 |  38.42$\pm$0.01 |  38.42$\pm$0.01