The rank-sensitive matrix discrepancy conjecture

Let ξ1,,ξn\xi_1,\ldots,\xi_n be independent scalar random variables with finite support, and let A1,,AnCd×d\mathbf{A}_1,\ldots,\mathbf{A}_n\in {\mathbb C}^{d\times d} be Hermitian matrices satisfying rank(Ai)r{\rm rank}(\mathbf{A}_i)\leq r for i=1,,ni=1,\ldots,n. Define

Cr,n:=maxlog(r/n),1,σ2=i=1nVar[ξi]Ai2.C_{r,n}:=\max{\log(r/n),1},\qquad \sigma^2=\bigg\|\sum_{i=1}^n \text{{\bf Var}}[\xi_i]\mathbf{A}_i^2\bigg\|.

The rank-sensitive matrix discrepancy conjecture. One has

Disc(A1,,An;ξ1,,ξn)O(Cr,nσ).{\rm Disc}(\mathbf{A}_1,\ldots,\mathbf{A}_n;\xi_1,\ldots,\xi_n)\leq O(\sqrt{C_{r,n}}\cdot \sigma).

The conjecture predicts that the logarithmic factor in matrix discrepancy depends on the matrix rank rather than the ambient dimension; the source presents it as a conjectural extension of the preceding bounds, and no resolution is supplied.

Sources & referencesView supporting material

Primary source

Jiaxin Xie, Zhiqiang Xu and Ziheng Zhu, “Upper and Lower bounds for matrix discrepancy”, arXiv:2006.12083 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.