Semidefinite tests for latent causal structures
Aditya Kela,1 Kai von Prillwitz,2 Johan Åberg,1, ∗ Rafael Chaves,3 and David Gross1, 4
1 Institute

for Theoretical Physics, University of Cologne, 50937 Cologne, Germany
for Chemistry and Biology of the Marine Environment,
University of Oldenburg, 26111 Oldenburg, Germany
3 International Institute of Physics, Federal University of Rio Grande do Norte, 59070-405 Natal, Brazil
4 Centre for Engineered Quantum Systems, School of Physics,
The University of Sydney, Sydney, NSW 2006, Australia
(Dated: January 4, 2017)

arXiv:1701.00652v1 [stat.ML] 3 Jan 2017

2 Institute

Testing whether a probability distribution is compatible with a given Bayesian network is a fundamental task in the field of causal inference, where Bayesian networks model causal relations. Here we
consider the class of causal structures where all correlations between observed quantities are solely
due to the influence from latent variables. We show that each model of this type imposes a certain
signature on the observable covariance matrix in terms of a particular decomposition into positive
semidefinite components. This signature, and thus the underlying hypothetical latent structure, can
be tested in a computationally efficient manner via semidefinite programming. This stands in stark
contrast with the algebraic geometric tools required if the full observable probability distribution is
taken into account. The semidefinite test is compared with tests based on entropic inequalities.

I.

INTRODUCTION

In spite of the primal importance of discovering causal relations in science, the statistical analysis of empirical
data has historically shied away from causality. Only releatively recently has a rigorous theory of causality emerged
(see, for instance, [1, 2]), showing that empirical data indeed can contain information about causation rather than
mere correlation. Since then, causal inference has quickly become influential. Examples range from applications
to the inference of genetic [3] and social networks [4], to a better understanding of the role of causality within
quantum physics [5–13].
To formalize causal mechanisms it has become popular to use directed acyclic graphs (DAGs) where nodes
denote random variables and directed edges (arrows) account for their causal relations. Central problems within
this context include inference or model selection: ‘Given samples from a number of observable variables, which DAG
should we associate with them?’, as well as hypothesis testing: ‘Can the observed data be explained in terms of an
assumed DAG?’ Here, we concentrate on the latter problem and propose a novel solution based on the covariances
that a given causal structure gives rise to. To understand the relevance and applicability of this method it is useful
to summarize the difficulties that we typically face when approaching such problems.
The most common method to infer the set of possible DAGs compatible with empirical observations is based
on the Markov condition and the faithfulness assumption [1, 2]. Under these conditions, and in the case where
all variables composing a given DAG can be assumed to be empirically accessible, the conditional statistical independencies implied by the graph contain all the information required to test for the compatibility of some data
with the causal structure. However, for a variety of practical and fundamental reasons, we do quite generally face
causal discovery in the presence of latent (hidden) variables, that is, variables that may play an important role
in the causal model, but nonetheless cannot be accessed empirically. In this case we have to characterize the set
of marginal probability distributions that a given DAG can give rise to. Unfortunately, as is widely recognized,
generic causal models with latent variables impose highly non-trivial constraints on the possible correlations compatible with it [14–25]. Although the marginal compatibility in principle can be completely characterized in terms
of semi-algebraic sets [16], it appears that the resulting tests in practice are computationally intractable beyond a
few variables [18, 22].
One possible approach to deal with the apparent intractability is to consider relaxations of the original problem,
that is, to design tests that define incomplete lists of constraints (outer approximations) to the set of compatible
distributions [17–20, 26–28]. For instance, this approach has previously been considered in [27–30], with tests

∗

johan.aberg@uni-koeln.de

2
based on entropic information theoretic inequalities; an idea originally conceived to tackle foundational questions
in quantum mechanics [31–37]. Here we consider a relaxation in a similar spirit, but based on covariances rather
than entropies.
Beyond dealing with potential computational intractabilities, an additional benefit with a relaxation based on
covariances is that it at most involves bipartite marginals, and it seems reasonable to expect that this would be less
data-intensive than methods based on the full multivariate distribution of the observables.

L1

L2

L3

O2

O3

O4

O1

O5

FIG. 1. Bipartite DAGs. In this investigation we focus on the class of causal models where all correlations among the observables are due to a collection of independent latent variables. This setting can be described in terms of DAGs that are bipartite,
where the latter means that all edges are directed from latent variables (L1 , L2 , L3 ) to the observables (O1 , O2 , O3 , O4 , O5 ), and
where there are no edges within each of these subsets.

A.

Main assumptions and results

We focus on a particular class of latent causal structures, where we assume that there are no direct causal influences between the observables, but only from latent variables to observables (see figure 1). Hence, all correlations
among the observables are due to the latent variables. This setting can be described by the class of DAGs where
all edges are directed from latent vertices to observable vertices, but no edges within these two groups (see figure
1). In other words, we consider the case of DAGs that are bipartite, with the coloring ‘observable’ and ‘latent’.
Alternatively, this can be described in terms of hypergraphs, where each independent latent cause is associated
with a hyperedge consisting of the affected observable vertices (see e.g. [38]).
This class of graphs has previously been considered in the context of marginalization of Bayesian networks [26,
29, 38]. They moreover provide examples of the difficulties that arise when characterizing latent structures [6, 27, 28,
39–41], where standard techniques based on the use of conditional independencies even can yield erroneous results
(for a discussion, see e.g. [42]). This type of latent structures furthermore emerges in the context of Bell’s theorem
[43], as well as in recent generalizations [6, 23, 24, 39–41, 44, 45], where they can be used to show that quantum
correlations between distant observers –thus without direct causal influences between them– are incompatible with
our most basic notions of cause and effect.
Irrespective of the nature of the observables (categorical or continuous) we are free to assign vectors to each
possible outcome of the observables. Our main result is to show that each bipartite DAG implies a particular decomposition of the resulting covariance matrix into positive semidefinite components. Hence, we can test whether
the observed covariance matrix is compatible with a hypothetical bipartite DAG by checking whether it satisfies
the corresponding positive semidefinite decomposition, and we will in the following somewhat colloquially refer
to this as the ‘semidefinite test’. The semidefinite test can thus be phrased as a semidefinite membership problem,
which in turn can be solved via semidefinite programming. The latter is known to be computationally efficient from
a theoretical point of view, and has a good track record concerning algorithms that are efficient also in practice (see
discussions in [46]).

B.

Structure of the paper

In section II we derive a general decomposition of covariance matrices, which forms the basis of our semidefinite
test. In section III we rephrase this general result to fit with the particular structure of observables and latent

3
variables that we employ, and in section IV we derive the main result, namely that every bipartite DAG implies
a particular semidefinite decomposition of the observable covariance matrix. Section V focuses on the converse,
namely that every covariance matrix that satisfies the decomposition of a given bipartite DAG can be realized by
a corresponding causal model. Section VI relates the semidefinite decomposition to previous types of operator
inequalities introduced in [47]. To obtain a covariance matrix we may be required to assign vectors to the outcomes
of the random variables, and section VII discusses the dependence of the semidefinite test on this assignment.
In section VIII we briefly discuss the fact that the compatibility with a given bipartite DAG is not affected if
the observables are processed locally, and that the semidefinite test respects this basic property under suitable
conditions. Section IX considers a specific class of distributions where it is possible to analytically determine the
conditions for a semidefinite decomposition. This class of distribution does in section X serve as a testbed for
comparisons with the above mentioned entropic tests. We conclude with a summary and outlook in section XI.
II.

SEMIDEFINITE DECOMPOSITION OF COVARIANCE MATRICES

In this section we develop the basic structure that forms the core of the semidefinite test. In essence it is obtained
via a repeated application of a law of total variance for covariance matrices.
For a vector-valued random variable Y, in a real or complex inner product space V , we define the covariance
matrix of Y as


† 
= E(YY † ) − E(Y ) E(Y )† ,
(1)
Cov(Y ) := E Y − E(Y ) Y − E(Y )
where E(Y ) denotes the expectation of Y and † denotes the transposition if the underlying vector space is real,
and the Hermitian conjugation if the space is complex. One should note that E(Y )† = E(Y † ). We also define the
cross-correlation for a pair of vector-valued variables Y 0 , Y (not necessarily belonging to the same vector space)
Cov(Y 0 , Y ) := E(Y 0 Y † ) − E(Y 0 ) E(Y )† ,

(2)

where Cov(Y, Y ) = Cov(Y ). For a pair of random variables X, Y we denote the expectation of Y conditioned on X
as E(Y | X ). Via the conditional expectation we can also define the conditional covariance matrix


† 
(3)
Cov(Y | X ) := E Y − E(Y | X ) Y − E(Y | X ) X = E(YY † | X ) − E(Y | X ) E(Y | X )† .
In a similar manner we can also obtain a conditional cross-correlation between two random vectors Y 0 , Y


† 
Cov(Y 0 , Y | X ) := E Y 0 − E(Y 0 | X ) Y − E(Y | X ) X = E(Y 0 Y † | X ) − E(Y 0 | X ) E(Y | X )† .
The starting point for our derivations is the law of total expectation

E (Y ) = E E (Y | X ) ,

(4)

(5)

where the ‘outer’ expectation corresponds to the averaging over the random variable E(Y | X ). The law of total
expectation can be iterated, such that for three random variables Y, X, Z, we have a law of total conditional expectation


E(Y | Z ) = E E(Y | X, Z ) Z ,
(6)



and thus E(Y ) = E E(Y | Z ) = E E E(Y | X, Z ) Z .
From the law of total expectation (5) one can obtain a covariance-matrix version of the law of total variance


Cov(Y ) = Cov E(Y | Z ) + E Cov(Y | Z ) ,
which can be confirmed by expanding the two sides of the above equality and applying (5).
For three random variables Y, W, Z a conditional version of the law of total covariance reads




Cov(Y | Z ) = Cov E(Y |W, Z ) Z + E Cov(Y |W, Z ) Z ,

(7)

(8)

which can be obtained by expanding the right hand side and applying the law of total conditional expectation (6).
The following lemma is obtained via an iterated application of the law of total covariance (7) and the law of total
conditional covariance (8). One may note the similarities with the chain-rule for entropies (see e.g. chapter 2 in
[48]).

4
Lemma 1. Let Y be a vector-valued random variable on a finite-dimensional real or complex inner product space V , let
X1 , . . . , X N be random variables over the same probability space. Assuming that the underlying measure is such that all
involved conditional expectations and covariances are well defined, then
N

Cov(Y ) = R +

∑ Cn ,

(9)

n =1

where R and C1 , . . . , CN are positive semidefinite operators on the space V , defined by

C1 :=Cov E(Y | X1 ) ,


Cn := E Cov E(Y | X1 , . . . , Xn ) X1 , . . . , Xn−1 , n = 2, . . . , N,

R := E Cov(Y | X1 , . . . , X N ) .

(10)

One may note that the above decomposition is not necessarily unique; we could potentially obtain a new decomposition if the variables in the sequence X1 , . . . , X N are permuted.
Proof. The law of total covariance (7) for Z = X1 , combined with the law of total conditional covariance (8) for
Z := X1 , W := X2 yields




Cov(Y ) =Cov E(Y | X1 ) + E Cov E(Y | X2 , X1 ) X1 + E Cov(Y | X2 , X1 ) .
(11)
Suppose that for some j ≥ 2 it would be true that

Cov(Y ) =Cov E(Y | X1 )

j


+ ∑ E Cov E(Y | X1 , . . . , Xn ) X1 , . . . , Xn−1

(12)

n =2


+ E Cov(Y | X1 , . . . , X j ) .
The law of total conditional covariance (8), with W := X j+1 and Z := X1 , . . . , X j , gives




Cov(Y | X1 , . . . , X j ) =Cov E(Y | X1 , . . . , X j , X j+1 ) X1 , . . . , X j + E Cov(Y | X1 , . . . , X j , X j+1 ) X1 , . . . , X j .
By inserting this expression into the last line of (12) one does again obtain (12) but with j substituted for j + 1. By
(11) we can see that (12) is true for j = 2. Thus, by induction to j = N,
 and the identifications in (10), we obtain (9).
