Unbiased Matrix Rounding

Details Unbiased Matrix Rounding Unbiased Matrix Rounding

2006-04-18

arxiv.org/abs/cs/0604068v2

Computer Science

Data Structures and Algorithms

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

Scientific paper

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((m n)^2 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.

Affiliated with

Also associated with

No associations

Rating

Unbiased Matrix Rounding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Unbiased Matrix Rounding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unbiased Matrix Rounding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-195435