Network data compression

Network scalable data compression

In wireless sensor networks, one could have multiple sensors measuring correlated information. In these cases, for efficient data collection, we would like to opportunistically utilize the dependencies between multiple observations, even when we may not have complete access to these dependent observations. Moreover, we may want to collect this information in a scalable manner, by asking for a better approximation (higher quality) of the sensory information in multiple stages, with the receivers having access to some correlated sensory information (side-information) which is not available to the encoder. In particular, the ``side-information scalability could be such that the node with access to the ``better quality side-information can decode with minimum delay. In a sense, this is an opportunistic scheme since we want to aggressively deliver the source to the ``better decoder, which should not be jeopardized simply because of the existence of ``worse decoders in the network. We posed this problem and have solved this completely for Gaussian sources with quadratic distortion measures.

We have solved an open problem (posed by Steinberg and Merhav, 2004) on multi-stage successive refinement with side information, when successive stages are for decoders with improving quality side-information. In solving this problem, we identified the general notion of successive refinability of data compression with side-information.

We studied the multi-user successive refinement problem (posed in Pradhan and Ramchandran, 2002), where the users are connected to a central server through links with different noiseless capacities. Each user requires to reconstruct the source in a scalable manner. We provided the best known achievable strategy for the two-user, two-layer case and the complete characterization of the rate-distortion region for the Gaussian source under the mean-squared error (MSE) distortion measure.

Papers

  1. Abstract:
    We introduce the problem of side-information scalable data compression In this problem, the encoder constructs a progressive description, such that the receiver with high quality side information will be able to truncate the bit-stream and reconstruct in the rate distortion sense, while the receiver with low quality side information will have to receive further data in order to decode. We provide a complete characterization of the rate distortion region for the important quadratic Gaussian case with multiple jointly Gaussian side-informations, where the side information quality does not have to be monotonic along the scalable coding order. Inner and outer bounds are provided to the rate distortion region for general discrete memoryless sources.
  2. Abstract:
    We study the multi-user successive refinement problem (posed in Pradhan and Ramchandran, 2002), where the users are connected to a central server through links with different noiseless capacities. Each user requires to reconstruct the source in a scalable manner. We provide the best known achievable strategy for the two-user, two-layer case and the complete characterization of the rate-distortion region for the Gaussian source under the mean-squared error (MSE) distortion measure.
  3. Abstract:
    This solves an open problem (posed by Steinberg and Merhav, 2004) on multi-stage successive refinement with side information, when successive stages are for decoders with improving quality side-information. In solving this problem, we identified the general notion of successive refinability of data compression with side-information. A source-channel separation theorem is provided when the descriptions are sent over independent channels for the multistage case.

—-

Compression with encoder side-informations

Suppose that one wants to distribute data to two receivers, each of which have a correlated version (side-information) of the data to be sent. Suppose further that the encoder has access to these side-informations. If the data is to be sent losslessly, then there is a classical result using Slepian-Wolf coding that shows that encoder knowledge is not useful in reducing transmission rate (though it might help encoding complexity). We investigated the case where the data is only needed approximately (with distortion). In this case, we have shown that encoder knowledge actually helps in transmission rate for Gaussian sources and quadratic distortion measures (also see longer version).

If the source was binary and the receivers had (different) partial knowledge of the source i.e., they had ``erased'' versions of the source) then we have also shown a complete characterization for some special cases of the problem. This also shows the value of encoder knowledge and leads to some interesting analogies between the Gaussian and the erasure cases.

Papers

  1. Download: pdtencsiisit09.pdf 
    Abstract:
    In this paper we find properties that are shared between two seemingly unrelated lossy source coding setups with side-information. The first setup is when the source and sideinformation are jointly Gaussian and the distortion measure is quadratic. The second setup is when the side-information is an erased version of the source. We begin with the observation that in both these cases the Wyner-Ziv and conditional ratedistortion functions are equal. Next, we consider the case when there are two decoders with access to different side-information sources. For the case when the encoder has access to the sideinformation we establish bounds on the rate-distortion function and a sufficient condition for tightness. Under this condition, we find a characterization of the rate-distortion function for physically degraded side-information. This characterization holds for both the Gaussian and erasure setups.
  2. E. Perron, S. N. Diggavi, and I E. Telatar, "On the Role of Encoder Side-Information in Source Coding for Multiple Decoders," in Proc. IEEE International Symposium on Information Theory, Seattle, 2006.