Covariance loss, Szemeredi regularity, and differential privacy

March Boedihardjo, Thomas Strohmer, Roman Vershynin

We show how randomized rounding based on Grothendieck's identity can be used to prove a nearly tight bound on the covariance loss--the amount of covariance that is lost by taking c…