In many resource allocation problems, a centralized controller needs to award some resource to a user selected from a collection of distributed users with the goal of maximizing the utility the user would receive from the resource. This can be modeled as the controller computing an extremum of the distributed users’ utilities. The overhead rate necessary to enable the controller to reproduce the users’ local state can be prohibitively high. An approach to reduce this overhead is interactive communication wherein rate savings are achieved by tolerating an increase in delay. In this paper, we consider the design of a simple achievable scheme based on successive refinements of scalar quantization at each user. The optimal quantization policy is computed via a dynamic program and we demonstrate that tolerating a small increase in delay can yield significant rate savings. We then consider two simpler quantization policies to investigate the scaling properties of the rate-delay tradeoffs. Using a combination of these simpler policies, the performance of the optimal policy can be closely approximated with lower computational costs.
A concern of signal processing is to provide optimized practical quantization algorithms for the DFC system with performance close to the rate-distortion limits @cite_9 @cite_13 @cite_17 @cite_33 @cite_11 @cite_5 @cite_6 . There are asymptotic results for sufficiently high-rate and low-distortion that are derived by applying high rate quantization theory @cite_16 , while there are also non-asymptotic results derived from generalizations of Lloyd's algorithm.
@cite_33 @cite_9 @cite_17 @cite_6 @cite_5 @cite_16 @cite_13 @cite_11
2103175928 2027315598 2163382065 2023267926 2049053255 2020053595 2139519968 2267540778
Quantization is the mapping of continuous quantities into discrete quantities, an operation far more general and flexible than the ubiquitous example of analog-to-digital conversion of scalar amplitude values. By appropriate choice of distortion measures and transmission constraints, quantization can incorporate signal processing such as statistical classification, estimation, and modeling. We here survey several approaches to incorporating such tasks into the quantization and possible extensions to distributed signal processing. An important class of engineering problems involves sensing an environment and making estimates based on the phenomena sensed. In the traditional model of this problem, the sensors' observations are available to the estimator without alteration. There is .growing interest in distributed sensing systems in which several observations are communicated to the estimator over channels of limited capacity. The observations must be separately encoded so that the target can be estimated with minimum distortion. Two questions are addressed for a special case of this problem wherein there are two sensors which observe noisy data and communicate with a single estimator: 1) if the encoder is unlimited in complexity, what communication rates and distortions can be achieved, 2) if the encoder must be a quantizer (a mapping of a single observation sample into a digital output), how can it be designed for good performance? The first question is treated by the techniques of information theory. It is proved that a given combination of rates and distortion is achievable if there exist degraded versions of the observations that satisfy certain formulas. The second question is treated by two approaches. In the first, the outputs of the quantizers undergo a second stage of encoding which exploits their correlation to reduce the output rate. Algorithms which design the second stage are presented and tested. The second approach is based on the distributional distance , a measure of dissimilarity between two probability distributions. An algorithm to modify a quantizer for increased distributional distance is derived and tested. In a decentralized hypothesis testing network, several peripheral nodes observe an environment and communicate their observations to a central node for the final decision. The presence of capacity constraints introduces theoretical and practical problems. The following problem is addressed: given that the peripheral encoders that satisfy these constraints are scalar quantizers, how should they be designed in order that the central test to be performed on their output indices is most powerful? The scheme is called cooperative design-separate encoding since the quantizers process separate observations but have a common goal; they seek to maximize a system-wide performance measure. The Bhattacharyya distance of the joint index space as such a criterion is suggested, and a design algorithm to optimize arbitrarily many quantizers cyclically is proposed. A simplified version of the algorithm, namely an independent design-separate encoding scheme, where the correlation is either absent or neglected for the sake of simplicity, is outlined. Performances are compared through worked examples. > We present an algorithm for designing locally optimal vector quantizers for general networks. We discuss the algorithm's implementation and compare the performance of the resulting "network vector quantizers" to traditional vector quantizers (VQs) and to rate-distortion (R-D) bounds where available. While some special cases of network codes (e.g., multiresolution (MR) and multiple description (MD) codes) have been studied in the literature, we here present a unifying approach that both includes these existing solutions as special cases and provides solutions to previously unsolved examples. Distributed functional scalar quantization (DFSQ) theory provides optimality conditions and predicts performance of data acquisition systems in which a computation on acquired data is desired. We address two limitations of previous works: prohibitively expensive decoder design and a restriction to source distributions with bounded support. We show that a much simpler decoder has equivalent asymptotic performance to the conditional expectation estimator studied previously, thus reducing decoder design complexity. The simpler decoder features decoupled communication and computation blocks. Moreover, we extend the DFSQ framework with the simpler decoder to source distributions with unbounded support. Finally, through simulation results, we demonstrate that performance at moderate coding rates is well predicted by the asymptotic analysis, and we give new insight on the rate of convergence. The authors consider how much performance advantage a fixed-dimensional vector quantizer can gain over a scalar quantizer. They collect several results from high-resolution or asymptotic (in rate) quantization theory and use them to identify source and system characteristics that contribute to the vector quantizer advantage. One well-known advantage is due to improvement in the space-filling properties of polytopes as the dimension increases. Others depend on the source's memory and marginal density shape. The advantages are used to gain insight into product, transform, lattice, predictive, pyramid, and universal quantizers. Although numerical prediction consistently overestimated gains in low rate (1 bit sample) experiments, the theoretical insights may be useful even at these rates. > Distributed nature of the sensor network architecture introduces unique challenges and opportunities for collaborative networked signal processing techniques that can potentially lead to significant performance gains. Many evolving low-power sensor network scenarios need to have high spatial density to enable reliable operation in the face of component node failures as well as to facilitate high spatial localization of events of interest. This induces a high level of network data redundancy, where spatially proximal sensor readings are highly correlated. We propose a new way of removing this redundancy in a completely distributed manner, i.e., without the sensors needing to talk, to one another. Our constructive framework for this problem is dubbed DISCUS (distributed source coding using syndromes) and is inspired by fundamental concepts from information theory. We review the main ideas, provide illustrations, and give the intuition behind the theory that enables this framework.We present a new domain of collaborative information communication and processing through the framework on distributed source coding. This framework enables highly effective and efficient compression across a sensor network without the need to establish inter-node communication, using well-studied and fast error-correcting coding algorithms. Communication of quantized information is frequently followed by a computation. We consider situations of distributed functional scalar quantization: distributed scalar quantization of (possibly correlated) sources followed by centralized computation of a function. Under smoothness conditions on the sources and function, companding scalar quantizer designs are developed to minimize mean-squared error (MSE) of the computed function as the quantizer resolution is allowed to grow. Striking improvements over quantizers designed without consideration of the function are possible and are larger in the entropy-constrained setting than in the fixed-rate setting. As extensions to the basic analysis, we characterize a large class of functions for which regular quantization suffices, consider certain functions for which asymptotic optimality is achieved without arbitrarily fine quantization, and allow limited collaboration between source encoders. In the entropy-constrained setting, a single bit per sample communicated between encoders can have an arbitrarily large effect on functional distortion. In contrast, such communication has very little effect in the fixed-rate setting.