# Principal Bit Analysis:
Autoencoding with Schur-Concave Loss

Sourbh Bhadane
Cornell University
<EMAIL_ADDRESS>
This research was supported by the US National Science Foundation under grants
CCF-2008266, CCF-1934985, CCF-1617673, CCF-1846300, CCF-1815893 and the US
Army Research Office under grant W911NF-18-1-0426.  Aaron B.
Wagner11footnotemark: 1
Cornell University
<EMAIL_ADDRESS>
Jayadev Acharya11footnotemark: 1
Cornell University
<EMAIL_ADDRESS>
###### Abstract

We consider a linear autoencoder in which the latent variables are quantized,
or corrupted by noise, and the constraint is Schur-concave in the set of
latent variances. Although finding the optimal encoder/decoder pair for this
setup is a nonconvex optimization problem, we show that decomposing the source
into its principal components is optimal. If the constraint is strictly Schur-
concave and the empirical covariance matrix has only simple eigenvalues, then
any optimal encoder/decoder must decompose the source in this way. As one
application, we consider a strictly Schur-concave constraint that estimates
the number of bits needed to represent the latent variables under fixed-rate
encoding, a setup that we call _Principal Bit Analysis (PBA)_. This yields a
practical, general-purpose, fixed-rate compressor that outperforms existing
algorithms. As a second application, we show that a prototypical autoencoder-
based variable-rate compressor is guaranteed to decompose the source into its
principal components.

##  1 Introduction

_Autoencoders_ are an effective method for representation learning and
dimensionality reduction. Given a centered dataset
$\bm{x}_{1},\bm{x}_{2},\ldots,\bm{x}_{n}\in\mathbb{R}^{d}$ (i.e.,
$\sum_{i}\bm{x}_{i}=0$), an autoencoder (with _latent dimension_ $k\leq d$)
consists of an _encoder_ $f:\mathbb{R}^{d}\mapsto\mathbb{R}^{k}$ and a
_decoder_ $g:\mathbb{R}^{k}\mapsto\mathbb{R}^{d}$. The goal is to select $f$
and $g$ from prespecified classes $\mathcal{C}_{f}$ and $\mathcal{C}_{g}$
respectively such that if a random point $\bm{x}$ is picked from the data set
then $g(f(\bm{x}))$ is close to $\bm{x}$ in some sense, for example in mean
squared error. If $\mathcal{C}_{f}$ and $\mathcal{C}_{g}$ consist of linear
mappings then the autoencoder is called a _linear autoencoder_.

Autoencoders have achieved striking successes when $f$ and $g$ are selected
through training from the class of functions realized by multilayer
perceptrons of a given architecture [HS06]. Yet, the canonical autoencoder
formulation described above has a notable failing, namely that for linear
autoencoders, optimal choices of $f$ and $g$ do not necessarily identify the
principal components of the dataset; they merely identify the principal
subspace [BK88, BH89]. That is, the components of $f(\bm{x})$ are not
necessarily proportional to projections of $\bm{x}$ against the eigenvectors
of the covariance matrix

$\bm{K}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\frac{1}{n}\sum_{i=1}^{n}\bm{x}_{i}\cdot\bm{x}_{i}^{\top},$
(1)

which we assume without loss of generality is full rank. Thus, linear
autoencoders do not recover Principal Component Analysis (PCA). The reason for
this is that both the objective (the distortion) and the constraint (the
dimensionality of the latents) are invariant to an invertible transformation
applied after the encoder with its inverse applied before the decoder. It is
desirable for linear autoencoders to recover PCA for two reasons. First, from
a representation learning standpoint, it guarantees that the autoencoder
recovers uncorrelated features. Second, since a conventional linear
autoencoder has a large number of globally optimal solutions corresponding to
different bases of the principal subspace, it is preferable to eliminate this
indeterminism.

Autoencoders are sometimes described as “compressing” the data [San12, BK88,
LZW+21, Bis06], even though $f$ can be invertible even when $k<d$. We show
that by embracing this compression-view, one can obtain autoencoders that are
able to recover PCA. Specifically, we consider linear autoencoders with
quantized (or, equivalently, noisy) latent variables with a constraint on the
estimated number of bits required to transmit the quantized latents under
fixed-rate coding. We call this problem _Principal Bit Analysis (PBA)._ The
constraint turns out to be a strictly Schur-concave function of the set of
variances of the latent variables (see the supplementary for a review of
Schur-concavity). Although finding the optimal $f$ and $g$ for this loss
function is a nonconvex optimization problem, we show that for any strictly
Schur-concave loss function, an optimal $f$ must send projections of the data
along the principal components, assuming that the empirical covariance matrix
of the data has only simple eigenvalues. That is, imposing a strictly Schur-
concave loss in place of a simple dimensionality constraint suffices to ensure
recovery of PCA. The idea is that the strict concavity of the loss function
eliminates the rotational invariance described above. As we show, even a
slight amount of “curvature” in the constraint forces the autoencoder to
spread the variances of the latents out as much as possible, resulting in
recovery of PCA. If the loss function is merely Schur-concave, then projecting
along the principal components is optimal, but not necessarily uniquely so.

Using this theorem, we can efficiently solve PBA. We validate the solution
experimentally by using it to construct a fixed-rate compression algorithm for
arbitrary vector-valued data sources. We find that the PBA-derived compressor
beats existing linear, fixed-rate compressors both in terms of mean squared
error, for which it is optimized, and in terms of the structural similarity
index measure (SSIM) and downstream classification accuracy, for which it is
not.

A number of variable-rate multimedia compressors have recently been proposed
that are either related to, or directly inspired by, autoencoders [TAL18,
TVJ+17, BLS16, TOH+16, TSCH17, RB17, HRTC19, AMT+17, BMS+18, ZCG+18, ATM+19,
BCM+20]. As a second application of our result, we show that for Gaussian
sources, a linear form of such a compressor is guaranteed to recover PCA. Thus
we show that ideas from compression can be fruitfully fed back into the
original autoencoder problem.

The contributions of the paper are

  * •

We propose a novel linear autoencoder formulation in which the constraint is
Schur-concave. We show that this generalizes conventional linear autoencoding.

  * •

If the constraint is strictly Schur-concave and the covariance matrix of the
data has only simple eigenvalues, then we show that the autoencoder provably
recovers PCA, providing a new remedy for a known limitation of linear
autoencoders.

  * •

We use the new linear autoencoder formulation to efficiently solve a fixed-
rate compression problem that we call _Principal Bit Analysis (PBA)._

  * •

We demonstate experimentally that PBA outperforms existing fixed-rate
compressors on a variety of data sets and metrics.

  * •

We show that a linear, variable-rate compressor that is representative of many
autoencoder-based compressors in the literature effectively has a strictly
Schur-concave loss, and therefore it recovers PCA.

Related Work. Several recent works have examined how linear autoencoders can
be modified to guarantee recovery of PCA. Most solutions involve eliminating
the invariant global optimal solutions by introducing regularization of some
kind. [OSWS20] propose a loss function which adds $k$ penalties to recover the
$k$ principal directions, each corresponding to recovering up to the first
$i\leq k$ principal directions. [KBGS19] show that $\ell_{2}$ regularization
helps reduce the symmetry group to the orthogonal group. [BLSG20] further
break the symmetry by considering non-uniform $\ell_{2}$ regularization and
deterministic dropout. [LNP19] consider a nonlinear autoencoder with a
covariance loss term to encourage finding orthogonal directions. Recovering
PCA is an important problem even in the stochastic counterpart of
autoencoders. [LTGN19] analyze linear variational autoencoders (VAEs) and show
that the global optimum of its objective is identical to the global optimum of
log marginal likelihood of probabilistic PCA (pPCA). [RZM19] analyze an
approximation to the VAE loss function and show that the linear approximation
to the decoder is orthogonal.

Our result on variable-rate compressors is connected to the sizable recent
literature on compression using autoencoder-like architectures. Representative
contributions to the literature were noted above. Those works focus mostly on
the empirical performance of deep, nonlinear networks, with a particular
emphasis on finding a differentiable proxy for quantization so as to train
with stochastic gradient descent. In contrast, this work considers provable
properties of the compressors when trained perfectly.

Notation. We denote matrices by bold capital letters e.g. $\bm{M}$, and
vectors by bold small, e.g. $\bm{v}$. The $j^{\text{th}}$ column of a matrix
$\bm{M}$ is denoted by $\bm{m}_{j}$ and the $j^{\text{th}}$ entry of a vector
$\bm{v}$ by $\left[\bm{v}\right]_{j}$. We denote the set $\left\\{1,2,\cdots
d\right\\}$ by $\left[d\right]$. A sequence $a_{1},a_{2},\cdots a_{n}$ is
denoted by $\\{a_{i}\\}_{i=1}^{n}$. We denote the zero column by $\bm{0}$.
Logarithms without specified bases denote natural logarithms.

Organization. The balance of the paper is organized as follows. We describe
our constrained linear autoencoder framework in Section 2. This results in an
optimization problem that we solve for any Schur-concave constraint in Section
2.1. In Section 3, we recover linear autoencoders and PBA under our framework.
We apply the PBA solution to a problem in variable-rate compression of
Gaussian sources in Section 4. Section 5 contains experiments comparing the
performance of the PBA-based fixed-rate compressor against existing fixed-rate
linear compressors on image and audio datasets.

##  2 Linear Autoencoding with a Schur-Concave Constraint

Throughout this paper we consider $\mathcal{C}_{f}$ and $\mathcal{C}_{g}$ to
be the class of linear functions. The functions $f\in\mathcal{C}_{f}$ and
$g\in\mathcal{C}_{g}$ can then be represented by $d$-by-$d$ matrices,
respectively, which we denote by $\bm{W}$ and $\bm{T}$, respectively. Thus we
have

$\displaystyle f(\bm{x})$ $\displaystyle=\bm{W}^{\top}\bm{x}$ (2)
$\displaystyle g(\bm{x})$ $\displaystyle=\bm{T}\bm{x}.$ (3)

We wish to design $\bm{W}$ and $\bm{T}$ to minimize the mean squared error
when the latent variables $\bm{W}^{\top}\bm{x}$ are quantized, subject to a
constraint on the number of bits needed to represent the quantized latents. We
accomplish this via two modifications of the canonical autoencoder. First, we
perturb the $d$ latent variables with zero-mean additive noise with covariance
matrix $\sigma^{2}\bm{I}$, which we denote by $\bm{\varepsilon}.$ Thus the
input to the decoder is

$\bm{W}^{\top}\bm{x}+\bm{\varepsilon}$ (4)

and our objective is to minimize the mean squared error

