The rank-sensitive matrix discrepancy conjecture

About 6 years old · traced to

Let ξ1,…,ξn\xi_1,\ldots,\xi_n be independent scalar random variables with finite support, and let A1,…,An∈Cd×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:=max⁡log⁡(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.

References

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.