# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Unbiased Matrix Rounding

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Doerr, B., Friedrich, T., Klein, C., & Osbild, R. (2006). Unbiased Matrix Rounding.
In *Algorithm theory - SWAT 2006: 10th Scandinavian Workshop on Algorithm Theory* (pp. 102-112).
Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2460-3

##### Abstract

We show several ways to round a real matrix to an integer one in such a way
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 $m
\times n$ matrices, we reduce the runtime from $O( (m n)^2 ) $ to $O(m n \log(m
n))$. Second, our roundings also have a rounding error of less than one in all
initial intervals of rows and columns. Consequently, arbitrary intervals have
an error of at most two. This is particularly useful in the statistics
application of controlled rounding.
The same result can be obtained via (dependent) randomized rounding. This has
the additional advantage that the rounding is unbiased, that is, for all
entries $y_{ij}$ of our rounding, we have $E(y_{ij}) = x_{ij}$, where $x_{ij}$
is the corresponding entry of the input matrix.