Revisiting Tropical Polynomial Division: Theory, Algorithms and
  Application to Neural Networks
Ioannis Kordonis Petros Maragos
Tropical geometry has recently found several applications in the analysis of
neural networks with piecewise linear activation functions. This paper presents
a new look at the problem of tropical polynomial division and its application
to the simplification of neural networks. We analyze tropical polynomials with
real coefficients, extending earlier ideas and methods developed for
polynomials with integer coefficients. We first prove the existence of a unique
quotient-remainder pair and characterize the quotient in terms of the convex
bi-conjugate of a related function. Interestingly, the quotient of tropical
polynomials with integer coefficients does not necessarily have integer
coefficients. Furthermore, we develop a relationship of tropical polynomial
division with the computation of the convex hull of unions of convex polyhedra
and use it to derive an exact algorithm for tropical polynomial division. An
approximate algorithm is also presented, based on an alternation between data
partition and linear programming. We also develop special techniques to divide
composite polynomials, described as sums or maxima of simpler ones. Finally, we
present some numerical results to illustrate the efficiency of the algorithms
proposed, using the MNIST handwritten digit and CIFAR-10 datasets.