# A Modified Decomposition Covariance Matrix Estimation for Undirected Gaussian Graphical Model

DOI : 10.17577/IJERTV3IS060820

Text Only Version

#### A Modified Decomposition Covariance Matrix Estimation for Undirected Gaussian Graphical Model

Ridawarni P., Yenny Hermiana A., Saprilina G.

Graduate School of Mathematics, University of Sumatera Utara Medan, Indonesia

Abstract – A covariance matrix is an undirected graph that associated with a multivariate probability of a given random vector where each vertex represents the different components of the random vector. Graphical model are framework for representing and conditional independence structures with distribution using graph G. This paper discussed a distribution estimation in determining decomposable covariance matrix in an undirected Gauss graphical model related to sparsity of invers covariance (concentration matrix). It showed decomposable covariance estimation with lower computational complexity. The result showed the correlation each different components in a given random vector that determined from decomposition covariance matrix estimation.

Keywords – conditional independence, covariance decomposition, Gauss graphical model, concentration graph

1. INTRODUCTION

Graphical models are a framework in determine a conditional independence structures within distributions that represented by a graph. In representing a distribution, undirected graph is used as a common model to describe a distribution problem in high dimension. Some previous researches that related to undirected graph model has been successfully applied to determine a conditional independence structures within a multivariate distribution and computation techniques that implemented using a graph for complexity enhancement problem of a high dimension data [1].

Covariance is an estimation of the two certain variables, x

and y, in n sizes of data sample. This estimation is used to

sequence of the variables and estimation that based on estimator, permutation of invariance to each available variable index. Some researches of undirected graphical model was studied and developed to determine a conditional independence structure in a multivariate distribution, and extended with a computation method using a representation by a graph, especially for dimension enhancement and complexity problem. The results showed a sum of weighted path of all available paths that connected the two variables in an undirected independence graph [11].

An estimation of decomposition covariance matrix is the main focus topic in this paper. The estimation is focused on an undirected Gaussian graphical model of two random variables that gives correlation of each vertex on a Gaussian graph as a result.

2. REVIEWS

The Gaussian distribution is also referred to as the normal distribution or the bell curve distribution for its bell-shaped density curve. The formula for a d-dimension Gaussian probability distribution is

1 (x )T 1(x )

(2 )d /2 | |1/2 2

p(x) exp (2.1)

where x is a d-element column vector of variables along each dimension, is the mean vector, calculated by

determine a variance and linear correlation of a multivariate or multi-dimension data. Estimation of covariance in a Gaussian distribution is basically a common problem in statistical signal processing such as speech recognition [2], [3], image processing [4], [5], sensor networks [6], computer networks

[7] and other fields that related to statistical graphical models. Efficient Bayesian inference in Gaussian graphical models is well established [8] [10].

A conditional independence among some random variables that distributed to some estimated covariance inverse. Estimation of covariance in a high dimension data can be classified to two categories: estimation that based on the

E[x] x(x) dx

and is the d d covariance matrix, calculated by

E[(x )(x T )] (x )(x T ) p(x) dx

with the following form

(2.2)

(2.3)

11

21

1d

2d

(2.4)

E {(i1, j1),, (i|| , j|| )} , where each node is connected to itself, i.e., (i,i) E for all i V . Let x [x ,, x ]T be a

1 p

d1

dd

zero random vector of length

p | V |

whose elements are

The covariance matrix is always symmetric and positive semidefinite, where positive semidefinite means that for all

indexed by the nodes in V. The vector x satisfies the Markov property with respect to G, if for any pair of nonadjacent nodes the corresponding pair of elements in x are

non-zero

x Rd , xT x 0 . We normally only deal with

conditionally independent of the remaining elements, i.e., xi

covariance matrices that are positive definite where for all

and x j are conditionally independent of xr

for any

non-zero x Rd , xT x 0 , such the determinant | | will

{i, j} E

and r {V \ i, j} where

be strictly positive. The diagonal elements,

ii

are the

variances of the respective

