Asymptotic Bounds and Online Algorithms for Average-Case Matrix Discrepancy
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911190976823296 |
|---|---|
| author | Kunisky, Dmitriy Oertel, Timm Wengiel, Nicola Zhang, Peiyuan |
| author_facet | Kunisky, Dmitriy Oertel, Timm Wengiel, Nicola Zhang, Peiyuan |
| contents | We study the matrix discrepancy problem in the average-case setting. Given a sequence of $m \times m$ symmetric matrices $A_1,\ldots,A_n$, its discrepancy is defined as the minimal spectral norm over all signed sums $\sum_{i=1}^n x_iA_i$ with $x_1,\ldots,x_n \in \{\pm1\}$. 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 $Θ(\sqrt{nm}4^{-(1 + o(1))n/m^2})$, under the assumption $m^2 \ll n/\log{n}$. We observe that the trivial bound $O(\sqrt{nm})$ cannot be improved when $n \ll m^2$ and show that this phenomenon occurs for a broad class of random matrices. In the case $n = Ω(m^2)$, 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(m\log{m})$ for a broad class of random matrices, including Wigner matrices with entries satisfying a hypercontractive inequality and Gaussian Wishart matrices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_23915 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Asymptotic Bounds and Online Algorithms for Average-Case Matrix Discrepancy Kunisky, Dmitriy Oertel, Timm Wengiel, Nicola Zhang, Peiyuan Probability Discrete Mathematics Combinatorics We study the matrix discrepancy problem in the average-case setting. Given a sequence of $m \times m$ symmetric matrices $A_1,\ldots,A_n$, its discrepancy is defined as the minimal spectral norm over all signed sums $\sum_{i=1}^n x_iA_i$ with $x_1,\ldots,x_n \in \{\pm1\}$. 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 $Θ(\sqrt{nm}4^{-(1 + o(1))n/m^2})$, under the assumption $m^2 \ll n/\log{n}$. We observe that the trivial bound $O(\sqrt{nm})$ cannot be improved when $n \ll m^2$ and show that this phenomenon occurs for a broad class of random matrices. In the case $n = Ω(m^2)$, 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(m\log{m})$ for a broad class of random matrices, including Wigner matrices with entries satisfying a hypercontractive inequality and Gaussian Wishart matrices. |
| title | Asymptotic Bounds and Online Algorithms for Average-Case Matrix Discrepancy |
| topic | Probability Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2410.23915 |