Topological and Algebraic Properties of Chernoff
Information between Gaussian Graphs

arXiv:1712.09741v1 [] 28 Dec 2017

Binglin Li, Shuangqing Wei, Yue Wang, Jian Yuan

Abstract—In this paper, we want to find out the determining
factors of Chernoff information in distinguishing a set of Gaussian graphs. We find that Chernoff information of two Gaussian
graphs can be determined by the generalized eigenvalues of their
covariance matrices. We find that the unit generalized eigenvalue
doesn’t affect Chernoff information and its corresponding dimension doesn’t provide information for classification purpose.
In addition, we can provide a partial ordering using Chernoff
information between a series of Gaussian trees connected by
independent grafting operations. With the relationship between
generalized eigenvalues and Chernoff information, we can do
optimal linear dimension reduction with least loss of information
for classification.
Key words: Gaussian graphs, generalized eigenvalue, Chernoff
information, dimension reduction

I. I NTRODUCTION
Gaussian graphical model is widely used in constructing the
conditional independence of continuous random variables. It
is used in many applications such as social network [1], economics [2], biology [3] and so on. Our work is about statistical
inference problems related to Gaussian graphical model where
we want to learn the error exponents for classification.
There are two different error events in this learning problem.
If we want to classify the learnt distribution from the true one,
we often use Kullback-Leibler(KL) distance as the error exponent [4], [5]. Otherwise, we use Chernoff information when we
measure the average error exponent for the error probability in
discerning M distributions based on a sequence of data drawn
independently from one of M distributions. The minimum
pair-wise Chernoff information among these distributions is
the error exponent characterizing the performance of an M ary hypothesis testing problem.
In algebraic analysis of hypothesis testing problem, we
also use generalized eigenvalues of covariance matrices as
a metric of the difference between them [6], [7]. Clearly,
Chernoff information and generalized eigenvalues of covariance matrices are respectively probabilistic and algebraic ways
to describe the difference between two Gaussian graphs. So
there must be relation among topology, statistical distributions
(Chernoff information), and algebra (generalized eigenvalues).
This paper will study this relationship and show how Chernoff
B. Li, Y. Wang and J. Yuan are with Department of Electronic Engineering, Tsinghua University, Beijing, P. R. China, 100084. (E-mail:
libl13@mails.tsinghua.edu.cn; wangyue, jyuan@mail.tsinghua.edu.cn). S. Wei
is with the school of Electrical Engineering and Computer Science, Louisiana
State University, Baton Rouge, LA 70803, USA (Email: swei@lsu.edu). This
material is based upon work supported in part by the National Science
Foundation (USA) under Grant No. 1320351, and the National Natural
Science Foundation of China under Grant 61673237.

information can be determined by generalized eigenvalues.
What’s more, we will show how topology differences affect
generalized eigenvalues and thus Chernoff information.
More specifically, we find that two Gaussian graphs can
be linearly and inversely transformed to two graphs whose
covariance matrices are diagonal. And entries of the diagonal
matrices are related to generalized eigenvalues. Thus we find
that Chernoff information between two Gaussian graphs is an
expression of generalized eigenvalues and a special parameter
λ∗ which is also determined by generalized eigenvalues.
What’s more, we find that the unit generalized eigenvalue
doesn’t affect Chernoff information and the corresponding
dimension is not making contributions to differentiating two
Gaussian graphs for classification problem.
Our former paper [8] dealt with the classification problem
related to Gaussian trees. And we found that some special
operations on Gaussian trees, namely, adding operation and
division operation, don’t change Chernoff information between
them. Now in this paper, we find that the two operations only
add one extra unit generalized eigenvalue and don’t affect
other generalized eigenvalues. So we can use generalized
eigenvalues to prove the same probabilities. [8] also dealt
with two Gaussian trees connected by one grafting operation
and showed that Chernoff information between them is the
same with that of two special 3-node trees whose weights are
related to the underlying operation. In this paper, we extend
this result to a Gaussian tree chain connected by independent
grafting operations and provide a partial ordering of Chernoff
information between these trees.
In practice, the collection and storage of data have cost and
we may need to reduce the dimension of data. An good choice
here is doing linear dimension reduction in collection stage.
We linearly transform an N dimensional Gaussian vector x
to an NO < N dimensional vector y = Ax, through an
NO × N matrix A. An immediate question here is the optimal
selection of A which can maximize the error exponent in the
classification of two hypothesis. In our former paper [8], we
only dealt with a simple, but non-trivial case with NO = 1.
In this work, we offer an optimal method to maximize the
resulting Chernoff information after a linear transformation
for an arbitrary NO ≥ 1.
Our major and novel results can be summarized as follows.
We first provide the relationship between Chernoff information
and generalized eigenvalues. According to the former result,
we show that generalized eigenvalues which are equal to 1
make no contribution to Chernoff information. And we use
this to explain why adding and division operations of [8]

don’t affect Chernoff information between Gaussian trees.
These results build a relationship between topology, statistical
distribution and algebra. What’s more, we deal with Gaussian
trees connected by more than one grafting operation and show
a partial ordering inside the chain. At last, we provide an
optimal linear dimension reduction method.
This paper is organized as below. In Section II, we propose
the model of our analysis. The relationship between topology,
Chernoff information and generalized eigenvalues is shown
in Section III. The partial ordering of Gaussian tree chain
is presented in Section IV. Section V shows the optimal
dimension reduction method. And in Section VI we conclude
the paper.
II. S YSTEM M ODEL
Consider a set of Gaussian graphs, namely,
Gk (x), k = 1, 2, . . . , M , with their prior probabilities
given by π1 , π2 , . . . , πM . For simplification, we normalize
the variance of all Gaussian variables to be 1 and the mean
values to be 0. They share the same entropy, and thus the
(k)
same determinant of their covariance matrices Σk = [σij ].
The same entropy means the same amount of randomness.
This assumption can let us compare these Gaussian graphs
fairly. We want to do an M -ary hypothesis testing to find
out from which Gaussian distribution the data sequence
T
X = [x1 , . . . , xt ] (xl = [x1,l , . . . , xN,l ] ) comes from. We
define the average error probability of the hypothesis testing
to be Pe , and let Ee = limt→∞ − lnt Pe be the resulting
error exponent, which depends on the smallest Chernoff
information between the graphs [9] , namely,
Ee =

min

1≤i6=j≤M

CI(Σi ||Σj )

(1)

where CI(Σi ||Σj ) is the Chernoff information between the
ith and j th graphs.
For two 0-mean N-dim Gaussian joint distributions, x1 ∼
N (0, Σ1 ) and x2 ∼ N (0, Σ2 ), their Kullback-Leibler divergence is as follows
D(Σ1 ||Σ2 ) =

1
|Σ2 | 1
N
log
+ tr(Σ−1
2 Σ1 ) −
2
|Σ1 | 2
2

(2)

P
where tr(X) = i xii is the trace of square matrix X. We
define a new distribution N (0, Σλ ) in the exponential family
of the N (0, Σ1 ) and N (0, Σ2 ), namely
−1
−1
Σ−1
λ = Σ1 λ + Σ2 (1 − λ)

(3)

So the Chernoff information is given below
CI(Σ1 ||Σ2 ) = D(Σλ∗ ||Σ2 ) = D(Σλ∗ ||Σ1 )

(4)

where λ∗ is the point at which the latter equation is satisfied
[10]. It is unique in interval [0, 1].
We already know that the overall Chernoff information in
an M -ary testing is bottle-necked by the minimum pair-wise
difference [10], thus we next focus on the calculation of
Chernoff information of pair-wise Gaussian graphs. Further
research will show that pair-wise Chernoff information can