x , i.e., 2 , and the off-diagonal

p(x , x

| x ) p(x | x ) p(x

| x )

(2.10)

i i i j r i r j r

elements,

ij , are the covariances of xi

and

x j . If the

variables along each dimension is statistically independent, then ij 0 , and we would have a diagonal covariance

Therefore, the joint distribution satisfies the following factorization:

matrix

2 0 0

p(xi , x j , xr )

p(xi , xr ) p(x j , xr )

p(xr )

(2.11)

1

2

0 2 0

(2.5)

In the Gaussian setting, this factorization leads to sparsity in

the concentration (inverse covariance) matrix. The multivariate Gaussian distribution is defined as

2

0 0 d

p(x; K) c | K |1/2 e1/2xT Kx

(2.12)

If the covariances along each dimension is the same, then we will have an identify matrix multiplied by a scalar,

where c in an appropriate constant and the marginal

2 I

by the Eq. (2.6), the determinant of becomes

(2.6)

concentration matrix is

Kr ([K 1]r,r )1

(2.13)

| | 2d

and the inverse of becomes

(2.7)

Together with Eq. (2.11) this implies that

Kr ([K 1]r,r )1; K [Kir ]0 [K jr ]0 [Kr ]0

(2.14)

0

1

2

| K | | Kir || K jr |

| Kr |

(2.15)

1

(2.8)

where K ,

K and

K are the marginal concentrations of

ir

jr r

1

{x , x },{x , x } and {x } , respectively, and are defined in a

0 2

i r j r r

For 2-d Gaussian where d = 2, formulation becomes

x [x1

x2 ]T , | | 4 , the

similar manner to Eq. (2.13). All the matrices in the right hand side of Eq. (2.14) have a zero value in the {i, j} th position, and therefore

[K ]i, j 0 for all {i, j} E

1 x2 x2

p(x1, x2 )

exp 1 2

(2.9)

2 2

2 2

This property is the core of Gaussian graphical models: the

then we often denote a Gaussian distribution of Eq. (2.1) as

p(x) N(, ) .

An undirected graph G (V , E) is a set of nodes

V {1,,| V |} connected by undirected edges

concentration matrix K has a sparsity pattern which represents the topology of the conditional independence graph.

Decomposable models are a special type of graphicl model in which the conditional independence graphs satisfy an appealing structure. A decomposable graph can be divided

into an ordered sequence of fully connected subgraphs known as cliques and denoted by C1,,Ck

=1

3. DECOMPOSITION COVARIANCE MATRIX

where = as a result of sum and multiple matrix. Thus, the likelihood equation of Gaussian matrix can be formulated as

E W n w

(3.4)

In our estimation, we use some notations in determine covariance matrix in Gaussian graphical model. Assume

2 2 2

K 1 w

(3.5)

V

X X

p

where

Vp {1,, p}

is a random vector with n

normal multivariate distribution with p-dimension,

log L(K ) n log(det K ) tr(Kw)

(3.6)

N p (0, K 1) . Set a graph G (Vp , E) where for each vertex 2 2

i V is pair to a variable

Xi and

E Vp Vp which is an

log(det K ) wij

(3.7)

undirected graph. Set the definition that (i, j) E if and only if ( j,i) E . A Gaussian graphical model with conditional independence graph is determined with the limit of diagonal

kij

kij

n

log(det K ) K 1

(3.8)

elements of K that not pair to any edge in G. If (i, h) E ,

then

Xi and X j

is conditionally independence of a given

random variables. Concentration matrix

K (Kij )1i, j p is a

4. DECOMPOSITION COVARIANCE MATRIX FOR

limit to a symmetric positive definite matrix with diagonal

UNDIRECTED GAUSSIAN GRAPH

entry Kij 0 for all (i, j) E . Using G-Wishart distribution,

Adopted by a basic structure of variance component and

WisG ( , D) with density

, , = 1

det (2)/2 exp{ 1

} (3.1)

time series problem, we suggest definition of linear covariance formula model that represented as

,

2 ,

