Upper and Lower bounds for matrix discrepancy

Abstract

The aim of this paper is to study the matrix discrepancy problem. Assume that ${\xi }_1,\dots ,{\xi }_n$ are independent scalar random variables with finite support and ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_n\in {\mathbb{C}}^d$. Let ${\mathcal{C}}_0$ be the minimal constant for which the following holds: \[ {\rm Disc}(\mathbf{u}_1\mathbf{u}_1^*,\ldots,\mathbf{u}_n\mathbf{u}_n^*; ξ_1,\ldots,ξ_n)\,\,:=\,\,\min_{\varepsilon_1\in \mathcal{S}_1,\ldots,\varepsilon_n\in \mathcal{S}_n}\bigg\|\sum_{i=1}^n\mathbb{E}[ξ_i]\mathbf{u}_i\mathbf{u}_i^*-\sum_{i=1}^n\varepsilon_i\mathbf{u}_i\mathbf{u}_i^*\bigg\|\leq \mathcal{C}_0\cdotσ, \] where ${\sigma }^2=\Vert {\sum }_{i=1}^n\mathbf{Var}[{\xi }_i]({\mathbf{u}}_i{\mathbf{u}}_i^{\ast }{)}^2\Vert$ and ${\mathcal{S}}_j$ denotes the support of ${\xi }_j,j=1,\dots ,n$. Motivated by the technology developed by Bownik, Casazza, Marcus, and Speegle, we prove ${\mathcal{C}}_0\le 3$. This improves Kyng, Luh and Song's method with which ${\mathcal{C}}_0\le 4$. For the case where $\{{\mathbf{u}}_i{\}}_{i=1}^n\subset {\mathbb{C}}^d$ is a unit-norm tight frame with $n\le 2d-1$ and ${\xi }_1,\dots ,{\xi }_n$ are independent Rademacher random variables, we present the exact value of $\mathrm{Disc}({\mathbf{u}}_1{\mathbf{u}}_1^{\ast },\dots ,{\mathbf{u}}_n{\mathbf{u}}_n^{\ast };{\xi }_1,\dots ,{\xi }_n)=\sqrt{\frac{n}{d}}\cdot \sigma$, which implies ${\mathcal{C}}_0\ge \sqrt{2}$.

References in corpus (3)

• Hyperbolic polynomials and the Kadison-Singer problem
• Mixed Determinants and the Kadison-Singer problem
• Approximation of the average of some random matrices