$\frac{1}{n}\sum\limits_{i=1}^{n}\mathbb{E}_{\bm{\varepsilon}}\left[\left\lVert\bm{x}_{i}-\bm{T}\left(\bm{W}^{\top}\bm{x}_{i}+\bm{\varepsilon}\right)\right\rVert_{2}^{2}\right].$
(5)

This is equivalent to quantizing the latents, in the following sense [ZF92].
Let $Q(\cdot)$ be the function that maps any real number to its nearest
integer and $\varepsilon$ be a random variable uniformly distributed over
$[-1/2,1/2]$. Then for $X$ independent of $\varepsilon$, the quantities
$Q(X+\varepsilon)-\varepsilon$ and $X+\varepsilon$ have the same joint
distribution with $X$. Thus (5) is exactly the mean squared error if the
latents are quantized to the nearest integer and $\sigma^{2}=\frac{1}{12}$,
assuming that the quantization is dithered. The overall system is depicted in
Fig. 1.

Linear Encoder ($\bm{W}$) Quantizer Linear Decoder ($\bm{T}$)
$\bm{T}\left(\bm{W}^{\top}\bm{x}_{i}+\bm{\varepsilon}\right)$ $\bm{x}_{i}$
$\bm{W}^{\top}\bm{x}_{i}$ $\bm{W}^{\top}\bm{x}_{i}+\bm{\varepsilon}$ Figure 1:
Compression Block Diagram

We wish to constrain the number of bits needed to describe the latent
variables. We assume that the $j$th quantized latent is clipped to the
interval

$\left(-\frac{\sqrt{(2a)^{2}\bm{w}_{j}^{\top}\bm{K}\bm{w}_{j}+1}}{2},\frac{\sqrt{(2a)^{2}\bm{w}_{j}^{\top}\bm{K}\bm{w}_{j}+1}}{2}\right],$

where $a>0$ is a hyperparameter and the covariance matrix $\bm{K}$ is as
defined in (1). The idea is that for sufficiently large $a$, the interval

$\left(-a\sqrt{\bm{w}_{j}^{\top}\bm{K}\bm{w}_{j}},a\sqrt{\bm{w}_{j}^{\top}\bm{K}\bm{w}_{j}}\right]$

contains the latent with high probability, and adding $1$ accounts for the
expansion due to the dither. The number of bits needed for the $j$th latent is
then

$\displaystyle\log\left(\sqrt{4a^{2}\bm{w}_{j}^{\top}\bm{K}\bm{w}_{j}+1}\right)=\frac{1}{2}\log\left(4a^{2}\bm{w}_{j}^{\top}\bm{K}\bm{w}_{j}+1\right).$
(6)

We arrive at our optimization problem:

$\displaystyle\inf\limits_{\bm{W},\bm{T}}$
$\displaystyle\frac{1}{n}\sum\limits_{i=1}^{n}\mathbb{E}_{\bm{\varepsilon}}\left[\left\lVert\bm{x}_{i}-\bm{T}\left(\bm{W}^{\top}\bm{x}_{i}+\bm{\varepsilon}\right)\right\rVert_{2}^{2}\right]$
(7) subject to $\displaystyle
R\geq\sum_{j=1}^{d}\frac{1}{2}\log\left(4a^{2}\bm{w}_{i}^{\top}\bm{K}\bm{w}_{i}+1\right).$

Note that the function

$\\{\bm{w}_{j}^{\top}\bm{K}\bm{w}_{j}\\}_{j=1}^{d}\mapsto\sum_{j=1}^{d}\frac{1}{2}\log\left(4a^{2}\bm{w}_{i}^{\top}\bm{K}\bm{w}_{i}+1\right)$

is strictly Schur-concave (see Appendix A for a brief review of Schur-
concavity). Our first result only requires that the constraint is Schur-
concave in the set of latent variances, so we will consider the more general
problem

$\displaystyle\inf\limits_{\bm{W},\bm{T}}$
$\displaystyle\frac{1}{n}\sum\limits_{i=1}^{n}\mathbb{E}_{\bm{\varepsilon}}\left[\left\lVert\bm{x}_{i}-\bm{T}\left(\bm{W}^{\top}\bm{x}_{i}+\bm{\varepsilon}\right)\right\rVert_{2}^{2}\right]$
(8) subject to $\displaystyle
R\geq\rho\left(\left\\{\bm{w}_{j}^{\top}\bm{K}\bm{w}_{j}\right\\}_{j=1}^{d}\right)$

where $\rho(\cdot)$ is any Schur-concave function.

Expressing the objective in (8) in terms of $\bm{K}$, the optimization problem
reduces to

$\displaystyle\inf\limits_{\bm{W},\bm{T}}$
$\displaystyle\text{tr}\left(\bm{K}\right)-2\text{tr}\left(\bm{K}\bm{W}\bm{T}^{\top}\right)+\text{tr}\left(\bm{T}\left(\bm{W}^{\top}\bm{K}\bm{W}+\sigma^{2}\bm{I}\right)\bm{T}^{\top}\right)$
(9) subject to $\displaystyle
R\geq\rho\left(\left\\{\bm{w}_{j}^{\top}\bm{K}\bm{w}_{j}\right\\}_{j=1}^{d}\right).$

Since $\bm{T}$ does not appear in the rate constraint, the optimal $\bm{T}$
can be viewed as the Linear Least Squares Estimate (LLSE) of a random $\bm{x}$
given $\bm{W}^{\top}\bm{x}+\bm{\varepsilon}$. Therefore, the optimal decoder,
$\bm{T}^{*}$ for a given encoder $\bm{W}$ is (e.g. [Kay98]):

$\bm{T}^{*}=\bm{K}\bm{W}(\bm{W}^{\top}\bm{K}\bm{W}+\sigma^{2}\bm{I})^{-1}.$
(10)

Substituting for $\bm{T}$ in (9) yields an optimization problem over only
$\bm{W}$

$\displaystyle\inf\limits_{\bm{W}}$
$\displaystyle\text{tr}(\bm{K})-\text{tr}(\bm{K}\bm{W}(\bm{W}^{\top}\bm{K}\bm{W}+\sigma^{2}\bm{I})^{-1}\bm{W}^{\top}\bm{K})$
(11) subject to $\displaystyle
R\geq\rho\left(\left\\{\bm{w}_{j}^{\top}\bm{K}\bm{w}_{j}\right\\}_{j=1}^{d}\right).$

This problem is nonconvex in general. In the following subsection, we prove a
structural result about the problem for a Schur-concave $\rho$. Namely, we
show that the nonzero rows of $\bm{W}$ must be eigenvectors of $\bm{K}$. In
Section 3, we solve the problem for the specific choice of $\rho$ in (7). We
also show how this generalizes conventional linear autoencoders.

###  2.1 Optimal Autoencoding with a Schur-Concave Constraint

The following is the main theoretical result of the paper.

######  Theorem 1.

For Schur-concave $\rho:\mathbb{R}_{\geq 0}^{d}\rightarrow\mathbb{R}_{\geq 0}$
and $R>0$, the set of matrices whose nonzero columns are eigenvectors of the
covariance matrix $\bm{K}$ is optimal for (11). If $\rho$ is strictly Schur-
concave and $\bm{K}$ contains distinct eigenvalues, this set contains all
optimal solutions of (11).

###### Proof.

Let the eigenvalues of $\bm{K}$ be $\\{\sigma_{i}^{2}\\}_{i=1}^{d}$ with
$\sigma_{1}^{2}\geq\sigma_{2}^{2}\geq\ldots\geq\sigma^{2}_{d}$. Let the
eigendecomposition of $\bm{K}$ be given by
$\bm{K}=\bm{U}\bm{\Sigma}\bm{U}^{\top}$ where $\bm{U}$ is an orthogonal matrix
whose columns are the eigenvectors of $\bm{K}$ and $\bm{\Sigma}$ is a diagonal
matrix with entries $\left\\{\sigma_{i}^{2}\right\\}_{i=1}^{d}$.

We first prove that the optimal value of (11) can be achieved by  a $\bm{W}$
such that $\bm{W}^{\top}\bm{K}\bm{W}$ is a diagonal matrix. Let
$\widetilde{\bm{W}}=\bm{W}\bm{Q}$ where $\bm{Q}$ is the orthogonal matrix
obtained from the eigendecomposition of $\bm{W}^{\top}\bm{K}\bm{W}$ i.e.,

$\bm{W}^{\top}\bm{K}\bm{W}=\bm{Q}\bm{\Lambda}\bm{Q}^{\top},$

where $\bm{\Lambda}$ is a diagonal matrix formed from the eigenvalues of
$\bm{W}^{\top}\bm{K}\bm{W}$. Note that

$\displaystyle\text{tr}\left(\bm{K}\widetilde{\bm{W}}\left(\widetilde{\bm{W}}^{\top}\bm{K}\widetilde{\bm{W}}+\sigma^{2}\bm{I}\right)^{-1}\widetilde{\bm{W}}^{\top}\bm{K}\right)$
$\displaystyle=\text{tr}\left(\bm{K}\bm{W}\bm{Q}\left(\bm{\Lambda}+\sigma^{2}\bm{I}\right)^{-1}\bm{Q}^{\top}\bm{W}^{\top}\bm{K}\right)$
$\displaystyle=\text{tr}\left(\bm{K}\bm{W}\left(\bm{Q}\bm{\Lambda}\bm{Q}^{\top}+\sigma^{2}\bm{Q}\bm{Q}^{\top}\right)^{-1}\bm{W}^{\top}\bm{K}\right).$

Since $\bm{Q}\bm{\Lambda}\bm{Q}^{\top}=\bm{W}^{\top}\bm{K}\bm{W}$ and
$\bm{Q}\bm{Q}^{\top}=\bm{I}$, the objective remains the same. We now show that
the constraint is only improved. Denoting the eigenvalues of
$\bm{W}^{\top}\bm{K}\bm{W}$ by $\left\\{\nu_{j}\right\\}_{j=1}^{d}$, we have

$\rho\left(\left\\{\widetilde{\bm{w}}_{j}^{\top}\bm{K}\widetilde{\bm{w}}_{j}\right\\}_{j=1}^{d}\right)=\rho\left(\left\\{\bm{q}_{j}^{\top}\bm{W}^{\top}\bm{K}\bm{W}\bm{q}_{j}\right\\}_{j=1}^{d}\right)=\rho\left(\left\\{\nu_{j}\right\\}_{j=1}^{d}\right).$

Now since the eigenvalues of a Hermitian matrix majorize its diagonal elements
by the Schur-Horn theorem [HJ13, Theorem 4.3.45],