a1U1 aqUq

(4.1)

based on Lebesgue estimation (see [12]; [13]; [14]). If G is a complete graph E (Vp Vp ) , then WisG ( , D) is a G- Wishart distribution WisG ( , D) . We then using Cholesky

are symmetric matrices and is an unknown parameter that supposed to be a requirement so that the matrix is positive definite. Eq. (4.1) represents a common formula of

decomposition for matrix K with

K PG is

K PG where

time-series covariance model, mixed-linear and graph model.

=

1

and =

1

is an upper triangle

Specifically, high dimension q for any covariance matrix can be denoted as

where 1 = is the decomposition Cholesky of 1.

Estimation of covariance matrix is a basic problem of multivariate statistical that related to signal processing,

p q

(ij ) ijUij

i1 j 1

(4.2)

financial mathematics, pattern recognition and convex geometry computation. Set a sample of n points that independent, 1, , , from distribution. We then have a sample of covariance matrix

with is matrix with dimension Ã— with element 1 at

, and 0 otherwise. For each column and row, we can set variance matrix with these following steps.

n

Step 1. Set matrix X as a deviation for x where =

n

1 T 1 T 1

n Xk X k i1

A A n

(3.1)

11 .

Step 2. Calculate as a result of sum and multiple matrix

with is a random matrix. Then we estimated the covariance matrix with rate of accurancy, = 0.01 that represented by a norm operation as follows.

with dimension Ã— at matrix x.

Step 3. Each element of matrix x is divided by n. Thus, we determined variance-covariance matrix of matrix x,

' 1

n (3.2)

Assume = (1 , 2, , ) of a multivariate Gaussian distribution (0, ) where is a regular matrix. Then we determined likelihood function

(det K )n/ 2 etr (Kw)

L(K ) (3.3)

2

= , where

1 : column vector with element 1 of dimension Ã— 1

x : deviation matrix of dimension Ã—

X : data matrix of dimension Ã—

V : covariance matrix of dimension Ã—

: result of sum and multiple matrix

n : number of trial of matrix X

Thus, we then determined a decomposition covariance matrix that showed correlation partial of the two random variables by

B. Matrix m Ã— n

Assume that there exist matrix

ij

kij kii k jj

(4.3)

4.0 2.0 0.60

4.2 2.1 0.59

A. Matrix m Ã— m

5. RESULTS

A53 3.9 2.0 0.58

4.3 2.1 0.62

4.1 2.2 0.63

For illustration, we use a given matrix data of dimension

Ã— . Assume that there exist matrix 3Ã—3 as follows.

which the covariance matrix of matrix A is determined by the definition = 11. Thus,

 1 4 1 3Ã—3 = 2 1 4 3 3 1

0.1 0.08 0.004

0.1 0.02 0.014

cov( A) 0.2 0.08 0.024

Then, covariance matrix of matrix A is determined by the definition = 11. Thus,

0.2 0.02 0.016

0.0 0.12 0.026

5 4 cov( A) 4 7

5

2

Because = 5, for each element of covariance matrix we

have

3 5 5

0.1

0.08

0.004

Because = 3, for each element of covariance matrix we

have

0.1 0.02 0.014

1

cov( A) 0.2 0.08 0.024 5

5 4

5 1.667

1.333

1.667

0.2 0.02 0.016

1

cov( A) 4 7

2 1.333

2.333

0.667

0.0 0.12 0.026

3

3 5 5 1.000 1.667 1.667

0.02 0.006 0.0014

with the decomposition of inverse matrix is

0.006 0.0056 0.0011

0.0014 0.0011 0.0003

1.172 0.234 1.266

0.656 0.469 0.469

with the decomposition of inverse matrix is

inv( A)

0.047 0.609 0.890

76.1 55.3 136.2

inv( A) 20.8 492.8 1322.1

and for each correlation of the two random variables, we determined

136.2 1322.1 7612.2

and for each correlation of the two random variables, we

0.2344

0.2344

determined

12 3 = 1.1719 0.4688 = 0.7412 = 0.3162

