Linear universal decoding for compound channels: an Euclidean Geometric Approach

On a discrete memoryless channel (DMC), the maximum likelihood (ML) decoding rule is not only optimal (for equiprobable messages and average error probability), but it is also linear (the metric that it maximizes is additive over the block length), which in particular, makes ML practically conceivable. On a compound DMC, the use of ML is ruled out by the channelpsilas law ignorance. In order to account for this, the universal decoders proposed in (Feder et al., 1998) can be employed. However, none of these decoders is linear. Hence, we consider the problem of finding good linear decoders for compound DMCpsilas. We show that on most compound sets, when universality requires to be capacity achieving, there exists a universal decoding rule which is generalized linear, in the sense that it maximizes only a finite number of additive metrics. A local to global geometric method is developed to solve this problem. By considering very noisy channels, the global problem is reduced, in the limit, to an inner product space problem, for which insightful solutions can be found. We describe a heuristic method used, in this problem, to ldquoliftrdquo local results to global results.