Note that Cov E(Y | X1 , . . . , Xn−1 , Xn ) X1 = x1 , . . . , Xn−1 = xn−1 is a positive semidefinite operator on V for
each value of x1 , . . . , xn−1 . Hence, by averaging over these variables, and thus implementing the expectation
that yields Cn , we do still have a positive semidefinite operator on V . The same observation applies to R =
E Cov(Y | X1 , . . . , X N ) .
III.

OBSERVABLE VS. LATENT VARIABLES, AND FEATURE MAPS

Here we consider the decomposition developed in the previous section for the more specific setting of observable
and latent variables.
We consider a collection of observable variables O1 , . . . , O M . To each of these variables Om we associate a mapping
Y (m) , in some contexts referred to as a ‘feature map’ [49], into a finite-dimensional vector space Vm . We denote
the resulting vector-valued random variables by Ym := Y (m) (Om ), and for the sake of simplicity we will in the
following tend to abuse the terminology and refer to the vectors Ym themselves as feature maps. We also define the
LM
M
joint random vector Y := ∑m
=1 Ym on V : =
m=1 Vm . (Hence, we can view Y as the concatenation of the vectors
Ym .) One should note that while we regard the observable variables Om as being part of the setup that is ‘given’, the
feature maps Y (m) are part of the analysis, and we are free to assign these as we see fit. (Concerning the question
of how the test depends on this choice, see section VII.)
Let Pm denote the projector onto the subspace Vm in V . We divide the total covariance matrix Cov(Y ) into the
M
cross-correlations between the separate observable quantities Cov(Y ) = [Cov(Ym , Ym0 )]m,m
0 =1 . One can note that
Cov(Ym , Ym0 ) = Pm Cov(Y ) Pm0 .

5

Y1

Y=

O1

L2

Y2

L4

O3

Y3

O2
L1

O4

Y4

O5

L3

Y5
FIG. 2. Observables, latent variables, and feature maps. The model consists of a collection of observable variables O1 , . . . , O M
and a collection of latent variables L1 , . . . , L N . Via feature maps, each Om is mapped to a vector Ym in a vector space Vm . On the
LM
vector space V = m
=1 Vm we define the joint random vector Y : = Y1 + · · · + YM .

For a collection of latent variables L1 , . . . , L N , we make the identifications X j := L j in Lemma 1. Similarly as
0

M
for the covariance matrix we decompose the operators Cn and R into ‘block-matrices’ Cn = [Cnm,m ]m,m
0 =1 and
0

0

0

m,m
M
:= Pm Cn Pm0 and Rm,m := Pm RPm0 , where we can write
R = [ Rm,m ]m,m
0 =1 , with Cn


0
C1m,m =Cov E(Ym | L1 ), E(Ym0 | L1 ) ,



0
Cnm,m = E Cov E(Ym | L1 , . . . , Ln ), E(Ym0 | L1 , . . . , Ln ) L1 , . . . , Ln−1 ,

(13)


0
Rm,m = E Cov(Ym , Ym0 | L1 , . . . , L N ) ,
for 2 ≤ n ≤ N. In terms of these blocks we can thus reformulate (9) as
0

Cov(Ym , Ym0 ) = Rm,m +

N

0

∑ Cnm,m .

(14)

n =1
0

0

One should keep in mind that Cnm,m and Rm,m in the general case are matrices (rather than scalar numbers) for
each single pair m, m0 .

IV.

DECOMPOSITION OF THE COVARIANCE MATRIX FOR BIPARTITE DAGS

We define a bipartite DAG as a finite DAG G = (V, E) with vertices V and edges E, with a bipartition V = O ∪ L,
O ∩ L = ∅ such that all edges in E are directed from the elements in L (the latent variables) to the elements in
O (the observables). Since G is finite, we enumerate the elements of O as O1 , . . . , O M and the elements of L as
L1 , . . . , L N . One may note that we generally will overload the notation and let Om and Ln denote the vertices in the
underlying bipartite DAG, as well as denoting the random variables associated with these vertices.
For a vertex v in a directed graph G we let ch(v) denote the children of v, i.e., the set of vertices v0 for which
there is an edge directed from v to v0 . We let pa(v) denote the parents of v, i.e., the set of vertices v0 for which
there is an edge directed from v0 to v. For bipartite DAGs an element in L can only have children in O (and have
no parents), and an element in O can only have parents in L (and no children). As an example, for the bipartite
DAG in figure 1 we have ch( L1 ) = {O1 , O2 , O3 }, ch( L2 ) = {O2 , O5 }, and ch( L3 ) = {O3 , O5 }, and pa(O1 ) = { L1 },
pa(O2 ) = { L1 , L2 }, pa(O3 ) = { L1 , L3 }, pa(O4 ) = ∅, and pa(O5 ) = { L2 , L3 }.
For a causal model defined by a general DAG G = (V, E) the underlying probability distribution can be described
via the Markov condition where each edge represents a direct causal influence, and thus each vertex v can only be
directly influenced by its parents pa(v), resulting in distributions of the form P = Πv∈V P v pa(v) . Hence, for a

bipartite DAG we get P = Πm P Om pa(Om ) Πn P( Ln ), and thus all the latent variables are independent, and the
observables are independent when conditioned on the latent variables.

6
As in the previous section, we map the observables O1 , . . . , O M to vectors Y1 , . . . , YM in vector spaces V1 , . . . , V M .
For each n we define the projector P(n) in V by
P(n) : =

∑

Pm .

(15)

m∈ch( Ln )

Hence, P(n) is the projector onto all subspaces of V that are associated with the children ch( Ln ) of the latent variable
Ln . (In the above sum we should strictly speaking write ∑m:Om ∈ch( Ln ) . However, in order to avoid a too cumbersome
notation we will from time to time take the liberty of writing m ∈ ch( Ln ) rather than Om ∈ ch( Ln ), and n ∈ pa(Om )
rather than Ln ∈ pa(Om ).)

FIG. 3. Example: Triangular bipartite DAG. The covariance matrix resulting from the observables in a bipartite DAG is subject
to a decomposition where each latent variable gives rise to a positive semidefinite component, and where the support of that
component is determined by the children of the corresponding latent variable. In the case of the ‘triangular’ scenario of the
the bipartite DAG to the left, each of the three latent variables has two children. The covariance matrix, schematically depicted
to the right, can consequently be decomposed into three positive semidefinite components, each with bipartite supports. This
observation yields a method (which we refer to as the ‘semidefinite test’) to falsify a given bipartite DAG as an explanation of
an observed covariance matrix.

Proposition 1. For a bipartite DAG with latent variables L1 , . . . , L N and observables O1 , . . . , O M with assigned feature maps
M
Y1 , . . . , YM into finite-dimensional real or complex inner-product spaces V1 , . . . , V M , the covariance matrix of Y = ∑m
=1 Ym
satisfies
N

Cov(Y ) = R +

∑ Cn ,

R ≥ 0,

Cn ≥ 0,

(16)

n =1

where
P(n) Cn P(n) = Cn ,

M

R=

∑

Pm RPm .

(17)

m =1

