Submodularity of Mutual Information for Multivariate Gaussian Sources with Additive Noise
George Crowley Inaki Esnaola


§ ABSTRACT 
Sensor placement approaches in networks often involve using information-theoretic measures such as entropy and mutual information. We prove that mutual information abides by submodularity and is non-decreasing when considering the mutual information between the states of the network and a subset of k nodes subjected to additive white Gaussian noise. We prove this under the assumption that the states follow a non-degenerate multivariate Gaussian distribution.


 

[
    [
    
=====





§ INTRODUCTION


A graph is characterized by the set of nodes = {1,2, …, n} with n ∈ℕ,  where each node corresponds to a system element, and the set of edges as = {(i,j) ∈× : node i   is connected to node j }, where each edge represents a connection between nodes in the network. Jointly, the set of edges  and the set of nodes  define an undirected graph = (, ). We assume that the state of the network can be described by the vector of random variables X^n := (X_1,X_2,…,X_n)^. The observations obtained for a sensor placed at a node i ∈ are denoted as Y_i and are subject to i.i.d. additive white Gaussian noise (AWGN), denoted as formally as Z_i ∼ N(0,σ^2), with σ∈ℝ_+. Hence, the measurements obtained by the placed sensor i is given by
    
    Y_i = X_i + Z_i,    i ∈.

    
Assuming that k < n with k ∈ℕ sensors are placed in the network amongst n nodes, then the observation vector Y^k is defined as

    Y^k := (Y_i_1, …, Y_i_k)^,


where the subscript i_j denotes the j-th selected sensor. 
 
The set of linear observation matrices 
is given by





    ℋ_k := ⋃_𝒜⊆
     |𝒜| = kℋ_k(𝒜),

with

    ℋ_k(𝒜) := {∈{0,1}^k × n:  = [ _i_1^,_i_2^,,_i_k^ ]^where i_j ∈𝒜⊆ for j = 1,…,k },

where _i ∈{0,1}^n is the i-th column basis vector, i.e. 1 in the i-th position and 0 otherwise. 


Combining Definition <ref> with (<ref>) yields the following observation model:

    Y^k :=  X^n + Z^k,   for all ∈ℋ_k.


We consider the problem of finding the sensor placement 𝒜⊂ such that we seek to extremize the optimization problem

    ^*_k := _∈ℋ_k I(X^n;  X^n +  Z^k),


where I(·,·) denotes the information-theoretic measure mutual information <cit.>. Further assuming that the probability distribution of the state variables satisfies X^n ∼ N_n(, ), where ∈ℝ^n and ∈ S_++^n, then 
   
    f() := I(X^n;  X^n +  Z^k) = 12log( 1σ^2k( ^ + σ^2 _k ) ),    ∈ℋ_k,


where (·) denotes the determinant of a square matrix, and _k denotes the (k × k) identity matrix. 


Under the assumption X^n ∼ N_n(, ), where ∈ℝ^n and ∈ S_++^n, the function f() satisfies the following properties:


    
  * f() is 0 when ∈ℋ_0.
    
  * f() is submodular.
    
  * f() is non-decreasing.



Under the conditions of Theorem <ref>, when the greedy heuristic is applied to the optimization problem posed in (<ref>), the heuristic always produces a solution whose value is at least 1 - (k-1/k)^k times the optimal value, which has a limiting value of (e-1/e) <cit.>.



§ SUBMODULARITY


We begin by introducing the definitions of non-decreasing and submodular set functions.

Given a finite set Ω, a real-valued function z on the set of subsets of Ω is called submodular if 

    z(𝒜) + z(ℬ) ≥ z(𝒜∪ℬ) + z(𝒜∩ℬ),   ∀𝒜,ℬ⊆Ω.


We shall often make use of the incremental value of adding element j to the set 𝒮, let ρ_j(𝒮) = z(𝒮∪{ j}) - z(𝒮).



Each of the following statements is equivalent and defines a submodular set function. 


    
  (i) z(𝒜) + z(ℬ) ≥ z(𝒜∪ℬ) + z(𝒜∩ℬ),   ∀𝒜,ℬ⊆Ω.
    
  (ii) ρ_j(𝒮) ≥ρ_j(𝒯),   ∀𝒮⊆𝒯⊆Ω,   ∀ j ∈Ω∖𝒯.



Condition (ii) can be re-written as

    z(𝒮∪{ j}) - z(𝒮) ≥ z(𝒯∪{ j}) - z(𝒯),   ∀𝒮⊆𝒯⊆Ω,   ∀ j ∈Ω∖𝒯.


 Each of the following statements is equivalent and defines a non-decreasing submodular set function.


    
  (i') Submodularity: z(𝒜) + z(ℬ) ≥ z(𝒜∪ℬ) + z(𝒜∩ℬ),   ∀𝒜,ℬ⊆Ω.
    
   Non-decreasing: z(𝒜) ≤ z(ℬ),   ∀𝒜⊆ℬ⊆Ω.





§ PROOF OF SUBMODULARITY


To keep the notation consistent, we translate the notation used in <cit.> to ours. Set Ω = and 𝒮 := {i_𝒮_1,i_𝒮_2,…,i_𝒮_s} 

such that the cardinalty of 𝒮 = s, with 𝒮⊆Ω.

Then, we can write our cost function z(𝒮) as

    z(𝒮) = f(_𝒮) := 12log( 1σ^2s( _𝒮_𝒮^ + σ^2 _s) ),


where the observation matrix _𝒮 = [ _i_𝒮_1^,_i_𝒮_2^,,_i_𝒮_s^ ]^. We will now prove conditions (1) - (3) from Theorem <ref>.


Let ∈ℋ_0, then I(X^n;Z^k) = 0 since Z^k are i.i.d. Gaussian random variables.


Before proving condition (2), we first note some key results used throughout the proof. 



Denote the block matrix  as

    :=
        [  ;   ].


If  is invertible <cit.>, then (<ref>) holds. If  is invertible, then (<ref>) holds, where 

    () = [  ;   ]    = () ( - ^-1) 
        = ()( - ^-1).



 

Define  as in Lemma <ref>. If the inverse of  exists, <cit.>, and = ^, then
    
    ^-1 =
        [    ; ^   ]^-1 = [ ^-1    ;         ] + [ -^-1;   _γ ]( - ^^-1)^-1[ -^^-1,     _γ ].





Let ≻ 0, and let  be p × n of rank q (q ≤ p) <cit.>. Then:   

    ^≽ 0.



 
Define the matrix  as in Lemma <ref>. Further, assume that  is symmetric ( = ^) <cit.>. Then the following statement holds: 


    
  (a) ≻ 0 if and only if  () ≻ 0 and - ^-1^≻ 0.  

    



 
Suppose ≽ 0 and ≽ 0 be n × n Hermitian matrices  <cit.>.  Then the following inequality holds:  



    
  (c) ( + ) ≥() + () with equality if and only if + is singular or = or =.

    


 
Define the matrix  as in Lemma <ref>. Suppose that  is non-singular and  is also non-singular <cit.>. Define _· =  - ^-1, then

    ^-1 = [             _·^-1        - _·^-1^-1;                  ;        - ^-1_·^-1 ^-1 + ^-1_·^-1^-1 ].



For the proof, we first note that j ∉𝒯, to match notation with (<ref>), and 𝒮⊆𝒯. We further make note of the following observation matrices:
 
    _{j}    = [ _j^ ]^, 
    
            _𝒮∪{j}    = [ _i_𝒮_1^,_i_𝒮_2^,,_i_𝒮_s^, _j^ ]^.


Assue there exists a set Γ such that 𝒮∪Γ = 𝒯. Note that if 𝒮 = 𝒯, then the function is equal and hence submodular. Otherwise,   
 
    _Γ    = [ _i_Γ_1^,…, _i_Γ_γ^ ]^, 
    _𝒯 = _𝒮∪Γ    = [ _i_𝒮_1^,_i_𝒮_2^,,_i_𝒮_s^,_i_Γ_1^,…, _i_Γ_γ^ ]^
        = [ _𝒮; _Γ ], 
    _𝒯∪{j} = _𝒮∪Γ∪{j}    = [ _i_𝒮_1^,_i_𝒮_2^,,_i_𝒮_s^, _i_Γ_1^,…, _i_Γ_γ^,_j^ ]^
        = [   _𝒮;   _Γ; _{j} ].


The cardinality of each subset is denoted by: || = n,   |Γ| = γ,  |𝒯| = s + γ = t, and |{j}| = 1. 


From Proposition <ref>, we need to show (with 𝒮⊆𝒯, j ∉𝒯)
    
    12log( 1σ^2 (s + 1)( _𝒮∪{j }_𝒮∪{ j }^ + σ^2 _s+1) ) -   12log( 1σ^2s( _𝒮_𝒮^ + σ^2 _s) ) 
    ≥    12log( 1σ^2 (t + 1)( _𝒯∪{ j }_𝒯∪{ j }^ + σ^2 _t+1) ) -   12log( 1σ^2t( _𝒯_𝒯^ + σ^2 _t) ),


    which can be simplified to
        
    log( 1σ^2( _𝒮∪{ j }_𝒮∪{ j }^ + σ^2 _s+1)( _𝒮_𝒮^ + σ^2 _s)) ≥log(1σ^2( _𝒯∪{ j }_𝒯∪{ j }^ + σ^2 _t+1)( _𝒯_𝒯^ + σ^2 _t)).


         Since all determinant values are positive (confirmed by the assumption that  is positive definite) and log is a monotonic increasing function, (<ref>) becomes
         
    1σ^2( _𝒮∪{ j }_𝒮∪{ j }^ + σ^2 _s+1)( _𝒮_𝒮^ + σ^2 _s)   ≥1σ^2( _𝒯∪{ j }_𝒯∪{ j }^ + σ^2 _t+1)( _𝒯_𝒯^ + σ^2 _t)
    ( _𝒮∪{ j }_𝒮∪{ j }^ + σ^2 _s+1)( _𝒮_𝒮^ + σ^2 _s)   ≥( _𝒯∪{ j }_T ∪{ j}^ + σ^2 _t+1)( _𝒯_𝒯^ + σ^2 _t).


Before proceeding, we notice that
  
    _𝒮∪{ j }_𝒮∪{ j }^ + σ^2 _s+1 = [ _𝒮_𝒮^ + σ^2 _s        _𝒮_{j}^;               ;        _{j}_𝒮^ _{j}_{j} + σ^2 ],


    and 
     
    _𝒮∪Γ∪{ j }_𝒮∪Γ∪{ j }^ + σ^2 _s + γ +1      = [       _𝒯_𝒯^ + σ^2 _t   (_𝒯 X^n, _{j} X^n);                     ; ((_𝒯 X^n, _{j} X^n)^      _{j}_{j}^ + σ^2 ].


    The covariances can be calculated as

    (_𝒯 X^n, _{j} X^n )     = _𝒯(X^n,X^n)_{j}^
        = _𝒯_{j}^,


and its transposition is

    (_𝒯_{j}^)^ = _{j}_𝒯^.


Then, using Lemma <ref>, with = _𝒮_𝒮^ + σ^2 _s, = _{j}_{j}^ + σ^2,
 = _𝒮_{j}^, and = _{j}_𝒮^), it follows that the left-hand side of (<ref>) can be written as

    = ( _𝒮∪{ j }_𝒮∪{ j }^ + σ^2 _s+1)( _𝒮_𝒮^ + σ^2 _s)
        = ( _𝒮_𝒮^ + σ^2 _s) (_{j}_{j} + σ^2  - _{j}_𝒮^(_𝒮_𝒮^ + σ^2 _s)^-1_𝒮_{j}^) ( _𝒮_𝒮^ + σ^2 _s)
        = (_{j}_{j}^ + σ^2  - _{j}_𝒮^(_𝒮_𝒮^ + σ^2 _s)^-1_𝒮_{j}^).



Using Lemma <ref>, taking = _𝒯_𝒯^ + σ^2 _t,  = _{j}_{j}^ + σ^2,  = (_𝒯 X^n, _{j} X^n), and = ^, it follows that the right-hand side of (<ref>) can be written as

    = ( _𝒯∪{ j }_𝒯∪{ j }^ + σ^2 _t+1)( _𝒯_𝒯^ + σ^2 _t)
        = ( _𝒯_𝒯^ + σ^2 _t) ( _{j}_{j}^ + σ^2 - _{j}_𝒯^(_𝒯_𝒯^ + σ^2 _t)^-1_𝒯_{j}^)( _𝒯_𝒯^ + σ^2 _t)
        = ( _{j}_{j}^ + σ^2 - _{j}_𝒯^(_𝒯_𝒯^ + σ^2 _t)^-1_𝒯_{j}^).


Since is (n × n),  _{j} is (1 × n),  _𝒮 is (s × n),  _𝒯 is (t × n), and hence _{j}_𝒮^ is (1 × s), it follows that the resulting matrices inside the determinants of both (<ref>) and (<ref>) are scalars. Since the determinant of a scalar is just the scalar itself, this observation shows us that we can rewrite (<ref>) as

    -    _{j}_𝒮^(_{j}_𝒮^ + σ^2 _s)^-1_𝒮_{j}^≥ - _{j}_𝒯^(_𝒯_𝒯^ + σ^2 _t)^-1_𝒯_{j}^
       _{j}_𝒮^(_{j}_𝒮^ + σ^2 _s)^-1_𝒮_{j}^≤_{j}_𝒯^(_𝒯_𝒯^ + σ^2 _t)^-1_𝒯_{j}^
       _{j}_𝒯^(_𝒯_𝒯^ + σ^2 _t)^-1_𝒯_{j}^ - _{j}_𝒮^(_{j}_𝒮^ + σ^2 _s)^-1_𝒮_{j}^≥ 0 
       _{j}( _𝒯^(_𝒯_𝒯^ + σ^2 _t)^-1_𝒯 -  _𝒮^(_{j}_𝒮^ + σ^2 _s)^-1_𝒮) _{j}^≥ 0.
 

Using (<ref>) and (<ref>) yields

    _{j}(  [ _𝒮^,  _Γ^ ](_𝒯_𝒯^ + σ^2 _t)^-1[ _𝒮; _Γ ]    -  _𝒮^(_𝒮_𝒮^ + σ^2 _s)^-1_𝒮) _{j}^≥ 0.


Observe that we can further manipulate the inequality in (<ref>) to obtain

    _{j}[  [ _𝒮^,  _Γ^ ](_𝒯_𝒯^ + σ^2 _t)^-1[ _𝒮; _Γ ]    -  [ _𝒮^,  _Γ^ ][ (_𝒮_𝒮^ + σ^2 _s)^-1                    ;                                    0*_γ ][ _𝒮; _Γ ]] _{j}^≥ 0.


It then follows after using (<ref>) that 

    _{j}_𝒯^[ (_𝒯_𝒯^ + σ^2 _t)^-1    -  [ (_𝒮_𝒮^ + σ^2 _s)^-1                    ;                   ^                0*_γ ]] _𝒯_{j}^≥ 0.


The inequality holds if the matrix inside is positive semi-definite, i.e.

    ( ( _𝒯_𝒯^ + σ^2 _t)^-1    -  [ ( _𝒮_𝒮^ + σ^2 _s)^-1                     ;                    ^                 0*_γ ]) ≽ 0.


The block form of _𝒯_𝒯^ + σ^2 _t can be expressed as

    _𝒮∪Γ_𝒮∪Γ^ + σ^2 _s + γ    = [        _𝒮_𝒮^ + σ^2 _s      (_𝒮 X^n, _Γ X^n)                      ;                      ; ( (_𝒮 X^n, _Γ X^n) )^        _Γ_Γ^ + σ^2 _γ ] = [    ;  ; ^   ].


Using Lemma <ref>, with = _𝒮_𝒮^ + σ^2 _s,  and  as indicated from (<ref>), it follows that 

    ( _S ∪Γ_𝒮∪Γ^ + σ^2 _s + γ)^-1 = [ ^-1    ;         ] + [ -^-1;   _γ ]( - ^^-1)^-1[ -^^-1,     _γ ].


Inserting equation (<ref>) into (<ref>) yields the condition

    [ -^-1;   _γ ]( - ^^-1)^-1[ -^^-1,     _γ ]≽ 0.


Observe that = _𝒮_𝒮^ + σ^2 _s is symmetric and positive definite, then it follows that ^-1 is also symmetric and positive definite (i.e. ≻ 0, and (^-1)^ = ^-1). Then it follows that

    [ -^-1;   _γ ]^ = [ (-^-1)^,       _γ ] = [ -^^-1,     _γ ].


By setting

    := [ -^-1;   _γ ],


and using Lemma 3, it follows that the inequality in (<ref>) can be written as

    ( - ^^-1)^-1^≽ 0 ( - ^^-1)^-1≻ 0  - ^^-1≻ 0.


Moreover, by setting := _𝒮∪Γ_𝒮∪Γ^ + σ^2 _s + γ as in (<ref>), which is positive definite, by Lemma <ref>, it follows that  is positive definite if and only if ≻ 0 and - ^^-1≻ 0. But - ^^-1≻ 0 is the inequality in (<ref>), and so the result follows.





Using the same notation as before, the non-decreasing property states

    z(𝒮) ≤ z(𝒯),   ∀𝒮⊆𝒯⊆.


In our formulation, the non-decreasing property yields as 

    12log( 1σ^2s( _𝒮_𝒮^ + σ^2 _s) ) ≤12log( 1σ^2t( _𝒯_𝒯^ + σ^2 _t) ).


First, let us assume that 𝒮 = 𝒯, then the equality holds trivially. Hence, we assume that 𝒯 =𝒮∪Γ, then using the monotonicity of the logarithm, it follows that

    1σ^2s( _𝒮_𝒮^ + σ^2 _s) ≤1σ^2t( _𝒯_𝒯^ + σ^2 _t).


We set the block matrix  as

    = _𝒯_𝒯^ + σ^2 _t    = [        _𝒮_𝒮^ + σ^2 _s      (_𝒮 X^n, _Γ X^n);                      ; ( (_𝒮 X^n, _Γ X^n) )^        _Γ_Γ^ + σ^2 _γ ] = [  ;   ],


then, by Lemma <ref>, it follows that

    ()     = () ( - ^-1) 
        = (_𝒮_𝒮^ + σ^2 _s) ( - ^-1).


Using (<ref>) in (<ref>) yields

    1σ^2s( _𝒮_𝒮^ + σ^2 _s) ≤1σ^2t(_𝒮_𝒮^ + σ^2 _s) ( - ^-1).


Since _𝒮_𝒮^ + σ^2 _s≻ 0 ( _𝒮_𝒮^ + σ^2 _s) > 0, we can divide this term out of (<ref>) such that

    1σ^2s≤1σ^2t( - ^-1),


and hence, using t = s + γ and fully expanding all the terms, (<ref>) can be written as 

    ( _Γ_Γ^ + σ^2 _γ - ( (_𝒮 X^n, _Γ X^n) )^( _𝒮_𝒮^ + σ^2 _s)^-1(_𝒮 X^n, _Γ X^n) ) ≥σ^2γ.


Set = σ^2 _γ and = _Γ_Γ^ - ( (_𝒮 X^n, _Γ X^n) )^( _𝒮_𝒮^ + σ^2 _s)^-1(_𝒮 X^n, _Γ X^n). We omit temporarily showing that ≽ 0, but will invoke Lemma <ref> on (<ref>) which yields the inequality

    (+) ≥() + () ≥σ^2γ.


Since = σ^2 _γ, we have () = σ^2γ. Then

    (+) ≥σ^2γ + () ≥σ^2γ() ≥ 0 ≽ 0.


We will now proceed by showing that  is semi-positive definite. We can write the joint random vector of _Γ X^n and _𝒮 X^n + Z^s as

    [       _Γ X^n; _𝒮 X^n + Z^s ]   ∼ N( [ _Γ[X^n]; _𝒮[X^n] ], [             (_Γ X^n,_Γ X^n)       (_Γ X^n,_𝒮 X^n + Z^s);       (_𝒮 X^n + Z^s,_Γ X^n) (_𝒮 X^n + Z^s,_𝒮 X^n + Z^s) ]) 
       ∼ N( [ _Γ[X^n]; _𝒮[X^n] ], [          _Γ_Γ^          _Γ_𝒮^;          _𝒮_Γ^ _𝒮_𝒮^ + σ^2 _s ]).


Observe that the covariance matrix in (<ref>) is positive definite, since

    [          _Γ_Γ^          _Γ_𝒮^;          _𝒮_Γ^ _𝒮_𝒮^ + σ^2 _s ] = [ _Γ_Γ^ _Γ_𝒮^; _𝒮_Γ^ _𝒮_𝒮^ ] + [   _γ×γ       ;      ^ σ^2 _s ],


and the first matrix is a principle submatrix of , which is positive definite by assumption. Hence, the inverse of the covariance matrix in (<ref>) exists, which is also positive definite. By Lemma <ref>, it then follows that

    [          _Γ_Γ^          _Γ_𝒮^;          _𝒮_Γ^ _𝒮_𝒮^ + σ^2 _s ]^-1 = [ (_Γ_Γ^ - _Γ_𝒮^(_𝒮_𝒮^ + σ^2 _s)^-1_𝒮_Γ^)^-1                                          …;                                           ;                                          …                                          … ].


Since the covariance matrix is positive definite, Lemma <ref> implies that 

    (_Γ_Γ^ - _Γ_𝒮^(_𝒮_𝒮^ + σ^2 _s)^-1_𝒮_Γ^)^-1   ≻ 0 
    _Γ_Γ^ - _Γ_𝒮^(_𝒮_𝒮^ + σ^2 _s)^-1_𝒮_Γ^   ≻ 0.


But the matrix in (<ref>) is , since ( (_𝒮 X^n, _Γ X^n) )^ = (_𝒮_Γ^)^ = _Γ_𝒮^, and hence the result follows.   



[]
