Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
entropy vectors; information inequalities; subgroup indices
entropy vectors; information inequalities; subgroup indices
Summary:
The entropy region is a fundamental object of study in mathematics, statistics, and information theory. On the one hand, it involves pure group theory, governing inequalities satisfied by subgroup indices, whereas on the other hand, computing network coding capacities amounts to a convex optimization over this region. In the case of four random variables, the points in the region that satisfy the Ingleton inequality (corresponding to abelian groups and to linear network codes) form a well-understood polyhedron, and so attention has turned to Ingleton-violating points in the region. How far these points extend is measured by their Ingleton score, where points with positive score are Ingleton-violating. The Four-Atom Conjecture stated that the Ingleton score cannot exceed 0.089373, but this was disproved by Matúš and Csirmaz. In this paper we employ two methods to investigate Ingleton-violating points and thereby produce the currently largest known Ingleton scores. First, we obtain many Ingleton-violating examples from non-abelian groups. Factorizability appears in many of those and is used to propose a systematic way to produce more. Second, we rephrase the problem of maximizing Ingleton score as an optimization question and introduce a new Ingleton score function, which is a limit of Ingleton scores with maximum unchanged. We use group theory to exploit symmetry in these new Ingleton score functions and the relations between them. Our approach yields some large Ingleton scores and, using this methodology, we find that there are entropic points with score 0.0925000777, currently the largest known score.
References:
[1] Ahlswede, R., Cai, N., Li, S.-Y. R., Yeung, R. W.: Network information flow. IEEE Trans. Inform. Theory 46 (2007), 1204-1216. DOI 10.1109/18.850663 | MR 1768542
[2] Alam, S., Thakor, S., Abbas, S.: On Enumerating Distributions for Associated Vectors in the Entropy Space. arXiv:1807.08573, 2018.
[3] Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. The user language, J. Symbolic Comput. 24 (1997), 235-265. DOI 10.1006/jsco.1996.0125 | MR 1484478
[4] Boston, N., Nan, T.-T.: Large violations of the Ingleton inequality. In: 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012. DOI 10.1109/allerton.2012.6483410
[5] Boston, N., Nan, T.-T.: A refinement of the four-atom conjecture. In: International Symposium on Network Coding (NetCod), 2013. DOI 10.1109/netcod.2013.6570833
[6] Chen, T.: Group characterizable entropiy functions. In: Proc. of the 2005 IEEE International Symposium on Information Theory, Nice 2007, pp. 507-510. DOI 10.1109/isit.2007.4557275
[7] Chen, T. H., Yeung, R. W.: On a relation between information inequalities and group theory. IEEE Trans. Inform. Theory 48 (2002), 1992-1995. DOI 10.1109/tit.2002.1013138 | MR 1930005
[8] Chou, P. A., Wu, Y., Jain, K.: Practical network coding. In: Proc. 2003 Allerton Conf. on Commun., Control, and Computing, 2003, pp. 40-49.
[9] Dougherty, R., Freiling, C., Zeger, K.: Insufficiency of linear coding in network information flow. IEEE Trans. Inform. Theory 51 (2005), 2745-2759. DOI 10.1109/tit.2005.851744 | MR 2236245
[10] Dougherty, R., Freiling, C., Zeger, K.: Networks, matroids, and non-Shannon information inequalities. IEEE Trans. Inform. Theory 53 (2007), 1949-1969. DOI 10.1109/tit.2007.896862 | MR 2321860
[11] Dougherty, R., Freiling, C., Zeger, K.: Non-Shannon information inequalities in four random variables. arXiv:1104.3602v1, 2011. MR 2321860
[12] Ho, T., Médard, M., Koetter, R., Karger, D. R., Effros, M., Shi, J., Leong, B.: A random linear network coding approach to multicast. IEEE Trans. Inform. Theory 52 (2006), 4413-4430. DOI 10.1109/tit.2006.881746 | MR 2300827
[13] Ingleton, A.: Representation of matroids. In: Combinatorial Mathematics and its Applications, 1971, pp. 149-167. MR 0278974
[14] M.Isaacs, I.: Finite Group Theory. American Mathematical Society, 2008. DOI 10.1090/gsm/092 | MR 2426855
[15] Koetter, R., Médard, M.: An algebraic approach to network coding. IEEE/ACM Trans. Network. 2 (2003), 782-795. DOI 10.1109/tnet.2003.818197
[16] Li, R., Yeung, R., Cai, N.: Linear network coding. IEEE Trans. Inform. Theory 49 (2003), 371-381. DOI 10.1109/tit.2002.807285 | MR 1966785
[17] Makarycheve, K., Makarycheve, L., Romashchenko, A. E., Vereshchagin, N. K.: A new class of non-Shannon type inequalities for entropies. Com. Inform. Syst. 2 (2002), 147-166. DOI 10.4310/cis.2002.v2.n2.a3 | MR 1958013
[18] Mao, W., Thill, M., Hassibi, B.: On Ingleton-violating finite groups. IEEE Trans. Inform. Theory 63 (2017), 183-200. DOI 10.1109/tit.2016.2627530 | MR 3599943
[19] Matúš, F.: Conditional independences among four random variables II. Combin. Probab. Comput. 4 (1995), 407-417. DOI 10.1017/s0963548300001747 | MR 1377558
[20] Matúš, F.: Conditional independences among four random variables III: Final conclusion. Combin. Probab. Comput. 8 (1999), 269-276. DOI 10.1017/s0963548399003740 | MR 1702569
[21] Matúš, F.: Infinitely many information inequalities. In: IEEE International Symposium on Information Theory, IEEE 2007, pp. 41-44. DOI 10.1109/isit.2007.4557201
[22] Matúš, F., Csirmaz, L.: Entropy region and convolution. IEEE Trans. Inform. Theory 62 (2016), 6007-6018. DOI 10.1109/tit.2016.2601598 | MR 3565097
[23] Matúš, F., Studený, M.: Conditional independences among four random variables I. Combin. Probab. Comput. 4 (1995), 269-278. DOI 10.1017/s0963548300001644 | MR 1356579
[24] Muralidharan, V. T., Rajan, B. S.: On the vector linear solvability of networks and discrete polymatroids. GLOBECOM 2013, pp. 1979-1984.
[25] Nan, T.-T.: Entropy Regions and the Four-Atom Conjecture. PhD. Dissertation, Department of Mathematics, University of Wisconsin-Madison, 2015. MR 3358242
[26] Paajanen, P.: Finite p-groups, entropy vectors and the ingleton inequality for nilpotent groups. IEEE Trans. Inform. Theory 60 (2014), 3821-3824. DOI 10.1109/TIT.2014.2321561 | MR 3225931
[27] Stancu, R., Oggier, F.: Finite nilpotent and metacyclic groups never violate the Ingleton inequality. 2012 International Symposium on Network Coding (NetCod), 2012, pp. 25-30. DOI 10.1109/netcod.2012.6261879
[28] Waterhouse, W.: Do symmetric problems have symmetric solutions?. Amer. Math. Monthly 90 (1983), 378-387. DOI 10.1080/00029890.1983.11971235 | MR 0707152
[29] Yeung, R. W.: Information Theory and Network Coding. Springer, 2008.
[30] Zhang, Z., Yeung, R. W.: A non-Shannon type conditional inequality of information quantities. IEEE Trans. Inform. Theory 43 (1997), 1982-1986. DOI 10.1109/18.641561 | MR 1481054
[31] Zhang, Z., Yeung, R. W.: On characterization of entropy function via information inequalities. IEEE Trans. Inform. Theory 44 (1998), 1440-1452. DOI 10.1109/18.681320 | MR 1665794
Search
Partner of
