Error diffusion on acute simplices: invariant tiles
| Autor: | Charles Tresser, Tomasz Nowicki, Roy L. Adler, Shmuel Winograd, Grzegorz Świrszcz |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Simplex Birkhoff polytope General Mathematics 010102 general mathematics Uniform k 21 polytope 0102 computer and information sciences 01 natural sciences Combinatorics 010201 computation theory & mathematics Cross-polytope Convex polytope Piecewise Mathematics::Metric Geometry 0101 mathematics Invariant (mathematics) Vertex enumeration problem Mathematics |
| Zdroj: | Israel Journal of Mathematics. 221:445-469 |
| ISSN: | 1565-8511 0021-2172 |
| DOI: | 10.1007/s11856-017-1550-7 |
| Popis: | 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¨i 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink