DocumentCode :
3248673
Title :
Matroid bounds on the region of entropic vectors
Author :
Congduan Li ; Walsh, John MacLaren ; Weber, Simon
Author_Institution :
Dept. of ECE, Drexel Univ., Philadelphia, PA, USA
fYear :
2013
fDate :
2-4 Oct. 2013
Firstpage :
796
Lastpage :
803
Abstract :
Several properties of the inner bound on the region of entropic vectors obtained from representable matroids are derived. In particular, it is shown that: I) It suffices to check size 2 minors of an integer-valued vector to determine if it is a valid matroid rank; II) the subset of the extreme rays of the Shannon outer bound (the extremal polymatroids) that are matroidal are also the extreme rays of the cone of matroids; III) All matroid ranks are convex independent; and IV) the extreme rays of the conic hull of the binary/ternary/quaternary representable matroid ranks inner bound are a subset of the extreme rays of the conic hull of matroid ranks. These properties are shown to allow for substantial reduction in the complexity of calculating important rate regions in multiterminal information theory, including multiple source multicast network coding capacity regions.
Keywords :
combinatorial mathematics; computational complexity; entropy; matrix algebra; vectors; Shannon outer bound; binary representable matroid rank; entropic vector region; extremal polymatroids; integer-valued vector; matroid bounds; multiple source multicast network coding capacity regions; multiterminal information theory; quaternary representable matroid rank; substantial reduction; ternary representable matroid rank; Complexity theory; Encoding; Entropy; Manganese; Network coding; Random variables; Vectors; entropic vectors; matroids; network coding; polymatroids;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Communication, Control, and Computing (Allerton), 2013 51st Annual Allerton Conference on
Conference_Location :
Monticello, IL
Print_ISBN :
978-1-4799-3409-6
Type :
conf
DOI :
10.1109/Allerton.2013.6736606
Filename :
6736606
Link To Document :
بازگشت