55.3

55.3

0.0469

13 3 = =

1.1719 0.8906

0.0469

= 0.0459

1.0216

12 3 = 76.1 492.8 = 193.65 = 0.285

55.3 55.3

0.4788

0.4688

13 3 = 7612.2 = 761.109 = 0.072

23 3 = 0.4688 0.8906 = 0.6461 = 0.7255

1322.1

1322.1

23 3 = 492.8 7612.2 = 1936.825 = 0.682

6. CONCLUSIONS

In this paper, we studied the decomposition of covariance for undirected Gaussian graph. Estimation of covariance in a Gaussian distribution is a common problem in statistic. Gaussian graphical model is a method that can be used to represent the structure are independent among different independence random variables in a graph. This paper has examined the results of the covariance estimation for undirected Gaussian by using a likelihood function in order to obtain the concentration of each random variables. The results of the decomposition matrix is decomposed and can be used in solving problems that related to signal transmission, patter recognition and other concentrations matrix problem.

REFERENCES

1. Dobra, A., Hans, C., Jones, B. Nevins, J.R., Yao, G. and West, M. Sparse graphical models for exploring gene expression data, Journal of Multivariate Analysis, special issue on Multivariate Methods in Genomic Data Analysis, Vol. 90 (2004), pp. 196-212.

2. Bilmes, J.A. Factored sparse inverse covariance matrices. In Proc. IEEE Int. Conf. Acoust. Speech Signal Process (ICASSP). (2000), pp. 1009-1012.

3. Bilmes, J.A., and Bartels, C. Graphical model architectures for speech recognition. IEEE Signal Processing Mag., Vol. 22 (2005), pp. 89-100.

4. Willsky, A. Multiresolution Markov models for signal and image processing. Proc. IEEE, Vol. 90 (2002), pp. 1396-1458.

5. Choi, M.J., and Willsky, A. Multiscale Gaussian graphical models and algorithms for large-scale inference. In Proc. IEEE 14-th Work-Shop Statistical Signal Process (SSP). (2007), pp. 229-233.

6. Cetin, M., Chen, L., Fisher, W., Ihler, A.T., Moses, R.L., Wainwright, M.J., and Willsky, A.S. Distributed fusion in sensor networks: A graphical models perspective. IEEE Signal Process Mag., Vol. 23 (2006), pp. 42-55.

7. Wiesel, A. and Hero, A.O. Decomposable principal component analysis. IEEE Trans. Signal Process, Vol. 59 (2009), pp. 4369-4377.

8. Sudderth, E.B., Wainwright, M.J. and Willsky, A.S. Embedded trees: estimation of Gaussian processes on graphs with cycles, Vol. 52 (2004), pp. 3136-3150.

9. Malioutov, D.M., Johnson, J.K., and Willsky, A.S. Walk-sums and belief propagation in Gaussian graphical models. J. Mach. Learn., Res., Vol. 7 (2006), pp. 2031-2064.

10. Chandrasekaran, V., Johnson, J.,K. and Willsky, A.S. Estimation in Gaussian graphical models using tractable subgraphs: A-walk sum analysis. IEEE Trans. Signal Process, Vol., 56 (2008), pp. 1916-1930.

11. Wiesel, A. and Hero III, A.O. Distributed covariance estimation in Gaussian graphical models., IEEE Trans. On Signal Processing, Vol. 60 (2012), pp. 211-220.

12. Roverato, A. Hyper inverse Wishart distribution for nondecomposable graphs and its applications to Bayesian inference for Gaussian graphical models, Scandinavian Journal of Statistics, Vol. 29 (2002), pp.391-411.

13. Atay-Kayis, A. and Massam, H. A Monte Carlo method for computing the marginal likelihood in nondecomposable Gaussian graphical models, Biometrica, Vol. 92 (2005), pp. 317-335.

14. Letac, G. and Massam, H. Wishart distributions for decomposable graphs, The Annals of Statistics, Vol. 35 (2007), pp. 1278-1323.