In this paper, we aim to provide a systematic study of the relationship between Chernoff information and topological, as well as algebraic properties of the corresponding Gaussian tree graphs for the underlying graphical testing problems. We first show the relationship between Chernoff information and generalized eigenvalues of the associated covariance matrices. It is then proved that Chernoff information between two Gaussian trees sharing certain local subtree structures can be transformed into that of two smaller trees. Under our proposed grafting operations, bottleneck Gaussian trees, namely, Gaussian trees connected by one such operation, can thus be simplified into two 3-node Gaussian trees, whose topologies and edge weights are subject to the specifics of the operation. Thereafter, we provide a thorough study about how Chernoff information changes when small differences are accumulated into bigger ones via concatenated grafting operations. It is shown that the two Gaussian trees connected by more than one grafting operation may not have bigger Chernoff information than that of one grafting operation unless these grafting operations are separate and independent. At the end, we propose an optimal linear dimensional reduction method related to generalized eigenvalues.
The error exponent of an @math -ary hypothesis testing problem is the minimum pair-wise Chernoff information among them @cite_17 . So we focus on pair-wise topological differences at first. We come up with a typical topological pair, namely two trees connected by one grafting operation, which is deemed to represent the case where two Gaussian trees have a minimal topological difference. Grafting is a kind of topological operation by cutting down a subtree from another tree and pasting it to another location as shown in Fig. . In this figure, @math are the nodes in both trees, representing random variables @math . We separate subtree1 and subtree2 by cutting the edge @math with weight @math and paste subtree2 to subtree1 by adding new edge @math with the same weight @math . We call @math anchor nodes of this grafting operation. Our formulation is for the purpose of identifying the contributing factors to Chernoff information in distinguishing Gaussian trees with minimum topological difference, which can be deemed as a worst case scenario.
@cite_17
2153397702
We present a simple geometrical interpretation for the solution to the multiple hypothesis testing problem in the asymptotic limit. Under this interpretation, the optimal decision rule is a nearest neighbor classifier on the probability simplex.