Random Structures and Algorithms Applied Mathematics

Asymptotic Bounds and Online Algorithms for Average‐Case Matrix Discrepancy

Dmitriy Kunisky, Timm Oertel, Nicola Wengiel, Peiyuan Zhang
Wiley · 2026-10-01 · DOI 10.1002/rsa.70102

Abstract

ABSTRACT We study the matrix discrepancy problem in the average‐case setting. Given a sequence of symmetric matrices , its discrepancy is defined as the minimal spectral norm over all signed sums with . Our contributions are twofold. First, we study the asymptotic discrepancy of random matrices. When the matrices belong to the Gaussian orthogonal ensemble, we provide a sharp characterization of the asymptotic discrepancy and show that the limiting distribution is concentrated around , under the assumption . We show that a broad class of random matrices has discrepancy when . For , we give efficiently achievable complementary upper bounds of and , which match the lower bound up to constants when . Second, we analyse the matrix hyperbolic cosine algorithm, an online algorithm for matrix discrepancy minimization due to Zouzias (2011), in the average‐case setting. We show that the algorithm achieves with high probability a discrepancy of for a broad class of random matrices, including Wigner matrices with entries satisfying a hypercontractive inequality and Gaussian Wishart matrices.

Read at publisher →