Sharp concentration for sums of matrices with Markovian dependence through universality
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908998110806016 |
|---|---|
| author | Van Werde, Alexander Sanders, Jaron |
| author_facet | Van Werde, Alexander Sanders, Jaron |
| contents | We prove that a sum of random matrices generated by a $ψ$-mixing Markov chain has similar spectral properties to a Gaussian matrix with the same mean and covariance structure. This nonasymptotic universality principle enables sharp concentration inequalities when combined with recent advances in the Gaussian literature. We illustrate the theory with examples, showing how it enables polynomial dimensional improvements relative to previous Markovian matrix concentration results when applied to Wigner-type matrices, and how one can recover sharp limiting values for a model used to study spectral clustering techniques.
A key challenge in the proof is that techniques based only on classical cumulants, which can be used when summands are independent, are not sufficient on their own for efficient estimates in a Markovian setting. Our approach exploits Boolean cumulants and a change--of--measure argument. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_11632 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Sharp concentration for sums of matrices with Markovian dependence through universality Van Werde, Alexander Sanders, Jaron Probability Operator Algebras 60B20, 60J05, 46L53 We prove that a sum of random matrices generated by a $ψ$-mixing Markov chain has similar spectral properties to a Gaussian matrix with the same mean and covariance structure. This nonasymptotic universality principle enables sharp concentration inequalities when combined with recent advances in the Gaussian literature. We illustrate the theory with examples, showing how it enables polynomial dimensional improvements relative to previous Markovian matrix concentration results when applied to Wigner-type matrices, and how one can recover sharp limiting values for a model used to study spectral clustering techniques. A key challenge in the proof is that techniques based only on classical cumulants, which can be used when summands are independent, are not sufficient on their own for efficient estimates in a Markovian setting. Our approach exploits Boolean cumulants and a change--of--measure argument. |
| title | Sharp concentration for sums of matrices with Markovian dependence through universality |
| topic | Probability Operator Algebras 60B20, 60J05, 46L53 |
| url | https://arxiv.org/abs/2307.11632 |