On the discrepancy of random matrices with many columns. Issue 1 (26th March 2020)

• Record Type: Journal Article
• Authors: Franks, Cole; Saks, Michael
• Is Part Of: Random structures & algorithms. Volume 57:Issue 1(2020)
• Page Start: 64
• Page End: 96
• Publication Date: 2020-03-26
• Subjects: random matrix -- discrepancy -- balancing -- lattice -- Fourier; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20909
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : Motivated by the Komlós conjecture in combinatorial discrepancy, we study the discrepancy of random matrices with m rows and n independent columns drawn from a bounded lattice random variable. We prove that for n at least polynomial in m, with high probability the ℓ ∞ ‐discrepancy is at most twice the ℓ ∞ ‐covering radius of the integer span of the support of the random variable. Applying this result to random t ‐sparse matrices, that is, uniformly random matrices with t ones and m − t zeroes in each column, we show that the ℓ ∞ ‐discrepancy is at most 2 with probability 1 − 3 exp ( − Ω ( n / m ) ) for n = Ω ( m 3 log 2 m ) . This improves on a bound proved by Ezra and Lovett showing the same bound for n at least m t .