The finite-dimensional Witsenhausen counterexample
The finite-dimensional Witsenhausen counterexample
复制标题
有限维 Witsenhausen 反例
DOI：
10.1109/wiopt.2009.5291559
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Se Yong Park
中科院分区：
文献类型：
--
作者：
P. Grover;A. Sahai;Se Yong Park
最近，我们考虑了一个向量版本的维森豪森的反例，并使用了一个新的下限，以表明在无限向量长度的限制，某些基于量化的策略是可证明的最佳成本为所有可能的问题参数的一个常数的因素。在本文中，有限的向量长度被视为一个额外的问题参数的向量长度被认为是。通过应用“球包装”的哲学，这个有限长度的问题的最佳成本的下限推导出使用适当的阴影的无限长度的界限。我们还介绍了任何有限长度的基于格的量化策略。使用新的有限长度的下限，我们表明，基于格的策略实现在一个恒定的因素内的最佳成本均匀的所有可能的问题参数，包括向量长度。对于Witsenhausen的原始问题-对应于标量情况-基于格的策略在最优成本的8倍内达到。基于在标量情况下和无限维情况下的观察，我们还推测什么是最佳策略可以为任何有限的向量长度。
Recently, we considered a vector version of Witsenhausen's counterexample and used a new lower bound to show that in that limit of infinite vector length, certain quantization-based 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.