On the Expected Value of the Determinant of Random Sum of Rank-One Matrices
Kasra Khosoussi

Gain and loss  in open quantum systems
    
Hichem Eleuch^1[email: hichemeleuch@tamu.edu] and 
Ingrid Rotter^2[email: rotter@pks.mpg.de, corresponding author]
    December 30, 2023
=======================================================================================================================



  We present a simple, yet useful result about the expected value of the determinant
  of random sum of rank-one matrices. Computing such expectations in general
  may involve a sum over exponentially many terms. Nevertheless, we show that an
  interesting and useful class of such expectations that arise in, e.g.,
  D-optimal estimation and random graphs can be computed efficiently via
  computing a single determinant.



§ PROBLEM DEFINITION


  
  * [n] ≜{1,2,…,n}, and for any finite set 𝒲,
	𝒲k is the set of k-subsets of 𝒲.
  
  * Suppose we are given a pair of m real n-vectors,
	{_i}_i=1^m and {_i}_i=1^m. Define,



	
    ≜[
    		_1   _2   ⋯  _m
    	  ]     ≜[
    		_1   _2   ⋯  _m
    	  ]

  
  * Let {π_i}_i=1^m be m independent Bernoulli random
	variables distributed as,
	
    π_i    ∼(p_i)     i ∈ [m]
    π_i    ⊥π_j             i,j∈[m], i≠ j

	where {p_i}_i=1^m are given. Define ≜ [p_1    p_2
	  ⋯   p_m]^⊤ and π≜ 
	  [π_1  π_2  ⋯ π_m]^⊤.


  
  * We are interested in computing the expression below,
	
    e(,,)    ≜_π [(∑_i=1^mπ_i _i_i^⊤)] 
       = 
    	  _π [(Π^⊤)]

	where Π≜(π_1,π_2,…,π_m). 
	Note that the naive way of computing this expectation leads to a
	computationally	intractable sum over
	{0,1}^m.


§ MAIN RESULT


	
    e(,,)     = (∑_i=1^m p_i _i_i^⊤) 
       = 
    	  (^⊤),

	where ≜(p_1,p_2,…,p_m).
	  
	
 The proof outline is as follows:
  
	
  Step 1. First, the Cauchy-Binet formula is used to expand the determinant
	  as a sum over mn terms.
	
  Step 2. The expected value of each of the mn terms can be easily computed. 
	
  Step 3. Finally, the Cauchy-Binet formula
	  is applied again to shrink the sum.
  
  We begin by applying the Cauchy-Binet formula:

    _π [(∑_i=1^mπ_i _i_i^⊤)]
         =
      _π [∑_𝒬∈[m]n(∑_k ∈𝒬π_k _k_k^⊤)] 
       =
      ∑_𝒬∈[m]n_π [(∑_k ∈𝒬π_k _k_k^⊤)].

Since |𝒬| = n,  we will have (∑_k ∈𝒬π_k _k_k^⊤) < n if there exists k ∈𝒬 for which π_k = 0.








  Hence, the determinant can be non-zero only when 
  π_k = 1 for all k ∈𝒬. Therefore,

    (∑_k ∈𝒬π_k _k_k^⊤) = 
    	(∑_k ∈𝒬_k_k^⊤)      iff π_k = 1 for all k ∈𝒬,
    
    	0    otherwise.

  But from the independence assumption we know that,

    ℙ [⋀_k ∈𝒬π_k = 1] =
      ∏_k ∈𝒬 p_k.

Each individual expectation in (<ref>) can be computed as follows.

    _π [(∑_k ∈𝒬π_k _k_k^⊤)] 
          =  (∑_k ∈𝒬_k_k^⊤) 
       ∏_k ∈𝒬 p_k 
        = 
      (∑_k ∈𝒬 p_k _k_k^⊤).

Plugging (<ref>) back into (<ref>) yields,

    _π [(∑_i=1^mπ_i _i_i^⊤)]
         = 
      ∑_𝒬∈[m]n(∑_k ∈𝒬 p_k _k_k^⊤).

Note that (<ref>) is
nothing but the Cauchy-Binet expansion of (∑_i=1^m p_i _i_i^⊤). This concludes the proof.










§ MOTIVATION & APPLICATIONS