be determined by the generalized eigenvalues of covariance
matrices Σ1 , Σ2 and λ∗ . And λ∗ can also be determined by
these generalized eigenvalues.
In addition to the full observation case, we will also study
a dimension reduction case. For two N variables Gaussian
graphs G1 , G2 , in the full observation case, we can have access
to all N variables and only need to calculate Chernoff information CI(Σ1 ||Σ2 ). But in the dimension reduction case, we can
only observe an NO -dim vector each time, namely, y = Ax,
where A is an NO × N matrix and x ∈ RN , y ∈ RNO .
The new variables follow joint distributions N (0, Σ̃1 ) and
N (0, Σ̃2 ) where Σ̃i = AΣi AT , i = 1, 2. For fixed NO , we
want to find out the optimal A∗ and its Chernoff information
result CI(Σ̃∗1 ||Σ̃∗2 ), s.t.
A∗ = arg max CI(Σ̃1 ||Σ̃2 )
A

(5)

We only consider binary hypothesis testing in this dimension
reduction problem.
III. G ENERALIZED EIGENVALUES , C HERNOFF
INFORMATION AND TOPOLOGY

Chernoff information is the measurement of the difference
between statistical distributions. It is hard to be calculated
directly and we rarely study its insights about the relationship between Chernoff information and structure characters.
Chernoff information and generalized eigenvalues are both
important parameters to describe Gaussian graphical models.
We will expose the relationship between them.
A. Linear transformation to diagonal covariance matrix related to generalized eigenvalues
For two N -node 0-mean Gaussian graphs G1 and G2 on
random variables x, whose covariance matrices are Σ1 and
Σ2 , we can use an inverse linear transformation matrix P to
transform them to x0 = Px whose covariance matrices Σ01 and
Σ02 are diagonal and related to the generalized eigenvalues of
Σ1 and Σ2 .
Σ1 and Σ2 are real symmetric positive definite matrices,
so the eigenvalues of Σ1 Σ−1
are all positive, as shown in
2
Appendix A. The eigenvalue decomposition of Σ1 Σ−1
is
2
QΛQ−1 , where Q is an N × N matrix and Λ = Diag({λi })
is a diagonal matrix of eigenvalues, in which we put multiple
eigenvalues adjacent. {λi } are the eigenvalues of Σ1 Σ−1
2 ,
namely, the generalized eigenvalues of Σ1 and Σ2 . Note that
Q may be non-orthogonal when Σ1 Σ−1
2 isn’t symmetric.
Proposition 1: For two N -node 0-mean Gaussian graphs
G1 and G2 whose covariance matrices are Σ1 and Σ2 respectively, we can construct a linear transformation matrix

 1
T − 2 −1
Q and thus
P = Q−1 Σ2 (Q−1 )
Σ02 =PΣ2 PT = IN

(6)

Σ01 =PΣ1 PT = Λ

(7)

−1
where eigenvalue decomposition of Σ1 Σ−1
.
2 is QΛQ
The proof of Proposition 1 is shown in Appendix A.

We can treat Σ01 and Σ02 as two graphs G01 and G02 on x0
obtained from G1 and G2 by inverse linear transformation P.
G01 and G02 are graphs with N independent variables.
The distances of G01 and G02 are as follows. The distances
between G1 and G2 are the same with the distances of G01
and G02 just because P is inverse.
1X
(− ln λi + λi − 1)
2 i


1X
1
0
0
ln λi +
−1
D(Σ2 ||Σ1 ) =D(Σ2 ||Σ1 ) =
2 i
λi
D(Σ1 ||Σ2 ) =D(Σ01 ||Σ02 ) =

G_1

G_1

GT1

GT1

GT1

w N+1
i

GT1

G_1'

G_2

G_2

GT2

GT2
w N+1 i
i
G_2'

GT2

w

G_1'

(8)

N+1

GT2

w

G_2'
G_2

G_1

(9)

D(Σλ ||Σ1 ) =D(Σ0λ ||Σ01 )


1X
1
=
ln (λ + (1 − λ)λi ) +
−1
2 i
λ + (1 − λ)λi
(10)

GT_11

GT_11

G_1
GT_12
q
w1w2
GT_11
q
p

w1w2
p

N+1

i

GT_21
p
GT_12

w1w2

q
GT_21

G_2
GT_22
w1w2
q
p

GT_22

w1 N+1 w2
w1 N+1 w2
GT_12
GT_21
GT_22
q w1 N+1 w2
q w1 N+1 w2
p
p
GT_11
GT_12
GT_21
GT_22
G_1'
G_2'
q
q
p
p
G_1'
G_2'

Fig. 1. Adding and Division operations of two trees

=D(Σ0λ ||Σ02 )

D(Σλ ||Σ2 )


λi
λ + (1 − λ)λi
1X
ln
=
+
−1
2 i
λi
λ + (1 − λ)λi
(11)
CI(Σ1 ||Σ2 ) =CI(Σ01 ||Σ02 ) = D(Σ0λ∗ ||Σ01 ) = D(Σ0λ∗ ||Σ02 )
(12)
−1

−1

−1
−1
0
where Σ−1
= Σ01 λ +
λ = Σ1 λ + Σ2 (1 − λ) and Σλ
0 −1
0
Σ2 (1 − λ). Σλ is also a diagonal matrix. λ∗ in (12) is
the unique root of D(Σ0λ∗ ||Σ01 ) = D(Σ0λ∗ ||Σ02 ), namely,
P
1−λi
i λ∗ +(1−λ∗ )λi + ln λi = 0.
In this way, we can conclude that the KL and CI divergences
between two Gaussian graphs can be determined by their
generalized eigenvalues.

B. Relationship between generalized eigenvalues and Chernoff
information
Here we will show the relationship between Chernoff information of two Gaussian graphs and generalized eigenvalues
of their covariance matrices Σ1 and Σ2 under the assumption
of same entropy
QN and normalized covariance matrix. Under this
assumption, i=1 λi = |Σ1 |/|Σ2 | = 1.
Proposition 2: For two N -node Gaussian distributions who
have the same entropy and normalized covariance matrix
Σ1 , Σ2 , their Chernoff information satisfies


p
λ∗
1X
CI(Σ1 ||Σ2 ) =
ln{(1 − λ∗ ) λi + √ }
(13)
2 i
λi
where {λi } are the generalized eigenvalues of Σ1 , Σ2 , namely
eigenvalues of Σ1 Σ2−1 , and λ∗ ∈ [0, 1] is the unique result of
X
X
1
λi
=
=N
(14)
∗
∗
∗
λ + (1 − λ )λi
λ + (1 − λ∗ )λi
i
i
We can prove this proposition from the equation (12), as
shown in Appendix B.
We find that generalized eigenvalues of covariance matrices
Σ1 and Σ2 are the key parameters of Chernoff information.
We can get Chernoff information with these N generalized

