Greedy sparsifications of sums of positive semidefinite matrices
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911704010457088 |
|---|---|
| author | Ivanov, Grigory |
| author_facet | Ivanov, Grigory |
| contents | 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 $λ_1,\dots,λ_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,\dots \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<\varepsilon\le 1$ and $N \ge 9M\ln(2d)\varepsilon^{-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. \] |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_06439 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Greedy sparsifications of sums of positive semidefinite matrices Ivanov, Grigory Functional Analysis 15A45, 47A58, 52A23, 46B20 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 $λ_1,\dots,λ_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,\dots \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<\varepsilon\le 1$ and $N \ge 9M\ln(2d)\varepsilon^{-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. \] |
| title | Greedy sparsifications of sums of positive semidefinite matrices |
| topic | Functional Analysis 15A45, 47A58, 52A23, 46B20 |
| url | https://arxiv.org/abs/2604.06439 |