Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Communication Cost of Determining an Approximate Nearest Lattice Point
175
0
0.0
(
0
)
Added by
Maiara F. Bollauf
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider the closest lattice point problem in a distributed network setting and study the communication cost and the error probability for computing an approximate nearest lattice point, using the nearest-plane algorithm, due to Babai. Two distinct communication models, centralized and interactive, are considered. The importance of proper basis selection is addressed. Assuming a reduced basis for a two-dimensional lattice, we determine the approximation error of the nearest plane algorithm. The communication cost for determining the Babai point, or equivalently, for constructing the rectangular nearest-plane partition, is calculated in the interactive setting. For the centralized model, an algorithm is presented for reducing the communication cost of the nearest plane algorithm in an arbitrary number of dimensions.
rate research
Read More
We consider the problem of finding the closest lattice point to a vector in n-dimensional Euclidean space when each component of the vector is available at a distinct node in a network. Our objectives are (i) minimize the communication cost and (ii) obtain the error probability. The approximate closest lattice point considered here is the one obtained using the nearest-plane (Babai) algorithm. Assuming a triangular special basis for the lattice, we develop communication-efficient protocols for computing the approximate lattice point and determine the communication cost for lattices of dimension n>1. Based on available parameterizations of reduced bases, we determine the error probability of the nearest plane algorithm for two dimensional lattices analytically, and present a computational error estimation algorithm in three dimensions. For dimensions 2 and 3, our results show that the error probability increases with the packing density of the lattice.
The lattice $A_n^*$ is an important lattice because of its covering properties in low dimensions. Clarkson cite{Clarkson1999:Anstar} described an algorithm to compute the nearest lattice point in $A_n^*$ that requires $O(nlog{n})$ arithmetic operations. In this paper, we describe a new algorithm. While the complexity is still $O(nlog{n})$, it is significantly simpler to describe and verify. In practice, we find that the new algorithm also runs faster.
We present a communication-efficient distributed protocol for computing the Babai point, an approximate nearest point for a random vector ${bf X}inmathbb{R}^n$ in a given lattice. We show that the protocol is optimal in the sense that it minimizes the sum rate when the components of ${bf X}$ are mutually independent. We then investigate the error probability, i.e. the probability that the Babai point does not coincide with the nearest lattice point. In dimensions two and three, this probability is seen to grow with the packing density. For higher dimensions, we use a bound from probability theory to estimate the error probability for some well-known lattices. Our investigations suggest that for uniform distributions, the error probability becomes large with the dimension of the lattice, for lattices with good packing densities. We also consider the case where $mathbf{X}$ is obtained by adding Gaussian noise to a randomly chosen lattice point. In this case, the error probability goes to zero with the lattice dimension when the noise variance is sufficiently small. In such cases, a distributed algorithm for finding the approximate nearest lattice point is sufficient for finding the nearest lattice point.
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(nlog{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.
We consider an energy-harvesting communication system where a transmitter powered by an exogenous energy arrival process and equipped with a finite battery of size $B_{max}$ communicates over a discrete-time AWGN channel. We first concentrate on a simple Bernoulli energy arrival process where at each time step, either an energy packet of size $E$ is harvested with probability $p$, or no energy is harvested at all, independent of the other time steps. We provide a near optimal energy control policy and a simple approximation to the information-theoretic capacity of this channel. Our approximations for both problems are universal in all the system parameters involved ($p$, $E$ and $B_{max}$), i.e. we bound the approximation gaps by a constant independent of the parameter values. Our results suggest that a battery size $B_{max}geq E$ is (approximately) sufficient to extract the infinite battery capacity of this channel. We then extend our results to general i.i.d. energy arrival processes. Our approximate capacity characterizations provide important insights for the optimal design of energy harvesting communication systems in the regime where both the battery size and the average energy arrival rate are large.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