eigenvalues, so these N parameters contain all the information about the difference between two Gaussian trees. The
generalized eigenvalues are so important that we need more
property about them.
C. Performance of unit generalized eigenvalues
In former equation, we find that unit generalized eigenvalues
are very special to Chernoff information.
Proposition 3: Assuming that the generalized eigenvalues
of (N + 1)-node G01 and G02 are the same with that of N node G1 and G2 except a newly additional unit generalized
eigenvalue, the optimal parameter λ∗ of (Σ01 , Σ02 ) is the same
with that of (Σ1 , Σ2 ) and CI(Σ01 ||Σ02 ) = CI(Σ1 ||Σ2 ).
Proposition 3 can be proved from Proposition 2 as shown
in Appendix C.
Proposition 3 shows a possible way to do dimension reduction that we can reduce the dimension of Gaussian graphs from
N +1 to N without changing their Chernoff information if we
only remove an unit generalized eigenvalue in this procedure.
Gaussian tree models, whose definition can be seen in
[8], represent the dependence of multiple Gaussian random
variables by tree topologies. [8] dealt with the classification on
Gaussian trees. In that paper, we defined two special operations
on two Gaussian trees, namely adding operation and division
operation, as shown in Fig. 1. We add the same leaf node or
divide the same edge by adding or division operations. These
two operations don’t change Chernoff information between
two Gaussian trees. Next we will show how generalized
eigenvalues change after adding or division operation.
Proposition 4: Assume that Gaussian trees G01 and G02 are
obtained from G1 and G2 by adding operation or division
operation. Their covariance matrices are (Σ01 , Σ02 ), (Σ1 , Σ2 )
respectively. The generalized eigenvalues of (Σ01 , Σ02 ) are
the same with that of (Σ1 , Σ2 ) except a newly added unit
eigenvalue.
Proposition 4 is proved in Appendix D. From Proposition
3 and 4, we can conclude that adding and division operations
don’t affect Chernoff information between two Gaussian trees.

p i

subtree2

grafting

Subtree1

Subtree1

q
i

subtree2

Fig. 2. T2 is obtained from T1 by grafting operation

3
2

subtr
ee3

2

subt
ree2

subt
ree4

Unchanged
subtree

1

3

subt
ree2

subt
ree4

Unchanged
subtree

i

subt
ree5

1

……

subt
ree1

j

subt
ree5

subt
ree1

subt
ree3

……

Fig. 3. Independent grafting operations

This result has been proved in our former paper [8] and is one
of key contribution of that paper.
IV. PARTIAL ORDERING IN INDEPENDENT GRAFTING
CHAIN

Grafting operation is a topological operation by cutting
down a subtree from another tree and pasting it to another
location, as shown in Figure 2. It is defined in our former
paper [8].
In that former paper, we have shown that two Gaussian
trees connected by one grafting operation have the same
Chernoff information with two special 3-node Gaussian trees
whose weights are related to the underlying operation. Now
we consider a more complex situation: two Gaussian trees
connected by more than one grafting operation.
Gaussian trees connected by more grafting operations can’t
be simplified to a fixed couple of small trees because the
interaction of these grafting operations varies. Our initial
expectation was that bigger difference in topology between
two Gaussian trees leads to larger Chernoff information. But
this may not be true for all situations.
Before we deal with a sequence of grafting operations, we
need to constrain the interaction among them. So we will
define the independence of grafting operations at first.
Definition 1: If all the grafting operations can be divided
into different subtrees, as shown in Fig. 3, then these grafting
operations are independent. After regrouping all the nodes
into small subtrees represented by circles, the whole tree
has super star-shaped topology. The subtree in the center is
unchanged during grafting operations. And grafting operations
are involved in disjoint super leaf nodes of the star.
In Fig. 3, we show 4 independent grafting operations around
the unchanged subtree. There are three types of grafting
operations in the star-shaped topology. From left to right, the
1-st, 2-nd grafting operations belong to the first type, the 4-th
one belongs to the second type and the 3-rd operation belongs

to the third type. For the first type, we can cut a subtree,
represented by a small circle with a number in it, from the
super leaf node(subtree1,2) and paste it to another part of this
super leaf node. In the second type, we can cut the unchanged
subtree outside the super leaf node(subtree5) and paste it to
another location in this super leaf node. But for the third type,
we will cut a subtree, represented by a small circle with a
number in it, from a super leaf node(subtree3) and paste it to
another super leaf node(subtree4). The third kind of grafting
operation involves two super leaf nodes of the star while the
first and second kinds of operation only involve one.
If all the grafting operations are independent, then we can
make the following conclusion.
Proposition 5: For two Gaussian trees connected by several
independent grafting operations, λ∗ = 1/2 holds.
The trees have the same number of nodes and the same entropy due to grafting operations. So λ∗ satisfies tr(Σλ∗ (Σ−1
1 −
Σ−1
))
=
0,
which
can
be
transformed
from
the
definition
2
−1
formulas of λ∗ . tr(Σλ∗ (Σ−1
1 −Σ2 )) is a summation formula
with 4n term, where each 4 terms are related to one single
grafting operation. So we can deal with the terms respectively
−1
and prove tr(Σ0.5 (Σ−1
1 − Σ2 )) = 0 eventually. More details
can be found in Appendix E.
Considering a grafting chain T1 ↔ T2 ↔ T3 , intuition
tells us that CI(T1 ||T3 ) is likely larger than CI(T1 ||T2 ) and
CI(T2 ||T3 ), because the difference between T1 and T3 is the
accumulation of T1 − T2 ’s difference and T2 − T3 ’s difference.
If the assumption is true, we only need to consider the adjacent
pairs of Gaussian trees in the chain when looking for the
minimum Chernoff information. Later results will tell us that
it depends on the structure of the chain.
Proposition 6: For the grafting chain T1 ↔ T2 ↔ T3 ↔
· · · ↔ Tn where all the grating operations in the chain are
independent, we can conclude that CI(Ti ||Tj ) ≤ CI(Tp ||Tq )
if p ≤ i ≤ j ≤ q.
Detail of the proof can be found in Appendix F.
If we want to find out the minimum Chernoff information
in this set, weonly need to try n − 1 pairs of Ti − Ti+1 , rather
than all the n2 pairs. The number of candidates is significantly
reduced.
It is a partial ordering because we can’t compare CI(T1 ||T2 )
and CI(T2 ||T3 ) even in a simplest chain T1 ↔ T2 ↔ T3
without knowing the weights. We can only compare Chernoff
information pairs CI(Ti ||Tj ), CI(Tp ||Tq ) when p ≤ i ≤ j ≤
q ordering, and thus this result is a partial inequality, rather
than a full ordering inequality.
In proposition 6, we constrain the grafting operations independent. So we may wonder whether the result suits for all the
possible grafting chains T1 ↔ T2 ↔ T3 ↔ · · · ↔ Tn without
independent assumption. Taking grafting chain T1 ↔ T2 ↔ T3
in Fig. 4 as an example, the two grafting operations are
not independent. Some special cases is shown in Table I. In
this table, we can find that CI(T1 ||T3 ) < CI(T1 ||T2 ) can
hold in some special situations. This is a counter-intuitive
result because more topological differences can’t lead to larger
Chernoff information between Gaussian trees.

cases
1
2
3
4

λ∗T ||T
1
3
0.5191
0.5073
0.5254
0.5082

λ
CIT1 ||T3
CIT1 ||T2
CIT2 ||T3
19.5746, 0.0433, 1.5439, 0.7642, 1, 1, 1
0.8983
0.9142
0.0251
9.2341, 0.1019, 1.2982, 0.8185, 1, 1, 1
0.5402
0.5418
0.0113
9.4328, 1.653, 0.0844, 0.7603, 1, 1, 1
0.5982
0.6103
0.0392
5.0195, 0.1863, 1.2201, 0.8766, 1, 1, 1
0.3102
0.3132
0.0056
TABLE I
N UMERICAL CASES DISSATISFYING P ROPOSITION 6 IN THE CHAIN OF F IG . 4

1 w5 6
w1

5

5

