View abstract

Session II.5 - Random Matrices - Semi-plenary talk

Saturday, June 17, 14:00 ~ 15:00

A new weak Szemeredi regularity lemma, and the covariance loss

Roman Vershynin

University of California, Irvine, U.S.A.   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

We will prove a new type of weak Szemeredi regularity lemma. It states that a positive semidefinite matrix with bounded diagonal can be decomposed into a small number of constant blocks, up to a small error in the Frobenius norm. The proof utilizes the probabilistic method, specifically a randomized rounding mechanism based on Grothendieck's identity. The new regularity lemma implies a nearly tight bound on the covariance loss--the amount of covariance that is lost by taking conditional expectations of random vectors. I will try to present the proof of the regularity lemma, which is simple and educational.

Joint work with March Boedihardjo (ETH Zurich) and Thomas Strohmer (UC Davis).

View abstract PDF