Upper and Lower bounds for matrix discrepancy

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: $$\mathrm{D}\mathrm{i}\mathrm{s}\mathrm{c}({\mathbf{u}}_1{\mathbf{u}}_1^{\ast },\dots ,{\mathbf{u}}_n{\mathbf{u}}_n^{\ast };{\xi }_1,\dots ,{\xi }_n):=\underset{{\epsilon }_1\in {\mathcal{S}}_1,\dots ,{\epsilon }_n\in {\mathcal{S}}_n}{\min }\parallel \sum _{i=1}^n\mathbb{E}[{\xi }_i]{\mathbf{u}}_i{\mathbf{u}}_i^{\ast }-\sum _{i=1}^n{\epsilon }_i{\mathbf{u}}_i{\mathbf{u}}_i^{\ast }\parallel \le {\mathcal{C}}_0\cdot \sigma ,$$ where $\sigma^2 = \big|\sum_{i=1}^n $\mathbf{V}\mathbf{a}\mathbf{r}$\xi_i^2\big|$and$$\mathcal{S}$_j$denotesthesupportof$\xi_j, j=1,\ldots,n$. Motivated by the technology developed by Bownik, Casazza, Marcus, and Speegle, we prove $$\mathcal{C}$_0\leq 3$\mathrm{.}ThisimprovesKyng,LuhandSon{g}^{\mathrm{\prime }}smethodwithwhich$$\mathcal{C}$_0\leq 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 ${\rm Disc}($\mathbf{u}$_1$\mathbf{u}$_1^,\ldots,$\mathbf{u}$_n$\mathbf{u}$_n^; \xi_1,\ldots,\xi_n)=\sqrt{\frac{n}{d}}\cdot\sigma$,whichimplies$$\mathcal{C}$_0\geq \sqrt{2}$.