This work investigates functional source coding problems with maximal distortion, motivated by approximate function computation in many modern applications. The maximal distortion treats imprecise reconstruction of a function value as good as perfect computation if it deviates less than a tolerance level, while treating reconstruction that differs by more than that level as a failure. Using a geometric understanding of the maximal distortion, we propose a hypergraph-based source coding scheme for function computation that is constructive in the sense that it gives an explicit procedure for finding optimal or good auxiliary random variables. Moreover, we find that the hypergraph-based coding scheme achieves the optimal rate-distortion function in the setting of coding for computing with side information and achieves the Berger-Tung sum-rate inner bound in the setting of distributed source coding for computing. It also achieves the El Gamal-Cover inner bound for multiple description coding for computing and is optimal for successive refinement and cascade multiple description problems for computing. Lastly, the benefit of complexity reduction of finding a forward test channel is shown for a class of Markov sources.
翻译:这项工作调查了由许多现代应用程序的近似函数计算驱动的最大扭曲的功能源编码问题。 最大扭曲将功能值的不精确重整作为完美的计算, 如果它偏差小于容忍水平, 将功能值的不精确重整作为完美的计算, 而将比该水平不同的重整作为失败处理。 使用对最大扭曲的几何理解, 我们提议了一个基于高光谱的功能计算源编码方案, 它具有建设性, 因为它为找到最佳或良好的辅助性随机变量提供了明确的程序。 此外, 我们发现基于高光谱的编码方案在设定边端信息计算编码时实现了最佳的速率调试功能, 并在计算分布源编码的设置中实现了 Berger- Tung 和速率内部约束 。 它还实现了 El Gamal- Cover 内部连接, 用于计算多重描述编码, 并且对于连续的完善和串联计算多个描述问题来说是最佳的。 此外, 我们发现基于超光谱的编码方案在使用前导测试频道时实现了最佳的复杂程度的效益。