$\left\\{\bm{w}_{j}^{\top}\bm{K}\bm{w}_{j}\right\\}_{j=1}^{d}\prec\left\\{\nu_{j}\right\\}_{j=1}^{d}.$

Since $\rho$ is Schur-concave, this implies

$\rho\left(\left\\{\bm{w}_{j}^{\top}\bm{K}\bm{w}_{j}\right\\}_{j=1}^{d}\right)\geq\rho\left(\left\\{\nu_{j}\right\\}_{j=1}^{d}\right)=\rho\left(\left\\{\widetilde{\bm{w}}_{j}^{\top}\bm{K}\widetilde{\bm{w}}_{i}\right\\}_{j=1}^{d}\right).$

Therefore, if $\rho$ is Schur-concave, the rate constraint can only improve.
This implies an optimal solution can be attained when $\bm{W}$ is such that
$\bm{W}^{\top}\bm{K}\bm{W}$ is diagonal. If $\rho$ is strictly Schur-concave,
the rate constraint strictly improves implying that the optimal $\bm{W}$ must
be such that $\bm{W}^{\top}\bm{K}\bm{W}$ is diagonal. This implies that

$\displaystyle\text{tr}\left(\bm{K}\bm{W}\left(\bm{W}^{\top}\bm{K}\bm{W}+\sigma^{2}\bm{I}\right)^{-1}\bm{W}^{\top}\bm{K}\right)$
$\displaystyle=\text{tr}\left(\bm{W}^{\top}\bm{K}^{2}\bm{W}\left(\bm{W}^{\top}\bm{K}\bm{W}+\sigma^{2}\bm{I}\right)^{-1}\right)$
$\displaystyle=\sum\limits_{i=1}^{d}\frac{\bm{w}_{i}^{\top}\bm{K}^{2}\bm{w}_{i}}{\sigma^{2}+\bm{w}_{i}^{\top}\bm{K}\bm{w}_{i}}.$

Note that minimizing the objective in (11) is equivalent to maximizing the
above expression. Perform the change of variable

$\displaystyle\bm{w}_{j}$
$\displaystyle\mapsto\begin{cases}\left(\frac{\bm{K}^{1/2}\bm{w}_{j}}{||\bm{K}^{1/2}\bm{w}_{j}||},||\bm{K}^{1/2}\bm{w}_{j}||^{2}\right)&\text{if
$\bm{K}^{1/2}\bm{w}_{j}\neq\bm{0}$}\\\ (\bm{0},0)&\text{if
$\bm{K}^{1/2}\bm{w}_{j}=\bm{0}$}\end{cases}$
$\displaystyle=(\bm{y}_{j},y_{j}).$

The assumption that $\bm{W}^{\top}\bm{K}\bm{W}$ is diagonal and the
normalization in the definition of $\bm{y}_{j}$ implies that

$\bm{Y}=[\bm{y}_{1}\bm{y}_{2},\cdots,\bm{y}_{d}]$

is a matrix whose nonzero columns form an orthonormal set. Rewriting the
objective in terms of the $(\bm{y}_{j},y_{j})$, we have

$\sum\limits_{i=1}^{d}\frac{\bm{w}_{i}^{\top}\bm{K}^{2}\bm{w}_{i}}{\sigma^{2}+\bm{w}_{i}^{\top}\bm{K}\bm{w}_{i}}=\sum\limits_{i=1}^{d}\bm{y}_{i}^{\top}\bm{K}\bm{y}_{i}\frac{y_{i}}{\sigma^{2}+y_{i}}=\sum\limits_{i=1}^{d}\bm{y}_{i}^{\top}\bm{K}\bm{y}_{i}m_{i},$
(12)

where $m_{i}=\frac{y_{i}}{\sigma^{2}+y_{i}}$. Observe that under this new
parametrization, the constraint only depends on $\\{y_{i}\\}_{i=1}^{d}$.
Without loss of generality, we assume that $y_{1}\geq y_{2}\geq\cdots\geq
y_{d}$, implying that $m_{1}\geq m_{2}\geq\cdots\geq m_{d}$. We now prove that
for given $\\{y_{i}\\}_{i=1}^{d}$, choosing the $\bm{y}_{i}$ along the
eigenvectors of $\bm{K}$ is optimal.

Denote the diagonal elements of $\bm{Y}^{\top}\bm{K}\bm{Y}$ by
$\\{\lambda_{i}^{2}\\}_{i=1}^{d}$ and let
$\\{\lambda_{i,\downarrow}^{2}\\}_{i=1}^{d}$ denote the same diagonal elements
arranged in descending order. Denote the eigenvalues of
$\bm{Y}^{\top}\bm{K}\bm{Y}$ by $\\{\mu_{i}^{2}\\}_{i=1}^{d}$ where
$\mu_{1}\geq\mu_{2}\geq\cdots\geq\mu_{d}$. Again invoking the Schur-Horn
theorem, the eigenvalues of $\bm{Y}^{\top}\bm{K}\bm{Y}$ majorize its diagonal
entries

$\left\\{\lambda_{i}^{2}\right\\}_{i=1}^{d}\prec\left\\{\mu_{i}^{2}\right\\}_{i=1}^{d}.$
(13)

Substituting $\lambda_{i}^{2}=\bm{y}_{i}^{\top}\bm{K}\bm{y}_{i}$ in (12), we
have

$\displaystyle\sum\limits_{i=1}^{d}\lambda_{i}^{2}m_{i}\stackrel{{\scriptstyle(a)}}{{\leq}}\sum\limits_{i=1}^{d}\lambda_{i,\downarrow}^{2}m_{i}$
$\displaystyle=\lambda_{1,\downarrow}^{2}m_{1}+\sum\limits_{i=2}^{d}\left(\sum\limits_{j=1}^{i}\lambda_{j,\downarrow}^{2}-\sum\limits_{j=1}^{i-1}\lambda_{j,\downarrow}^{2}\right)m_{i}$
$\displaystyle=\lambda_{1,\downarrow}^{2}m_{1}+\sum\limits_{i=2}^{d}m_{i}\sum\limits_{j=1}^{i}\lambda_{j,\downarrow}^{2}-\sum\limits_{i=2}^{d}m_{i}\sum\limits_{j=1}^{i-1}\lambda_{j,\downarrow}^{2}$
$\displaystyle=\lambda_{1,\downarrow}^{2}(m_{1}-m_{2})+m_{d}\left(\sum\limits_{j=1}^{d}\lambda_{j,\downarrow}^{2}\right)+\sum\limits_{i=2}^{d-1}\left(m_{i}-m_{i+1}\right)\sum\limits_{j=1}^{i}\lambda_{j,\downarrow}^{2}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\mu_{1}^{2}(m_{1}-m_{2})+m_{d}\left(\sum\limits_{j=1}^{d}\mu_{j}^{2}\right)+\sum\limits_{i=2}^{d-1}(m_{i}-m_{i+1})\sum\limits_{j=1}^{i}\mu_{j}^{2}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\sigma_{1}^{2}(m_{1}-m_{2})+m_{d}\left(\sum\limits_{j=1}^{d}\sigma_{j}^{2}\right)+\sum\limits_{i=2}^{d-1}(m_{i}-m_{i+1})\sum\limits_{j=1}^{i}\sigma_{j}^{2}$
$\displaystyle=\sum\limits_{i=1}^{d}\sigma_{i}^{2}m_{i},$

where inequality $(a)$ follows from the assumption that $m_{1}\geq
m_{2}\geq\cdots\geq m_{d}$, and $(b)$ from the definition in (13). Since
$\bm{Y}$’s nonzero columns form an orthonormal set, the eigenvalues of
$\bm{Y}^{\top}\bm{K}\bm{Y}$, when arranged in descending order, are at most
the eigenvalues of $\bm{K}$ from Corollary 4.3.37 in [HJ13], and therefore
$(c)$ follows.

This upper bound is attained when $\bm{y}_{i}=\bm{u}_{i}$ for nonzero $y_{i}$,
where $\bm{u}_{i}$ is the normalized eigenvector of $\bm{K}$ corresponding to
eigenvalue $\sigma_{i}^{2}$. To see this, note that when
$\bm{y}_{i}=\bm{u}_{i}$, $\lambda_{i}^{2}=\mu_{i}^{2}=\sigma_{i}^{2}$. From
the definition of
$\bm{y}_{i},\bm{w}_{i}=\bm{K}^{-1/2}\bm{u}_{i}\sqrt{y_{i}}=\bm{u}_{i}\frac{\sqrt{y_{i}}}{\sigma_{i}}$.
Therefore, for a Schur-concave $\rho$, the set of matrices whose nonzero
columns are eigenvectors of $\bm{K}$ is optimal. We now prove that for a
strictly Schur-concave $\rho$, if $\bm{K}$ has distinct eigenvalues, this set
contains all of the optimal solutions $\bm{W}$.

We know that for a fixed $y_{1}\geq y_{2}\geq\cdots\geq y_{d}$, (implying a
fixed $m_{1}\geq m_{2}\geq\cdots\geq m_{d}$) the upper bound
$\sum\limits_{i=1}^{d}\sigma_{i}^{2}m_{i}$ is attained by the previous choice
of $\bm{y}_{i}$. Note that if all nonzero $m_{i}$ are distinct, equality in
$(b)$ and $(c)$ is attained if and only if the nonzero diagonal elements of
$\bm{Y}^{\top}\bm{K}\bm{Y}$ equal the corresponding eigenvalues of $\bm{K}$.
This implies that, if all nonzero $m_{i}$ are distinct, the upper bound is
attained if and only if $\bm{y}_{i}=\bm{u}_{i}$ for nonzero $y_{i}$.
Therefore, it is sufficient to prove that for the following optimization
problem

$\displaystyle\sup\limits_{\\{y_{i}\geq 0\\}}$
$\displaystyle\sum\limits_{i=1}^{d}\sigma_{i}^{2}\frac{y_{i}}{\sigma^{2}+y_{i}}$
(14) subject to $\displaystyle
R\geq\rho\left(\left\\{y_{i}\right\\}_{i=1}^{d}\right),$

