The finite-dimensional Witsenhausen counterexample
Pages 604 - 613
Abstract
Recently, we considered a vector version of Witsenhausen's counterexampIe and used a new lower bound to show that in that limit of infinite vector length, certain quantizationbased strategies are provably within a constant factor of the optimal cost for all possible problem parameters. In this paper, finite vector lengths are considered with the vector length being viewed as an additional problem parameter. By applying the "sphere-packing" philosophy, a lower bound to the optimal cost for this finite-length problem is derived that uses appropriate shadows of the infinite-length bounds. We also introduce latticebased quantization strategies for any finite length. Using the new finite-length lower bound, we show that the lattice-based 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 corresponds to the scalar case - lattice-based strategies attain within a factor of 8 of the optimal cost. Based on observations in the scalar case and the infinite-dimensional case, we also conjecture what the optimal strategies could be for any finite vector length.
References
[1]
P. Grover and A. Sahai, "Vector Witsenhausen counterexample as assisted interference suppression," To appear in the special issue on Information Processing and Decision Making in Distributed Control Systems of the International Journal on Systems, Control and Communications (IJSCC), Sep. 2009. {Online}. Available: http://www.eecs.berkeley.edu/~rvsahai/
[2]
P. Grover and A. Sahai, "A vector version of Witsenhausen's counterexample: Towards convergence of control, communication and computation," Proceedings of the 47th IEEE Conference on Decision and Control (CDC), Oct. 2008.
[3]
S. Y. Park, P. Grover, and A. Sahai, "A constant-factor approximately optimal solution to the witsenhausen counterexample," Submitted to the 48th IEEE Conference on Decision and Control (CDC), 2009.
[4]
H. S. Witsenhausen, "A counterexample in stochastic optimum control," SIAM Journal on Control, vol. 6, no. 1, pp. 131-147, Jan. 1968.
[5]
Y.-C. Ho, "Review of the Witsenhausen problem," Proceedings of the 47th IEEE Conference on Decision and Control (CDC), pp. 1611-1613, 2008.
[6]
R. Bansal and T. Basar, "Stochastic teams with nonclassical information revisited: When is an affine control optimal?" IEEE Trans. Automat. Contr., vol. 32, pp. 554-559, Jun. 1987.
[7]
M. Baglietto, T. Parisini, and R. Zoppoli, "Nonlinear approximations for the solution of team optimal control problems," Proceedings of the IEEE Conference on Decision and Control (CDC), pp. 4592-4594, 1997.
[8]
J. T. Lee, E. Lau, and Y.-C. L. Ho, "The Witsenhausen counterexample: A hierarchical search approach for nonconvex optimization problems," IEEE Trans. Automat. Contr., vol. 46, no. 3, pp. 382-397, 2001.
[9]
Y.-C. Ho and T. Chang, "Another look at the nonclassical information structure problem," IEEE Trans. Automat. Contr., vol. 25, no. 3, pp. 537-540, 1980.
[10]
C. H. Papadimitriou and J. N. Tsitsiklis, "Intractable problems in control theory," SIAM Journal on Control and Optimization, vol. 24, no. 4, pp. 639-654, 1986.
[11]
T. Basar, "Variations on the theme of the Witsenhausen counterexample," Proceedings of the 47th IEEE Conference on Decision and Control (CDC), pp. 1614-1619, 2008.
[12]
G. Lipsa and N. Martins, "Finite horizon optimal memoryless control of a delay in Gaussian noise: A simple counterexample," Proceedings of the 47th IEEE Conference on Decision and Control (CDC), pp. 1628-1635, 2008.
[13]
M. Rotkowitz, "On information structures, convexity, and linear optimality," Proceedings of the 47th IEEE Conference on Decision and Control (CDC), pp. 1642-1647, 2008.
[14]
M. Rotkowitz and S. Lall, "A characterization of convex problems in decentralized control," IEEE Trans. Automat. Contr., vol. 51, no. 2, pp. 1984-1996, Feb. 2006.
[15]
S. K. Mitter and A. Sahai, "Information and control: Witsenhausen revisited," in Learning, Control and Hybrid Systems: Lecture Notes in Control and Information Sciences 241, Y. Yamamoto and S. Hara, Eds. New York, NY: Springer, 1999, pp. 281-293.
[16]
M. Costa, "Writing on dirty paper," IEEE Trans. Inform. Theory, vol. 29, no. 3, pp. 439-441, May 1983.
[17]
N. Devroye, P. Mitran, and V. Tarokh, "Achievable rates in cognitive radio channels," IEEE Trans. Inform. Theory, vol. 52, no. 5, pp. 1813-1827, May 2006.
[18]
A. Jovicic and P. Viswanath, "Cognitive radio: An information-theoretic perspective," in Proceedings of the 2006 International Symposium on Information Theory, Seattle, WA, Seattle, WA, Jul. 2006, pp. 2413-2417.
[19]
Y.-H. Kim, A. Sutivong, and T. M. Cover, "State amplification," IEEE Trans. Inform. Theory, vol. 54, no. 5, pp. 1850-1859, May 2008.
[20]
N. Merhav and S. Shamai, "Information rates subject to state masking," IEEE Trans. Inform. Theory, vol. 53, no. 6, pp. 2254-2261, Jun. 2007.
[21]
T. Philosof, A. Khisti, U. Erez, and R. Zamir, "Lattice strategies for the dirty multiple access channel," in Proceedings of the IEEE Symposium on Information Theory, Nice, France, Jul. 2007, pp. 386-390.
[22]
S. Kotagiri and J. Laneman, "Multiaccess channels with state known to some encoders and independent messages," EURASIP Journal on Wireless Communications and Networking, no. 450680, 2008.
[23]
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. MarchettiSpaccamela, and M. Protasi, Complexity and Approximation: Combinatorial optimization problems and their approximability properties. Springer Verlag, 1999.
[24]
R. Cogill and S. Lall, "Suboptimality bounds in stochastic control: A queueing example," in American Control Conference, 2006, Jun. 2006, pp. 1642-1647.
[25]
R. Cogill, S. Lall, and J. P. Hespanha, "A constant factor approximation algorithm for event-based sampling," in American Control Conference, 2007. ACC '07, Jul. 2007, pp. 305-311.
[26]
R. Etkin, D. Tse, and H. Wang, "Gaussian interference channel capacity to within one bit," IEEE Trans. Inform. Theory, vol. 54, no. 12, Dec. 2008.
[27]
A. Avestimehr, S. Diggavi, and D. Tse, "A deterministic approach to wireless relay networks," in Proc. of the Allerton Conference on Communications, Control and Computing, October 2007.
[28]
R. G. Gallager, Information Theory and Reliable Communication. New York, NY: John Wiley, 1971.
[29]
M. S. Pinsker, "Bounds on the probability and of the number of correctable errors for nonblock codes," Problemy Peredachi Informatsii, vol. 3, no. 4, pp. 44-55, Oct./Dec. 1967.
[30]
A. Sahai, "Why block-length and delay behave differently if feedback is present," IEEE Trans. Inform. Theory, no. 5, pp. 1860-1886, May 2008.
[31]
A. Sahai and P. Grover, "The price of certainty : "waterslide curves" and the gap to capacity," Dec. 2007. {Online}. Available: http://arXiv.org/abs/080 1.0352v1
[32]
H. S. Witsenhausen, "Separation of estimation and control for discrete time systems," Proceedings of the IEEE, vol. 59, no. 11, pp. 1557-1566, Nov. 1971.
[33]
R. F. H. Fisher, Precoding and Signal Shaping for Digital Transmission. New York, NY: John Wiley, 2002.
[34]
J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups. New York: Springer-Verlag, 1988.
[35]
U. Erez, S. Litsyn, and R. Zamir, "Lattices which are good for (almost) everything," IEEE Trans. Inform. Theory, vol. 51, no. 10, pp. 3401-3416, Oct. 2005.
[36]
R. Blahut, "A hypothesis testing approach to information theory," Ph.D. dissertation, Cornell University, Ithaca, NY, 1972.
[37]
P. Grover, A. Sahai, and S. Y. Park, "The finitedimensional Witsenhausen counterexample," 2009. {Online}. Available: http://www.eecs.berkeley.edu/rvpulkit/WitsenhausenConCom.pdf
[38]
D. Micciancio and S. Goldwasser, Complexity of Lattice Problems: A Cryptographic Perspective. Springer, 2002.
[39]
W. Wu, S. Vishwanath, and A. Arapostathis, "Gaussian interference networks with feedback: Duality, sum capacity and dynamic team problems," in Proceedings of the Allerton Conference on Communication, Control, and Computing, Monticello, IL, Oct. 2005.
[40]
N. Elia, "When Bode meets Shannon: control-oriented feedback communication schemes," IEEE Trans. Automat. Contr., vol. 49, no. 9, pp. 1477-1488, Sep. 2004.
[41]
R. Durrett, Probability: Theory and Examples, 1st ed. Belmont, CA: Brooks/Cole, 2005.
[42]
R. Courant, F. John, A. A. Blank, and A. Solomon, Introduction to Calculus and Analysis. Springer, 2000.
[43]
S. M. Ross, A first course in probability, 6th ed. Prentice Hall, 2001.
Recommendations
Witsenhausen's counterexample as Assisted Interference Suppression
Motivated by the existence of an implicit channel in Witsenhausen's counterexample, we formulate a vector extension that can be viewed as a toy wireless communication problem "Assisted Interference Suppression" (AIS). Information-theoretic lower and ...
On Witsenhausen's zero-error rate for multiple sources
We investigate the problem of minimum rate zero-error source coding when there are several decoding terminals having different side information about the central source variable and each of them should decode in an error-free manner. For one decoder ...
Studies on finite Sturmian words
Several properties of finite Sturmian words are proved. The inverse of the Richomme-Séébold bijection between factor sets of given length of Sturmian sequences and left special Sturmian words is constructed (using circular factors of Christoffel words) ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2009
638 pages
ISBN:9781424449194
Publisher
IEEE Press
Publication History
Published: 23 June 2009
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in