2026-07-22T00:15:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22719 2026-04-17T05:32:45Z ddc:004 open_access

Simple Norm Bounds for Polynomial Random Matrices via Decoupling Tulsiani, Madhur Wu, June Matrix Concentration Decoupling Graph Matrices We present a new method for obtaining norm bounds for random matrices, where each entry is a low-degree polynomial in an underlying set of independent real-valued random variables. Such matrices arise in a variety of settings in the analysis of spectral and optimization algorithms, which require understanding the spectrum of a random matrix depending on data obtained as independent samples. Using ideas of decoupling and linearization from analysis, we show a simple way of expressing norm bounds for such matrices, in terms of matrices of lower-degree polynomials corresponding to derivatives. Iterating this method gives a simple bound with an elementary proof, which can recover many bounds previously required more involved techniques. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Madhur Tulsiani and June Wu 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.91 urn:nbn:de:0030-drops-227194 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.91 eng https://creativecommons.org/licenses/by/4.0/legalcode