Matrix Chaos Inequalities and Chaos of Combinatorial Type
OPEN ACCESS
Loading...
Author / Producer
Date
2025-06
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
Matrix concentration inequalities and their recently discovered sharp counterparts provide powerful tools to bound the spectrum of random matrices whose entries are linear functions of independent random variables. However, in many applications in theoretical computer science and in other areas one encounters more general random matrix models, called matrix chaoses, whose entries are polynomials of independent random variables. Such models have often been studied on a case-by-case basis using ad-hoc methods that can yield suboptimal dimensional factors.
In this paper we provide general matrix concentration inequalities for matrix chaoses, which enable the treatment of such models in a systematic manner. These inequalities are expressed in terms of flattenings of the coefficients of the matrix chaos. We further identify a special family of matrix chaoses of combinatorial type for which the flattening parameters can be computed mechanically by a simple rule. This allows us to provide a unified treatment of and improved bounds for matrix chaoses that arise in a variety of applications, including graph matrices, Khatri-Rao matrices, and matrices that arise in average case analysis of the sum-of-squares hierarchy.
Permanent link
Publication status
published
External links
Book title
STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing
Journal / series
Volume
Pages / Article No.
795 - 805
Publisher
Association for Computing Machinery
Event
57th Annual ACM Symposium on Theory of Computing (STOC 2025)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Random matrices; matrix concentration inequalities
Organisational unit
09679 - Bandeira, Afonso / Bandeira, Afonso