A vector version of witsenhausen’s counterexample: A convergence of control, communication and computation

We argue that Witsenhausen´s counterexample provides a useful conceptual bridge between distributed control, communication and computation. Inspired by the utility of studying long block-lengths in information theory, we formulate a vector version of the counterexample. Information-theoretic arguments are then used to derive bounds on the minimum cost for the vector problem. Restricted to the scalar case, the lower bounds are a strict improvement over Witsenhausen´s lower bound for some parameter values. The upper bounds are based on two strategies that can asymptotically outperform optimal linear and nonlinear scalar strategies. To investigate the computational aspects of such problems, we then consider a simpler problem of lossless source coding. From a distributed control perspective, the computations required for encoding and decoding can be viewed as internal communication between virtually distributed agents. We derive new lower bounds that establish a tradeoff between the computation, communication and distortion costs for lossless source coding.