Paper Info
Title
A vector version of witsenhausen's counterexample: A convergence of control, communication and computation
Abstract
Abstract— At its core, the renowned Witsenhausen’s coun- terexample contains an implicit communication problem. Con- sequently, we argue that the counterexample provides a useful conceptual bridge between distributed control and communcation problems. Inspired by the success in studying long block lengths in information theory, we consider a vector version of the Witsen- hausen counterexample. For this example, information-theoretic arguments relating to lossy compression, channel coding, and dirty-paper-coding are used to show the existence of nonlinear encoding-decoding control strategies that outperform optimal linear laws and have the ratio of costs go to infinity asymptot ically in the vector-space dimension over a much,broader range of cost parameters than the previous scalar examples. The vector example is then in turn viewed as a collection of scalar random,variables with a four-phase distributed control strategy. First a set of agents make observations and communicate with each other to coordinate a first-stage control strategy , then they individually act on their state. A second set of agents now,make,noisy observations and communicate,to coordinate a control strategy, and finally they act on the state again. Th e vector case can be considered one in which the first and third phase are free. It is thus natural to impose a cost on the length of the first and third phases and this can in turn be viewed as inducing a natural cost function on the information pattern itself. Inspired by this, we close by considering the simplest possible information-theoretic analog of the problem — lossless compres- sion of a binary state vector. It turns out that the information- pattern can be used as a natural proxy for computational
Year
DOI
Venue
2008
10.1109/CDC.2008.4739477
CDC
Keywords
Field
DocType
source coding,telecommunication control,Witsenhausen's counterexample,decoding,distributed control,encoding,information theory,lossless source coding,lower bounds,nonlinear scalar strategies,optimal linear strategies,vector problem,virtually distributed agents
Information theory,Witsenhausen's counterexample,Mathematical optimization,Computer science,Upper and lower bounds,Counterexample,Decoding methods,Quantization (signal processing),Version vector,Computation
Conference
ISSN
Citations 
PageRank 
0743-1546
3
0.97
References 
Authors
11
2
Name
Order
Citations
PageRank
Pulkit Grover155765.99
A. Sahai21888198.31