paper

Unbiased Matrix Rounding

arXiv:cs/0604068

Abstract

We show several ways to round a real matrix to an integer one such that the rounding errors in all rows and columns as well as the whole matrix are less than one. This is a classical problem with applications in many fields, in particular, statistics. We improve earlier solutions of different authors in two ways. For rounding matrices of size $m \times n$ , we reduce the runtime from $O ((mn)^{2} S eco n d, o u r r o u n d in g s a l so ha v e a r o u n d in g er r or o f l ess t han o n e ina l l ini t ia l in t er v a l so f r o w s an d co l u mn s . C o n se q u e n tl y, a r bi t r a r y in t er v a l s ha v e an er r or o f a t m os ttw o . T hi s i s p a r t i c u l a r l y u se f u l in t h es t a t i s t i cs a ppl i c a t i o n o f co n t r o l l e d r o u n d in g . T h es am er es u l t c anb eo b t ain e d v ia (d e p e n d e n t) r an d o mi z e d r o u n d in g . T hi s ha s t h e a dd i t i o na l a d v an t a g e t ha tt h er o u n d in g i s u nbia se d, t ha t i s, f or a l l e n t r i es$ y_{ij} $o f o u r r o u n d in g, w e ha v e$ E(y_{ij}) = x_{ij} $, w h er e$ x_{ij}$ is the corresponding entry of the input matrix.

10th Scandinavian Workshop on Algorithm Theory (SWAT), 2006, to appear