Hypothesis testing and information theory
Statistical hypothesis testing problems appear in areas as diverse as information theory, image processing, signal processing, social sciences or biology. In the context of reliable communication, binary hypothesis testing has been instrumental in the derivation of converse bounds on the error probability. Already in 1967, Shannon, Gallager and Berlekamp used an instance of binary hypothesis testing to derive the well known sphere-packing bound. Later, Blahut an Omura emphasized the fundamental role of binary hypothesis testing by obtaining converse bounds for different information-theoretic problems. More recently, the hypothesis-testing method has been used to obtain accurate finite-length lower bounds to several communication problems.
The meta-converse bound is tight
In [1] and [2], we study the relationship between hypothesis testing, information-spectrum, and converse bounds in the field of information theory. We introduce several alternative formulations for the error probability of Bayesian M-ary hypothesis testing, shedding new light on its characterization. Specifically, we establish an equivalence between the error probability of M-ary hypothesis testing and the error probability of a binary hypothesis test with specific parameters. This finding implies that the meta-converse bound for a fixed codebook, proposed by Polyanskiy, Poor, and Verdú yields the minimum error probability when optimized over its free parameters.
Furthermore, in [1] and [2] we present an explicit alternative expression for the error probability using information-spectrum measures, showcasing the connection with existing information-spectrum bounds. Remarkably, this result suggests that a properly optimized extension of the Verdú-Han bound also provides the minimum error probability. To enhance understanding, [1] introduces several detailed examples and explores potential extensions of this finding.
Generalized perfect codes
In [3] and [4], we study the code-structure that arises from the analysis of certain hypothesis testing converse bounds. This exploration leads us to propose a novel definition of generalized perfect and quasi-perfect codes, which takes into account the characteristics of the channel being used. Our definition incorporates the packing and covering properties of generalized spheres that are intentionally skewed by utilizing an auxiliary probability measure.
We establish that generalized perfect and quasi-perfect codes achieve the minimum error probability among all codes with the same blocklength and rate. To exemplify this concept, we focus on a family of q-ary symmetric erasure channels and demonstrate that maximum-distance separable (MDS) codes exhibit the properties of generalized quasi-perfect codes for these channels, thus confirming their optimality.
Moreover, in [3], we extend our findings to encompass almost-lossless source-channel coding and lossy compression under an excess-distortion constraint. By applying the principles of generalized perfect and quasi-perfect codes, we gain insights into achieving optimal performance in these scenarios.
Gaussian channels under power constraints
The AWGN channel is of significant practical importance and has been extensively studied under various power limitations at the transmitter:
Equal power constraint: All codewords in the transmission code must have equal energy.
Maximal power constraint: Each codeword must satisfy a specified energy threshold.
Average power constraint: The energy constraint is satisfied on average, allowing some codewords to violate the threshold.
The work presented in [5] and [6] stablishes new lower bounds on the error probability of codes under maximal and average power limitations at the transmitter. To this end, we first provide a comprehensive analysis of the error probability of a binary hypothesis test between two Gaussian distributions. This test's error probability corresponds to the meta-converse bound for an equal power constraint and an auxiliary independent and identically distributed (i.i.d.) zero-mean Gaussian distribution, which may not necessarily achieve channel capacity.
The key step is then the optimization of the meta-converse bound over input distributions that satisfy maximal and average power constraints. For the maximal power limitation, the resulting bound corresponds to a hypothesis test between two i.i.d. Gaussian distributions. For the average power constraint, the same lower bound holds if the codebook size is below a specific threshold, and with a certain transformation, it also holds above this threshold.
To demonstrate the effectiveness of the new bounds, [5] provides several numerical examples and compare them with previous results in the literature. While the results are specific to the AWGN channel, the techniques employed in this work have the potential to be extended to other scenarios where the optimization of the meta-converse bound over input distributions is required.
Saddlepoint approximation and asymptotic analysis
The saddlepoint expansion technique can be used to compute tail distributions of i.i.d. random variables, and provides an accurate approximation that is computationally efficient. In [7], we use this technique to analyze the minimum error probability trade-off in non-Bayesian hypothesis testing between two arbitrary independent and identically distributed (i.i.d.) distributions.
We analyze the meta-converse lower bound for symmetric channels. Notably, the saddlepoint expansion can be computed for auxiliary distributions other than the capacity-achieving output distribution. We demonstrate the advantages of computing it for the tilted output distribution, which achieves the sphere-packing exponent [8].
Our findings contribute to a better understanding of the error probability trade-off in non-Bayesian hypothesis testing, offering insights into the behavior of the meta-converse bound for symmetric channels. The saddlepoint expansion provides a valuable approximation technique, enabling efficient computations for channels of practical interest. See, e.g., [9] and [10].