Speaker: 

Vishesh Jain

Institution: 

Stanford University

Time: 

Thursday, June 2, 2022 - 2:00pm

Location: 

510R Rowland Hall

Let $X$ be a random vector valued in $\mathbb{R}^m$ such that $\|X\|_{2} \leq 1$ almost surely. In this talk, I will discuss two proofs -- one based on the pinning lemma from statistical physics and another based on randomized rounding -- showing that for every $k \geq 3$, there exists a sigma algebra $\mathcal{F}$ generated by a partition of $\mathbb{R}^{m}$ into $k$ sets such that
    \[\|\operatorname{Cov}(X) - \operatorname{Cov}(\mathbb{E}[X\mid\mathcal{F}])
    \|_{\mathrm{F}} \lesssim \frac{1}{\sqrt{\log{k}}}.\]
This estimate is optimal up to the implicit constant, and improves a previous result of Boedihardjo, Strohmer, and Vershynin, obtained in connection to the design of accurate, privacy-preserving synthetic data, by a factor of $\sqrt{\log\log{k}}$. Joint work with Ashwin Sah (MIT) and Mehtaab Sawhney (MIT).