any optimal $\\{y_{i}\\}$ must be such that the nonzero $y_{i}$ are distinct.
Firstly, note that since
$\sigma_{1}^{2}>\sigma_{2}^{2}>\cdots>\sigma_{d}^{2}$, we must have $y_{1}\geq
y_{2}\geq\cdots\geq y_{d}$. Assume to the contrary that for an optimal
$\\{y_{i}\\}_{i=1}^{d}$ there exists $1\leq j,\ell<d$ such that
$y_{j-1}>y_{j}=y_{j+1}=y_{j+2}=\cdots=y_{j+\ell}>y_{j+\ell+1}\geq 0$, where
$y_{0}$ is chosen to be any real number strictly greater than $y_{1}$ and
$y_{d+1}=0$. Take $\delta>0$ small. Denote a new sequence
$\\{y^{\prime}_{i}\\}_{i=1}^{d}$ where
$y^{\prime}_{j}=y_{j}+\delta,y^{\prime}_{j+\ell}=y_{j+\ell}-\delta$ and
$y^{\prime}_{i}=y_{i}$ for $1\leq i\leq d$ with $i\neq j$ and $j+\ell$. Since
$\rho$ is strictly Schur-concave, the constraint is strictly improved,

$\rho\left(\\{y^{\prime}_{i}\\}_{i=1}^{d}\right)<\rho\left(\\{y_{i}\\}_{i=1}^{d}\right).$

Since $\sigma^{2}_{j}>\sigma^{2}_{j+\ell}$, the objective is strictly improved
for sufficiently small $\delta$,

$\sum\limits_{i=1}^{d}\sigma_{i}^{2}\frac{y_{i}}{\sigma^{2}+y_{i}}<\sum\limits_{i=1}^{d}\sigma_{i}^{2}\frac{y^{\prime}_{i}}{\sigma^{2}+y^{\prime}_{i}},$

as desired. ∎

As a consequence of Theorem 1, encoding via an optimal $\bm{W}$ can be viewed
as a projection along the eigenvectors of $\bm{K}$, followed by different
scalings applied to each component, i.e. $\bm{W}=\bm{U}\bm{S}$ where $\bm{S}$
is a diagonal matrix with entries $s_{i}\geq 0$ and $\bm{U}$ is the normalized
eigenvector matrix. Only $\bm{S}$ remains to be determined, and to this end,
we may assume that $\bm{K}$ is diagonal with nonincreasing diagonal entries,
implying $\bm{U}=\bm{I}$. In subsequent sections, our choice of $\rho$ will be
of the form $\sum\limits_{i=1}^{d}\rho_{sl}$, where
$\rho_{sl}:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$111“sl” stands
for single-letter is (strictly) concave, making $\rho$ (strictly) Schur-
concave (see Proposition 9 in Appendix A). Therefore, (11) reduces to

$\displaystyle\inf\limits_{\bm{S}}$
$\displaystyle\text{tr}(\bm{K})-\text{tr}(\bm{K}\bm{S}(\bm{S}^{\top}\bm{K}\bm{S}+\sigma^{2}\bm{I})^{-1}\bm{S}^{\top}\bm{K})$
(15) subject to $\displaystyle
R\geq\rho_{sl}\left(\\{s_{i}^{2}\sigma^{2}_{i}\\}\right),$

where the infimum is over diagonal matrices $\bm{S}$. To handle situations for
which

$\lim_{s\rightarrow\infty}\rho_{sl}(s)<\infty,$ (16)

we allow the diagonal entries of $\bm{S}$ to be $\infty$, with the objective
for such cases defined via its continuous extension.

In the next section, we will solve (15) for several specific choices of
$\rho_{sl}$.

##  3 Explicit Solutions: Conventional Linear Autoencoders and PBA

###  3.1 Conventional Linear Autoencoders

Given a centered dataset
$\bm{x}_{1},\bm{x}_{2},\cdots,\bm{x}_{n}\in\mathbb{R}^{d}$, consider a linear
autoencoder optimization problem where the encoder and decoder, $\bm{W}$ and
$\bm{T}$, respectively, are $d$-by-$k$ matrices where $k\leq d$ is a
parameter. The goal is to minimize the mean squared error as given by (5). PCA
corresponds to the global optimal solution of this optimization problem, where
$\bm{W}=\bm{T}=\bm{U}_{k}$, where $\bm{U}_{k}\in\mathbb{R}^{d\times k}$ is a
matrix whose columns are the $k$ eigenvectors corresponding to the $k$ largest
eigenvalues of $\bm{K}$. However, there are multiple global optimal solutions,
given by any encoder-decoder pair of the form
$\left(\bm{U}_{k}\bm{V},\bm{U}_{k}\bm{V}\right)$, where $\bm{V}$ is an
orthogonal matrix [BH89].

We now recover linear autoencoders through our framework in Section 2.
Consider the optimization problem in (15) where $\rho_{sl}:\mathbb{R}_{\geq
0}\rightarrow\\{0,1\\}$ is a concave function defined as

$\rho_{sl}(x)=\bm{1}\left[x>0\right].$ (17)

Note that this penalizes the dimension of the latents, as desired. Note also
that this cost is Schur-concave but not strictly so. The fact that PCA solves
conventional linear autoencoding, but is not necessarily the unique solution,
follows immediately from Theorem 1.

######  Theorem 2.

If $\rho_{sl}(\cdot)$ is given by (17), then an optimal solution for (15) is
given by a diagonal matrix $\bm{S}$ whose top $\min(\lfloor R\rfloor,d)$
diagonal entries are equal to $\infty$ and the remaining entries are $0$.

###### Proof.

Let ${\cal
F}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\left\\{i\in\left[d\right]:s_{i}>0\right\\}$,
implying $\left\lvert{\cal F}\right\rvert\leq R$. Since $\bm{K}$ and $\bm{S}$
are diagonal, the optimization problem in (15) can be written as

$\displaystyle\inf\limits_{\left\\{s_{\ell}\right\\}}$
$\displaystyle\sum\limits_{j\in\left[d\right]\backslash{\cal
F}}\sigma_{j}^{2}+\sum\limits_{\ell\in{\cal
F}}\frac{\sigma^{2}\sigma_{\ell}^{2}}{\sigma^{2}+\sigma_{\ell}^{2}s_{\ell}^{2}}$
(18) subject to $\displaystyle
R\geq\sum\limits_{i=1}^{d}\bm{1}\left[s_{i}>0\right].$

Since the value of $s_{\ell},\ell\in{\cal F}$ does not affect the rate
constraint, each of the $s_{\ell}$ can be made as large as possible without
changing the rate constraint. Therefore, the infimum value of the objective is
$\sum\limits_{j\in\left[d\right]\backslash{\cal F}}\sigma^{2}_{j}$. Since we
seek to minimize the distortion, the optimal ${\cal F}$ is the set of indices
with the largest $\left\lvert{\cal F}\right\rvert$ eigenvalues. Since the
number of these eigenvalues cannot exceed $R$, we choose $\left\lvert{\cal
F}\right\rvert=\min(\lfloor R\rfloor,d)$. ∎

Unlike the conventional linear autoencoder framework, in Section 2, the latent
variables $\bm{W}^{\top}\bm{x}$ are quantized, which we model with additive
white noise of fixed variance. Therefore, an infinite value of $s_{i}$
indicates sending $\bm{u}_{i}^{\top}\bm{x}$ with full precision where
$\bm{u}_{i}$ is the eigenvector corresponding to the $i^{th}$ largest
eigenvalue. This implies that PCA with parameter $k$ corresponds to
$\bm{W}=\bm{U}\bm{S}$, where $\bm{S}$ is a diagonal matrix whose top $k$
diagonal entries are equal to $\infty$ and the $d-k$ remaining diagonal
entries are $0$. Therefore, for any $R$ such that $\lfloor R\rfloor=k$, an
optimal solution to (15) corresponds to linearly projecting the data along the
top $k$ eigenvectors, which is the same as PCA. Note that, like [BH89], we
only prove that projecting along the eigenvectors is one of possibly other
optimal solutions. However, even a slight amount of curvature in $\rho$ would
make it strictly Schur-concave, thus recovering the principal directions. We
next turn to a specific cost function with curvature, namely the PBA cost
function that was our original motivation.

###  3.2 Principal Bit Analysis (PBA)

Consider the choice of $\rho_{sl}:\mathbb{R}_{\geq
0}\rightarrow\mathbb{R}_{\geq 0}$ that provided the original impetus for
Theorem 1. For $\gamma>\frac{2}{\sigma^{2}}$,

$\rho_{sl}(x)=\frac{1}{2}\log(\gamma x+1).$ (19)

The nature of the optimization problem depends on the value of $\gamma$. For
$1\leq\gamma\sigma^{2}\leq 2$, the problem can be made convex with a simple
change of variable. For $\gamma\sigma^{2}=1$, the problem coincides with the
classical waterfilling procedure in rate-distortion theory, in fact. For
$\gamma\sigma^{2}>2$, the problem is significantly more challenging. Since we
are interested in relatively large values of $\gamma$ for our compression
application (see Section 5 to follow), we focus on the case
$\gamma>2/\sigma^{2}$.

Algorithm 1 Principal Bit Analysis (PBA)

1:$\lambda>0$, $\alpha>2$,
$\bm{K}=\left[\begin{array}[]{cccc}\sigma^{2}_{1}&0&\cdots&0\\\
0&\sigma^{2}_{2}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\sigma^{2}_{d}\\\ \end{array}\right]\succ 0,$ (20) such that
$\sigma^{2}_{1}\geq\sigma^{2}_{2}\geq\cdots\geq\sigma^{2}_{d}$.

2:If $\lambda\geq\sigma^{2}_{1}/(4(\alpha-1))$, Output
$\bar{R}_{\text{opt}}=0,\bar{D}_{\text{opt}}=\sum_{i=1}^{d}\sigma^{2}_{i}$.

3:Set $\bar{d}=\max\left\\{i:\lambda<\sigma_{i}^{2}/4(\alpha-1)\right\\}$.

4:Set $\bar{R}$, $\bar{D}$ to zero arrays of size $2\bar{d}$.

5:for $r\in\left\\{1,2,\cdots\bar{d}\right\\}$ do

6:
$\bar{D}(2r-1)=\sum\limits_{i=1}^{r}\frac{\sigma_{i}^{2}}{2(\alpha-1)}\left(1-\sqrt{1-\frac{4\lambda(\alpha-1)}{\sigma_{i}^{2}}}\right)+\sum\limits_{i=r+1}^{d}\frac{\sigma_{i}^{2}}{\alpha}$,

7:
$\bar{R}(2r-1)=\sum\limits_{i=1}^{r}\frac{1}{2}\log\left(\frac{\sigma_{i}^{2}}{4\lambda}\right)+\log\left(1+\sqrt{1-\frac{4\lambda(\alpha-1)}{\sigma_{i}^{2}}}\right)$.

