Upper and Lower Bounds for Matrix Discrepancy

The aim of this paper is to study the matrix discrepancy problem. Assume that ξ₁, … , ξ_n are independent scalar random variables with finite support and u₁, … , u_n∈ C^d. Let C be the minimal constant for which the following holds: Disc(u1u1∗,…,unun∗;ξ1,…,ξn):=minε1∈S1,…,εn∈Sn‖∑i=1nE[ξi]uiui∗-∑i=1nεiuiui∗‖≤C0·σ,where σ2=‖∑i=1nVar[ξi](uiui∗)2‖ and S_j denotes the support of ξ_j, j= 1 , … , n. Motivated by the technology developed by Bownik, Casazza, Marcus, and Speegle [7], we prove C≤ 3. This improves Kyng, Luh and Song’s method with which C≤ 4 [21]. For the case where {ui}i=1n⊂Cd is a unit-norm tight frame with n≤ 2 d- 1 and ξ₁, … , ξ_n are independent Rademacher random variables, we present the exact value of Disc(u1u1∗,…,unun∗;ξ1,…,ξn)=nd·σ, which implies C0≥2.