3 w3

4

G_2

7

4
w6

2 w2

3 w3

w1

4

w6

3 w3

G_1

2 w2

w4

w4
2 w2

5
w4

w1

1 w5 6 w6 7

1 w5 6

7

G_3

Fig. 4. Example for dependent grafting operations

So we can only provide a partial ordering with independent
grafting operations in this section. The problems of ordering
is much more complex than what we have expected. For a
grafting
chain T1 ↔ T2 ↔ T3 , the Chernoff information
G_1
between T1 and T3 may be larger than that between T1 and T2 ,
even though the difference between T1 and T2 seems smaller.
Here we only consider topological difference, rather than
parameterized difference, between Gaussian trees. Topological
difference is not the only contribution factor affecting such
comparisons [5], [11].
V. D IMENSION REDUCTION
The analysis in former section deals with Chernoff information in full-observation situation where we can get access
to all the variables. But in practice, there is significant cost
in collecting and storing data. So we can only use linearly
transformed low-dimensional samples to do the classification.
The linear transformation matrix should make sure that the
reduced data have maximum information for classification.
Traditional dimension reduction methods, such as Principal
Component Analysis (PCA) and other Representation Learning [12], aim to find the optimal features with maximum
information. They only consider a distribution at one time and
don’t care how we use the resulting low-dimensional data. But
our method considers two hypothesises at the same time and
want to keep the most information for classification. Some
features may be important in PCA, but invalid in our method
because these features in two hypothesis are similar. Our object
function here is the Chernoff information between the resulting
low-dimensional distributions.
In section III-A, we have shown linear transformation
method which can make the distribution in new space independent. In these new space, x0i , the i-th variable of x0 , follows
N (0, 1) in hypothesis 2 and N (0, λi ) in hypothesis 1. If λi is
farther from 1, this dimension can provide more information
for classification than other dimensions.
Assume that m of all the N eigenvalues {λi } are greater
than 1 and the other N − m eigenvalues are no more than 1. If
we want to reduce the observation dimension from N to NO ,

we choose the dimensions of x0 corresponding to the first k
rank and last NO − k rank of {λi }, where NO + m − N ≤
k ≤ m and k ≥ 0. We can choose a sub-matrix of Σ01 and
Σ02 corresponding to the NO chosen eigenvalues as the result
of dimension reduction. The NO × N linear transformation
matrix Ak is the corresponding NO rows of P corresponding
to the chosen eigenvalues.
Proposition 7: A∗ is the optimal NO ×N linear transformation matrices to maximize the Chernoff information in transformed space, namely A∗ = arg maxANO ×N CI(Σ̂1 ||Σ̂2 )
where Σ̂i = A∗ Σi A∗ T for i = 1, 2. So A∗ ∈ {Ak |NO +
m − N ≤ k ≤ m, k ≥ 0}.
Proof of proposition 7 can be seen in Appendix G and this
proposition ensure the optimality of our method.
The observation is y = A∗ x and the covariance matrices
of y in two hypothesis are
Σ002 = A∗ Σ2 A∗ T = INO
Σ001

∗

= A Σ1 A

∗T

= Diag({µi })

(15)
(16)

where Σ001 and Σ002 are NO × NO diagonal matrices and
{µ1 , µ2 , . . . , µNO } (including multiple eigenvalues) are NO
chosen eigenvalues.
D(Σ00λ ||Σ001 )


1X
1
=
ln (λ + (1 − λ)µi ) +
−1
2 i
λ + (1 − λ)µi
D(Σ00λ ||Σ002 )


λ + (1 − λ)µi
λi
1X
ln
+
−1
=
2 i
λi
λ + (1 − λ)µi

(17)

(18)

CI(Σ001 ||Σ002 ) = max min{D(Σ00λ ||Σ001 ), D(Σ00λ ||Σ002 )}
λ∈[0,1]

(19)
Equation (19) is another definition of Chernoff information
[10]. The distances are only related to the eigenvalues we have
chosen.
VI. C ONCLUSION
In this paper, we show the relationship between topology,
statistical distribution and algebra. Chernoff information between two Gaussian graphs can be determined by the generalized eigenvalues of their covariance matrices. Among them
unit generalized eigenvalue is very special and doesn’t affect
the Chernoff information. Adding and division operations on
Gaussian trees only add a newly unit generalized eigenvalues
and don’t change other generalized eigenvalues. Thus these
operations keep the Chernoff information. We also extend

our former result about grafting operation to Gaussian trees
connected by more than one independent grafting operation
and provide a partial ordering among these trees. What’s more,
we provide an optimal linear dimension reduction method with
the metric of Chernoff information.
R EFERENCES
[1] F. Vega-Redondo, Complex social networks. Cambridge University
Press, 2007, no. 44.
[2] A. Dobra, T. S. Eicher, and A. Lenkoski, “Modeling uncertainty in
macroeconomic growth determinants using Gaussian graphical models,”
Statistical Methodology, vol. 7, no. 3, pp. 292–306, 2010.
[3] A. Ahmed, L. Song, and E. P. Xing, “Time-varying networks: Recovering temporally rewiring genetic networks during the life cycle of
drosophila melanogaster,” arXiv preprint arXiv:0901.0138, 2008.
[4] V. Y. F. Tan, A. Anandkumar, and A. S. Willsky, “Learning Gaussian
tree models: analysis of error exponents and extremal structures.” IEEE
Transactions on Signal Processing, vol. 58, no. 5, pp. 2701–2714, 2010.
[5] V. Y. Tan, A. Anandkumar, L. Tong, and A. S. Willsky, “A largedeviation analysis of the maximum-likelihood learning of markov tree
structures,” Information Theory, IEEE Transactions on, vol. 57, no. 3,
pp. 1714–1735, 2011.
[6] G. Doretto and Y. Yao, “Region moments: Fast invariant descriptors
for detecting small image structures,” in 2010 IEEE Computer Society
Conference on Computer Vision and Pattern Recognition, 2010, pp.
3019–3026.
[7] R. Wang, H. Guo, L. S. Davis, and Q. Dai, “Covariance discriminative
learning: A natural and efficient approach to image set classification,”
in 2012 IEEE Conference on Computer Vision and Pattern Recognition,
2012, pp. 2496–2503.
[8] B. Li, S. Wei, Y. Wang, and J. Yuan, “Chernoff information of bottleneck
Gaussian trees,” in 2016 IEEE International Symposium on Information
Theory (ISIT). IEEE, 2016, pp. 970–974.
[9] M. B. Westover, “Asymptotic geometry of multiple hypothesis testing,”
IEEE transactions on information theory, vol. 54, no. 7, pp. 3327–3329,
2008.
[10] T. M. Cover and J. A. Thomas, Elements of information theory. John
Wiley & Sons, 2012.
[11] V. Jog and P.-L. Loh, “On model misspecification and KL separation
for Gaussian graphical models,” in 2015 IEEE International Symposium
on Information Theory (ISIT). IEEE, 2015, pp. 1174–1178.
[12] Y. Bengio, A. Courville, and P. Vincent, “Representation learning: A
review and new perspectives,” IEEE Transactions on Pattern Analysis
and Machine Intelligence, vol. 35, no. 8, pp. 1798–1828, 2013.

A PPENDIX A
P ROOF OF P ROPOSITION 1
Because Σ1 and Σ−1
are real symmetric positive definite
2
T
matrices, Σ1 = L1 LT1 and Σ−1
2 = L2 L2 due to Cholesky decomposition where L1 and L2 are real non-singular triangular
matrices.
The characteristic polynomial of Σ1 Σ−1
2 is
−1
f (Σ1 Σ−1
2 ) = |λI − Σ1 Σ2 |

