Affordable Access

Publisher Website

Matrix approximation and Tusnády’s problem

Authors
Journal
European Journal of Combinatorics
0195-6698
Publisher
Elsevier
Publication Date
Volume
28
Issue
3
Identifiers
DOI: 10.1016/j.ejc.2005.09.006
Disciplines
  • Mathematics

Abstract

Abstract We consider the problem of approximating a given matrix by an integer one such that in all geometric submatrices the sum of the entries does not change by much. We show that for all integers m , n ≥ 2 and real matrices A ∈ R m × n there is an integer matrix B ∈ Z m × n such that | ∑ i ∈ I ∑ j ∈ J ( a i j − b i j ) | < 4 log 2 ( min { m , n } ) holds for all intervals I ⊆ [ m ] , J ⊆ [ n ] . Such a matrix can be computed in time O ( m n log ( min { m , n } ) ) . The result remains true if we add the requirement | a i j − b i j | < 2 for all i ∈ [ m ] , j ∈ [ n ] . This is surprising, as the slightly stronger requirement | a i j − b i j | < 1 makes the problem equivalent to Tusnády’s problem.

There are no comments yet on this publication. Be the first to share your thoughts.