8:
$\bar{D}(2r)=\left(\sum\limits_{i=1}^{r-1}\frac{\sigma_{i}^{2}}{2(\alpha-1)}\left(1-\sqrt{1-\frac{4\lambda(\alpha-1)}{\sigma_{i}^{2}}}\right)+\frac{\sigma_{r}^{2}}{2(\alpha-1)}\left(1+\sqrt{1-\frac{4\lambda(\alpha-1)}{\sigma_{r}^{2}}}\right)+\sum\limits_{i=r+1}^{d}\frac{\sigma_{i}^{2}}{\alpha}\right)$.

9:
$\bar{R}(2r)=\sum\limits_{i=1}^{r}\frac{1}{2}\log\left(\frac{\sigma_{i}^{2}}{4\lambda}\right)+\sum\limits_{i=1}^{r-1}\log\left(1+\sqrt{1-\frac{4\lambda(\alpha-1)}{\sigma_{i}^{2}}}\right)+\log\left(1-\sqrt{1-\frac{4\lambda(\alpha-1)}{\sigma_{r}^{2}}}\right)$.

10:end for

11:$r^{*}\leftarrow\operatorname*{arg\,min}_{j\in\left[2\bar{d}\right]}\bar{D}(j)+\lambda\bar{R}(j).$

12:Output
$\bar{R}_{\text{opt}}=\bar{R}(r^{*}),\bar{D}_{\text{opt}}=\bar{D}(r^{*})$.

######  Theorem 3.

If $\rho_{sl}(\cdot)$ is given by (19) for $\gamma>\frac{2}{\sigma^{2}}$, then
for any $\lambda>0$, the pair $\bar{R}_{\text{opt}},\bar{D}_{\text{opt}}$
obtained from the output of Algorithm 1 satisfies

$\bar{D}_{\text{opt}}+\lambda\bar{R}_{\text{opt}}=\inf\limits_{\bm{S}}\quad\text{tr}(\bm{K})-\text{tr}(\bm{K}\bm{S}(\bm{S}^{\top}\bm{K}\bm{S}+\sigma^{2}\bm{I})^{-1}\bm{S}^{\top}\bm{K})+\lambda\sum_{i=1}^{d}\rho_{sl}\left(\\{s_{i}^{2}\sigma^{2}_{i}\\}\right),$
(21)

###### Proof.

Since $\bm{K}$ and $\bm{S}$ are diagonal, the optimization problem in (21) can
be written as

$\displaystyle\inf\limits_{\left\\{s_{i}\right\\}}$
$\displaystyle\sum\limits_{i=1}^{d}\frac{\sigma^{2}\sigma_{i}^{2}}{\sigma^{2}+s_{i}^{2}\sigma_{i}^{2}}+\lambda\cdot\frac{1}{2}\sum\limits_{i=1}^{d}\log\left(1+\gamma
s_{i}^{2}\sigma_{i}^{2}\right).$ (22)

With the following change of variables $\alpha=\gamma\sigma^{2}$,
$s_{i}\mapsto s_{i}^{\prime 2}=\alpha\frac{s_{i}^{\prime 2}}{\sigma^{2}}$, we
obtain

$\displaystyle\inf\limits_{\left\\{s_{i}^{\prime}\right\\}}$
$\displaystyle\sum\limits_{i=1}^{d}\alpha\frac{\sigma_{i}^{2}}{\alpha+s_{i}^{{}^{\prime}2}\sigma_{i}^{2}}+\lambda\cdot\frac{1}{2}\sum\limits_{i=1}^{d}\log\left(1+s_{i}^{\prime
2}\sigma_{i}^{2}\right).$ (23)

Ignoring the constant factor in the objective, perform the change of variable
$s^{\prime}_{i}\mapsto D_{i}=\frac{\sigma_{i}^{2}}{\alpha+s_{i}^{\prime
2}\sigma_{i}^{2}}$ to obtain

$\displaystyle\inf\limits_{\left\\{D_{i}\right\\}}$
$\displaystyle\sum\limits_{i=1}^{d}D_{i}+\frac{\lambda}{2}\sum\limits_{i=1}^{d}\log\left(\frac{\sigma_{i}^{2}}{D_{i}}-(\alpha-1)\right),$
(24) subject to $\displaystyle D_{i}\leq\frac{\sigma_{i}^{2}}{\alpha}\hskip
14.22636pt\text{ for all }i\in\left[d\right].$

This optimization problem is nonconvex since the function
$\log\left(\frac{\sigma_{i}^{2}}{D_{i}}-(\alpha-1)\right)$ is convex for
$0\leq D_{i}\leq\frac{\sigma_{i}^{2}}{2(\alpha-1)}$ but concave for
$\frac{\sigma_{i}^{2}}{2(\alpha-1)}<D_{i}\leq\frac{\sigma_{i}^{2}}{\alpha}$
and the latter interval is nonempty since $\alpha>2$.

Any optimizing $\\{D_{i}\\}$ must be a stationary point of

${\cal
L}\left(\left\\{D_{i}\right\\}_{i=1}^{d},\lambda,\left\\{\mu_{i}\right\\}_{i=1}^{d}\right)=\sum\limits_{i=1}^{d}D_{i}+\lambda\left(\sum\limits_{i=1}^{d}\log\left(\frac{\sigma_{i}^{2}}{D_{i}}-(\alpha-1)\right)\right)+\sum\limits_{i=1}^{d}\mu_{i}\left(D_{i}-\frac{\sigma_{i}^{2}}{\alpha}\right).$
(25)

for some $\\{\mu_{i}\\}_{i=1}^{d}$ with $\mu_{i}\geq 0$ for all
$i\in\left[d\right]$ and satisfying the complementary slackness condition
[Ber99, Prop. 3.3.1]. The stationary points satisfy, for each $i$

$\frac{\partial{\cal L}}{\partial
D_{i}}=1-\lambda\left(\frac{\frac{\sigma_{i}^{2}}{D_{i}^{2}}}{\left(\frac{\sigma_{i}^{2}}{D_{i}}-(\alpha-1)\right)}\right)+\mu_{i}=0.$
(26)

Let ${\cal F}=\left\\{i:D_{i}<\frac{\sigma_{i}^{2}}{\alpha}\right\\}$. For
$i\in{\cal F}$, $\mu_{i}=0$ due to complementary slackness. Substituting in
(26) we obtain a quadratic equation in $D_{i}$

$(\alpha-1)D_{i}^{2}-\sigma_{i}^{2}D_{i}+\lambda\sigma_{i}^{2}=0.$

which gives

$D_{i}=\frac{\sigma_{i}^{2}}{2(\alpha-1)}\left(1\pm\sqrt{1-\frac{4\lambda(\alpha-1)}{\sigma_{i}^{2}}}\right).$

Let $c_{i}=\sqrt{1-\frac{4\lambda(\alpha-1)}{\sigma_{i}^{2}}}$. Note that
$\frac{\sigma_{i}^{2}}{2(\alpha-1)}\left(1+c_{i}\right)$ is always in the
concave region and $\frac{\sigma_{i}^{2}}{2(\alpha-1)}\left(1-c_{i}\right)$ is
always in the convex region for a $\lambda$ chosen such that $D_{i}$ is a real
number strictly less than $\frac{\sigma_{i}^{2}}{\alpha}$.

Therefore the optimal set of distortions are contained in the following set of
$3^{d}$ points

$\prod_{i=1}^{d}\left\\{\frac{\sigma_{i}^{2}}{2(\alpha-1)}\left(1+\sqrt{1-\frac{4\lambda(\alpha-1)}{\sigma_{i}^{2}}}\right),\frac{\sigma_{i}^{2}}{2(\alpha-1)}\left(1-\sqrt{1-\frac{4\lambda(\alpha-1)}{\sigma_{i}^{2}}}\right),\frac{\sigma_{i}^{2}}{\alpha}\right\\}.$

We now reduce the size of the above set by making a two observations:

(1). ${\cal F}$ is contiguous.

######  Lemma 4.

There exists an optimal $\left\\{D_{i}^{*}\right\\}_{i=1}^{d}$ for (24) such
that (a) $\frac{\sigma_{i}^{2}}{D_{i}^{*}}$ is a nonincreasing sequence and
(b) ${\cal F}=\\{1,2,\cdots\left\lvert{\cal F}\right\rvert\\}$.

###### Proof.

Substitute $x_{i}=\frac{\sigma_{i}^{2}}{D_{i}}$ in (24). This gives us

$\displaystyle\inf\limits_{\left\\{x_{i}\right\\}}$
$\displaystyle\sum\limits_{i=1}^{d}\frac{\sigma_{i}^{2}}{x_{i}}+\frac{\lambda}{2}\sum\limits_{i=1}^{d}\log\left(x_{i}-(\alpha-1)\right),$
(27) subject to $\displaystyle x_{i}\geq\alpha\hskip 14.22636pt\text{ for all
}i\in\left[d\right].$

Let $\\{x_{i}^{*}\\}_{i=1}^{d}$ be an optimal solution for (27). If, for
$i>j$, $x_{i}^{*}>x_{j}^{*}\geq\alpha$, then exchanging the values provides a
solution that has the same rate and lower distortion since
$\frac{\sigma_{i}^{2}}{x_{i}^{*}}+\frac{\sigma_{j}^{2}}{x_{j}^{*}}\geq\frac{\sigma_{i}^{2}}{x_{j}^{*}}+\frac{\sigma_{j}^{2}}{x_{i}^{*}}$.
This proves (a). Part (b) follows immediately. ∎

(2). No two solutions are concave.

######  Lemma 5.

For $R>0$, let $\left\\{D_{i}^{*}\right\\}_{i=1}^{d}$ be an optimal solution
for (24). There exists at most one $D_{i}^{*}$ such that
$\frac{\sigma_{i}^{2}}{2(\alpha-1)}<D_{i}^{*}<\frac{\sigma_{i}^{2}}{\alpha}$.

###### Proof.

Let $D_{i}^{*},D_{j}^{*}$ be such that
$\frac{\sigma_{i}^{2}}{2(\alpha-1)}<D_{i}^{*}<\frac{\sigma_{i}^{2}}{\alpha}$
and
$\frac{\sigma_{j}^{2}}{2(\alpha-1)}<D_{j}^{*}<\frac{\sigma_{j}^{2}}{\alpha}$ .
Without loss of generality, assume $D_{i}^{*}<D_{j}^{*}$. Denote the
individual rate constraint function by
$r\left(D_{i}\right)\triangleq\log\left(\frac{\sigma_{i}^{2}}{D_{i}}-(\alpha-1)\right)$.
Since $r$ is concave in
$\left(\frac{\sigma_{i}^{2}}{2(a-1)},\frac{\sigma_{i}^{2}}{\alpha}\right)$,
there exist an $\varepsilon>0$ such that