= |λI − L1 LT1 L2 LT2 |
= |L1 (λI − LT1 L2 LT2 L1 )L−1
1 |
= |λI − LT1 L2 LT2 L1 |
T

= |λI − (LT1 L2 )(LT1 L2 ) |

(20)
T

T
T
So Σ1 Σ−1
2 has the same eigenvalues with (L1 L2 )(L1 L2 ) ,
which is a real symmetric positive definite matrix. So the
−1
eigenvalues of Σ1 Σ−1
2 are all positive and Σ1 Σ2 is a positive
definite matrix.
The eigenvalue decomposition of Σ1 Σ−1
is QΛQ−1 ,
2
where Q is an N × N matrix and Λ = Diag({λi }) is
a diagonal matrix of eigenvalues, in which we put multiple
eigenvalues adjacent. {λi } are the eigenvalues of Σ1 Σ−1
2 ,
namely, the generalized eigenvalues of Σ1 and Σ2 .
T
(1)
(1)
And Σ1
= Q−1 Σ1 Q−1
= [aij ] and Σ2
=
T
(1)
(1)
Q−1 Σ2 Q−1 = [bij ] satisfy Σ1 = ΛΣ2 .

aij = λi bij

(21)

aij = aji = λj bji = λj bij

(22)

So for ∀i 6= j, aij = bij = 0 or λi = λj .
If the eigenvalues of Σ1 Σ−1
have k different
2
multiple eigenvalues λ(1) , λ(2) , . . . , λ(k) with multiplicity
n1 , n2 , . . . , nk , so


J1


J2




(1)
J
3
Σ2 = 
 (23)


.
..


Jk
 (1)

λ J1


λ(2) J2


(3)


(1)
λ J3
Σ1 = 
 (24)


..


.
λ(k) Jk
where Ji is ni × ni inverse matrix.
(1) −0.5
We can also get an inverse matrix Q(1) = Σ2
so that
(2)

(1)

T

Σ2 = Q(1) Σ2 Q(1) = IN
(2)
Σ1

=Q

(1)

T
(1)
Σ1 Q(1)

=Λ

(25)
(26)

So we can construct a linear
 1transformation matrix P =
T − 2 −1
Q and thus
Q(1) Q−1 = Q−1 Σ2 (Q−1 )
Σ02 =PΣ2 PT = IN

(27)

Σ01 =PΣ1 PT = Λ

(28)

A PPENDIX B
P ROOF OF P ROPOSITION 2
λ∗ satisfies D(Σ0λ∗ ||Σ01 ) = D(Σ0λ∗ ||Σ02 ), and thus


1X
1
ln (λ∗ + (1 − λ∗ )λi ) + ∗
−
1
2 i
λ + (1 − λ∗ )λi


1X
λ∗ + (1 − λ∗ )λi
λi
=
ln
+ ∗
−1
2 i
λi
λ + (1 − λ∗ )λi
(29)
QN
With knowing i=1 λi = 1, we can conclude
X
X
1
λi
=
(30)
∗
∗
∗
λ + (1 − λ )λi
λ + (1 − λ∗ )λi
i
i
We also know
X
X
λi
1
+(1 − λ∗ )
λ∗
∗
∗
∗
λ + (1 − λ )λi
λ + (1 − λ∗ )λi
i
i
X
=
1 =N
(31)
i
∗

So λ ∈ [0, 1] is the unique result of
X
X
1
λi
=
=N
∗
∗
∗
λ + (1 − λ )λi
λ + (1 − λ∗ )λi
i
i

(32)

And
CI(Σ1 ||Σ2 ) = D(Σ0λ∗ ||Σ01 )


1X
1
=
ln (λ∗ + (1 − λ∗ )λi ) + ∗
−
1
2 i
λ + (1 − λ∗ )λi
1X
ln (λ∗ + (1 − λ∗ )λi )
=
2 i


p
1X
λ∗
=
ln (1 − λ∗ ) λi + √
(33)
2 i
λi
A PPENDIX C
P ROOF OF P ROPOSITION 3
λ∗ is unique in the range of [0, 1]. So if λ∗ satisfies equation
(14), then
X
1
1
+ ∗
=
∗
∗
λ + (1 − λ )λi
λ + (1 − λ∗ ) × 1
i
X
λi
1
+ ∗
(34)
∗ + (1 − λ∗ )λ
λ
λ
+
(1
−
λ∗ ) × 1
i
i
where {λi } are the generalized eigenvalues
S of (Σ1 , Σ2 ).
So the generalized eigenvalues {λi } {1} of (Σ01 , Σ02 ) and
λ∗ also satisfies equation (14). The optimal λ∗ is the same.
And

N 
p
1X
λ∗
CI(Σ01 ||Σ02 ) =
ln{(1 − λ∗ ) λi + √ }
2 i=1
λi


∗
√
1
λ
+
ln{(1 − λ∗ ) 1 + √ }
2
1

N 
X
p
1
λ∗
=
ln{(1 − λ∗ ) λi + √ }
2 i=1
λi
=CI(Σ1 ||Σ2 )

(35)

A PPENDIX D
P ROOF OF P ROPOSITION 4
Assume that Gaussian trees G01 and G02 are obtained from
G1 and G2 by adding operation or division operation. Their
covariance matrices are (Σ01 , Σ02 ), (Σ1 , Σ2 ) respectively. The
generalized eigenvalues of (Σ01 , Σ02 ) are the same with that of
(Σ1 , Σ2 ) except a newly added unit eigenvalue.
We use the equation of block matrix to prove this proposition. We deal with adding operation and division operation in
different subsections.
A. Proof on adding operation case
Adding operation is shown in Fig. 1. Assume G1 and G2
have node 1, .. . , N , and
 their covariance matrices are
D α
G1 : Σ1 =
αT  1

A2 B2
G2 : Σ2 , Σ−1
=
.
2
BT2 a2
Without loss of generality, the new edge is eN,N +1 with parameter w. So new covariance matrices after adding operation
are


D
α wα
1
w 
Σ01 =  αT
(36)
T
wα
w
1


A2
B2
0
2
−w 
w
(37)
Σ0−1
= BT2 a2 + 1−w
2
2
1−w2
w
1
0
− 1−w2
1−w2
The generalized eigenvalues of Σ1 and Σ2 are the roots of
|λI − Σ1 Σ−1
2 | = 0.
Σ1 Σ−1
2

Σ01 Σ0−1
2





D α A2 B2
= T
α
1 BT2 a2


DA2 + αBT2 DB2 + a2 α
=
(38)
αT A2 + BT2 αT B2 + a2


DA2 + αBT2 DB2 + a2 α 0

= αT A2 + BT2 αT B2 + a2 0 (39)
∗
∗
1

−1
|λI − Σ01 Σ0−1
2 | =(λ − 1)|λI − Σ1 Σ2 |

(40)

So new trees have an extra unit generalized eigenvalue without
changing other eigenvalues.
B. Proof on division operation case
Division operation is shown in Fig. 1. Assume that G1 and
G2 have node 1, . . . , N , and the connecting points are p =
1, q = N without loss of generality.
If we set edge e1N in G2 to be 0, we can treat it as a new
N -node tree, whose covariance matrix is A−1 . We divide A
as


x XT 0
A = X Z Y
(41)
0 YT y
where X, Y are (N −2)×1 matrices and Z is (N −2)×(N −2)
matrix.

