2024/10/31 by Kunisky, Dmitriy, Oertel, Timm, Wengiel, Nicola +1
Mathematics · Physics and Astronomy · #Advanced Mathematical Theories and Applications #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Approximation and Integration #Probability (math.PR) #advanced mathematical theories
paper · pdf · doi:10.48550/arxiv.2410.23915
openalex publication_date 2024/10/31 · openalex created_date 2024/11/14 · openalex updated_date 2026/07/28
We study the matrix discrepancy problem in the average-case setting. Given a sequence of m × m symmetric matrices A1,…,An, its discrepancy is defined as the minimal spectral norm over all signed sums ∑i=1n xiAi with x1,…,xn ∈ \±1\. 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 Θ(√(nm)4-(1 + o(1))n/m2), under the assumption m2 ≪ n/logn. We observe that the trivial bound O(√(nm)) cannot be improved when n ≪ m2 and show that this phenomenon occurs for a broad class of random matrices. In the case n = Ω(m2), we provide a matching upper bound. 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 O(mlogm) for a broad class of random matrices, including Wigner matrices with entries satisfying a hypercontractive inequality and Gaussian Wishart matrices.