$\displaystyle
r\left(D_{i}^{*}-\varepsilon\right)+r\left(D_{j}^{*}+\varepsilon\right)$
$\displaystyle=r\left(D_{i}^{*}\right)-\varepsilon
r^{\prime}\left(D_{i}^{*}\right)+O(\varepsilon^{2})+r\left(D_{j}^{*}\right)+\varepsilon
r^{\prime}\left(D_{j}^{*}\right)+O(\varepsilon^{2})$ (28)
$\displaystyle<r\left(D_{i}^{*}\right)+r\left(D_{j}^{*}\right)$ (29)

The last inequality follows from concavity of $r$. Therefore, replacing
$\left(D_{i}^{*},D_{j}^{*}\right)$ with
$\left(D_{i}^{*}-\varepsilon,D_{j}^{*}+\varepsilon\right)$, the rate
constraint can be improved while keeping the objective in (24) constant,
contradicting the optimality assumption of $\left\\{D_{i}^{*}\right\\}$. ∎

There is at most one $D_{i}^{*}$ such that
$D_{i}^{*}=\frac{\sigma_{i}^{2}}{2(\alpha-1)}\left(1+c_{i}\right)$. Assuming
such an $i$ exists, $x_{i}=\frac{2(\alpha-1)}{1+c_{i}}<2(\alpha-1)$. For the
convex roots, $x_{i}=\frac{2(\alpha-1)}{1-c_{i}}>2(a-1)$. Therefore from Lemma
4, all the convex roots are contiguous. Therefore, the set of potentially
optimal solutions reduces to cardinality $2d$, where each solution is
characterized by the number of components that send non-zero rate and whether
or not a concave root is sent. PBA, detailed in Algorithm 1 finds the minimum
value of the Lagrangian across these $2d$ solutions for a fixed $\lambda$. ∎

Note that by sweeping $\lambda>0$, one can compute the lower convex envelope
of the $(D,R)$ curve. Since every Pareto optimal $(D,R)$ must be a stationary
point of (21), one can also use Algorithm 1 to compute the $(D,R)$ curve
itself by sweeping $\lambda$ and retaining all those stationary points that
are not Pareto dominated.

##  4 Application to Variable-Rate Compression

We have seen that an autoencoder formulation inspired by data compression
succeeds in providing guaranteed recovery the principal source components.
Conversely, a number of successful multimedia compressors have recently been
proposed that are either related to, or directly inspired by, autoencoders
[TAL18, TVJ+17, BLS16, TOH+16, TSCH17, RB17, HRTC19, AMT+17, BMS+18, ZCG+18,
ATM+19, BCM+20]. In particular, Ballé _et al._ [BMS+18] show that the
objective minimized by their compressor coincides with that of variational
autoencoders. Following [BCM+20], we refer to this objective as _nonlinear
transform coding (NTC)_. We next use Theorem 1 to show that any minimizer of
the NTC objective is guaranteed to recover the principal source components if
(1) the source is Gaussian, (2) the transforms are restricted to be linear,
and (3) the entropy model is _factorized_ , as explained below.

Let $\bm{x}\sim{\cal N}\left(0,\bm{K}\right)$, where $\bm{K}$ is a positive
semidefinite covariance matrix. As before, we consider an autoencoder defined
by its encoder-decoder pair $(f,g)$, where for $k\leq d$,
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{k}$ and
$g:\mathbb{R}^{k}\rightarrow\mathbb{R}^{d}$ are chosen from prespecified
classes ${\cal C}_{f}$ and ${\cal C}_{g}$. The NTC framework assumes dithered
quantization during training, as in Section 2 and [AT20, CEKL19], and seeks to
minimize the Lagrangian

$\inf_{f\in{\cal C}_{f},g\in{\cal
C}_{g}}\mathbb{E}_{\bm{x},\bm{\varepsilon}}\left[\left\lVert\bm{x}-g\left(Q\left(f(\bm{x})+\bm{\varepsilon}\right)-\bm{\varepsilon}\right)\right\rVert_{2}^{2}\right]+\lambda
H\left(Q\left(f(\bm{x})+\bm{\varepsilon}\right)-\bm{\varepsilon}|\bm{\varepsilon}\right).$
(30)

where $\lambda>0$ and $\bm{\varepsilon}$ has i.i.d.
$\text{Unif}\left[-0.5,0.5\right]$ components. NTC assumes variable-length
compression, and the quantity

$H\left(Q\left(f(\bm{x})+\bm{\varepsilon}\right)-\bm{\varepsilon}|\bm{\varepsilon}\right)$

is an accurate estimate of minimum expected codelength length for the discrete
random vector $Q\left(f(\bm{x})+\bm{\varepsilon}\right)$. As we noted in
Section 2, [ZF92] showed that for any random variable $\bm{x}$,
$Q\left(\bm{x}+\bm{\varepsilon}\right)-\bm{\varepsilon}$ and
$\bm{x}+\bm{\varepsilon}$ have the same joint distribution with $\bm{x}$. They
also showed that
$H\left(Q\left(\bm{x}+\bm{\varepsilon}\right)-\bm{\varepsilon}|\bm{\varepsilon}\right)=I\left(\bm{x}+\bm{\varepsilon};\bm{x}\right)=h(\bm{x}+\bm{\varepsilon})$,
where $h(\cdot)$ denotes differential entropy. Therefore, the objective can be
written as

$\inf_{f\in{\cal C}_{f},g\in{\cal
C}_{g}}\mathbb{E}_{\bm{x},\bm{\varepsilon}}\left[\left\lVert\bm{x}-g\left(f\left(\bm{x}\right)+\bm{\varepsilon}\right)\right\rVert_{2}^{2}\right]+\lambda
h\left(f\left(\bm{x}\right)+\bm{\varepsilon}\right).$ (31)

(Compare eq.(13) in [BCM+20]).

We consider the case in which ${\cal C}_{f},{\cal C}_{g}$ are the class of
linear functions. Let $\bm{W},\bm{T}$ be $d$-by-$d$ matrices. Define
$f\left(\bm{x}\right)=\bm{W}^{\top}\bm{x}$,
$g\left(\bm{x}\right)=\bm{T}\bm{x}$. Substituting this in the above equation,
we obtain

$\inf\limits_{\bm{W},\bm{T}}\mathbb{E}_{\bm{x},\bm{\varepsilon}}\left[\left\lVert\bm{x}-\bm{T}\left(\bm{W}^{\top}\bm{x}+\bm{\varepsilon}\right)\right\rVert_{2}^{2}\right]\\\
+\lambda h\left(\bm{W}^{\top}\bm{x}+\bm{\varepsilon}\right).$ (32)

Since $\bm{T}$ does not appear in the rate constraint, the optimal $\bm{T}$
can be chosen to be the minimum mean squared error estimator of
$\bm{x}\sim{\cal N}\left(0,\bm{K}\right)$ given
$\bm{W}^{\top}\bm{x}+\bm{\varepsilon}$, as in Section 2. This gives

$\inf\limits_{\bm{W}}\text{tr}(\bm{K})-\text{tr}(\bm{K}\bm{W}\left(\bm{W}^{\top}\bm{K}\bm{W}+\frac{\bm{I}}{12}\right)^{-1}\bm{W}^{\top}\bm{K})+\lambda
h\left(\bm{W}^{\top}\bm{x}+\bm{\varepsilon}\right).$ (33)

As noted earlier, the rate term
$h\left(\bm{W}^{\top}\bm{x}+\bm{\varepsilon}\right)$ is an accurate estimate
for the minimum expected length of the compressed representation of
$Q\left(\bm{W}^{\top}\bm{x}+\bm{\varepsilon}\right)$. This assumes that the
different components of this vector are encoded jointly, however. In practice,
one often encodes them separately, relying on the transform $\bm{W}$ to
eliminate redundancy among the components. Accordingly, we replace the rate
term with

$\sum_{i=1}^{d}h\left(\bm{w}_{i}^{\top}\bm{x}+[\bm{\varepsilon}]_{i}\right),$

to arrive at the optimization problem

$\inf\limits_{\bm{W}}\text{tr}(\bm{K})-\text{tr}(\bm{K}\bm{W}\left(\bm{W}^{\top}\bm{K}\bm{W}+\frac{\bm{I}}{12}\right)^{-1}\bm{W}^{\top}\bm{K})+\lambda\cdot\sum_{i=1}^{d}h\left(\bm{w}_{i}^{\top}\bm{x}+[\bm{\varepsilon}]_{i}\right).$
(34)

######  Theorem 6.

Suppose $\bm{K}$ has distinct eigenvalues. Then any $\bm{W}$ that achieves the
infimum in (34) has the property that all of its nonzero rows are eigenvectors
of $\bm{K}$.

###### Proof.

Since the distribution of $\bm{\varepsilon}$ is fixed, by the Gaussian
assumption on $\bm{x}$,
$h\left(\bm{w}_{j}^{\top}\bm{x}+[\bm{\varepsilon}]_{j}\right)$ only depends on
$\bm{w}_{j}$ through $\bm{w}^{\top}_{j}\bm{K}\bm{w}_{j}$. Thus we may write

$h(\bm{w}_{j}^{\top}\bm{x}+\epsilon)=\rho_{sl}(\bm{w}_{j}^{\top}\bm{K}\bm{w}_{j}).$
(35)

By Theorem 1, it suffices to show that $\rho_{sl}(\cdot)$ is strictly concave.
Let $Z$ be a standard Normal random variable and let $\epsilon$ be uniformly
distributed over $[-1/2,1/2]$, independent of $Z$. Then we have

$\displaystyle\rho_{sl}(s)$ $\displaystyle=h(\sqrt{s}\cdot Z+\epsilon).$ (36)

Thus by de Bruijn’s identity [CT06],

$\rho^{\prime}_{sl}(s)=\frac{1}{2}J(\epsilon+\sqrt{s}\cdot Z),$ (37)

where $J(\cdot)$ is the Fisher information. To show that
$\rho^{\prime}_{sl}(\cdot)$ is strictly concave, it suffices to show that
$J(\epsilon+\sqrt{s}\cdot Z)$ is strictly decreasing in $s$.222If
$g^{\prime}(\cdot)$ is strictly decreasing then for all $t>s$,
$g(t)=g(s)+\int_{s}^{t}g^{\prime}(u)du<g(s)+g^{\prime}(s)(t-s)$ and likewise
for $t<s$. That $g(\cdot)$ is strictly concave then follows from the standard
first-order test for concavity [BV04]. To this end, let $t>s>0$ and let
$Z_{1}$ and $Z_{2}$ be i.i.d. standard Normal random variables, independent of
$\epsilon$. Then

$J(\epsilon+\sqrt{t}\cdot Z)=J(\epsilon+\sqrt{s}\cdot Z_{1}+\sqrt{t-s}\cdot
Z_{2})$ (38)