2 w2
w1
2
2 w2
1−w1
2

XT

X

−

Z

w1 w2
−
2 w2
1−w1
2

Y

T

w1 w2
2 w2
1−w1
2

Y

y+

2 w2
w1
2
2 w2
1−w1
2






(43)

0

T
αT
1 + w1 w2 α2
P
T
w1 w2 αT
1 + α2
T
w1 αT
+
w
α
2
1
2

1
α1 + w1 w2 α2
=

w1 w2
w1

2
w1



0
G2

:

−1
Σ22 , Σ22

x + 1−w12

X


=
0



w1
−
2
1−w1

w1 w2
w1 w2 α1 + α2
1
w2

XT

0

Z

Y

YT

2
w2
2
1−w2
w2
−
2
1−w2

The generalized eigenvalues of Σ1 and
|λI − Σ1 Σ−1
2 | = 0.

0

Σ11 Σ−1
12 =Σ11 A + −w1 w2 α2
−w1 w2
Σ21 Σ−1
22

Σ11 Σ−1
12
=
∗




w1
2
1−w1

0

w2
2
1−w2
2
w2
1
+
2
2
1−w1
1−w2

−

y+

0


w1
w1 α1 + w2 α2 


w2
1
(44)
−









(45)

Σ2 are the roots of
0
0
0


0
1

−1
|λI − Σ21 Σ−1
22 | =(λ − 1)|λI − Σ11 Σ12 |

4

5

TYPE1
Other parts

1 w1

2 w2

3

Other parts’

2 w1

1 w2

4

4

TYPE2

Other parts

1 w1

2 w2

Other parts’

Other
5 6 parts 1
4 w

5 w
6

3

2 w2

TYPE3
7

Other
parts 2

5
4 w

Other
6 parts 1'

1 w1

3 w4

5 w
6

7

Other
parts 2'



G1 :
Σ21


3 w3

w3

x+

2 w2

5

3 w4

(42)

1 w1

w3

−1

G2 : Σ12 , Σ12



=



w1 w2
w1 w2 α1 + α2 
1

4

w4



T
αT
1 + w1 w2 α2
P
T
w1 w2 αT
1 + α2

3 w3

w3

G1 : Σ11

1
= α1 + w1 w2 α2
w1 w2

2 w2

w3



1 w1

w4

In G1 and G01 , we define the column node 1 to nodes 2
to N − 1 to be α1 (setting the respective rows to the nodes
in GT12 0) and the column node N to nodes 2 to N − 1 to
be α2 (setting the respective rows to the nodes in GT11 0).
Then in G1 and G01 , the column from node 1 to nodes 2 to
N − 1 is α1 + w1 w2 α2 because node 1 can reach the nodes
in GT11 directly, but reach the nodes in GT12 through node N
with path weighted by w1N = w1 w2 . And the column from
node N to node 2 to N − 1 is w1 w2 α1 + α2 because node
N can reach the nodes in GT12 directly, but reach the nodes
in GT11 through node 1 with path weighted by w1N = w1 w2 .
In G01 , the column from node N + 1 to node 2 to N − 1 is
w1 α1 + w2 α2 because node N + 1 can reach the nodes in
GT11 through node 1 with path e1,N +1 weighted by w1 , and
reach the nodes in GT12 through node N with path eN,N +1
weighted by w2 .
The covariance matrices of these trees are as shown below:


−w1 w2
−w1 w2 α1 
0
(46)
(47)
(48)

So new trees have an extra unit generalized eigenvalue without
changing other eigenvalues.
A PPENDIX E
P ROOF OF P ROPOSITION 5
λ∗ satisfies D(Σλ∗ ||Σ2 ) = D(Σλ∗ ||Σ1 ). When |Σ1 | =
|Σ2 |, it will become
the unique root in [0, 1] of

−1
tr Σλ∗ (Σ−1
−
Σ
)
=
0. We only need to prove
1
2

−1
tr Σ0.5 (Σ−1
−
Σ
)
=
0
before
we get λ∗ = 1/2.
1
2

Fig. 5. Simplified separate grafting operation types

P
tr (AB) =
i,j aij bij when A, B are both symmetric
−1
matrices. Luckily, A = Σ0.5 and B = Σ−1
are both
1 − Σ2
−1
symmetric matrices. What’s more, B = Σ1 − Σ−1
only
2
have 2n non-zero diagonal elements and 2n pairs of non-zero
non-diagonal elements, where n is the number of grafting
w2
w2
operations. For example, bpp = 1−w
2 , bqq = − 1−w 2 , biq =
w
w
1−w2 , bip = − 1−w2 if we cut node i from node p with
edge eip weighting w and paste it to node q, and there aren’t
any other grafting operations
involving these three nodes.

−1
So tr Σ0.5 (Σ−1
1 − Σ2 ) is a sum of 4n terms, each 4
terms respecting to one grafting operation. We can divide
the polynomial into n parts corresponding
each grafting
 to P
−1
operation, namely, tr Σ0.5 (Σ−1
−
Σ
)
=
1
2
k Pk . Then
we only need to prove each Pt equals to 0.
As Fig. 3 shows, there are three different types of grafting
operations here. After simplification by using adding and
merging as shown in [8], the three types of subparts can
be translated as shown in Fig. 5. In this figure, we label
these relevant nodes as 1, 2, 3 . . . for simplification because
it doesn’t change the result if we exchange labels of nodes.
Before we deal with Pk in each case, we will show Σ−1
λ
is positive definite matrix. Σ1 and Σ2 are positive definite
matrices, so Σ−1
and Σ−1
are positive definite matrices,
1
2
T −1
namely , z Σ1 z > 0 and zT Σ−1
2 z > 0 for any non-zero
T −1
vector z. Then zT Σ−1
z
=
λz
Σ
z + zT (1 − λ)Σ−1
1
2 z > 0
λ
−1
for any non-zero vector z. So Σλ is positive definite matrix
and its order principal minors are invertible matrices. This
result is useful in our later proof.
w2

−wi
2
i
We define fi = 1−w
2 and gi = 1−w 2 , so (1 + gi )gi = fi .
i
i
Then we will prove Pk = 0 in different type of Fig. 5 later.

Mij is the (i, j) minor of Σ−1
0.5 , so

A. TYPE1
In this type, we focus on node 1 to 4, which is involved in
this grafting operation. So
Σ−1
1 =

1 + g1
f1


1 + g1 + g2
f2

 f1




f
1
+
g
+
g
+
g
f
V
2
2
3
4
3




f3
1 + g3


T
(1)
V
K


Σ−1
2 =


1 + g1






 f
 1



f1
1 + g2
f2
f2 1 + g2 + g3 + g4
f3
f3
1 + g1 + g3
V

T




V 



(2)
K

where V is a 4 × (N − 4) matrix with all zero elements except
v3,1 = f4 and K(1) , K(2) are covariance matrices of node 5
to N in G1 and G2 respectively. And then
−1
Σ−1
1 − Σ2 =
0 f1
−f1
 f1 g1


0


−g1
 −f1