e(,,) arises in the following problems:

  
  * Estimation
	

	Suppose ∈^n is an unknown quantity to be estimated
	using m observations {z_i}_i=1^m (m ≥ n) generated according to,
	
    𝐳 = 𝐇𝐱 + ϵ  where  ϵ∼𝒩(0,Σ)

	where 𝐳≜ [z_1    z_2   ⋯   z_m]^⊤.



	To simplify our notation, let us define  ≜Σ^-1/2. The maximum likelihood estimator  has the
	following form:
	
    = (^⊤)^-1^⊤𝐳.

	It is well known that  is unbiased and efficient; i.e., it
	achieves the Cramé-Rao lower bound,
	
    [] = (^⊤)^-1.

	
	Geometrically speaking, the hypervolume of uncertainty hyperellipsoids are
	proportional to √( []) (see, e.g.,
	<cit.>).
	The D-optimality (determinant-optimality) criterion is
	defined as []^-1. 
	Note that [] = ( ℱ)^-1
	where ℱ≜^⊤ is the so-called Fisher
	information matrix. Hence, minimizing the determinant of the estimation
	error covariance matrix is
	equivalent to maximizing the D-optimality criterion, (^⊤).
	Now consider the following scenarios.
	
	  
  * Sensor Failure: The ith “sensor” may “fail”
		independently with probability 1-p_i, for all i ∈ [m]. In this case, the
		row corresponding to each failed sensor has to be removed from
		.
		Hence, e(^⊤,,) gives the expected
		value of the D-optimality criterion.
  
  * Sensor Selection: 
	The goal in D-optimal sensor selection is to select a subset (e.g.,
	k-subset) of m available sensors (observations) such that the
	D-optimality criterion is maximized. 
	Joshi and Boyd <cit.> proposed an approximate solution to
	this problem through convex relaxation. In <cit.>, we showed
	that their convex program can be interpreted as the problem of finding the optimal
	probabilities {p_i}_i=1^m for randomly selecting (e.g., k) sensors
	via independent coin tosses such that the expected value of the D-optimality
	criterion,
	i.e., e(^⊤,,), is maximized. See
	<cit.> for the details.
	
	 For sufficiently smooth nonlinear measurement models,  should be
	  replaced by the normalized Jacobian of the measurement function.



	









	
	
  * Spanning Trees in Random Graphs[We first presented Theorem <ref>, and its special case used
for computing the weighted number of spanning trees, in
<cit.>. Recently
we discovered an earlier result for computing the expected number of spanning
trees in unweighted anisotropic random graphs by Joel E. Cohen in 1986
<cit.>. Cohen in <cit.> provides a
different proof and extends his result to the case of random directed graphs.
Our result, however, considers the weighted graphs, while our Theorem <ref>
extends it to the general case of random sum of arbitrary rank-one matrices.]
	
	

	Networks with “reliable” (against, e.g., noise in estimation, or failure
	in communication) topologies are crucial in many applications across science
	and engineering. In general, the notion of reliability in networks is
	closely related to graph connectivity.  Among the existing combinatorial and
	spectral graph connectivity criteria, the number of spanning trees
	(sometimes referred to
	as graph complexity or tree-connectivity) stands out: despite
	its combinatorial origin, it can also be characterized solely by the
	spectrum of the graph Laplacian (Kirchhoff) matrix. This result is due to
	Kirchhoff's matrix-tree theorem (and its extensions):
	
	
	  Consider graph = (,,w) where =
	  {v_i}_i=0^n,
	  ⊆2, and w : →_>0.
	  The reduced Laplacian matrix of , denoted by _, is
	  obtained by removing an arbitrary row and the corresponding column from
	  the (weighted) Laplacian matrix of ; e.g., v_0.
	  The weighted number of spanning is given by,
	  
    t_w()    ≜∑_𝒯∈𝕋()∏_e ∈(𝒯) w(e) 
        =  (_)

	  where 𝕋() is the set of all spanning trees of , and
	  (𝒯) denotes the edge set of graph 𝒯. 
	  Note that in case of unit weights, t_w() is simply the number of
	  spanning trees in .
	  
	
	
	Now consider a random graph whose ith edge is “operational” with
	probability p_i, independent of other edges
	(Figure <ref>).[Here, “operational” means that the
	corresponding vertices are connected via an edge.]
	Define indicator variables {π_i}_i=1^m such that π_i = 1 iff
	the ith edge is operational, otherwise π_i = 0.
	The reduced (unweighted) incidence matrix of , =
	[_1  _2  ⋯ _m], is
	obtained by removing an arbitrary row from the (unweighted) incidence matrix
	of . From Theorem <ref> we know that,
	
    _π [ t_w(_π) ] = 
    	  _π [ ( ∑_i=1^mπ_i w(e_i) _i_i^⊤) ].

	Define _w ≜√(𝐖) in which 𝐖≜(w(e_1)   w(e_2)  ⋯  w(e_m)). Note that
	this expression is equal to e(_w,_w^⊤,). From
	Theorem <ref> we have,
	
    _π [ t_w(_π) ]    = 
    	  _π [ ( ∑_i=1^mπ_i w(e_i) _i_i^⊤) ] 
       = e(_w,_w^⊤,) 
        = 
    	  ( ∑_i=1^m p_i w(e_i) _i_i^⊤) 
        = ∑_𝒯∈𝕋()∏_e_i ∈(𝒯) p_i w(e_i).

	
	
	  It is worth mentioning that, according to above equations, the expected
	  weighted number of spanning trees is given by computing the weighted number
	  of spanning trees after multiplying the edge weights by their probabilities;
	  i.e.,
	  
    _π [ t_w(_π) ]    = t_w_p(),

	  where w_p : e_i ↦ p_i w(e_i).
	




















































































§ RANDOM SUM OF RANK-R MATRICES

It is not immediately clear whether there is an efficient way for computing

    _π [(∑_i=1^mπ_i _i_i^⊤)]

in which _i and _i belong to ^n × r_i for i ∈ [m].
Nevertheless, the following results provide some preliminary insights into this
more general case.
The proofs of the following lemmas follow that of Theorem <ref>—i.e.,
Cauchy-Binet formula.

  
    _π [(∑_i=1^mπ_i _i_i^⊤)]    ≥(∑_i=1^m p_i _i_i^⊤).



 Consider a random graph _π (over graph ) whose edge set  is
 partitioned into k blocks {_i}_i=1^k. The edges in the ith
 block are operational, independent of other blocks, with probability p_i.
 Let _i be the collection of the columns of the reduced weighted 
 incidence matrix that belong to the ith block of edges _i. We have,
	
    _π [ t_w(_π) ]    = 
    	  _π [ ( ∑_i=1^mπ_i  _i_i^⊤) ] 
        = ∑_𝒯∈𝕋()∏_e_i ∈(𝒯) p_b_i^1/n_b_i(𝒯) w(e_i)

	where b_i is the block index that contains e_i  
	and n_i(𝒯) ≜ |(𝒯)
	∩_i|.
  
 




















































































../wafr16/paper/splncs_srt

