论文标题
用于功能压缩的分数图颜色和侧面信息
Fractional Graph Coloring for Functional Compression with Side Information
论文作者
论文摘要
我们描述了一种合理的方法，以减少使用侧面信息计算的无损点对点压缩的计算和通信复杂性。传统方法依赖于用代表源符号的顶点构建特征图，并带有将源符号分配给源符号的边缘，该集合为独立集合的集合而言，该集合以确切的函数恢复而进行区分。我们的方法使用分数着色的特征图的B折，以为传统着色方法提供线性编程放松，并以细粒度的粒度进行编码。我们通过推广Körner的图形熵的概念来得出由分数特征图熵给出的压缩的基本下限。我们通过计算示例演示了在传统着色上的分数着色的编码收益。我们猜想，分数着色和传统着色之间的整体差距是最小的B，它达到分数色数以无损代表给定特征图的独立集，最多是线性缩放，这是分数变色数的函数。
We describe a rational approach to reduce the computational and communication complexities of lossless point-to-point compression for computation with side information. The traditional method relies on building a characteristic graph with vertices representing the source symbols and with edges that assign a source symbol to a collection of independent sets to be distinguished for the exact recovery of the function. Our approach uses fractional coloring for a b-fold coloring of characteristic graphs to provide a linear programming relaxation to the traditional coloring method and achieves coding at a fine-grained granularity. We derive the fundamental lower bound for compression, given by the fractional characteristic graph entropy, through generalizing the notion of Körner's graph entropy. We demonstrate the coding gains of fractional coloring over traditional coloring via a computation example. We conjecture that the integrality gap between fractional coloring and traditional coloring approaches the smallest b that attains the fractional chromatic number to losslessly represent the independent sets for a given characteristic graph, up to a linear scaling which is a function of the fractional chromatic number.
