Calmon, Flavio P. and Varia, Mayank and Medard, Muriel and Christiansen, Mark M. and Duffy, Ken R. and Tessaro, Stefano (2013) Bounds on inference. Working Paper. arXiv.org.

Preview

Download (187kB) | Preview

Abstract

Lower bounds for the average probability of error of estimating a hidden variable X given an observation of a correlated random variable Y , and Fano’s inequality in particular, play a central role in information theory. In this paper, we present a lower bound for the average estimation error based on the marginal distribution of X and the principal inertias of the joint distribution matrix of X and Y . Furthermore, we discuss an information measure based on the sum of the largest principal inertias, called k-correlation, which generalizes maximal correlation. We show that k-correlation satisfies the Data Processing Inequality and is convex in the conditional distribution of Y given X. Finally, we investigate how to answer a fundamental question in inference and privacy: given an observation Y , can we estimate a function f(X) of the hidden random variable X with an average error below a certain threshold? We provide a general method for answering this question using an approach based on rate-distortion theory.

Item Type:	Monograph (Working Paper)
Additional Information:	Paper given at the 51st Allerton Conference on Communication, Control, and Computing (2013). This work is sponsored by the Intelligence Advanced Research Projects Activity under Air Force Contract FA8721-05-C-0002. Opinions, interpretations, conclusions and recommendations are those of the authors and are not necessarily endorsed by the United States Government. M.C. and K.D. are supported by Science Foundation Ireland Grant No. 11/PI/1177.
Keywords:	Bounds; inference; information theory; rate-distortion theory;
Academic Unit:	Faculty of Science and Engineering > Research Institutes > Hamilton Institute
Item ID:	5982
Identification Number:	arXiv:1310.1512
Depositing User:	Dr Ken Duffy
Date Deposited:	24 Mar 2015 17:02
Publisher:	arXiv.org
Refereed:	Yes
Funders:	Intelligence Advanced Research Projects Activity, Science Foundation Ireland (SFI)
URI:
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads