Multi-variate correlation and mixtures of product measures

Tim Austin

Kybernetika (2020)

  • Volume: 56, Issue: 3, page 459-499
  • ISSN: 0023-5954

Abstract

top
Total correlation (‘TC’) and dual total correlation (‘DTC’) are two classical ways to quantify the correlation among an n -tuple of random variables. They both reduce to mutual information when n = 2 . The first part of this paper sets up the theory of TC and DTC for general random variables, not necessarily finite-valued. This generality has not been exposed in the literature before. The second part considers the structural implications when a joint distribution μ has small TC or DTC. If TC ( μ ) = o ( n ) , then μ is close to a product measure according to a suitable transportation metric: this follows directly from Marton’s classical transportation-entropy inequality. If DTC ( μ ) = o ( n ) , then the structural consequence is more complicated: μ is a mixture of a controlled number of terms, most of them close to product measures in the transportation metric. This is the main new result of the paper.

How to cite

top

Austin, Tim. "Multi-variate correlation and mixtures of product measures." Kybernetika 56.3 (2020): 459-499. <http://eudml.org/doc/297001>.

@article{Austin2020,
abstract = {Total correlation (‘TC’) and dual total correlation (‘DTC’) are two classical ways to quantify the correlation among an $n$-tuple of random variables. They both reduce to mutual information when $n=2$. The first part of this paper sets up the theory of TC and DTC for general random variables, not necessarily finite-valued. This generality has not been exposed in the literature before. The second part considers the structural implications when a joint distribution $\mu $ has small TC or DTC. If $\mathrm \{TC\}(\mu ) = o(n)$, then $\mu $ is close to a product measure according to a suitable transportation metric: this follows directly from Marton’s classical transportation-entropy inequality. If $\mathrm \{DTC\}(\mu ) = o(n)$, then the structural consequence is more complicated: $\mu $ is a mixture of a controlled number of terms, most of them close to product measures in the transportation metric. This is the main new result of the paper.},
author = {Austin, Tim},
journal = {Kybernetika},
keywords = {total correlation; dual total correlation; transportation inequalities; mixtures of products},
language = {eng},
number = {3},
pages = {459-499},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Multi-variate correlation and mixtures of product measures},
url = {http://eudml.org/doc/297001},
volume = {56},
year = {2020},
}

TY - JOUR
AU - Austin, Tim
TI - Multi-variate correlation and mixtures of product measures
JO - Kybernetika
PY - 2020
PB - Institute of Information Theory and Automation AS CR
VL - 56
IS - 3
SP - 459
EP - 499
AB - Total correlation (‘TC’) and dual total correlation (‘DTC’) are two classical ways to quantify the correlation among an $n$-tuple of random variables. They both reduce to mutual information when $n=2$. The first part of this paper sets up the theory of TC and DTC for general random variables, not necessarily finite-valued. This generality has not been exposed in the literature before. The second part considers the structural implications when a joint distribution $\mu $ has small TC or DTC. If $\mathrm {TC}(\mu ) = o(n)$, then $\mu $ is close to a product measure according to a suitable transportation metric: this follows directly from Marton’s classical transportation-entropy inequality. If $\mathrm {DTC}(\mu ) = o(n)$, then the structural consequence is more complicated: $\mu $ is a mixture of a controlled number of terms, most of them close to product measures in the transportation metric. This is the main new result of the paper.
LA - eng
KW - total correlation; dual total correlation; transportation inequalities; mixtures of products
UR - http://eudml.org/doc/297001
ER -

References

top
  1. Abdallah, S. A., Plumbley, M. D., Predictive Information, Multi-Information and Binding Information., Technical Report C4DM-TR-10-10, Queen Mary University of London, 2010. 
  2. Ahlswede, R., An elementary proof of the strong converse theorem for the multiple-access channel., J. Combin. Inform. System Sci. 7 (1982), 3, 216-230. MR0724363
  3. Ahlswede, R., 10.1109/tit.1985.1057102, IEEE Trans. Inform. Theory 31 (1985), 6, 721-726. MR0823593DOI10.1109/tit.1985.1057102
  4. Austin, T., 10.1214/19-aop1352, Ann. Probab. 47 (2019), 6, 4002-4023. MR4038047DOI10.1214/19-aop1352
  5. Austin, T., 10.1007/s10240-018-0098-3, Publ. Math. Inst. Hautes Etudes Sci. 128 (2018), 1-119. MR3905465DOI10.1007/s10240-018-0098-3
  6. Ay, N., Olbrich, E., Bertschinger, N., Jost, J., A unifying framework for complexity measures of finite systems., Working Paper 06-08-028, Santa Fe Institute, 2006. 
  7. Balister, P., Bollobás, B., 10.1007/s00493-012-2453-1, Combinatorica 32 (2012), 2, 125-141. MR2927635DOI10.1007/s00493-012-2453-1
  8. Chatterjee, S., Dembo, A., 10.1016/j.aim.2016.05.017, Adv. Math. 299 (2016), 396-450. MR3519474DOI10.1016/j.aim.2016.05.017
  9. Chung, F. R. K., Graham, R. L., Frankl, P., Shearer, J. B., 10.1016/0097-3165(86)90019-1, J. Combin. Theory Ser. A 43 (1986), 1, 23-37. MR0859293DOI10.1016/0097-3165(86)90019-1
  10. Coja-Oghlan, A., Krzakala, F., Perkins, W., Zdeborová, L., 10.1016/j.aim.2018.05.029, Adv. Math. 333 (2018), 694-795. MR3818090DOI10.1016/j.aim.2018.05.029
  11. Coja-Oghlan, A., Perkins, W., 10.1007/s00220-019-03387-7, Comm. Math. Phys. 366 (2019), 1, 173-201. MR3919446DOI10.1007/s00220-019-03387-7
  12. Cover, T. M., Thomas, J. A., Elements of Information Theory. Second edition., Wiley-Interscience, John Wiley and Sons, Hoboken, NJ 2006. MR2239987
  13. Crooks, G., On Measures of Entropy and Information., Technical note. 
  14. Csiszár, I., 10.1214/aop/1176993227, Ann. Probab. 12 (1984), 3, 768-793. MR0744233DOI10.1214/aop/1176993227
  15. Csiszár, I., Narayan, P., 10.1109/tit.2004.838380, IEEE Trans. Inform. Theory 50 (2004), 12, 3047-3061. MR2103483DOI10.1109/tit.2004.838380
  16. Dembo, A., Zeitouni, O., 10.1007/978-1-4612-5320-4, Springer-Verlag, Stochastic Modelling and Applied Probability 38, Berlin 2010. MR2571413DOI10.1007/978-1-4612-5320-4
  17. Dobrušin, R. L., A general formulation of Shannon's fundamental theorem in the theory of information., Dokl. Akad. Nauk SSSR 126 (1959), 474-477. MR0107573
  18. Dougherty, R., Freiling, C., Zeger, K., 10.1109/tit.2007.896862, IEEE Trans. Inform. Theory 53 (2007), 6, 1949-1969. MR2321860DOI10.1109/tit.2007.896862
  19. Dudley, R. M., 10.1017/cbo9780511755347, Cambridge University Press, Cambridge Studies in Advanced Mathematics 74, Cambridge 2002. Zbl1023.60001MR1932358DOI10.1017/cbo9780511755347
  20. Dueck, G., The strong converse of the coding theorem for the multiple-access channel., J. Combin. Inform. System Sci. 6 (1981), 3, 187-196. MR0652388
  21. Eldan, R., 10.1007/s00039-018-0461-z, Geometr. Funct. Anal. 28 (2018), 6, 1548-1596. MR3881829DOI10.1007/s00039-018-0461-z
  22. Eldan, R., Gross, R., , Preprint, available online at MR3861824DOI
  23. Eldan, R., Gross, R., 10.1214/18-EJP159, Electron. J. Probab. 23 (2018), 35, 24. MR3798245DOI10.1214/18-EJP159
  24. Ellis, D., Friedgut, E., Kindler, G., Yehudayoff, A., 10.19086/da.784, Discrete Anal. 10 (2016), 28 pp. MR3555193DOI10.19086/da.784
  25. Fritz, T., Chaves, R., 10.1109/tit.2012.2222863, IEEE Trans. Inform. Theory 59 (2013), 2, 803-817. MR3015697DOI10.1109/tit.2012.2222863
  26. Fujishige, S., 10.1016/s0019-9958(78)91063-x, Inform. Control 39 (1978), 1, 55-72. MR0514262DOI10.1016/s0019-9958(78)91063-x
  27. Gelfand, I., Kolmogorov, A., Yaglom, I., On the general definition of the quantity of information., Doklady Akad. Nauk SSSR 111 (1956), 4, 745-748. MR0084440
  28. Han, T. S., 10.1016/s0019-9958(75)80004-0, Inform. Control 29 (1975), 4, 337-368. MR0453264DOI10.1016/s0019-9958(75)80004-0
  29. Han, T. S., 10.1016/s0019-9958(78)90275-9, Inform. Control 36 (1978), 2, 133-156. MR0464499DOI10.1016/s0019-9958(78)90275-9
  30. Kolmogorov, A. N., 10.1016/s0019-9958(78)90275-9, IEEE Trans. Inform. Theory IT-2 (1956), 102-108. MR0097987DOI10.1016/s0019-9958(78)90275-9
  31. Ledoux, M., 10.1051/ps:1997103, ESAIM Probab. Statist. 1 (1995/97), 63-87. MR1399224DOI10.1051/ps:1997103
  32. Madiman, M., Tetali, P., 10.1109/tit.2010.2046253, IEEE Trans. Inform. Theory 56 (2010), 6, 2699-2713. MR2683430DOI10.1109/tit.2010.2046253
  33. Makarychev, K., Makarychev, Y., Romashchenko, A., Vereshchagin, N., 10.4310/cis.2002.v2.n2.a3, Commun. Inf. Syst. 2 (2002), 2, 147-165. MR1958013DOI10.4310/cis.2002.v2.n2.a3
  34. Marton, K., 10.1109/tit.1986.1057176, IEEE Trans. Inform. Theory 32 (1986), 3, 445-446. MR0838213DOI10.1109/tit.1986.1057176
  35. Marton, K., 10.1214/aop/1039639365, Ann. Probab. 24 (1996), 2, 857-866. MR1404531DOI10.1214/aop/1039639365
  36. Matúš, F., 10.1109/tit.2006.887090, IEEE Trans. Inform. Theory 53 (2007), 1, 320-330. MR2292891DOI10.1109/tit.2006.887090
  37. McDiarmid, C., 10.1017/cbo9781107359949.008, In: Surveys in Combinatorics, Norwich 1989, London Math. Soc. Lecture Note Ser. 141, Cambridge Univ. Press, Cambridge 1989, pp. 148-188. MR1036755DOI10.1017/cbo9781107359949.008
  38. McGill, W. J., 10.1109/tit.1954.1057469, Trans. I.R.E. PGIT-4 (1954), 93-111. MR0088155DOI10.1109/tit.1954.1057469
  39. Pearl, J., Paz, A., Graphoids: a graph-based logic for reasoning about relevance relations., In: Advances in Artificial Intelligence - II (B. Du Boulay, D. Hogg, and L. Steels, eds.), North Holland, Amsterdam 1987, pp. 357-363. 
  40. Perez, A., 10.1137/1104007, Theory Probab. Appl. 4 (1959), 99-102. MR0122613DOI10.1137/1104007
  41. Perez, A., ϵ -admissible simplifications of the dependence structure of a set of random variables., Kybernetika 13 (1977), 6, 439-449. MR0472224
  42. Pinsker, M. S., Information and information Stability of Random Variables and Processes., Holden-Day, Inc., San Francisco 1964. MR0213190
  43. Radhakrishnan, J., Entropy and counting., In: Computational Mathematics, Modelling and Applications (IIT Kharagpur, Golden Jubilee Volume) (J. Mishra, ed.), Narosa Publishers, 2001, pp. 146-168. 
  44. Schneidman, E., Still, S., Berry, M. J., Bialek, W., 10.1103/physrevlett.91.238701, Phys. Rev. Lett. 91 (2003), 238701. DOI10.1103/physrevlett.91.238701
  45. Studený, M., Vejnarová, J., 10.1007/978-94-011-5014-9_10, In: Proc. NATO Advanced Study Institute on Learning in Graphical Models, Kluwer Academic Publishers, Norwell 1998, pp. 261-297. DOI10.1007/978-94-011-5014-9_10
  46. Timme, N., Alford, W., Flecker, B., Beggs, J. M., 10.1007/s10827-013-0458-4, J. Comput. Neurosci. 36 (2014), 2, 119-140. MR3176934DOI10.1007/s10827-013-0458-4
  47. Watanabe, S., 10.1147/rd.41.0066, IBM J. Res. Develop. 4 (1960), 66-82. MR0109755DOI10.1147/rd.41.0066
  48. Yan, J., , Preprint, available online at MR4108123DOI
  49. Zhang, Z., Yeung, R. W., 10.1109/18.681320, IEEE Trans. Inform. Theory 44 (1998), 4, 1440-1452. MR1665794DOI10.1109/18.681320

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.