1
M22 =|K(3) |(1 + g1 ){(1 + g3 )(1 + g2 + g4 + g1 )
4
1
1
+ g1 (g2 + g4 )} − (1 + g1 )(1 + g3 + g1 )X
4
4
1
M44 =|K(3) |(1 + g1 ){(1 + g2 )(1 + g3 + g4 + g1 )
4
1
1
+ g1 (g3 + g4 )} − (1 + g1 )(1 + g2 + g1 )X
4
4
1
(3) 1
M12 =|K |{ f1 {(1 + g3 )(1 + g2 + g4 + g1 )
2
2
1
1
1
1
+ g1 (g2 + g4 )} + f1 f2 f3 } − f1 (1 + g3 + g1 )X
2
2
2
2
1
1
M14 =|K(3) |{ f1 {(1 + g2 )(1 + g3 + g4 + g1 )
2
2
1
1
1
1
+ g1 (g3 + g4 )} + f1 f2 f3 } − f1 (1 + g2 + g1 )X
2
2
2
2
and
2f1 (−M12 + M14 ) + g1 (M22 − M44 ) = 0

= (2f1 (−M12 + M14 ) + g1 (M22 − M44 )) |Σ0.5 | = 0
(51)
B. TYPE2
In this type, we focus on node 1 to 3, which is involved in
this grafting operation. So
Σ−1
1 =








1 + g1
f1
 f1
1
+
g
f2
1 + g2


f2
1 + g2 + g3



K(1) − K(2)

VT

1 −1
1 −1
Σ−1
0.5 = 2 Σ1 + 2 Σ2 =


1
 1 + 2 g1



1

f

2 1







1f

2 1



(50)

Pk =g1 m22 − g1 m44 + 2f1 m12 − 2f1 m14


V 



K(1)

Σ−1
2 =

1f
2 1

1 + g1 + g2
f1
f2

f1
1 + g1


f2
1 + g2 + g3


1 + g2 + 1 g1
2

f2

f2

1 + g2 + g3 + g4

f3

f3

1 + 1 g1 + g3
2

V

VT

K(3)


















VT

where K(3) = 12 K(1) + 12 K(2) is an invertible matrix because
Σ−1
λ is positive definite matrix. And we define

0

−1
VK(3) VT = 


X
|K(3) |





V 



K(2)

where V is a 3 × (N − 3) matrix with all zero elements except
v3,1 = f3 and K(1) , K(2) are covariance matrices of node 4
to N in G1 and G2 respectively. And then we use the same
progress and get
Pk =g2 m22 − g2 m11 + 2f2 m23 − 2f2 m13 = 0


0







1f
2 1

(49)

(52)

where mij is the ij-th element of Σ0.5 .

0
C. TYPE3
So Pk related to this grafting operation is g1 m22 − g1 m44 +
2f1 m12 − 2f1 m14 where mij is the ij-th element of Σ0.5 .

In this type, we focus on node 1 to 5, which is involved in
this grafting operation. So

Σ−1
1 =
f1
1 + g1 + g2

f2
1 + g4

f2
f4

f4
1 + g2 + g3 + g5

f3

f3

1 + g3 + g4 + g6
K(1)

subtr
ee2

1

2



 1 + g1







f1










f1
1 + g2

f2
1 + g1 + g4

f2
f4

f4
1 + g2 + g3 + g5

f3

f3

1 + g3 + g4 + g6

VT

V

K(2)



















where V is a 5 × (N − 5) matrix with all zero elements except
v4,1 = f5 , v5,2 = f6 and K(1) , K(2) are covariance matrices
of node 6 to N in G1 and G2 respectively. And then we use
the same progress and get
Pk =g1 m22 − g1 m33 + 2f1 m12 − 2f1 m13 = 0

(53)

where mij is the ij-th element of Σ0.5 .
Pk = 0 in all types of grafting operations
these operations
 if P
−1
are separate. And tr Σ0.5 (Σ−1
1 − Σ2 ) =
k Pk = 0.
So λ∗ = 12 if all the grafting operations in the chain are
separate.
A PPENDIX F
P ROOF OF P ROPOSITION 6
We prove this proposition by using adding and merging
operation of [8] repeatedly.
For p ≤ i ≤ j ≤ q, there are q − p grafting operations in
the grafting chain Tp ↔ · · · ↔ Tq . We divide these grafting
operations into two sets: grafting operations from Ti to Tj and
other grafting operations, namely, set 1 and set 2.
We can simplify tree pairs (Tp , Tq ) and (Ti , Tj ) into
(T̂p , T̂q ) and (T̃i , T̃j ) respectively by using adding and merging
operation of [8] repeatedly. (T̂p , T̂q ) have all the anchor nodes
of all q − p operations and the paths of backbone among these
operations. (T̃i , T̃j ) have all the anchor nodes of all set 1 operations and the paths of backbone among these operations. If all
the grafting operations in the chain are independent, (T̂p , T̂q )
have the same substructure with (T̃i , T̃j ) after dropping the
extra nodes. So CI(T̂p ||T̂q ) ≥ (T̃i ||T̃j ) holds by Proposition
2 of [8]. And then CI(Ti ||Tj ) ≤ CI(Tp ||Tq ).
Here we take a T1 ↔ T2 ↔ T3 case as an example, as
shown in Fig. 6. We can simplify the calculation of CI(T1 ||T3 )
and CI(T1 ||T2 ) as shown in Fig. 6. And then Proposition 2
of [8] can tell us CI(T1 ||T3 ) ≥ CI(T1 ||T2 ). In the same way,
we can conclude CI(T1 ||T3 ) ≥ CI(T2 ||T3 ).
A PPENDIX G
P ROOF OF P ROPOSITION 7
We want to prove CI(Σ̂1 ||Σ̂2 ) ≥ CI(Σ̃1 ||Σ̃2 ) where Σ̂i =
A∗ Σi A∗ T , Σ̃i = DΣi DT for arbitrary NO × N matrix D

1

3

7

subtr
ee1

subtr
ee2
6

5

3

Unchanged
subtree

2

subtr
ee2

Unchanged
subtree

T2

T1

1 w1

2 w2

CI(T1||T3)=CI（

CI(T1||T2)=CI（

T3

3 w3

8 w7

7 w4

1 w1

2 w2w3 4

6
8

5

4

Unchanged
subtree

Σ−1
2 =


8
7

4
subtr
ee1

6

5

3

4

2 w2

||

5 w5

6

3 w3

7 w4

||

4 w1

1

6 w7

8

）

w6

VT

V



















1 2

w6

 1 + g1



f1














8
7

4
subtr
ee1





5 w5

2 w2w3 4 w1 1

）

Fig. 6. Example for Proposition 6

and i = 1, 2. Due to equation (19), we only need to prove
D(Σ̂λ ||Σ̂2 ) ≥ D(Σ̃λ ||Σ̃2 ) and D(Σ̂λ ||Σ̂1 ) ≥ D(Σ̃λ ||Σ̃1 )
−1
−1
−1
−1
where Σ̂−1
λ = λΣ̂1 + (1 − λ)Σ̂2 and Σ̃λ = λΣ̃1 + (1 −
−1
λ)Σ̃2 .
In the following part, I will prove D(Σ̂λ ||Σ̂1 ) ≥
D(Σ̃λ ||Σ̃1 ) and the proof of D(Σ̂λ ||Σ̂2 ) ≥ D(Σ̃λ ||Σ̃2 ) is
similar.
D(Σλ ||Σ1 ) =

1X
g(νi )
2 i

(54)

1
where g(νi ) = ln (λ + (1 − λ)νi ) + λ+(1−λ)ν
− 1 and {νi }
i
are generalized eigenvalues of Σ1 and Σ2 .
g(1) = 0. g(νi ) is decreasing in (0, 1) and increasing in
(1)
(2)
(1)
(2)
(1)
(1, +∞). If ν1 ≤ ν1 ≤ ν2 ≤ ν2 ≤ · · · ≤ νN −1 ≤
(2)
(1)
(1)
(1)
(2)
νN −1 ≤ νN , we can choose µi = νi+1 for νi ≥ 1 and
(1)
(1)
(2)
(1)
µi = νi for νi < 1 so that {µi } is an (N − 1) subset
PN −1
PN −1
(1)
(1)
(2)
of {νi } and 12 i=1 g(µi ) ≥ 21 i=1 g(νi ).
(2)

