Greedy sparsifications of sums of positive semidefinite matrices

Abstract

We prove a deterministic analogue of Rudelson's sampling theorem for sums of positive semidefinite matrices. Let $A_1,\dots ,A_m$ be positive semidefinite \(d\times d\) matrices, and let ${\lambda }_1,\dots ,{\lambda }_m\ge 0$ satisfy \[ \sum_{i=1}^m λ_i = 1, \qquad \sum_{i=1}^m λ_i A_i = I_d, \qquad \|A_i\| \le M \quad\text{for all } i=1,\dots,m. \] We show that there exists a deterministic sequence of indices $i_1,i_2,\cdots \in \{1,\dots ,m\}$ such that for every integer $k\ge 1$, \[ \left\| \frac{1}{k}\sum_{r=1}^k A_{i_r} - I_d \right\| \le \begin{cases} \displaystyle \frac{2M\ln(2d)}{k}, & \text{if } k \le M\ln(2d),\\[2ex] \displaystyle 3\sqrt{\frac{M\ln(2d)}{k}}, & \text{if } k > M\ln(2d). \end{cases} \] In particular, if $0<\epsilon \le 1$ and $N\ge 9M\ln (2d){\epsilon }^{-2}$, then one can choose indices $i_1,\dots ,i_N\in \{1,\dots ,m\}$ such that \[ \left\| \frac{1}{N}\sum_{r=1}^N A_{i_r} - I_d \right\| \le \varepsilon. \]