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.
All Science Journal Classification (ASJC) codes
- Computer Graphics and Computer-Aided Design
- Applied Mathematics
- random matrix