Unbiased Matrix Rounding

2006/04/18 by Benjamin Doerr, Tobias Friedrich, Doerr, Benjamin +5
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Matrix Theory and Algorithms #VLSI and Analog Circuit Testing #VLSI and FPGA Design Techniques #cs.DM #cs.DS

paper · pdf · doi:10.48550/arxiv.cs/0604068

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

openalex publication_date 2006/04/18 · arxiv created 2006/04/20 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 × n, we reduce the runtime from O((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.

Related

• Statistical Rounding Error Analysis for Random Matrix Computations
• Stochastic Rounding Implicitly Regularizes Tall-and-Thin Matrices
• What You Will Gain By Rounding: Theory and Algorithms for Rounding Rank
• Bias- and Variance-Aware Probabilistic Rounding Error Analysis for Floating-Point Arithmetic
• Improved stochastic rounding