Approximately Optimal Solutions to the Finite-Dimensional Witsenhausen Counterexample
- 12 April 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 58 (9) , 2189-2204
Abstract
Recently, a vector version of Witsenhausen's counterexample was considered and it was shown that in the asymptotic limit of infinite vector length, certain vector-quantization-based control strategies are provably within a constant factor of the asymptotically optimal cost for all possible problem parameters. While suggestive, a constant factor result for the finite-dimensional problem has remained elusive. In this paper, we provide a resolution to this issue. By applying a large-deviation “sphere-packing” philosophy, we derive a lower bound to the optimal cost for the finite dimensional case that uses appropriate shadows of an existing vector lower bound that is the same for all dimensions. Using this new lower bound, we show that good lattice-quantization-based control strategies achieve within a constant factor of the optimal cost uniformly over all possible problem parameters, including the vector length. For Witsenhausen's original problem-which is the scalar case-the gap between regular lattice-quantization-based strategies and the lower bound is provably never more than a factor of 100, and computer calculations strongly suggest that the factor in fact may be no larger than 8. Finally, to obtain a numerical understanding of the possible room for improvement in costs using alternative strategies, we also include numerical comparison with strategies that are conjectured to be optimal. Using this comparison, we posit that there is more room for improvement in our lower bounds than in our upper bounds.Keywords
This publication has 44 references indexed in Scilit:
- Multiaccess Channels with State Known to Some Encoders and Independent MessagesEURASIP Journal on Wireless Communications and Networking, 2008
- Information and control: Witsenhausen revisited2007
- Lattices Which Are Good for (Almost) EverythingIEEE Transactions on Information Theory, 2005
- Numerical solutions to the Witsenhausen counterexample by approximating networksIEEE Transactions on Automatic Control, 2001
- The Witsenhausen counterexample: a hierarchical search approach for nonconvex optimization problemsIEEE Transactions on Automatic Control, 2001
- Simultaneous design of measurement and control strategies for stochastic systems with feedbackAutomatica, 1989
- Stochastic teams with nonclassical information revisited: When is an affine law optimal?IEEE Transactions on Automatic Control, 1987
- Writing on dirty paper (Corresp.)IEEE Transactions on Information Theory, 1983
- Another look at the nonclassical information structure problemIEEE Transactions on Automatic Control, 1980
- Theoretical limitations on the transmission of data from analog sourcesIEEE Transactions on Information Theory, 1965