Expression of Fractals Through Neural Network Functions
  To help understand the underlying mechanisms of neural networks (NNs),
several groups have, in recent years, studied the number of linear regions
$\ell$ of piecewise linear functions generated by deep neural networks (DNN).
In particular, they showed that $\ell$ can grow exponentially with the number
of network parameters $p$, a property often used to explain the advantages of
DNNs over shallow NNs in approximating complicated functions. Nonetheless, a
simple dimension argument shows that DNNs cannot generate all piecewise linear
functions with $\ell$ linear regions as soon as $\ell > p$. It is thus natural
to seek to characterize specific families of functions with $\ell$ linear
regions that can be constructed by DNNs. Iterated Function Systems (IFS)
generate sequences of piecewise linear functions $F_k$ with a number of linear
regions exponential in $k$. We show that, under mild assumptions, $F_k$ can be
generated by a NN using only $\mathcal{O}(k)$ parameters. IFS are used
extensively to generate, at low computational cost, natural-looking landscape
textures in artificial images. They have also been proposed for compression of
natural images, albeit with less commercial success. The surprisingly good
performance of this fractal-based compression suggests that our visual system
may lock in, to some extent, on self-similarities in images. The combination of
this phenomenon with the capacity, demonstrated here, of DNNs to efficiently
approximate IFS may contribute to the success of DNNs, particularly striking
for image processing tasks, as well as suggest new algorithms for representing
self similarities in images based on the DNN mechanism.
