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).