A sender communicates with a receiver who wishes to reliably evaluate a function of their combined data. We show that if only the sender can transmit, the number of bits required is a conditional entropy of a naturall...
详细信息
A sender communicates with a receiver who wishes to reliably evaluate a function of their combined data. We show that if only the sender can transmit, the number of bits required is a conditional entropy of a naturally defined graph, We also determine the number of bits needed when the communicators exchange two messages.
Consider a distributed coding for computing problem with constant decoding locality, i.e., with a vanishing error probability, any single sample of the function can be approximately recovered by probing only constant ...
详细信息
ISBN:
(纸本)9798350382853;9798350382846
Consider a distributed coding for computing problem with constant decoding locality, i.e., with a vanishing error probability, any single sample of the function can be approximately recovered by probing only constant number of compressed bits. We establish an achievable rate region by designing an efficient layered coding scheme, where the coding rate is reduced by introducing auxiliary random variables and local decoding is achieved by exploiting the expander graph code. Then we show the rate region is optimal under mild regularity conditions on source distributions. The proof relies on the reverse hypercontractivity and a rounding technique to construct auxiliary random variables. The rate region is strictly smaller than that for the classical problem without the constant locality constraint in most cases, which indicates that more rate is required in order to achieve lower coding complexity. Graph characterizations are also developed to simplify the computation of the achievable rate region.
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 ...
详细信息
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.
暂无评论