and where the projectors P(n) are as defined in (15) with respect to the given bipartite DAG, and where Pm is the projector
LM
onto Vm in m
=1 V m .
One may note that if the span of the supports of { P(n) }nN=1 covers V , then we can distribute the blocks Pm RPm of
R and add them to the different Cn in such a way that the new operators still are positive semidefinite and satisfy
the support structure of the original Cn s. The exception is if there is some observable that has no parent (as O4 in
figure 1).
Proof. Select an enumeration L1 , . . . , L N of the latent variables. By Lemma 1 we know that the covariance matrix
Cov(Y ) can be decomposed as in (9) with the positive semidefinite operators R and Cn as defined in (10). In the
0
M
m,m0 ] M
following we will make use of the block-decomposition Cn = [Cnm,m ]m,m
0 =1 and R = [ R
m,m0 =1 with respect to
the subspaces V1 , . . . , V M as in (13).
If Ln ∈
/ pa(Om ) then it means that Ym is independent of Ln and thus
E(Ym | L1 , . . . , Ln ) = E(Ym | L1 , . . . , Ln−1 ).

7
The analogous statement is true if Ln ∈
/ pa(Om0 ). By this it follows that


Cov E(Ym | L1 , . . . , Ln ), E(Ym0 | L1 , . . . , Ln ) L1 , . . . , Ln−1 = 0,

if

Ln ∈
/ pa(Om ) ∩ pa(Om0 ).

(18)

Note that Ln ∈ pa(Om ) ∩ pa(Om0 ) ⇔ Om , Om0 ∈ ch( Ln ). By comparing (18) with (13) we can conclude that
0
/ ch( Ln ) or Om0 ∈
/ ch( Ln ). The definition of the projector P(n) in (15) thus yields P(n) Cn P(n) = Cn .
Cnm,m = 0 if Om ∈
Moreover, we know from Lemma 1 that Cn ≥ 0.
By construction, all the observables O1 , . . . , O M and thus also Y1 , . . . , YM are independent when conditioned on
the latent variables. Hence,


0
Rm,m = E Cov(Ym , Ym0 | L1 , . . . , L N ) = δm,m0 E Cov(Ym | L1 , . . . , L N ) ,
M
and thus R = ∑m
=1 Pm RPm .
One may note that although the operators Cn potentially may change if we generated them via a permutation
of the sequence of latent variables L1 , . . . , L N , the resulting projectors P(n) would not change. Hence, the supportstructure described by (16) and (17) is stable under rearrangements of the sequence.

Deciding whether a given matrix is of the form (16) can be done via semi-definite programming (SDP). We end
this section by describing an explicit SDP formulation.
The optimization will be over matrices Z which can be interpreted as the direct sum of candidates for R and the
Cn ’s. More precisely, let

Z : = V1 ⊕ · · · ⊕ V M ⊕ W1 ⊕ · · · ⊕ W N ,
M
Wi : =
Vm .

(19)
(20)

m∈ch( L p )

Let Z be a matrix on Z . According to the direct sum decomposition (19), the matrix Z is a block matrix with
( M + N ) × ( M + N ) blocks. We think of the fist M diagonal blocks as carrying candidates for Rm = Pm RPm (which
completely defines R, according to (17)); while the rear N diagonal blocks correspond to candidate Cn ’s. Note that
the N rear sumands in (19) are dirct sums themselves. It therefore makes sense to use double indices to refer to
0
spaces inside the Wi ’s. Concretely, the SDP includes affine constraints on the blocks Z ( M+n,m),( M+n,m ) . The first
part of the indices selects the space Wn in (19). The second part refers to the space Vm within Wn according to (20).
0
We use the convention that Z ( M+n,m),( M+n,m ) denotes 0 if either Vm or Vm0 does not occur in Wn .
With these definitions, the semi-definite program that verifies whether a covariance matrix Cov(Y ) is of the form
(16) reads
maximize

0

(21)
M

subject to

δm,m0

∑

m =1

Z ( m ),( m ) +

N

0

0

∑ Z( M+n,m),( M+n,m ) = Cov(Y )m,m ,

(m, m0 = 1, . . . M)

(22)

n =1

Z ≥ 0,

(23)

where the optimization is over symmetric (hermitian) matrices Z on Z . Up to a trivial re-expression of the linear
functions of Z in terms of trace inner products with suitable matrices Fi , the optimization problem above is in the
(dual) standard form of an SDP [46, Section 3].
The left-hand side of (22) impliclity defines a linear map A from matrices on Z to matrices on V . Explicitly, A
maps off-diagonal blocks to 0 and acts on block-diagonal matrices as

A : R1 ⊕ · · · ⊕ R M ⊕ C1 ⊕ · · · ⊕ CN 7→ ∑ Rm + ∑ Cn .
m

n

The constraints of the SDP can thus be written slightly more transparently as

A( Z ) = Cov(Y ),
Z≥0

(24)
(25)

In this language, the dual of the above SDP is
minimize
subject to

tr X Cov(Y )
†

A ( X ) ≥ 0.



(26)
(27)

8

Let X ? be the optimizer of (26). If tr X ? Cov(Y ) < 0, then the original SDP is infeasible and therefore, Cov(Y ) is
not of the form (16). Indeed, by construction, such an X ? has a negative trace inner product with the covariance
matrix, but a positive trace inner product


tr A( Z ) X = tr Z A† ( X ) ≥ 0

∀Z ≥ 0

with all matrices A( Z ), Z ≥ 0 that could potentially be feasible for the primal SDP (24). Thus, the dual SDP (26)
can be used to find a witness or a dual certificate X ? for the incompatibility of a covariance matrix with a presumed
causal structure. The geometry of the involved objects is shown in figure 4. We will refer to this dual construction
in section XI, where we sketch possibilities to base statistical hypothesis tests such witnesses.

Γ

X*

Cov(Y)

FIG. 4. Dual Certificates. The set of covariance matrices compatible with a certain causal structure in the sense of proposition 1
forms a convex cone Γ. The cone is the feasible set of the SDP (21). If a given covariance matrix Cov(Y ) is not an element of that
cone, then there exists a hyperplane (depicted in red) seperating the two convex sets. A normal vector X ? for the seperating
hyperplane can be found using the dual SDP (26).

V.

REALIZING A GIVEN DECOMPOSITION

In the previous section we have shown that the observable covariance matrix associated with a given bipartite
DAG always satisfies a particular semidefinite decomposition implied by that DAG. Here we show the converse,
in the sense that if we have a positive semidefinite operator that satisfies the decomposition obtained from a
particular bipartite DAG, then there exists a causal model associated with that DAG that has the given operator as
its observable covariance matrix (see figure 5). The proof is based on the observation that each positive semidefinite
operator on a vector space can be interpreted as the covariance of a vector-valued random variable on that space
(e.g. as the covariance of a multivariate normal distribution, or of variable over finite alphabets, as discussed
in section V B). The essential idea is that we assign an independent random variable to each component in the
decomposition, and take these as the latent variables, and that the support structure of the components furthermore
determines the children of the latent variables.

A.

Realization of decompositions

Let O be a finite set, and let {Ωn }nN=1 be a collection of subsets of O. The collection {Ωn }nN=1 defines a bipartite
DAG with O as observable nodes, and a set of latent nodes L1 , . . . , L N , with the edges assigned by the identification
ch( Ln ) := Ωn for n = 1, . . . , N. In the following we denote this bipartite DAG by B({Ωn }nN=1 ).
Proposition 2. Let V1 , . . . , V M be finite-dimensional real or complex inner-product spaces. For a number N let {Ωn }nN=1 be
a collection of subsets Ωn ⊂ {1, . . . , M}. Suppose that Q is a positive semidefinite operator on the space V = V1 ⊕ · · · ⊕ V M ,

9

+

+

+

FIG. 5.
A positive semidefinite operator on a set of selected orthogonal subspaces can be regarded as the covariance matrix of a corresponding collection of vector-valued variables. If this operator separates into positive semidefinite components
(as schematically depicted to the left), then the support structures of these components define a bipartite DAG (on the right).
The components in the decomposition can be interpreted as the covariance matrices of independent vector-valued latent variables. Moreover, the collection of subspaces on which such an operator has support determines the observable children of the
corresponding latent variable. Each observable variable can be constructed by adding the components collected from its parents.

and that it can be written
N

Q = R+

∑ Cn ,

P(n) Cn P(n) = Cn ,

P(n) =

∑

R ≥ 0,

Cn ≥ 0,

(28)

n =1

for
M

Pm ,

m∈Ωn

R=

∑

Pm RPm ,

(29)

m =1

with Pm being the projectors onto the subspaces Vm . Then there exists a causal model for the bipartite DAG B({Ωn }nN=1 ) with
vector-valued variables Y1 , . . . , YM in V1 , . . . , V M such that Y = Y1 + · · · + YM satisfies
Cov(Y ) = Q.

(30)

Proof. Let us define the set Ω := ∪nN=1 Ωn and its complement Ωc := {1, . . . , M} \ Ω. By construction, Ωc is the set
of observable nodes in the bipartite DAG B({Ωn }nN=1 ) that have no parents (like vertex 4 in figure 1) and thus each
element in Ω has at least one parent. By the definition of P(n) in (29) it follows that ∑m0 ∈Ωc Pm0 Cn = Cn ∑m0 ∈Ωc Pm0 =
0. In other words, the operators Cn have no support on the subspaces belonging to parentless observable nodes.
M
Let us now turn to the operator R and its block diagonal decomposition R = ∑m
=1 Rm with Rm : = Pm RPm . We
can write R = ∑m0 ∈Ωc Rm0 + ∑m∈Ω Rm . Consequently, Q can be decomposed in one operator ∑m∈Ω Rm + ∑nN=1 Cn
L
on the subspace m∈Ω Vm , and a collection of blocks { Rm0 }m0 ∈Ωc on the corresponding subspaces Vm0 for m0 ∈ Ωc .
Since Rm0 is positive semidefinite, it can be interpreted as the covariance matrix of some random vector Ym0 in Vm0 .
In the following we assume that we have made such an assignment for all m0 ∈ Ωc . We also assume that these
random vectors are independent.
Each Rm for m ∈ Ω has its support inside the support of at least one Cn . Hence, we can ‘distribute’ the operators
Rm for m ∈ Ω by forming new positive semidefinite operators C̃n ≥ 0 such that

∑

m∈Ω

Rm +

N

N

n =1

n =1

∑ Cn = ∑ C̃n =: Q̃,

(31)

e
where one may note that Q = ∑m0 ∈Ωc Rm0 + Q.
In the following we shall assign observable and latent random variables to the vertices of the bipartite DAG
B({Ωn }nN=1 ). For each n ∈ {1, . . . , N } and each m ∈ Ω, let Lnm be a vector space that is isomorphic to Vm , and
n : Ln → V be an arbitrary isomorphism. (We assume that these isomorphisms preserve the inner-product
let φm
m
m
n maps orthonormal bases of Ln to orthonormal bases of V .) We regard the spaces in the
structure, such that φm
m
Lm
n
collection {Lm }m∈Ω,n=1,...,N as being orthogonal to each other. Define Ln := m∈Ω Lnm , and the corresponding
n . Since each C̃ is positive semidefinite, it can be interpreted as the covariance matrix
isomorphism φn := ∑m∈Ω φm
L n
of a vector-valued random variable on m∈Ω Vm . Consequently, we can also find a vector-valued random variable
Ln on Ln such that
C̃n =Cov(φn Ln ) = φn Cov( Ln )φn † .

(32)

10
We assume that the random variables L1 , . . . , L N are independent of each other, and also independent of {Ym0 }m0 ∈Ωc .
The variables L1 , . . . , L N serve as the latent variables corresponding to the latent nodes in the bipartite DAG
B({Ωn }nN=1 ). In the following we shall construct a collection of vector-valued variables {Ym }m∈Ω as deterministic functions of the latent variables L1 , . . . , L N , in such a way that these functions correspond to the arrows in
B({Ωn }nN=1 ), thus guaranteeing a valid causal model associated with this bipartite DAG.
Let us decompose the vector Ln into its projections Lnm onto the subspaces Lnm . For each m ∈ Ωn = ch( Ln ), the
vector Lnm is associated to the observable node Om . (One can imagine it to be transferred to node Om .) Equivalently
we can say that each observable node m ∈ Ω receives the vector Lnm from its ancestor n ∈ pa(Om ). On the observable
node m ∈ Ω we construct a new vector Ym by adding all the vectors ‘sent to it’ from its parents
Ym :=

∑

∑

n n
φm
Lm =

n∈pa(Om )

n
φm
Ln =

N

∑ φmn Ln ,

(33)

n =1

n∈pa(Om )

where the last equality follows since Pm Cn Pm = 0 if Om ∈
/ ch( Ln ), or equivalently if Ln ∈
/ pa(Om ), and thus
n L = 0 if n ∈
φm
/
pa
(
O
)
.
The
collection
{
Y
}
∪
{
Y
}
we
take
as
the
observable
variables,
and we define
0
0
c
n
m
m m∈Ω
m m ∈Ω
N
n
Y := ∑m0 ∈Ωc Ym0 + ∑m∈Ω Ym = ∑m0 ∈Ωc Ym0 + ∑n=1 φ Ln .
Due to the fact that all Ym0 for m0 ∈ Ωc are independent, and also independent of all Ln , we get
Cov(Y ) =



m ∈Ω

N

=

N

N

n =1

n =1

∑ c Cov(Ym0 ) + Cov ∑ φn Ln , ∑
0
0
∑ c Rm0 + ∑0
0

m ∈Ω

φn Cov( Ln , Ln0 )φn

0

φn Ln0



0†

n,n =1

[ L1 , . . . , L N are independent]
N

=

Rm0 + ∑ φn Cov( Ln )φn †
∑
0
c

m ∈Ω

n =1

[By (32)]
N

=

∑ c Rm0 + ∑ C̃n
0

m ∈Ω

n =1

[By (31)]
= Q.

B.

Positive semidefinite operators as covariance matrices of vector-valued random variables over finite alphabets

The material in the previous section presumes the existence of realizations of positive semidefinite operators as
the covariance of some vector-valued variable, without making any restriction on ther nature. As mentioned above,
each positive semi-definite operator (over a finite-dimensional real or complex vector space) can be regarded as the
covariance of a multivariate normal distribution. However, suppose that we would require that the variable only
can take a finite number of outcomes. Here we briefly discuss the conditions for such realizations, and provide an
explicit construction (in the proof of Lemma 3).
For a (possibly vector-valued) random variable over a finite alphabet, we say that that the supported alphabet
size is D, if there are precisely D outcomes that occur with a non-zero probability.
Lemma 2. If a random variable Y on a finite-dimensional real or complex inner-product space has a supported alphabet size
D, then rank Cov(Y ) ≤ D − 1.
D
D
D
†
†
Proof. We first note that Cov(Y ) = ∑ D
j=1 p j y j y j − ∑ j=1 p j y j ∑ j0 =1 p j0 y j0 . Since ∑ j=1 p j y j very manifestly is a linear
D
D
†
†
combination of y1 , . . . , y D , it follows that the range of ∑ D
j=1 p j y j ∑ j0 =1 p j0 y j0 is a subset of the range of ∑ j=1 p j y j y j , and


†
thus rank Cov(Y ) ≤ rank ∑ D
j=1 p j y j y j ≤ D. However, in the following we shall show that the stronger inequality

11

rank Cov(Y ) ≤ D − 1 holds. To see this, let us first consider the case that y1 , . . . , y D are linearly dependent. This

means that at least one of these vectors is a linear combination of the others, and thus rank Cov(Y ) ≤ D − 1. Let
us now instead assume that y1 , . . . , y D is a linearly independent set. Define Q := [ Q j,j0 ] D
j,j0 =1 by Q j,j0 : = p j δj,j0 −
p j p j0 , then Cov(Y ) = ∑ j,j0 y j Q j,j0 y†j0 . Hence, Q is the matrix representation of Cov(Y ) with respect to the linearly
independent, but not necessarily orthonormal set y1 , . . . , y D . One can realize that due to the linear independence,
√

it follows that rank Cov(Y ) = rank( Q). Finally, let us define the D-dimensional vector 1 := (1, . . . , 1)† / D. One

can confirm that Q1 = 0. Hence, rank( Q) ≤ D − 1, and we can conclude that rank Cov(Y ) ≤ D − 1.
Lemma 3. Let C be a positive semidefinite operator on a finite-dimensional real or complex inner-product space V . For
every D ≥ rank(C ) + 1 there exists a vector-valued random variable Y on V with supported alphabet size D, such that
C = Cov(Y ). However, C 6= Cov(Y ) for all Y with a supported alphabet size D < rank(C ) + 1.
Proof. Let D be the supported alphabet size of a vector-valued random variable Y. If D < rank(C ) + 1, then
we know from Lemma 2 that C 6= Cov(Y ). Hence, it remains to show that it is possible to find a Y such that
C = Cov(Y ) for every D ≥ rank(C ) + 1. We thus wish to find a collection of vectors y1 , . . . , y D ∈ V , and p1 , . . . , p D
D
D
D
†
†
with p j > 0, and ∑ D
j=1 p j = 1, such that C = ∑ j=1 p j y j y j − ∑ j=1 p j y j ∑ j0 =1 p j0 y j0 .
Let {zk }kK=1 be an orthonormal basis of the range (support) of the operator C, and let PC be the projector onto the
range. Let U be a matrix in RD× D (CD× D ) if the underlying space√V is real (complex). Since D ≥ K + 1, we can
assign the (K + 1)th column of U to be the vector 1 := (1, . . . , 1)† / D (i.e., Uj,K +1 = √1 for all j = 1, . . . , D) and
D
we arbitrarily complete the rest of the matrix U such that it becomes orthogonal (unitary). Since U is orthogonal
(unitary), it follows that its columns form an orthonormal basis of RD (CD ). Hence, for each k = 1, . . . , K it must
be the case that the vector (Uj,k ) D
j=1 is orthogonal to 1, and thus
D

∑ Uj,k = 0,

k = 1, . . . , K.

(34)

j =1

K
D
†
Next, define the set of vectors {v j } D
j=1 ⊂ V by v j : = ∑k =1 U j,k zk . One can confirm that ∑ j=1 v j v j = PC , as well as
√ √
D
K
D
∑ j=1 v j = ∑k=1 ∑ j=1 Uj,k zk = 0, where we use (34). As the final step we define p j := D1 and y j := D Cv j for
j = 1, . . . , D. One can confirm that
D

∑ p j y j y†j =

j =1

√

D
√
√
√
C ∑ v j v†j C = CPC C = C,
j =1

D

∑ pj yj =

j =1

1 √ D
√
C ∑ v j = 0.
D
j =1

Thus, if a vector-valued random variable Y takes y j with probability p j , we have Cov(Y ) = C.

VI.

IMPLIED OPERATOR INEQUALITIES

Here we show that the existence of positive semidefinite decompositions as in Proposition 1 implies operator
inequalities of a type studied in [47].
Consider as usual a bipartite DAG with latent variables L1 , . . . , L N and observables O1 , . . . , O M with assigned
feature maps Y1 , . . . , YM into vector spaces V1 , . . . , V M . For a number d (whose meaning is going to be evident
M V
shortly) we define the following map on the space of operators on V = ⊕m
=1 m
Φ( Q) := (d − 1) P1 QP1 +

M

∑ ( Pm QPm + P1 QPm + Pm QP1 ),

(35)

m =2

where Pm are the projectors onto the spaces Vm as discussed in section III. Theorem 4.1 in [47] does in essence say
that if all the latent variables Ln in the given bipartite DAG have degree at most d, then the resulting covariance
matrix Cov(Y ) satisfies

Φ Cov(Y ) ≥ 0,

(36)

12
or if one prefers matrix notation

(d − 1)Cov(Y1 ) Cov(Y1 , Y2 )
 Cov(Y2 , Y1 )
Cov(Y2 )


..

.
0


..
..

.
.
Cov(YM , Y1 )
0



· · · · · · Cov(Y1 , YM )

0 ···
0


.
.. ..
..
 ≥ 0.
.
.


.. ..

.
.
0
··· 0
Cov(YM )

(37)

Hence, by deleting a particular collection of blocks from the full covariance matrix Cov(Y ), and adding copies of
the diagonal block Cov(Y1 ), we obtain a positive semidefinite operator. It may be worth emphasizing that mere
positive semidefiniteness of Q is not enough to guarantee that Φ( Q) is positive semidefinite. Hence, (36) can indeed
be used as a test of the underlying latent structure. As one may note, equations (36) and (37) single out observable
1, but by relabelling we can obtain analogous inequalities for all observables. As an example, for the triangular
scenario in figure 3, the inequality (37) and its permutations take the form
"
#
"
#
"
#
Cov(Y1 ) Cov(Y1 ,Y2 )
0
Cov(Y2 ,Y1 ) Cov(Y2 ) Cov(Y2 ,Y3 )
0
Cov(Y3 ,Y2 ) Cov(Y3 )

≥ 0,

Cov(Y1 ) Cov(Y1 ,Y2 ) Cov(Y1 ,Y3 )
Cov(Y2 ,Y1 ) Cov(Y2 )
0
Cov(Y3 ,Y1 )
0
Cov(Y3 )

≥ 0,

Cov(Y1 )
0
Cov(Y1 ,Y3 )
0
Cov(Y2 ) Cov(Y2 ,Y3 )
Cov(Y3 ,Y1 ) Cov(Y3 ,Y2 ) Cov(Y3 )

≥ 0.

The following proposition shows that the semidefinite decomposition implies the operator inequality (36) under
the assumption that all the latent variables (regarded as vertices in a bipartite graph) have the degree at most d.
Proposition 3. For a bipartite DAG with latent variables L1 , . . . , L N , each with degree at most d, and observables O1 , . . . , O M
with assigned feature maps Y1 , . . . , YM into finite-dimensional
real or complex inner-product spaces V1 , . . . , V M , the covariance

M
matrix of Y = ∑m
Y
satisfies
Φ
Cov
(
Y
)
≥
0,
where
Φ
is
as defined in (35).
=1 m
Proof. We know from Proposition 1 that Cov(Y ) = R + ∑nN=1 Cn with P(n) Cn P(n) = Cn , Cn ≥ 0, and where R is such
that ∑m Pm RPm = R and R ≥ 0. Due to this, we have
Φ( R) = (1 − d) P1 RP1 +

M

∑

Pm RPm ≥ 0.

(38)

m =2

For each Cn we can distinguish two cases.
In the first case, Cn has no support on V1 , i.e., P1 Cn P1 = 0. Due to the positive semidefiniteness of Cn it also
follows that P1 Cn Pj = 0 for j = 2, . . . , M, and thus
Φ(Cn ) =

M

∑

Pm Cn Pm ≥ 0.

(39)

m =2

In the second case, Cn does have a support on V1 , meaning that P1 Cn P1 6= 0. By assumption, the latent variable
Ln has degree at most d, which means that Cn has support on at most d of the subspaces V1 , . . . , V M . Hence, apart
form V1 , there are at most d − 1 further spaces involved. We enumerate these spaces as Vm(2) , . . . , Vm(d) , and let
Vm(1) = V1 . Hence, it may be the case that Pm( j) Cn Pm( j) 6= 0 for j = 1, . . . , d, while Pm Cn Pm = 0 for the remaining
values of m. Due to the positive semidefiniteness of Cn , we can analogously have P1 Cn Pm( j) 6= 0, and Pm( j) Cn P1 6= 0,
but P1 Cn Pm = 0, and Pm Cn P1 = 0 for the other values of m. We can conclude that
Φ(Cn ) =(d − 1) P1 Cn P1 +

M

∑ ( Pm Cn Pm + P1 Cn Pm + Pm Cn P1 )

m =2
d

=(d − 1) P1 Cn P1 + ∑ ( Pm( j) Cn Pm( j) + P1 Cn Pm( j) + Pm( j) Cn P1 )
j =2

 

d 
= ∑ P1 + Pm( j) Cn P1 + Pm( j) ≥ 0.
j =2


The combination of (38), (39) and (40) yields Φ Cov(Y ) = Φ( R) + ∑nN=1 Φ(Cn ) ≥ 0, which proves (36).

(40)

13
We note that the operator inequalities derived here need not be tight in all cases. Indeed, it is not hard to verify
that the maps Φα defined by
"
Φα :

Cov(Y1 ) Cov(Y1 ,Y2 ) Cov(Y1 ,Y3 )
Cov(Y2 ,Y1 ) Cov(Y2 ) Cov(Y2 ,Y3 )
Cov(Y3 ,Y1 ) Cov(Y3 ,Y2 ) Cov(Y3 )

#

"

7→

Cov(Y1 )
e−iα Cov(Y2 ,Y1 )
Cov(Y3 ,Y1 )

eiα Cov(Y1 ,Y2 ) Cov(Y1 ,Y3 )
Cov(Y2 )
Cov(Y2 ,Y3 )
Cov(Y3 ,Y2 )
Cov(Y3 )

#

preserve the set of covariance matrices compatible with the triangle scenario. Here, α ∈ [0, 2π ) is a phase factor.
In particular, Φα preserves positivity when acting on covariance matrices arising in this context. This is a strictly
stronger result than the one we have obtained above: The map Φ treated in the proposition is just the equal-weight
convex combination of Φπ and Φ0 :
"
#
"
# "
#
Cov(Y1 ) Cov(Y1 ,Y2 ) Cov(Y1 ,Y3 )
Cov(Y1 ) −Cov(Y1 ,Y2 ) Cov(Y1 ,Y3 )
Cov(Y1 )
0
Cov(Y1 ,Y3 )
1
1
Cov(Y2 ,Y1 ) Cov(Y2 ) Cov(Y2 ,Y3 ) +
−Cov(Y2 ,Y1 ) Cov(Y2 ) Cov(Y2 ,Y3 ) =
0
Cov(Y2 ) Cov(Y2 ,Y3 ) .
2 Cov(Y3 ,Y1 ) Cov(Y3 ,Y2 ) Cov(Y3 )
2 Cov(Y3 ,Y1 ) Cov(Y3 ,Y2 ) Cov(Y3 )
Cov(Y3 ,Y1 ) Cov(Y3 ,Y2 ) Cov(Y3 )
It may potentially be fruitful to consider a general theory of maps that preserve the convex cone of covariances
compatible with a given causal structure.

VII.

UNIVERSAL FEATURE MAPS FOR FINITE CATEGORICAL VARIABLES

As the reader may have realized, the choice of feature maps Y (m) may affect the outcome of the semidefinite
test. In other words, even if we find a particular setup that is compatible with the given bipartite DAG, it may
be the case that another assignment of the vectors Ym could yield a violation; thus potentially suggesting that we
ideally should test an infinite number of choices. However, in the case of observable variables with only finite
number of outcomes, we shall here see that one can make a single test, based on a sufficiently ‘powerful’ choice of
feature maps. Suppose that the variables Om can only take a finite number of outcomes o1m , . . . , odmm . An arbitrary
assignment of a feature map would correspond to a collection of vectors y1m , . . . , ym
dm ∈ Vm for some vector space
Vm . Now suppose that we make the additional restriction that y1m , . . . , ym
are
linearly
independent, and that
dm
dim(Vm ) = dm . Suppose that we have some other arbitrary assignment of feature map Ỹm given by a collection
of vectors ỹ1m , . . . , ỹm
dm ∈ Ṽm for some vector space Ṽm (without any requirement of linear independence). One can
m
realize that it is always possible to find a linear map φm : Vm → Ṽm such that φm ym
j = ỹ j , and thus φm Ym = Ỹm .
To see this, one can note that since y1m , . . . , ym
dm is a linearly independent set in a dm -dimensional space, it follows
m
that the Gram matrix G = [ Gj,j0 ]dj,jm0 =1 with Gj,j0 := (ym
j , y j0 ) is invertible (and positive definite). One can confirm

m
m
−1
m
that φm defined by φm (v) := ∑ jj0 ỹm
j [ G ] jj0 ( y j0 , v ) satisfies φm y j = ỹ j . In other words, a feature map with linearly
independent components is ‘universal’ in the sense that we can generate all other feature maps on all other vector
spaces, and it is moreover sufficient to do this via linear transformations.
For a collection of universal feature maps Y1 , . . . , YM assigned to O1 , . . . , O M , we can reach all other feature maps
M
Ỹ1 , . . . , ỸM , by linear operations Ỹm = φm Ym . Moreover, the covariance matrix Cov(Y ) for Y = ∑m
=1 Ym and the
M
M
†
covariance matrix Cov(Ỹ ) for Ỹ = ∑m=1 Ỹm are related by Cov(Ỹ ) = φCov(Y )φ for φ := ∑m=1 φm . One can realize
that if Cov(Y ) satisfies the decomposition in Proposition 1 for a given bipartite DAG, then Cov(Ỹ ) also satisfies the
decomposition. We can conclude that it is sufficient to apply the semidefinite test for a single collection of feature
maps, where each of these have linearly independent components. (A convenient choice would be mappings to
orthonormal bases.)
It is conceivable that a similar construction would hold for variables with a countably infinite number of outcomes, and it is an interesting question if one in some sense could make ‘universal’ assignments of feature maps
also in the case of a continuum. However, we shall not consider these issues in this investigation, but leave them as
open questions.

VIII.

MONOTONICITY UNDER LOCAL OPERATIONS

Suppose that we would process each observable variable in a collection O1 , . . . , O M ‘locally’. In other words, the
output Õm is a (possibly random) function only of Om . If we restrict ourselves to discrete random variables, then

14
this type of mapping from an input distribution P M of the O1 , . . . , O M , to the output distribution P̃ M of Õ1 , . . . , Õ M
can be written
P̃ M ( x̃1 , . . . , x̃ M ) :=

∑

P1 ( x̃1 | x1 ) · · · P M ( x̃ M | x M ) P M ( x1 , . . . , x M ),

(41)

x1 ...,x M

where all Pm ( x̃m | xm ) are conditional distributions. From this construction it is clear that if a distribution P M is
compatible with the given bipartite DAG, then the resulting distribution P̃ M on Õ1 , . . . , Õ M will also be compatible
with the very same DAG. In other words, compatibility with a given bipartite DAG is in this sense a monotone
with respect to local operations.
There is a priori no reason to expect that relaxations of the compatibility problem would satisfy this monotonicity.
However, here we show that this property is respected by the semidefinite test, if the latter is based on universal
feature maps (in the sense of the previous section). The fact that universality is needed can be seen from the
following trivial special case. We assign feature maps Ym to Om , and Ỹm to Õm . In principle we can for each m
choose all components of Ym to be identical, thus resulting in a zero covariance matrix that trivially satisfies all
decompositions, while Ỹm may still result in a violation. By assuming that all the feature maps Ym are universal,
we shall in the following see that monotonicity is guaranteed.
Let us first focus on the transformation of a single observable variable Om to Õm , and let us assume that Ym
K
m m
has the linearly independent components y1m , . . . , ym
K , with Gram matrix G = [ Gx,x 0 ] x,x 0 =1 with Gx,x 0 = ( y x , y x 0 ),
m
m
m
in a K-dimensional vector space Vm . G is invertible since y1 , . . . , yK are linearly independent. Let ỹ1 , . . . , ỹm
L be
the components of Ỹm in Ṽm . (If L = K we can of course choose ỹm := ym as a special case.) Define ψm (v) :=
∑ x̃,x0 ,x00 ỹ x̃ Pm ( x̃ | x 0 )[ G −1 ] x0 ,x00 (y x00 , v). (Here and in the following we omit the superscript ‘m’ on the vectors y for
notational convenience.) One can confirm that E(Ỹm ) = ψm E(Ym ) , and thus with ψ = ∑m ψm we get E(Ỹ ) =

ψ E (Y ) .
It may be very tempting to assume that Cov(Ỹ ) would be equal to ψCov(Y )ψ† . However, this is generally not the
† .
case. The off-diagonal blocks for m 6= m0 satisfy Cov(Ỹm , Ỹm0 ) = ψm Cov(Ym , Ym0 )ψm
0
However, for the diagonal blocks it is the case that
†
Cov(Ỹm ) =ψm Cov(Ym )ψm
+ Wm ,

Wm := ∑ ỹ x̃ ỹ†x̃ Pm ( x̃ | x ) P(Om = x ) −
x̃,x

∑0

ỹ x̃ ỹ†x̃0 Pm ( x̃ | x ) Pm ( x̃ 0 | x ) P(Om = x ).

(42)

x̃,x̃ ,x

One can note that each ‘correction term’ Wm is supported only on the subspace Ṽm , and one can moreover show
that Wm ≥ 0. To see the latter, let c ∈ Ṽm , and define z x̃ = (c, ỹ x̃ ). Then

2
2
(c, Wm c) = ∑ P(Om = x ) ∑ |z x̃ |2 Pm ( x̃ | x ) − ∑ z x̃ Pm ( x̃ | x )
= ∑ P(Om = x ) Pm ( x̃ | x ) z x̃ − ∑ Pm ( x̃ 0 | x )z x̃0 ≥ 0.
x

x̃

x̃

x,x̃

x̃ 0

If Cov(Y ) satisfies the decomposition (16) in Proposition 1 for some bipartite DAG, then one can confirm that
ψCov(Y )ψ† also satisfies the corresponding decomposition with respect to the subspaces {Ṽm }m . Moreover, since
the correction terms Wm are positive semidefinite and block-diagonal with respect to these subspaces, it follows that
Cov(Ỹ ) = ψCov(Y )ψ† + ∑m Wm also satisfies the decomposition. We can thus conclude that if the initial feature
maps Y1 , . . . , YM are universal, then the test is monotonous with respect to local operations.
As a final remark one may note that in the special case that all Pm ( x̃ | x ) correspond to deterministic mappings,
i.e., when the output x̃ is a (deterministic) function of the input x, then Pm ( x̃ | x ) Pm ( x̃ 0 | x ) = δx̃,x̃0 Pm ( x̃ | x ), and
(42) results in Wm = 0, which yields Cov(Ỹ ) = ψCov(Y )ψ† . Linear transformations φm : Vm → Ṽm all result in
mappings Ỹm = φm (Ym ) that belong to this deterministic special case (presuming that the maps φm themselves are
m m
†
not random variables) where we let Pm ( x̃ | x 0 ) = δx̃,x0 and ỹm
x̃ = φ ( y x̃ ), thus leading to Cov( φY ) = φCov(Y ) φ
(cf. the isomorphisms in (32), or the maps φ used in section VII).
IX.

A MONOTONE FAMILY OF DISTRIBUTIONS

Here we shall consider a specific family of multi-partite distributions that is monotone in the sense of the previous
section, for which the analysis of the semidefinite decomposition simplifies. We shall in particular consider the case
of the triangular scenario in figure 3, which turns out to be convenient for the comparison with the entropic tests,
which we consider in section X.

15
A.

Defining the family

Suppose that we have a collection of variables, each of which has D ≥ 2 possible outcomes. In equation (41)
we described local operations transforming an initial distribution P M . For the local operations we do in this case
choose
Pp ( x̃ | x ) := (1 − p)δx̃,x + p

1
.
D

(43)

Hence, on each variable we (independently) apply the same type of process, where with probability p we replace
the input with a uniformly distributed output, and with probability 1 − p leave the input intact. Here we choose
the input distribution to be P M ( x1 , . . . , x M ) = δx1 ,...,x M /D, where the generalized Kronecker delta is such that
δx1 ,...,x M = 1 if x1 = · · · = x M , while zero otherwise. Hence, P M ( x1 , . . . , x M ) describes M perfectly correlated
variables. By applying (41) with the local operations (43) we thus obtain a new global distribution
P̃pM:D ( x̃1 , . . . , x̃ M ) :=

1
D

∑

x1 ,...,x M

Pp ( x̃1 | x1 ) · · · Pp ( x̃ M | x M )δx1 ,...,x M ,

(44)

where we have added the extra superscript D to indicate the alphabet size of the local random variables. By
construction, this distribution is permutation symmetric over all the variables. Moreover, one can confirm that all
mono-, bi-, and higher-partite margins of P̃pM:D are independent of how many parties M the total distribution P̃pM:D
involves. For example, the bipartite margin of P̃pM:D is equal to P̃p2:D . Generally, for M0 < M it is the case that
0

∑

P̃pM :D ( x̃1 , . . . , x̃ M0 ) =

P̃pM:D ( x̃1 , . . . , x̃ M ).

(45)

x̃ M0 +1 ,...,x̃ M

Hence, every margin of every family member is another family member.
Since P̃1M:D is a product distribution over all the observable variables, it is compatible with every bipartite DAG,
while P̃0M:D is perfectly correlated, and thus would only be compatible with bipartite DAGs where some latent
variable has edges to all observable variables. One can note that the local operations in (43) are such that if
1 ≥ p0 ≥ p ≥ 0, then there exists a 1 ≥ q ≥ 0 such that
Pp0 ( x̃ | x ) =

∑0 Pq (x̃|x0 ) Pp (x0 |x).

(46)

x

(Any 1 ≥ q ≥ 0 is a valid choice if p = 1, while q = ( p0 − p)/(1 − p) if 1 > p ≥ 0.) Consequently, if p0 ≥ p, then
can be generated from P̃pM:D by local operations. By the reasoning in section VIII it thus follows that there
P̃pM:D
0
is some value p∗ where P̃pM:D switches from being incompatible to being compatible with the given bipartite DAG
(and it cannot switch back again for higher values of p). From section VIII we also know that the semidefinite test
also has this monotonic behavior if we choose universal feature maps, although the switch may occur at a lower
value of p.
B.

Within the family: the existence of a semidefinite decomposition is independent of the local alphabet size

Here we show that the semidefinite test takes a particularly simple form for the family P̃pM:D . In essence we show
that the test can be reduced to a test on an M × M matrix that only depends on p, but not on the local alphabet size
D. A similar result was obtained in (section 4.5 of) [47], for the operator inequalities described in section VI, but
for distributions of the type vδx1 ,...,x M /D − (1 − v)/D2 , while we here consider the family P̃pM:D defined by (44).
Suppose that we have an M-partite distribution P̃pM:D . We know from the previous section that this distribution
is permutation symmetric, and in particular we know from (45) that all bipartite marginal distributions are of the
form P̃p2:D , and all mono-partite marginals are of the form P̃p1:D . One can moreover confirm that
P̃p2:D ( x̃, x̃ 0 ) = (1 − p)2

1
1
δx̃,x̃0 + p(2 − p) 2 ,
D
D

P̃p1:D ( x̃1 ) =

1
.
D

(47)

In order to construct a covariance matrix, we here assume feature maps Y1 , . . . , YM that have orthonormal components (i.e., feature map Ym maps the set of possible outcomes of the mth random variable to an orthonormal

16
basis of Vm , where dim(Vm ) = D). Hence, the total space V = V1 ⊕ · · · ⊕ V M is DM-dimensional, and we can write
it as a tensor product V = V D ⊗ V M of a D-dimensional space V D and an M-dimensional space V M . By choosing
M
M
D
an orthonormal basis {em }m
=1 of V , we can identify Vm = V ⊗ Sp{ em }. In section III we defined the projectors
Pm onto the subspaces Vm , and we can write these projectors as
Pm = 1̂D ⊗ êm ,

(48)

V D,

where 1̂D is the identity operator on
and êm is the projector onto em .
The covariance matrix Cov(Y ) for the random variable Y = Y1 + · · · + YM is an MD × MD matrix and takes a
particularly simple form


Q
(1 − p )2 Q
···
(1 − p )2 Q


..
..
 (1 − p )2 Q

.
Q
.
 = 1 Q ⊗ C ( p ),
Cov(Y ) = 
(49)


..
.
D
.
2

.
.
Q
(1 − p ) Q 
(1 − p )2 Q
···
(1 − p )2 Q
Q
where we define the M × M matrix


1

(1 − p )2


 (1 − p )2
C ( p) := 

..

.

1
..
.
···

(1 − p )2

···
..
.
(1 − p )2


(1 − p )2

..

.


2
(1 − p ) 
1

(50)

and the D × D matrix Q with elements
Q x̃,x̃0 := δx̃,x̃0 −

1
,
D

x̃, x̃ 0 = 1, . . . , D.

(51)

√
Note that we can write Q = 1̂D − cc† , where c = (1, . . . , 1)† / D ∈ V D is normalized. Hence, Q is the projector
onto the ( D − 1)-dimensional subspace of V D that is the orthogonal complement to the one-dimensional subspace
spanned by c. From Q being a projector, it also follows that Q ≥ 0.
Suppose now that we have a particular bipartite DAG B with observable variables O1 , . . . , O M and latent variables
L1 , . . . , L N . As we recall from section IV, the semidefinite test is characterized via the projectors P(n) = ∑m∈ch( Ln ) Pm
as
N

Cov(Y ) = R +

∑ Cn ,

P(n) Cn P(n) = Cn ,

M

Cn ≥ 0,

n =1

∑

Pm RPm = R,

R ≥ 0.

(52)

m =1

In the present case, we can write these projectors as
P(n) = ID ⊗ P̃(n) ,

P̃(n) =

∑

P̃m ,

(53)

m∈ch( Ln )

with P̃m as in (48).
For each fixed number of observable variables M, local alphabet size D, and given bipartite DAG B, we know
that the family P̃pM:D is monotone with respect to p, in the sense that the covariance matrix Cov(Y ) satisfies the
semidefinite decomposition for all p beyond a certain threshold value, while it is violated for all values below. The
following proposition shows that this threshold is independent of D, and that it can be determined via simplified
decomposition of the matrix C ( p).
Proposition 4. Let Cov(Y ) be the covariance matrix, for feature maps with orthonormal components, corresponding to the
distribution P̃pM:D , as defined in (44), for M observable variables, and local alphabet size D ≥ 2. For each value 1 ≥ p ≥ 0
it is the case that Cov(Y ) satisfies the semidefinite decomposition (52) with respect to a given bipartite DAG B, if and only if
C ( p), defined in (50), satisfies the decomposition
N

C ( p) = R̃ +

∑

n =1

C̃n ,

P̃(n) Cn P̃(n) ,

N

C̃n ≥ 0,

∑

P̃m R̃ P̃m = R̃,

R̃ ≥ 0.

(54)

m =1

Moreover, there exists a number 1 ≥ p( B) ≥ 0 that does not depend on D, such that Cov(Y ) satisfies (52) and C ( p) satisfies
(54) for all p > p( B), while Cov(Y ) and C ( p) do not satisfy the decompositions for p < p( B).

17
Proof. First we shall show that if C ( p) satisfies the decomposition, then Cov(Y ) also satisfies the decomposition. Let
p be any 1 ≥ p ≥ 0 such that there exists a semidefinite decomposition of C ( p) as in (50). Equation (54) provides
R̃ and C̃n . Define R := Q ⊗ R̃/D and Cn := Q ⊗ C̃n /D. Thus defined, it follows that
R + ∑ Cn =
n

1
1
Q ⊗ ( R̃ + ∑ C̃n ) = Q ⊗ C ( p) = Cov(Y ).
D
D
n

Moreover, by the conditions in (54) and the observations in (53), it follows that
P(n) Cn P(n) = [1̂D ⊗ P̃(n) ][

1
Q ⊗ C̃n ][1̂D ⊗ P̃(n) ] = Cn ,
D

and Cn = Q ⊗ C̃n /D ≥ 0.
Furthermore, by the conditions in (54) and (48), it follows that
1

∑ Pm RPm = ∑[1̂D ⊗ P̃m ][ D Q ⊗ R̃][1̂D ⊗ P̃m ] = R,
m

m

and R = Q ⊗ R̃/D ≥ 0. Hence, this procedure produces a valid semidefinite decomposition of Cov(Y ). Hence, for
every p for which C ( p) has a valid decomposition, it follows that Cov(Y ) also has a valid decomposition.
Next we prove the opposite implication, namely that the existence of a decomposition of Cov(Y ) implies a
decomposition of C ( p). Let us thus assume that there is a 1 ≥ p ≥ 0 for which there exists a decomposition of
Cov(Y ) as in (52). Equation (52) provides R and Cn . Let v ∈ V D be normalized, and such that Qv = v. Such a v
always exists, since Q is a projector onto a ( D − 1)-dimensional subspace of V D and D ≥ 2. Define R̃ := Dv† Rv
and C̃n := Dv† Cn v (where one should keep in mind that e.g. v† Rv is an operator on V M , since v ∈ V D ). Hence, by
(52) and (49)
R̃ + ∑ C̃n = Dv† ( R + ∑ Cn )v = Dv† Cov(Y )v = Dv† [
n

n

1
Q ⊗ C ( p)]v = v† QvC ( p) = C ( p).
D

Moreover, by the conditions in (52) and the observations in (53), it follows that
P̃(n) C̃n P̃(n) = P̃(n) Dv† Cn v P̃(n) = Dv† [1̂D ⊗ P̃(n) ]Cn [1̂D ⊗ P̃(n) ]v = Dv† P(n) Cn P(n) v = Dv† Cn v = C̃n ,
and C̃n := Dv† Cn v ≥ 0. Furthermore, (52) and (48) yields

∑ P̃m R̃ P̃M = ∑ P̃m Dv† Rv P̃m = ∑ Dv† [1̂D ⊗ P̃m ] R[1̂D ⊗ P̃m ]v = Dv† (∑ Pm RPm )v = Dv† Rv = R̃,
m

m

m

m

and R̃ := Dv† Rv ≥ 0. Hence, we can conclude that the decomposition of Cov(Y ) induces a valid decomposition of
C ( p) as in (54).
We know from section IX A that the family P̃pM:D is monotone, in the sense that Cov(Y ) (since it is based on
orthonormal feature maps) satisfies the semidefinite decomposition for all p beyond a certain threshold value,
which we can call p( B), while violating the decomposition for all p below p( B). From the above equivalence we
conclude that the same transition is valid for C ( p) with respect to the decomposition in (54).
C.

Compatibility with the triangular DAG

Here we consider the tripartite case and determine the value of p where P̃p3:D switches from not satisfying the
semidefinite decomposition, to satisfying it, with respect to the triangular scenario in figure 3. The family of
distributions P̃pM:D , defined in (44), does in the tripartite case take the form
1
δx̃ ,x̃ ,x̃
D 1 2 3
1
+ p(1 − p)2 2 [δx̃1 ,x̃2 + δx̃1 ,x̃3 + δx̃2 ,x̃3 ]
D
1
2
+ p (3 − 2p) 3 ,
D

P̃p3:D ( x̃1 , x̃2 , x̃3 ) =(1 − p)3

(55)

18
and the matrix C ( p) and the projectors P̃(1) , P̃(2) , and P̃(3) become

1
(1 − p )2 (1 − p )2
C ( p ) =  (1 − p )2
1
(1 − p )2  ,
2
2
(1 − p ) (1 − p )
1




P̃(1)


0 0 0
= 0 1 0 ,
0 0 1



P̃(2)


1 0 0
= 0 0 0 ,
0 0 1



P̃(3)


1 0 0
= 0 1 0 .
0 0 0

As a corollary of Proposition 4 we here determine the ‘transition point’ p( B) for the family P̃pM:D in the triangular
scenario.


1
(1− p )2
2
Lemma 4. For p ∈ R it is the case that
≥ 0 ⇔ 1 − √1 ≤ p ≤ 1 + √1 .
1
2
(1− p )

Lemma 5. Let a, b, r ∈ C, then [ ar br ] ≥ 0 ⇔



b r
r a

2

2



2

≥ 0.

Corollary 1. For the family P̃p3:D in equation (55), and for feature maps with orthonormal components, the covariance
matrix Cov(Y ) has a semidefinite decomposition
with respect to the triangular bipartite DAG B in figure 3, if and only if
√
1
√
≤ p ≤ 1. Hence, p( B) = 1 − 1/ 2.
1−
2

√
One may note that P̃p3:D has a semidefinite decomposition also in the case p = 1 − 1/ 2, i.e., at the transition
point. Proposition 4 does strictly speaking leave open the nature of the transition point per se.
Proof. By Proposition 4 we know that it is sufficient to determine the p for which C ( p) decomposes as in (54). Due
to Lemma 4 it follows that
"
#
" 1
#
" 1
#
2
2
0
0
0
1
0
(1− p )2
2
1
0 (1− p )2
2

R̃ = 0, C̃1 =

, C̃2 =

0 (1− p )
2
0
0
0
1
(1− p )2 0
2

, C̃3 =

2

(1− p )2
0

(1− p ) 0
1
0
2
0
0

√
satisfy the decomposition (54) for all 1 − 1/ 2 ≤ p ≤ 1. However, this does not exclude the possibility that there
exists some other decomposition that yields a smaller p.
√
Suppose that 0 ≤ p0 < 1 − 1/ 2. By the structure of the triangular DAG, it follows that the most general
decomposition of the form (54) possible (incorporating the diagonal matrix R̃ into C̃1 , C̃2 , and C̃3 ) can be written
C ( p) = C̃1 + C̃2 + C̃3 , where
0
C̃1 =

0
0
0
b2
(1− p 0 )2
0 (1− p 0 )2
c1




, C̃2 =

a1
0 (1− p 0 )2
0
0
0
(1− p 0 )2 0
c2




, C̃3 =

a2
(1− p 0 )2 0
(1− p 0 )2
b1
0
0
0
0


,

and where a1 , a2 , b1 , b2 , c1 , c2 ≥ 0 and a1 + a2 = 1, b1 + b2 = 1, c1 + c2 = 1. By the assumed semidefiniteness of C̃1 ,
C̃2 , and C̃3 , it follows that
h
h
i
h
i
i
a1
(1− p 0 )2
a2
(1− p 0 )2
b2
(1− p 0 )2
≥
0,
M
:
=
≥ 0.
(56)
M1 :=
≥
0,
M
:
=
3
2
0 2
0 2
0 2
(1− p )

(1− p )

c2

(1− p )

b1

c1

By Lemma 5 it follows that (56) implies
M4 :=

h

c2
(1− p 0 )2
0
2
(1− p )
a1

i

≥ 0,

M5 :=

h

b1
(1− p 0 )2
0
2
(1− p )
a2

i

≥ 0,

M6 :=

h

c1
(1− p 0 )2
0
2
(1− p )
b2

i

≥ 0.

Since these matrices all are positive semidefinite, it follows that every convex combinations of them is also positive
semidefinite. Thus one can confirm that


1
1
1
1
1
1
1
(1 − p 0 )2
2
= M1 + M2 + M3 + M4 + M5 + M6 ≥ 0.
(57)
1
(1 − p 0 )2
6
6
6
6
6
6
2
0
However,
√ the positive semidefiniteness of this matrix is a contradiction to√Lemma 4, since by assumption p <
1 − 1/ 2. Hence, C ( p) can only have a decomposition as in (54) if 1 − 1/ 2 ≤ p ≤ 1. By
√ Proposition 4 it thus
follows that Cov(Y ) satisfies the semidefinite decomposition as in (52) if and only if 1 − 1/ 2 ≤ p ≤ 1.

19
X.

COMPARISON WITH ENTROPIC TESTS

Outer relaxations of the compatibility set corresponding to latent variable structures, based on information theoretic inequalities, have been considered previously [27–30]. Here we make a numerical comparison of the performance of these entropic tests and the semidefinite test. A basic challenge is that we in practice do not know the true
set of compatible distributions. However, since we are dealing with outer approximations, a reasonable approach
is to compare how ‘strict’ the tests are, i.e., if one test generally tends to reject more distributions than the other.
Given the rather radical difference in appearance and functional form between the semidefinite test and tests
based on entropy inequalities (described in more detail in the next section) it is far from clear how these tests
relate, or if there even is a clear-cut relation in the sense that one would be systematically stronger than the other.
An indication can be gained from [47], where it was found that tests based on operator inequalities, of the type
described in section VI, appear to be stronger than the entropic ones for small alphabet sizes, but that there seems
to be a switchover for larger alphabets (see section 4.5 of [47]). Here we confirm similar trends for the semidefinite
test in comparison with the entropic test, where we focus on the ‘triangular’ DAG described in figure 3. In case of
binary variables, we do in section X B make a comparison over an ensemble of randomly constructed distributions.
However, our major testbed for these comparisons (in section X C) is the family of distributions P̃pM:D introduced
in section IX.
A.

Entropy inequalities for the triangular DAG

We focus on the triangular DAG in figure 3, since this has been a rather well investigated scenario with several known entropic inequalities associated with it. For the three observable variables O1 , O2 , O3 we let H (1) :=
H (O1 ) := − ∑ j P(O1 = j) log2 P(O1 = j) denote the Shannon entropy, and in a similar manner H (12) := H (O1 , O2 ),
etc, where ‘log2 ’ denotes the base 2 logarithm. The first inequality (58) for the triangular scenario was obtained in
[6] (see also [27] and [30])
E1 := − H (1) − H (2) − H (3) + H (13) + H (12) ≥ 0.

(58)

The following two inequalities were derived in [27]
E2 := − 3H (1) − 3H (2) − 3H (3) + 2H (12) + 2H (13) + 3H (23) − H (123) ≥ 0,

(59)

E3 := − 5H (1) − 5H (2) − 5H (3) + 4H (12) + 4H (13) + 4H (23) − 2H (123) ≥ 0.

(60)

Finally, inequalities (61) to (63) were obtained in [30]
E4 := − 4H (1) − 4H (2) − 4H (3) + 3H (12) + 3H (13) + 4H (23) − 2H (123) ≥ 0,

(61)

E5 := − 2H (1) − 2H (2) − 2H (3) + 3H (12) + 3H (13) + 3H (23) − 4H (123) ≥ 0,

(62)

E6 := − 8H (1) − 8H (2) − 8H (3) + 7H (12) + 7H (13) + 7H (23) − 5H (123) ≥ 0.

(63)

One should observe that the expressions in (58), (59), and (61) are not symmetric under permutations of the
O1 , O2 , O3 , and thus each of these generate two more inequalities. Whenever one of these inequalities is violated
we can conclude that the observable distribution cannot originate from the bipartite DAG in figure 3.
One may note that all of these entropic inequalities, apart from (58), depend on the full tripartite distribution,
while the semidefinite test only takes into account the mono- and bipartite marginals. One may thus intuitively
suspect that the semidefinite test would be at a disadvantage compared to these tripartite entropic tests.
B.

Rejection rates in random Ising models: The binary case

For a numerical comparison between the entropic and the semidefinite test for the triangular scenario in figure
3, we assume binary variables O1 , O2 , O3 ∈ {−1, 1}, and distributions P( x ) := P(O1 = x1 , O2 = x2 , O3 = x3 ),

20
x := ( x1 , x2 , x3 ) given by an Ising interaction model [50, 51]
†

P( x ) =

e− x Jx
,
Z

(64)

with Z being the normalization constant, and where J is a real 3 × 3 matrix. For each single instance of this model
we draw the elements of J independently from a Gaussian distribution with zero mean and variance 1.
For the semidefinite test we choose (universal) feature maps that associate the outcomes of the random variables
to elements of orthonormal bases, thus resulting in a 6 × 6 covariance matrix. The semidefinite test was implemented via a semidefinite program that minimizes a constant function, thus effectively testing whether there exist
any feasible elements.
For each instance over 106 independent repetitions of the Ising model in (64) we performed the semidefinite test,
as well as tested the entropic inequalities (58) to (63) together with all their permutations.
The following table gives the approximate fraction of rejections. In the table, E1∪ (and analogously for E2∪ and E4∪ )
means that we test the inequality in (58) as well as its two permutations, and we count the fraction of the sample
that violates any of these three inequalities, i.e., we take the union of the corresponding rejection regions. The entry
‘Combined’ signifies the fraction of rejections due to violations of at least one of the inequalities (58) to (63) or any
of their permutations. Finally ‘Semidefinite’ denotes the fraction of rejections for the semidefinite test.
E1∪ : 0.57,

E2∪ : 0.60,

E3 : 0.54,

E4∪

E5 : 0.40,

E6 : 0.60,

: 0.63,

Combined : 0.64,
Semidefinite : 0.77
Since the fraction of rejections is higher for the semidefinite test than for all the entropic inequalities combined,
this suggests that the semidefinite test in some sense has a ‘larger’ region of rejection, and thus would be the
stronger test. To get some information on the relation between the two regions of rejections, we checked whether
we could find any case where the semidefinite test accepted an instance that had been rejected by some of the
entropic inequalities. However, we could find no such case, which suggests that the region of rejection for the
collection of entropic inequalities is contained in the region of rejection for the semidefinite test.

C.

Comparison on a monotone family of distributions

In section VIII we argued that the compatibility of distributions with respect to a given bipartite DAG is
monotonous under local operations, and that the semidefinite test also satisfies this property if we use universal feature maps. In section IX C we introduced a particular tripartite family of distributions P̃p3:D that can be
generated from the appropriate maximally correlated distribution by local operations, and
√ where we could show
that this family cut the boundary of the semidefinite compatibility region at p = 1 − 1/ 2. Here we compare the
performance of the entropic tests with the semidefinite test on this particular family of distributions.

1.

Binary variables

We begin in the case of three binary variables, i.e., each variable can take two possible values. In this case P̃p3:2
reduces to
1
(4 − 6p + 3p2 ), if x̃1 = x̃2 = x̃2 ,
3:2
(65)
P̃p ( x̃1 , x̃2 , x̃3 ) = 8
1
otherwise.
8 p (2 − p ),
In figure 6 we plot E1 , . . . , E6 as functions of the parameter p. The entropic test rejects the model for a given p
whenever one of these functions become negative. For the calculation of the covariance matrix we choose feature
maps that assign orthonormal vectors to the outcomes of the three random variables, thus being universal. As one
can see from figure 6, the semidefinite test starts to reject at higher values of p than all the entropic tests, and is
thus closer to the true value p∗ of the transition than any of the entropic tests.

21
2.0

E1

1.5

E2

1.0

E3
0.5

E4
0.1

0.2

0.3

0.4

0.5

p

E5

-0.5

E6

-1.0

FIG. 6. Entropic versus semidefinite for binary variables. For three binary variables described by the distribution P̃p3:2 in
equation (65), we calculate E1 , . . . , E6 defined in (58) to (63) as functions of the parameter p. When one of these functions turns
negative, it implies that the distribution P̃p3:2 is not compatible with the triangular bipartite DAG in figure 3. Moreover, we
determine the 6 × 6 covariance matrix with √
respect to feature maps that assign orthogonal vectors to the outcomes. The red
vertical line indicates the value p = 1 − 1/ 2 ≈ 0.29, determined in section IX C, below which the semidefinite test rejects
the resulting covariance matrix. As one can see, the semidefinite test has the larger region of rejection, and is in this sense the
stronger test for this particular binary setup.

2.

Asymptotics of the E1 test

E1 defined in (58) is the only of the entropic quantities (58) to (63) that solely includes mono- and bipartite
marginals; the others also depend on the full tripartite distribution. Since the test based on E1 and the semidefinite
test thus are on ‘equal footing’ in this regard, it appears relevant to pay some additional attention to the relation
between these two tests. In section IX C, and in particular in Corollary 1, we proved that the distribution P̃p3:D ,
√
defined in equation (55), satisfies the semidefinite test if and only if p ≥ 1 − 1/ 2, irrespective of the alphabet
size D. Hence, the ‘transition point’ for the semidefinite test is independent of D for this particular family of
distributions.
Here we shall show that the corresponding transition point for the test based on E1 lies below
√
1 − 1/ 2, but asymptotically approaches this value as D increases.
The family of distributions P̃p3:D in (55) is permutation symmetric with respect to the three parties, and E1 can,
via equation (47), be evaluated as
E1 = − 3H (1) + 2H (12)

= − 3 log D
h
1
1 i
− 2(1 − ) p(2 − p) log p(2 − p) 2
D
D
h
h
1i
1
1 i
2
− 2 (1 − p ) + p (2 − p )
log (1 − p)2 + p(2 − p) 2 .
D
D
D

(66)

One can confirm that E1 (0) = − log D, E1 (1) = log D, and
h
dE1
1
(1 − p )2 i
= 4(1 − )(1 − p) log 1 + D
,
dp
D
p (2 − p )

(67)

which is non-negative for 0 ≤ p ≤ 1. Hence, for each fixed D, the function E1 is monotonically increasing for
0 ≤ p ≤ 1, and thus the equation E1 ( p) = 0 has exactly one root, which is situated somewhere in the open interval
(0, 1). Thus, analogous to the semidefinite test, the test based on E1 will reject all elements in the family P̃p3:D below
a certain transition point, and accept all distributions above that value. Next one can confirm that
1
2D
1
2D
E1 (1 − √ ) = log
+ log
> 0,
D+1 D
D+1
2

D = 2, 3, . . . .

Since E1 thus is√
monotonously increasing with respect to p, we can conclude that the root p̃ of E1 ( p̃) = 0 is such
that p̃ < 1 − 1/ 2 for all D ≥ 2. Finally we wish to the determine the asymptotic value of the root p̃ as D → ∞.

22
To this end we rewrite (66) such that we highlight the different orders of dependency on D,


1 
1
E1 =2 1 + √ − p p − (1 − √ ) log D
2
2
− 2p(2 − p) log[ p(2 − p)] − 4(1 − p)2 log(1 − p)
1
− 2p(2 − p) log D
D
h
p (2 − p ) 1 i
2
− 2(1 − p) log 1 +
(1 − p )2 D


1
p (2 − p )
+ 2p(2 − p) log
D
(1 − p )2
h
1
p (2 − p ) 1 i
− 2p(2 − p) log 1 +
.
D
(1 − p )2 D

(68)

On any interval δ ≤ p ≤ 1 − δ, with 1/2 > δ > 0, the last four lines of (68) each approaches zero as D → ∞.
Moreover, one can note that the leading order term (in the first line) does
√ for each fixed D increase monotonically
for 0 ≤ p ≤ 1 and switches from negative to positive at p = 1 − 1/ √2. If one fixes e > 0, one can realize that
for all sufficiently
√ large D, it is the case that E1 ( p) > 0 for all 1 − 1/ 2 + e ≤ p ≤ 1 − δ, and E1 ( p) ≤ 0 for all
0 ≤ p√
≤ 1 − 1/ 2 − e. We can thus conclude that the root p̃ of E1 ( p̃) = 0 in the interval 0 ≤ p̃ ≤ 1 approaches
1 − 1/ 2 as D → ∞.
3.

Comparison on increasing alphabets

p
0.32
0.28
0.24
0.2
0.16
0.12

àààààààààà
ààààààààà
àààààà
àààààà
à
à
à
àà
ààà
àà
àà
à
à
à
à
à
à
æ
ææææææææææææææ
ææææææææææ
æææææææ
æææææ
æ
æ
æ
æææ
ææ
ææ
æ
æ

2

10

20

30

40

50

à

Combined entropic tests

æ

E1 entropic test
Semidefinite test

Alphabet
Size

FIG. 7. Entropic versus semidefinite tests for increasing alphabet sizes. For the distribution P̃p3:D in (55) we compare the
entropic and semidefinite test as functions of D. Here we determine the smallest value of p for which the respective test accepts
P̃p3:D , as a function of the local alphabet size D. From section IX C we know that the transition point for the semidefinite test is
√
p = 1 − 1/ 2 ≈ 0.29, independently of D (the red dashed line). We also plot (blue squares) the minimal value of p for which all
of the entropic inequalities (58) to (63) are satisfied, as a function of D. The transition point for this entropic test crosses the red
line at D = 32. Hence, for the class of functions P̃p3:D , the entropic tests becomes stronger than the semidefinite test for alphabet
sizes beyond 32. Finally, we plot (green circles) the minimal value√of p for which E1 ( p) ≥ 0, as a function of D. By section X C 2
we know that this transition point asymptotically reaches 1 − 1/ 2.

In the previous section we found that the semidefinite test is stronger than the entropic one, for testing membership of distributions of the form P̃p3:2 . Here, we investigate how these two classes of tests compare when the
size D of the local alphabets increases. We know from section IX C that the semidefinite test is independent of D
for this particular family of distributions. It could thus potentially be the case that the entropic test would become
stronger than the semidefinite test for sufficiently large alphabet sizes. This is indeed what we find in the numerical
evaluation of the entropic test, which we display in figure 7.

23
As pointed out in section X C 2, all the entropic inequalities, apart from E1 , depend on the full tripartite distribution, while E1 and the semidefinite test only utilize the bi- and mono-partite margins. We already know from the
previous section that the test based on E1 always is weaker that the semidefinite test for the family P̃p3:D , but that
it approaches the semidefinite test in the limit of large alphabet sizes D. As suggested by the plot in figure 7, the
convergence is very slow. As an additional indication one may note that for an alphabet size of D = 107 the root of
the equation E1 ( p) = 0 is p ≈ 0.26 while the limit is p ≈ 0.29.

XI.

SUMMARY AND OUTLOOK

In this work we have considered the constraints imposed by a large class of causal structures on the covariance
matrix of the observed variables. More specifically, we have shown that each bipartite DAG induces a decomposition that every covariance matrix resulting from the corresponding causal model has to satisfy. Such decompositions
can be formulated in terms of semidefinite programs that allow for a straightforward and efficient computational
treatment of the problem (as opposed to algebraic geometry solutions). A violation of the condition imposed by
the bipartite DAG under test (or in other terms, the non-feasibility of the semidefinite program) thus implies that
the observed covariance matrix is not compatible with it. We have also shown that every decomposition associated
with a bipartite DAG can be realized by a causal model on that graph.
Furthermore, we have made comparisons between the performance of the semidefinite test and tests based on
information theoretic inequalities formulated in terms of entropies, where the results indicate that the semidefinite
test outperforms the entropic test for moderate alphabet sizes of the random variables, while the latter become
more powerful for large alphabet sizes.
These results open several directions for future research. Here, we have restricted attention to characterising the
set of covariance matrices compatible with a given causal structure. In real-world situations however, the covariance matrix is unknown and has to be estimated from a limited number of samples drawn from the underlying
distribution. This raises the question of how to turn the theory developed here into statistical hypothesis tests for
a presumed causal stucture. An obvious idea would be to construct a confidence region for the estimated covariance matrix and reject the hypothesis if the confidence region does not intersect the set compatible with the causal
assumption. We speculate, though, that it might be simpler to obtain statistically sound results by employing convex duality, as explained in the context of figure 4. Indeed, assume that X is such that all compatible covariance
matrices have non-negative inner product with X. The inner product betweeen X and the true covariance matrix
is a scalar linear
 function of the distribution of the observable variables. A one-sided statistical hypothesis test for
tr X Cov(Y ) ≤ 0 with any desired significance level is therefore easy to construct. It will automatically also test
the causal hypothesis at the same significance level. While any X gives rise to such a test, their power to identify a
given true incompatible distribution may very wildly. One way of making an informed choice for X would be as
follows: Split the samples into two parts. If the empirical covariance matrix of the first part is compatible with the
hypothesis, accept. If not, the dual SDP (26) will identify a witness X ? that seperates the empirical matrix from the
compatible set. Now use the test based on X ? with the second part of the samples. We leave the details to future
work.
Another immediate question is to better understand the relation between the semidefinite and the entropic
tests. Similarly, it would be highly desirable to combine our results with other tools that have very recently been
proposed in order to characterize complex DAGs [23–25]. On a more general level it is noteworthy that by restricting
to covariance we turn a highly non-linear problem into what essentially is a convex optimization. Understanding
how far this can be pushed (considering higher order moments, for instance) would certainly give us new geometric
insights on the nature of this problem. Since we here have focused on a setting where all correlations of observed
variables are due to latent variables, it is very reasonable to ask if tests based on covariances can be extended to
more general types of DAGs that do not have this bipartite structure.
From a more fundamental perspective our work may have implications for the current research program on the
foundations of quantum physics. Bayesian networks have attracted growing attention as means to understand
the role of causality in quantum mechanical systems [5–13]. One may thus ask whether the methods we have
employed here can be generalized to the case of quantum causal structures, where for example some nodes in the
graph represent quantum states without a classical analogue. Any positive results along this line would certainly
be highly relevant in the context of quantum causal modeling and once more highlight the very fruitful interplay
between the fields of causal inference and foundational aspects of quantum mechanics.

24
ACKNOWLEDGMENTS

We thank Thomas Kahle and Johannes Textor for productive discussions during the early stages of this project.
This work has been supported by the Excellence Initiative of the German Federal and State Governments (Grants
ZUK 43 and 81), the ARO under contract W911NF-14-1-0098 (Quantum Characterization, Verification, and Validation), and the DFG (SPP1798 CoSIP).

[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]

J. Pearl, Causality (Cambridge University Press, Cambridge, 2009).
P. Spirtes, N. Glymour, and R. Scheienes, Causation, Prediction, and Search, 2nd ed. (The MIT Press, 2001).
Nir Friedman, “Inferring cellular networks using probabilistic graphical models,” Science 303, 799–805 (2004).
G. Ver Steeg and A. Galstyan, “A sequence of relaxations constraining hidden variable models,” in Proceedings of the 27th
conference on Uncertainty in Artificial Intelligence (2011).
M. S. Leifer and Robert W. Spekkens, “Towards a formulation of quantum theory as a causally neutral theory of bayesian
inference,” Phys. Rev. A 88, 052130 (2013).
T. Fritz, “Beyond bell’s theorem: correlation scenarios,” New J. Phys. 14, 103001 (2012).
Tobias Fritz, “Beyond bell’s theorem ii: Scenarios with arbitrary causal structure,” Communications in Mathematical
Physics 341, 391–434 (2016).
Joe Henson, Raymond Lal, and Matthew F Pusey, “Theory-independent limits on correlations from generalized bayesian
networks,” New J. Phys. 16, 113043 (2014).
Rafael Chaves, Christian Majenz, and David Gross, “Information–theoretic implications of quantum causal structures,”
Nat. Commun. 6, 5766 (2015).
Jacques Pienaar and Caslav Brukner, “A graph-separation theorem for quantum causal models,” New J. Phys. 17, 073020
(2015).
Katja Ried, Megan Agnew, Lydia Vermeyden, Dominik Janzing, Robert W Spekkens, and Kevin J Resch, “A quantum
advantage for inferring causal structure,” Nature Physics 11, 414–420 (2015).
Fabio Costa and Sally Shrapnel, “Quantum causal modelling,” New Journal of Physics 18, 063032 (2016).
Dominic Horsman, Chris Heunen, Matthew F Pusey, Jonathan Barrett, and Robert W Spekkens, “Can a quantum state over
time resemble a quantum state at a single time?” arXiv preprint arXiv:1607.03637 (2016).
Itamar Pitowsky, “Correlation polytopes: Their geometry and complexity,” Mathematical Programming 50, 395–414 (1991).
J. Pearl, “On the testability of causal models with latent and instrumental variables,” in Proceedings of the 11th conference on
Uncertainty in Artificial Intelligence (1995) pp. 435–443.
D. Geiger and C. Meek, “Quantifier elimination for statistical problems,” in Proceedings of the 15th conference on Uncertainty
in Artificial Intelligence (1999) pp. 226–235.
B. Bonet, “Instrumentality tests revisited,” in Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence (2001)
pp. 48–55.
L. D. Garcia, M. Stillman, and B. Sturmfels, “Algebraic geometry of bayesian networks,” Journal of Symbolic Computation
39, 331–355 (2005).
C. Kang and J. Tian, “Inequality constraints in causal models with hidden variables,” in Proceedings of the 22nd Conference
on Uncertainty in Artificial Intelligence (2006) pp. 233–240.
C. Kang and J. Tian, “Polynomial constraints in causal bayesian networks,” in Proceedings of the 23rd Conference on Uncertainty
in Artificial Intelligence (2007) pp. 200–208.
Robin J Evans, “Graphical methods for inequality constraints in marginalized dags,” in 2012 IEEE International Workshop on
Machine Learning for Signal Processing (IEEE, 2012) pp. 1–6.
Ciarán M Lee and Robert W Spekkens, “Causal inference via algebraic geometry: necessary and sufficient conditions for
the feasibility of discrete causal models,” arXiv preprint arXiv:1506.03880 (2015).
Rafael Chaves, “Polynomial bell inequalities,” Phys. Rev. Lett. 116, 010402 (2016).
Denis Rosset, Cyril Branciard, Tomer Jack Barnea, Gilles Pütz, Nicolas Brunner, and Nicolas Gisin, “Nonlinear bell inequalities tailored for quantum networks,” Phys. Rev. Lett. 116, 010403 (2016).
Elie Wolfe, Robert W Spekkens, and Tobias Fritz, “The inflation technique for causal inference with latent variables,” arXiv
preprint arXiv:1609.00672 (2016).
Philipp Moritz, Jörg Reichardt, and Nihat Ay, “Discriminating between causal structures in bayesian networks given partial
observations,” Kybernetika 50 (2014).
Rafael Chaves, Lukas Luft, and David Gross, “Causal structures from entropic information: geometry and novel scenarios,”
New Journal of Physics 16, 043001 (2014).
R. Chaves, L. Luft, T. O. Maciel, D. Gross, D. Janzing, and B. Schölkopf, “Inferring latent structures via information
inequalities,” Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence , 112–121 (2014).
Bastian Steudel and Nihat Ay, “Information-theoretic inference of common ancestors,” Entropy 17, 2304–2327 (2015).

25
[30] Mirjam Weilenmann and Roger Colbeck, “Non-shannon inequalities in the entropy vector approach to causal structures,”
arXiv preprint arXiv:1605.02078 (2016).
[31] Samuel L. Braunstein and Carlton M. Caves, “Information-theoretic bell inequalities,” Phys. Rev. Lett. 61, 662–665 (1988).
[32] N. J. Cerf and C. Adami, “Entropic bell inequalities,” Phys. Rev. A 55, 3371–3374 (1997).
[33] Rafael Chaves and Tobias Fritz, “Entropic approach to local realism and noncontextuality,” Phys. Rev. A 85, 032113 (2012).
[34] T. Fritz and R. Chaves, “Entropic inequalities and marginal problems,” IEEE Trans. Inform. Theory 59, 803 (2013).
[35] Rafael Chaves, “Entropic inequalities as a necessary and sufficient condition to noncontextuality and locality,” Phys. Rev.
A 87, 022102 (2013).
[36] Rafael Chaves, Jonatan Bohr Brask, and Nicolas Brunner, “Device-independent tests of entropy,” Phys. Rev. Lett. 115,
110501 (2015).
[37] Rafael Chaves and Costantino Budroni, “Entropic nonsignaling correlations,” Phys. Rev. Lett. 116, 240501 (2016).
[38] Robin J Evans, “Graphs for margins of bayesian networks,” Scandinavian Journal of Statistics 3, 625–648 (2016).
[39] C. Branciard, N. Gisin, and S. Pironio, “Characterizing the nonlocal correlations created via entanglement swapping,”
Phys. Rev. Lett. 104, 170401 (2010).
[40] Cyril Branciard, Denis Rosset, Nicolas Gisin, and Stefano Pironio, “Bilocal versus nonbilocal correlations in entanglementswapping experiments,” Phys. Rev. A 85, 032119 (2012).
[41] Armin Tavakoli, Paul Skrzypczyk, Daniel Cavalcanti, and Antonio Acín, “Nonlocal correlations in the star-network configuration,” Physical Review A 90, 062109 (2014).
[42] Christopher J Wood and Robert W Spekkens, “The lesson of causal discovery algorithms for quantum correlations: causal
explanations of bell-inequality violations require fine-tuning,” New J. Phys. 17, 033002 (2015).
[43] J. S. Bell, “On the Einstein–Podolsky–Rosen paradox,” Physics 1, 195 (1964).
[44] Dylan J Saunders, Adam J Bennet, Cyril Branciard, and Geoff J Pryde, “Experimental demonstration of non-bilocal quantum correlations,” arXiv preprint arXiv:1610.08514 (2016).
[45] Gonzalo Carvacho, Francesco Andreoli, Luca Santodonato, Marco Bentivegna, Rafael Chaves, and Fabio Sciarrino, “Experimental non-locality in a quantum network,” arXiv preprint arXiv:1610.03327 (2016).
[46] Lieven Vandenberghe and Stephen Boyd, “Semidefinite programming,” SIAM review 38, 49–95 (1996).
[47] Kai von Prillwitz, Statistical aspects of inferring Bayesian networks from marginal observations, Master’s thesis, Fakultät für
Mathematik und Physik der Albert-Ludwigs-Universität Freiburg (2015).
[48] Thomas M Cover and Joy A Thomas, Elements of information theory (John Wiley & Sons, 2012).
[49] B. Schölkopf and A. J. Smola, Learning with Kernels (MIT Press, 2002).
[50] G. Gallavotti, Statistical mechanics (Springer, 1999).
[51] D. Koller and N. Friedman, Probabilistic Graphical Models (MIT Press, 2009).

