On the discrepancy of random matrices with many columns

Cole Franks, Michael Saks

Research output: Contribution to journalArticlepeer-review

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 (Formula presented.) for (Formula presented.). This improves on a bound proved by Ezra and Lovett showing the same bound for n at least mt.

Original languageEnglish (US)
Pages (from-to)64-96
Number of pages33
JournalRandom Structures and Algorithms
Volume57
Issue number1
DOIs
StatePublished - Aug 1 2020

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Keywords

  • Fourier
  • balancing
  • discrepancy
  • lattice
  • random matrix

Fingerprint Dive into the research topics of 'On the discrepancy of random matrices with many columns'. Together they form a unique fingerprint.

Cite this