(1)

If m elements of {νi } are greater than one, {µi }
contains the first k elements and last N − 1 − k elements
(1)
of {νi }.
We first introduce a preparation of proof.

A. The relationship of eigenvalues
0
 We have
 four covariance

 matrices Σ1 , Σ2 , Σ1
Σ1 m
Σ
p
and Σ02 = T2
.
mT a0
p
b0
(2)

(2)

=

(2)

The eigenvalues of Σ1 Σ−1
2 are λ1 ≤ λ2 ≤ · · · ≤ λN −1 .
(1)

(1)

(1)

The eigenvalues of Σ01 Σ0−1
are λ1 ≤ λ2 ≤ · · · ≤ λN .
2
For Σ1 and Σ2 , we can find an inverse matrix P where
(2)
(1)
(1)
(2)
(2)
Σ1 = PΣ1 PT = Diag{λ
1 , λ2 , . . . , λN −1 } and Σ2 =

P
0(1)
PΣ2 PT = I. So P0 =
satisfies Σ1 = P0 Σ01 P0T =
1
 (1)



I
b
0(1)
Σ1
a
0 0 0T
and Σ2 = P Σ2 P = T
, where a =
b
b0
aT
a0
{a1 , a2 , . . . , aN −1 }T and b = {b1 , b2 , . . . , bN −1 }T .

(1)

So {λk } are the roots of |λΣ02 − Σ01 | = 0, which is equal
to F (λ) = 0 where
0(1)

F (λ) = |λΣ2
=

0(1)

(1)

− Σ1 | =

N
−1
Y

λI − Σ1
λbT − aT

λb − a
λb0 − a0

(N −N )

(2)

(λ − λi )×

i=1

n
o
(1) −1
λb0 − a0 − (λbT − aT )(λI − Σ1 ) (λb − a)
)
(
N
−1
N
−1
Y
X
fi2 (λ)
(2)
(55)
=
(λ − λi ) × f0 (λ) −
(2)
i=1
i=1 λ − λi
0(1)

= |Σ2 |λN +

N
−1
X

ci λ i

(56)

i=0

and fi (λ) = bi λ − ai .
At first, we assume that there is no multiple eigenvalues for
(2)
(2)
{λi } and fi (λi ) 6= 0 for all 1 ≤ i ≤ N − 1.
So
(−1)

N −k

(2)

F (λk ) =(−1)

N −k+1 2 (2)
fk (λk )

N
−1
Y

(2)

(2)

(λk − λi )

i=1,i6=k

>0

The generalized eigenvalues after k dimension reduction are
(k+1)
{λi
} of size N − k.
In No. (N − NO ) dimension reduction stage, we can
(N −NO )
(N −NO )
always find
{µi
} of {λi
 an NO subset

 } so that
P
P
(N −NO )
(N −NO +1)
NO
NO
1
1
≥ 2 i=1 g λi
because
i=1 g µi
2

(57)

And F (+∞) = +∞, F (−∞) = (−1)N ∞ There is at least
(2)
(2)
one root of F (λ) = 0 in (−∞, λ1 ), (λN −1 , +∞) and
(2)
(2)
(λi , λi+1 ) for 1 ≤ i ≤ N − 2.
(1)
(2)
(1)
(2)
So we can conclude that λ1 < λ1 < λ2 < λ2 < · · · <
(1)
(2)
(1)
λN −1 < λN −1 < λN .
(2)
(2)
If λi has multiplicity ni , we can conclude that λi has
multiplicity ni − 1 in F (λ) = 0. If we put this exact multiple eigenvalues aside, other eigenvalues satisfy the ordering
before.
(2)
(2)
If fi (λi ) = 0, we can conclude that λi is also the root of
F (λ) = 0. If we put this eigenvalue aside, other eigenvalues
satisfy the ordering before.
(1)
(2)
(1)
(2)
So for all cases, λ1 ≤ λ1 ≤ λ2 ≤ λ2 ≤ · · · ≤
(1)
(2)
(1)
λN −1 ≤ λN −1 ≤ λN .
B. Main proof
For N -dimension graphs whose covariance matrices are A
and B, we can do inverse linear transformation by A0 =
KAKT and B0 = KBKT . Then we can do dimensionreduction from N to N − 1 by A00 = [IN −1 , 0]A0 [IN −1 , 0]T
and B00 = [IN −1 , 0]B0 [IN −1 , 0]T .
(1)
(1)
The generalized eigenvalues of A and B are λ1 ≤ λ2 ≤
(1)
· · · ≤ λN , which are also generalized eigenvalues of A0 and
(2)
0
B . And the generalized eigenvalues of A00 and B00 are λ1 ≤
(2)
(2)
(1)
(2)
(1)
(2)
λ2 ≤ · · · ≤ λN −1 . So λ1 ≤ λ1 ≤ λ2 ≤ λ2 ≤ · · · ≤
(1)
(2)
(1)
λN −1 ≤ λN −1 ≤ λN .
We can also do the procedure to reduce the dimension from
(2)
(3)
(2)
(3)
N − 1 to N − 2 and get λ1 ≤ λ1 ≤ λ2 ≤ λ2 ≤ · · · ≤
(2)
(3)
(2)
λN −2 ≤ λN −2 ≤ λN −1 .

(N −N +1)

(N −N )

(N −N +1)

O
O
O
O
λ1
≤ λ1
≤ λ2
≤ λ2
≤ ··· ≤
(N −NO )
(N −NO +1)
(N −NO )
λNO +1 ≤ λNO
≤ λNO +1 .
(N −NO −1)
We can always find NO subset {µi
} of
(N −NO −1)
(N −NO )
(N −NO )
{λi
} and {µi
}
of
{λ
},
which
sat
PNO
PiNO  (N −NO ) 
(N −NO −1)
1
1
≥ 2 i=1 g µi
≥
isfy 2 i=1 g µi
PNO  (N −NO +1) 
1
with the same reason.
i=1 g λi
2
With the same method, we can conclude that there
exist
PNO  (1) 
(1)
(1)
an NO subset {µi } of {λi } so that 21 i=1
g µi
≥
PNO  (N −NO +1) 
(N −NO +1)
1
. If k elements of {λi
} are
i=1 g λi
2

(1)

greater than one, {µi } contains the first k elements and last
(1)
NO − k elements

of {λi }.
P
(1)
N
O
1
is D(Σλ ||Σ1 ) with linear transformation
i=1 g µi
2
PNO  (N −NO +1) 
1
matrix Ak . 2 i=1 g λi
is D(Σ̃λ ||Σ̃1 ) under
arbitrary linear transformation where the arbitrariness is embodied in K.
So D(Σλ ||Σ1 ) ≥ D(Σ̃λ ||Σ̃1 ) holds for arbitrary D and its
corresponding Ak .
In the same way, D(Σλ ||Σ2 ) ≥ D(Σ̃λ ||Σ̃2 ) holds for
arbitrary D and its corresponding Ak .
So CI(Σ̂1 ||Σ̂2 ) ≥ CI(Σ̃1 ||Σ̃2 ) for for arbitrary D and
A∗ is the optimal matrix in the set {Ak |NO + m − N ≤ k ≤
m, k ≥ 0}.

