Linear-time nearest point algorithms for Coxeter lattices
| Autor: | McKilliam, Robby G., Smith, Warren D., Clarkson, I. Vaughan L. |
|---|---|
| Rok vydání: | 2009 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1109/TIT.2009.2039090 |
| Popis: | The Coxeter lattices, which we denote $A_{n/m}$, are a family of lattices containing many of the important lattices in low dimensions. This includes $A_n$, $E_7$, $E_8$ and their duals $A_n^*$, $E_7^*$ and $E_8^*$. We consider the problem of finding a nearest point in a Coxeter lattice. We describe two new algorithms, one with worst case arithmetic complexity $O(n\log{n})$ and the other with worst case complexity O(n) where $n$ is the dimension of the lattice. We show that for the particular lattices $A_n$ and $A_n^*$ the algorithms reduce to simple nearest point algorithms that already exist in the literature. Comment: submitted to IEEE Transactions on Information Theory |
| Databáze: | arXiv |
| Externí odkaz: |
|