Witsenhausen's counterexample as Assisted Interference Suppression

Abstract

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 upper bounds (based respectively on ideas from rate-distortion theory and dirty-paper coding) are then derived on the optimal cost and the asymptotic optimal cost is characterised to within a factor of 2 regardless of the problem parameters. Restricted to the scalar problem, it is shown that the new lower bound can be better than Witsenhausen's bound by an arbitrarily large factor.