Optimal Minimization of the Covariance Loss

Vishesh Jain; Ashwin Sah; Mehtaab Sawhney

首页> 外文期刊>IEEE Transactions on Information Theory >Optimal Minimization of the Covariance Loss

【24h】

Optimal Minimization of the Covariance Loss

机译：Optimal Minimization of the Covariance Loss

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相关主题

摘要

Let $X$ be a random vector valued in $mathbb {R}^{m}$ such that $X_{2} le 1$ almost surely. For every $kge 3$ , we show that there exists a sigma algebra $mathcal {F}$ generated by a partition of $mathbb {R}^{m}$ into $k$ sets such that $mathrm {Cov}(X) - mathrm {Cov}(mathbb {E}Xmid mathcal {F}) _{mathrm {F}} lesssim frac {1}{sqrt {log {k}}}$ . This is optimal up to the implicit constant and improves on a previous bound due to Boedihardjo, Strohmer, and Vershynin. Our proof provides an efficient algorithm for constructing $mathcal {F}$ and leads to improved accuracy guarantees for $k$ -anonymous or differentially private synthetic data. We also establish a connection between the above problem of minimizing the covariance loss and the pinning lemma from statistical physics, providing an alternate (and much simpler) algorithmic proof in the important case when $X in {pm 1}^{m}/sqrt {m}$ almost surely.

著录项

来源
《IEEE Transactions on Information Theory》 |2023年第2期|813-818|共6页
作者
Vishesh Jain; Ashwin Sah; Mehtaab Sawhney;
展开▼
作者单位

Department of Mathematics, Statistics, and Computer Science, University of Illinois Chicago, Chicago, IL, USA;

Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, USA;

展开▼
收录信息
原文格式 PDF
正文语种英语
中图分类通信;
关键词
Complexity theory; Covariance matrices; Physics; Partitioning algorithms; Loss measurement; Upper bound; Random variables;

Optimal Minimization of the Covariance Loss

摘要

著录项

相关主题

期刊订阅