and by the convolution inequality for Fisher information [Bla65],

$\displaystyle\frac{1}{J(\epsilon+\sqrt{s}\cdot Z_{1}+\sqrt{t-s}\cdot
Z_{2})}>\frac{1}{J(\epsilon+\sqrt{s}\cdot Z_{1})}+\frac{1}{J(\sqrt{t-s}\cdot
Z_{2})}>\frac{1}{J(\epsilon+\sqrt{s}\cdot Z_{1})},$ (39)

where the first inequality is strict because $\epsilon+\sqrt{s}\cdot Z_{1}$ is
not Gaussian distributed. ∎

##  5 Compression Experiments

We validate the PBA algorithm experimentally by comparing the performance of a
PBA-derived fixed-rate compressor against the performance of baseline fixed-
rate compressors. The code of our implementation can be found at
https://github.com/SourbhBh/PBA. As we noted in the previous section, although
variable-rate codes are more commonplace in practice, fixed-rate codes do
offer some advantages over their more general counterparts:

  1. 1.

In applications where a train of source realizations are compressed
sequentially, fixed-rated coding allows for simple concatenation of the
compressed representations. Maintaining synchrony between the encoder and
decoder is simpler than with variable-rate codes.

  2. 2.

In applications where a dataset of source realizations are individually
compressed, fixed-rate coding allows for random access of data points from the
compressed representation.

  3. 3.

In streaming in which a sequence of realizations will be streamed, bandwidth
provisioning is simplified when the bit-rate is constant over time.

Fixed-rate compressors exist for specialized sources such as speech [MB95,
SA85] and audio more generally [Vor]. We consider a general-purpose, learned,
fixed-rate compressor derived from PBA and the following two quantization
operations. The first, $Q_{CD}(a,\sigma^{2},U,x)$333“CD” stands for “clamped
dithered.” accepts the hyperparameter $a$, a variance estimate $\sigma^{2}$, a
dither realization $U$, and the scalar source realization to be compressed,
$x$, and outputs (a binary representation of) the nearest point to $x$ in the
set

$\left\\{i+U:i\in\mathbb{Z}\ \text{and}\
i+U\in\left(-\frac{\Gamma}{2},\frac{\Gamma}{2}\right]\right\\}{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}{,}}$
(40)

where

$\Gamma=2^{\lfloor\frac{1}{2}\log_{2}(4a^{2}\sigma^{2}+1)\rfloor}.$ (41)

This evidently requires $\log_{2}\Gamma$ bits. The second function,
$Q_{CD}^{\prime}(a^{2},\sigma^{2},U,b)$, where $b$ is a binary string of
length $\log_{2}\Gamma$, maps the binary representation $b$ to the point in
(40). These quantization routines are applied separately to each latent
component. The $\sigma^{2}$ parameters are determined during training. The
dither $U$ is chosen uniformly over the set $[-1/2,1/2]$, independently for
each component. We assume that $U$ is chosen pseudorandomly from a fixed seed
that is known to both the encoder and the decoder. As such, it does not need
to be explicitly communicated. For our experiments, we fix the $a$ parameter
at $15$ and hard code this both at the encoder and at the decoder. We found
that this choice balances the dual goals of minimizing the excess distortion
due to the clamping quantized points to the interval $(\Gamma/2,\Gamma/2]$ and
minimizing the rate.

PBA compression proceeds by applying Algorithm 1 to a training set to
determine the matrices $\bm{W}$ and $\bm{T}$. The variance estimates
$\sigma_{1}^{2},\ldots,\sigma_{d}^{2}$ for the $d$ latent variances are chosen
as the empirical variances on the training set and are hard-coded in the
encoder and decoder. Given a data point $\bm{x}$, the encoded representation
is the concatenation of the bit strings $b_{1},\ldots,b_{d}$, where

$b_{i}=Q_{CD}(a^{2},\sigma^{2}_{i},U_{i},\bm{w}_{i}^{\top}x),$

The decoder parses the received bits into $b_{1},\ldots,b_{d}$. and computes
the latent reconstruction $\hat{\bm{y}}$, where

$\hat{\bm{y}}_{i}=Q_{CD}^{\prime}(a^{2},\sigma^{2}_{i},U_{i},b_{i}),$

The reconstruction is then $\bm{T}\hat{\bm{y}}$.

We evaluate the PBA compressor on MNIST [LBBH98], CIFAR-10 [Kri09], MIT Faces
Dataset, Free Spoken Digit Dataset (FSDD) [Jac] and a synthetic Gaussian
dataset. The synthetic Gaussian dataset is generated from a diagonal
covariance matrix obtained from the eigenvalues of the Faces Dataset. We
compare our algorithms primarily using mean-squared error since our
theoretical analysis uses mean squared error as the distortion metric. Our
plots display Signal-to-Noise ratios (SNRs) for ease of interpretation. For
image datasets, we also compare our algorithms using the Structural Similarity
(SSIM) or the Multi-scale Strctural Similarity (MS-SSIM) metrics when
applicable [WBSS04]. We also consider errors on downstream tasks, specifically
classification, as a distortion measure.

For all datasets, we compare the performance of the PBA compressor against
baseline scheme derived from PCA that uses $Q_{CD}$ and $Q_{CD}^{\prime}$. The
PCA-based scheme sends some of the principal components essentially
losslessly, and no information about the others. Specifically, in the context
of our framework, for any given $k$, we choose the first $k$ columns of
$\bm{W}$ to be aligned with the first $k$ principal components of the dataset;
the remaining columns are zero. Each nonzero column is scaled such that its
Euclidean length multiplied by the eigenvalue has all the significant digits.
This is done so that at high rates, the quantization procedure sends the $k$
principal components losslessly. The quantization and decoder operations are
as in the PBA-based scheme; in particular the $a^{2}$ parameter is as
specified above. By varying $k$, we trade off rate and distortion.

###  5.1 SNR Performance

Figure 2: Reconstructions at different bits/pixel values for PCA (top) and PBA
(bottom)

Figure 3: SNR/pixel vs Rate (bits/pixel) for MNIST, CIFAR-10, Faces, FSDD
datasets. Figures in the bottom row are zoomed-in.

Figure 4: SNR/pixel vs Rate (bits/pixel) for MNIST, CIFAR-10, Faces and
Synthetic dataset. Reconstructions are not rounded to integers from $0$ to
$255$. The bottom four plots are zoomed-in versions of the top four plots.

Figure 5: Eigenvalue distribution of the datasets. The top three plots are the
largest 25 eigenvalues for MNIST, CIFAR-10, Faces and FSDD dataset. The bottom
four figures plot the remaining eigenvalues except the largest 500.

Figure 6: Plots of number of components sent vs rate (bits/pixel) for PBA and
PCA.

We begin by examining compression performance under mean squared error, or
equivalently, the SNR, defined as

$\text{SNR}=10\cdot\log_{10}\left(\frac{P}{\text{MSE}}\right).$

where $P$ is the empirical second moment of the dataset. This was the
objective that PBA (and PCA) is designed to minimize.

In Figure 2, we display reconstructions for a particular image in the Faces
Dataset under PBA and PCA. Figure 3 shows the tradeoff for PBA and PCA against
JPEG and JPEG2000 (for the image datasets) and AAC (for the audio dataset).
All of the image datasets have integer pixel values between 0 and 255.
Accordingly, we round the reconstuctions of PBA and PCA to the nearest integer
in this range. Figure 4 shows the same tradeoff for PBA and PCA when
reconstructions are not rounded off to the nearest integer. We see that PBA
consistently outperforms PCA and JPEG, and is competitive with JPEG2000, even
though the JPEG and JPEG2000 are variable-rate. 444It should be noted,
however, that JPEG and JPEG2000 aim to minimize subjective distortion, not
MSE, and they do not allow for training on sample images, as PBA and PCA do. A
similar caveat applies to AAC. We estimate the size of the JPEG header by
compressing an empty image and subtract this estimate from all the compression
sizes produced by JPEG. We do not plot JPEG2000 performance for MNIST since it
requires at least a 32x32 image. For audio data, we observe that PBA
consistently outperforms PCA and AAC. Since the image data all use $8$ bits
per pixel, one can obtain infinite SNR at this rate via the trivial encoding
that communicates the raw bits. PCA and PBA do not find this solution because
they quantize in the transform domain, where the lattice-nature of the pixel
distribution is not apparent. Determining how to leverage lattice structure in
the source distribution for purposes of compression is an interesting question
that transcends the PBA and PCA algorithms and that we will not pursue here.

The reason that PCA performs poorly is that it favors sending the less
significant bits of the most significant components over the most significant
bits of less significant components, when the latter are more valuable for
reconstructing the source. Arguably, it does not identify the “principal
bits.” Figure 5 shows the eigenvalue distribution of the different datasets,
and Figure 6 shows the number of distinct components about which information
is sent as a function of rate for both PBA and PCA. We see that PBA sends
information about many more components for a given rate than does PCA. We
discuss the ramifications of this for downstream tasks, such as
classification, in Section 5.3.

###  5.2 SSIM Performance

Structural similarity (SSIM) and Multi-Scale Structural similarity (MS-SSIM)
are metrics that are tuned to perceptual similarity. Given two images, the
SSIM metric outputs a real value between $0$ and $1$ where a higher value
indicates more similarity between the images. We evaluate the performance of
our algorithms on these metrics as well in Figure 7. We see that PBA
consistently dominates PCA, and although it was not optimized for this metric,
beats JPEG at low rates as well.

Figure 7: SSIM vs Rate (bits/pixel) for MNIST, CIFAR-10, Faces Dataset

###  5.3 Performance on Downstream tasks

Lastly, we compare the impact of using PBA and PCA on an important downstream
task, namely classification. We evaluate the algorithms on MNIST and CIFAR-10
datasets and use neural networks for classification. Our hyperparameter and
architecture choices are given in Table 1. We divide the dataset into three
parts. From the first part, we obain the covariance matrix that we use for PCA
and to obtain the PBA compressor. The second and third part are used as
training and testing data for the purpose of classification. For a fixed rate,
reconstructions are passed to the neural networks for training and testing
respectively. Since our goal is to compare classification accuracy across the
compressors, we fix both the architecture and hyperparameters, and do not
perform any additional tuning for the separate algorithms.

Figure 8 shows that PBA outperforms PCA in terms of accuracy. The difference
is especially significant for low rates; all algorithms attain roughly the
same performance at higher rates.

