Error diffusion on acute simplices: invariant tiles

Abstract

We study the absorbing invariant set of a dynamical system defined by a map derived from Error Diffusion, a greedy online approximation algorithm that minimizes the (Euclidean) norm of the cumulated error. This algorithm assigns a sequence of outputs, each a vertex of some polytope, to any sequence of inputs in that polytope. Here, the polytope is assumed to be a simplex that is acute, meaning that the pairs of distinct external normal vectors to the codimension-one faces form obtuse angles. The input is assumed to be constant. The map is a system which consists of piecewise translations acting on the partition of an affine space into the Vorono¨ı regions defined (once tie-breaking is resolved) by the vertices of the polytope. The translation vector in each partition piece is the difference between the input modified by adding the cumulated error and the corresponding vertex. When the polytope is a simplex such piecewise translation projects onto a translation of a torus. We prove that if the projected translation is ergodic, then there is an invariant absorbing set of the piecewise translation which is a fundamental set for the lattice generated by the simplex and which is a limit set of any bounded set with nonempty interior.