Unbiased Rounding of Rational Matrices

Abstract

Rounding a real-valued matrix to an integer one such that the rounding errors in all rows and columns are less than one is a classical problem. It has been applied to hypergraph coloring, in scheduling and in statistics. Here, it often is also desirable to round each entry randomly such that the probability of rounding it up equals its fractional part. This is known as unbiased rounding in statistics and as randomized rounding in computer science.

We show how to compute such an unbiased rounding of an m ×n matrix in expected time O(mnq ²), where q is the common denominator of the matrix entries. We also show that if the denominator can be written as $q=\Pi_{i=1}^{\ell} q_{i}$ for some integers q _i , the expected runtime can be reduced to $O(mn \sum_{i=1}^{\ell} q_{i}^{2})$. Our algorithm can be derandomised efficiently using the method of conditional probabilities.

Our roundings have the additional property that the errors in all initial intervals of rows and columns are less than one.