Hyperparameter | MNIST | CIFAR-10
---|---|---
Architecture | 2-layer fully connected NN | Convolutional Neural Network
|  | with 2 convolutional layers, pooling and
|  | three fully connected layers
# Hidden Neurons | 100 | NA
Optimization Algorithm | Adam | SGD with momentum
Loss | Cross-entropy | Cross-entropy
Learning Rate | 0.0005 | 0.01
Table 1: Hyperparameter Choices and Architecture for Classification

Figure 8: Accuracy vs Rate (bits/pixel) for MNIST, CIFAR-10

## References

  * [AMT+17] Eirikur Agustsson, Fabian Mentzer, Michael Tschannen, Lukas Cavigelli, Radu Timofte, Luca Benini, and Luc V Gool.  Soft-to-hard vector quantization for end-to-end learning compressible representations.  In Advances in Neural Information Processing Systems 30, pages 1141–1151, 2017.
  * [AT20] Eirikur Agustsson and Lucas Theis.  Universally quantized neural compression.  In Advances in Neural Information Processing Systems 33, pages 12367–12376, 2020.
  * [ATM+19] Eirikur Agustsson, Michael Tschannen, Fabian Mentzer, Radu Timofte, and Luc Van Gool.  Generative adversarial networks for extreme learned image compression.  In Proceedings of the IEEE International Conference on Computer Vision, pages 221–231, 2019.
  * [BCM+20] Johannes Ballé, Philip A Chou, David Minnen, Saurabh Singh, Nick Johnston, Eirikur Agustsson, Sung Jin Hwang, and George Toderici.  Nonlinear transform coding.  arXiv:2007.03034, 2020.
  * [Ber99] Dimitri P. Bertsekas.  Nonlinear Programming.  Athena Scientific, 1999.
  * [BH89] Pierre Baldi and Kurt Hornik.  Neural networks and principal component analysis: Learning from examples without local minima.  Neural Networks, 2(1):53 – 58, 1989.
  * [Bis06] Christopher M. Bishop.  Pattern Recognition and Machine Learning (Information Science and Statistics).  Springer-Verlag, Berlin, Heidelberg, 2006.
  * [BK88] Herve Bourlard and Y. Kamp.  Auto-association by multilayer perceptrons and singular value decomposition.  Biological Cybernetics, 59:291–294, 1988.
  * [Bla65] Nelson M. Blachman.  The convolution inequality for entropy powers.  IEEE Trans. Inf. Theory, 11(2):267–271, April 1965.
  * [BLS16] Johannes Ballé, Valero Laparra, and Eero Simoncelli.  End-to-end optimization of nonlinear transform codes for perceptual quality.  In 2016 Picture Coding Symposium (PCS), 2016.
  * [BLSG20] Xuchan Bao, James Lucas, Sushant Sachdeva, and Roger Grosse.  Regularized linear autoencoders recover the principal components, eventually.  arXiv:2007.06731, 2020.
  * [BMS+18] Johannes Ballé, David Minnen, Saurabh Singh, Sung Jin Hwang, and Nick Johnston.  Variational image compression with a scale hyperprior.  In International Conference on Learning Representations, 2018.
  * [BV04] Stephen Boyd and Lieven Vandenberghe.  Convex Optimization.  Cambridge, 2004.
  * [CEKL19] Yoojin Choi, Mostafa El-Khamy, and Jungwon Lee.  Variable rate deep image compression with a conditional autoencoder.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), October 2019.
  * [CT06] Thomas M. Cover and Joy A. Thomas.  Elements of Information Theory.  Wiley, 2006.
  * [HJ13] Roger A. Horn and Charles R. Johnson, editors.  Matrix Analysis.  Cambridge University Press, USA, 2013.
  * [HRTC19] Amirhossein Habibian, Ties van Rozendaal, Jakub M Tomczak, and Taco S Cohen.  Video compression with rate-distortion autoencoders.  In Proceedings of the IEEE International Conference on Computer Vision, pages 7033–7042, 2019.
  * [HS06] Geoffrey E Hinton and Ruslan R Salakhutdinov.  Reducing the dimensionality of data with neural networks.  Science, 313(5786):504–507, 2006.
  * [Jac] Zohar Jackson.  Free spoken digit dataset (fsdd).  https://github.com/Jakobovski/free-spoken-digit-dataset.
  * [Kay98] Steven M Kay.  Estimation Theory.  Prentice Hall PTR, 1998.
  * [KBGS19] Daniel Kunin, Jonathan Bloom, Aleksandrina Goeva, and Cotton Seed.  Loss landscapes of regularized linear autoencoders.  In International Conference on Machine Learning, volume 97, pages 3560–3569, 2019.
  * [Kri09] Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Master’s Thesis, Department of Computer Science, University of Toronto, 2009.
  * [LBBH98] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [LNP19] Saïd Ladjal, Alasdair Newson, and Chi-Hieu Pham.  A pca-like autoencoder.  abs/1904.01277, 2019.
  * [LTGN19] James Lucas, George Tucker, Roger B Grosse, and Mohammad Norouzi.  Don’t blame the elbo! a linear vae perspective on posterior collapse.  In Advances in Neural Information Processing Systems, volume 32, pages 9408–9418, 2019.
  * [LZW+21] Liang Liao, Xuechun Zhang, Xinqiang Wang, Sen Lin, and Xin Liu.  Generalized image reconstruction over t-algebra.  arXiv:2101.06650, 2021.
  * [MB95] Alan V. McCree and Thomas P. Barnwell.  A mixed excitation lpc vocoder model for low bit rate speech coding.  IEEE Transactions on Speech and Audio Processing, 3(4):242–250, 1995.
  * [MOA11] Albert W. Marshall, Ingram Olkin, and Barry C. Arnold.  Inequalities: Theory of Majorization and its Applications, volume 143.  Springer, 2011.
  * [OSWS20] Reza Oftadeh, Jiayi Shen, Zhangyang Wang, and Dylan Shell.  Eliminating the invariance on the loss landscape of linear autoencoders.  In International Conference on Machine Learning, pages 7405–7413, 2020.
  * [RB17] Oren Rippel and Lubomir Bourdev.  Real-time adaptive image compression.  In International Conference on Machine Learning, pages 2922–2930, 2017.
  * [RZM19] Michal Rolínek, Dominik Zietlow, and Georg Martius.  Variational autoencoders pursue pca directions (by accident).  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [SA85] M. Schroeder and B. Atal.  Code-excited linear prediction(celp): High-quality speech at very low bit rates.  In IEEE International Conference on Acoustics, Speech, and Signal Processing, volume 10, pages 937–940, 1985.
  * [San12] Rafael do EspArito Santo.  Principal Component Analysis Applied to Digital Image Compression.  Einstein (Sáo Paulo), 10:135 – 139, 06 2012.
  * [TAL18] Michael Tschannen, Eirikur Agustsson, and Mario Lucic.  Deep generative models for distribution-preserving lossy compression.  In Advances in Neural Information Processing Systems 31, pages 5929–5940. 2018.
  * [TOH+16] George Toderici, Sean M O’Malley, Sung Jin Hwang, Damien Vincent, David Minnen, Shumeet Baluja, Michele Covell, and Rahul Sukthankar.  Variable rate image compression with recurrent neural networks.  In International Conference on Learning Representations, 2016.
  * [TSCH17] Lucas Theis, Wenzhe Shi, Andrew Cunningham, and Ferenc Huszár.  Lossy image compression with compressive autoencoders.  In International Conference on Learning Reperesentations, 2017.
  * [TVJ+17] George Toderici, Damien Vincent, Nick Johnston, Sung Jin Hwang, David Minnen, Joel Shor, and Michele Covell.  Full resolution image compression with recurrent neural networks.  In IEEE Conference on Computer Vision and Pattern Recognition, pages 5435–5443, 2017.
  * [Vor] Vorbis audio compression.  https://xiph.org/vorbis/.  Accessed: 2021-01-26.
  * [WBSS04] Zhou Wang, A. C Bovik, H. R. Sheikh, and E. P. Simoncelli.  Image quality assessment: From error visibility to structural similarity.  IEEE Transactions on Image Processing, 13(4):600–612, 2004.
  * [ZCG+18] Lei Zhou, Chunlei Cai, Yue Gao, Sanbao Su, and Junmin Wu.  Variational autoencoder for low bit-rate image compression.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 2617–2620, 2018.
  * [ZF92] Ram Zamir and Meir Feder.  On universal quantization by randomized uniform/lattice quantizers.  IEEE Trans. Inf. Theory, 38:428–436, 1992.

##  Appendix A Review of Schur-Convexity

In this section, we review the key definitions and theorems related to Schur-
convexity that we use in the proof of Theorem 1.

######  Definition 7.

(Majorization)[HJ13] For a vector $\bm{v}\in\mathbb{R}^{d}$, let
$\bm{v}^{\downarrow}$ denote the vector with the same components arranged in
descending order. Given vectors $\bm{a},\bm{b}\in\mathbb{R}^{d}$, we say
$\bm{a}$ majorizes $\bm{b}$ and denote $\bm{a}\succ\bm{b}$, if

$\sum\limits_{i=1}^{d}\left[\bm{a}\right]_{i}=\sum\limits_{i=1}^{d}\left[\bm{b}\right]_{i},$

and for all $k\in\left[d-1\right]$,

$\sum\limits_{i=1}^{k}\left[\bm{a}^{\downarrow}\right]_{i}\geq\sum\limits_{i=1}^{k}\left[\bm{b}^{\downarrow}\right]_{i}.$

######  Definition 8.

(Schur-convexity) A function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is Schur-
convex if for any vectors $\bm{a},\bm{b}\in\mathbb{R}^{d}$, such that
$\bm{a}\succ\bm{b}$,

$f\left(\bm{a}\right)\geq f\left(\bm{b}\right).$

$f$ is strictly Schur-convex if the above inequality is a strict inequality
for any $\bm{a}\succ\bm{b}$ that are not permutations of each other. $f$ is
Schur-concave if the direction of the inequality is reversed and is strictly
Schur concave if the direction of the inequality is reversed and it is a
strict inequality for any $\bm{a}\succ\bm{b}$ that are not permutations of
each other.

######  Proposition 9.

[MOA11] If $f:\mathbb{R}\rightarrow\mathbb{R}$ is convex, then
$\phi:\mathbb{R}^{d}\rightarrow\mathbb{R}$ given by

$\phi\left(\bm{v}\right)=\sum\limits_{i=1}^{d}f\left(\left[v\right]_{i}\right)$

is Schur-convex. If $f$ is concave, then $\phi$ is Schur-concave. Likewise if
$f$ is strictly convex, $\phi$ is strictly Schur-convex and if $f$ is strictly
concave, $\phi$ is strictly Schur-concave.