  An autoencoder is a layered neural network whose structure can be viewed as
consisting of an encoder, which compresses an input vector of dimension $D$ to
a vector of low dimension $d$, and a decoder which transforms the
low-dimensional vector back to the original input vector (or one that is very
similar). In this paper we explore the compressive power of autoencoders that
are Boolean threshold networks by studying the numbers of nodes and layers that
are required to ensure that the numbers of nodes and layers that are required
to ensure that each vector in a given set of distinct input binary vectors is
transformed back to its original. We show that for any set of $n$ distinct
vectors there exists a seven-layer autoencoder with the smallest possible
middle layer, (i.e., its size is logarithmic in $n$), but that there is a set
of $n$ vectors for which there is no three-layer autoencoder with a middle
layer of the same size. In addition we present a kind of trade-off: if a
considerably larger middle layer is permissible then a five-layer autoencoder
does exist. We also study encoding by itself. The results we obtain suggest
that it is the decoding that constitutes the bottleneck of autoencoding. For
example, there always is a three-layer Boolean threshold encoder that
compresses $n$ vectors into a dimension that is reduced to twice the logarithm
of $n$.
