DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2025.91

Simple Norm Bounds for Polynomial Random Matrices via Decoupling

Authors: Madhur Tulsiani and June Wu

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

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.

Cite as

Madhur Tulsiani and June Wu. Simple Norm Bounds for Polynomial Random Matrices via Decoupling. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 91:1-91:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{tulsiani_et_al:LIPIcs.ITCS.2025.91,
  author =	{Tulsiani, Madhur and Wu, June},
  title =	{{Simple Norm Bounds for Polynomial Random Matrices via Decoupling}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{91:1--91:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.91},
  URN =		{urn:nbn:de:0030-drops-227194},
  doi =		{10.4230/LIPIcs.ITCS.2025.91},
  annote =	{Keywords: Matrix Concentration, Decoupling, Graph Matrices}
}

Search Results

Documents authored by Wu, June

Simple Norm Bounds for Polynomial Random Matrices via Decoupling

Abstract

Cite as

Thanks for your feedback!

Could not send message