# Probabilistic Modeling Using Tree Linear Cascades

Nicholas C. Landolfi1 and Sanjay Lall2 1Nicholas C. Landolfi is with the
Department of Computer Science, Stanford University, Stanford, CA 94305
<EMAIL_ADDRESS>Lall is with the Department of Electrical
Engineering, Stanford University, Stanford, CA 94305<EMAIL_ADDRESS>
###### Abstract

We introduce tree linear cascades, a class of linear structural equation
models for which the error variables are uncorrelated but need not be Gaussian
nor independent. We show that, in spite of this weak assumption, the tree
structure of this class of models is identifiable. In a similar vein, we
introduce a constrained regression problem for fitting a tree-structured
linear structural equation model and solve the problem analytically. We
connect these results to the classical Chow-Liu approach for Gaussian
graphical models. We conclude by giving an empirical-risk form of the
regression and illustrating the computationally attractive implications of our
theoretical results on a basic example involving stock prices.

##  I Introduction

Throughout engineering and the sciences, one is often interested in modeling
functional or causal relationships among high-dimensional multivariate data.
Examples range from molecular pathway modeling in genomics [28] and fMRI brain
imaging in neuroscience [24], to system performance monitoring in engineering
[11]. In the context of control and decision problems, such aspects arise, for
example, when modeling networks of dynamical systems [14, 26, 4].

Structural equation models and functional causal models are popular approaches
[21]. These models associate each variable with a node in a directed acyclic
graph and model the variable as a function of its parents (if any) in the
graph and some random noise. Both in theory and practice, one is interested in
(a) identifying the graphical structure from observational data and (b)
estimating the functional relations.

Not much can be said without assumptions on the class of models. Consequently,
functional assumptions (e.g., linearity, additive partial linearity) and
distributional assumptions (e.g., Gaussian, independent) are common. Even so,
the identifiability of the models is nontrivial [25]. It is natural to look
for subclasses of these models with favorable identifiability and estimation
properties.

#### Tree Linear Cascades

In this paper, we introduce a class of these models with linear functional
relations and a directed tree graphical structure. We prove that the tree
structure is identifiable under the weak assumption that the error variables
in the model are uncorrelated.

Given a tree $T$ and root vertex $r$, we call a random vector $x$ a tree
linear cascade on an uncorrelated random vector $e$ with respect to a sparse
matrix $A$ if $x$ satisfies $x=Ax+e$. The sparsity pattern of $A$ matches that
of the directed adjacency matrix of the rooted tree $(T,r)$. For precise
definitions, see Section III. As usual with structural equation models, we
interpret a tree linear cascade by associating the components of $x$ with the
vertices of $T$. Then $x_{i}$ is a linear function of its parent (if any) plus
some noise $e_{i}$.

Parallel to finding favorable model classes, it is natural to look for
favorable fitting methods. A reasonable approach is to pose a problem that
simultaneously finds a graphical structure and functional relations to give
good fit. Such formulations lead to computational difficulties, however,
because the number of directed graphs is exponential in the number of
variables and the estimation may be nontrivial.

#### Cascade Regression

In this paper, we introduce and solve a regression problem to fit a tree-
structured linear structural equation model. Although there are exponentially
many directed trees, we show that the problem reduces to a tractable maximum
spanning tree problem.

Given a random vector $x$, cascade regression finds a rooted tree $(T,r)$ and
set of coefficients $A$ matching the sparsity pattern of the directed
adjacency matrix of $(T,r)$ to minimize
$\mathbb{E}\left\lVert{Ax-x}\right\rVert$. For a precise definition, see
Problem 1 of Section IV-B. In theory, this problem correctly recovers a tree
linear cascade. In practice, it has a natural instantiation as empirical risk
minimization and the theoretical results lead to a computationally attractive
practical technique.

Our solution to this problem is reminiscent of the classical results of Chow
and Liu [3]. In particular, for the Gaussian density case, in which the
solution also involves a maximum spanning tree problem involving squared
correlations [29].

#### Gaussian Chow-Liu

Indeed, we show (easily, with our earlier results) that the trees found by
both approaches coincide. The Chow-Liu approach to approximating a density
$g:\mathbb{R}^{d}\to\mathbb{R}$ by one which factors according to a tree finds
a tree $T$ and a density $f$ factoring according to $T$ to minimize the
Kullback-Leibler divergence $d_{kl}(g,f)$. The famous solution to this problem
produces the maximum spanning tree of a graph weighted by pairwise mutual
informations of the components of $g$. The connection to cascade regression
suggests interpreting the regression as an approximation technique for
modeling a high-dimensional distribution with a simpler and sparser low-
dimensional one.

These results relate to a nice line of work in the control literature which
explores reconstructing the topology of a network of interconnected dynamical
systems from observational data [15, 4, 16, 27]. That formulation leads to
similar identifiability and estimation results for a set of linear dynamical
systems with a tree connection structure [14].

#### Contributions

The principal novel theoretical contributions of this paper are the statement
and proof of the maximum spanning tree property for tree linear cascades
(Theorem 1) and the posing and solution of cascade regression (Theorem 2). We
also give interesting, but easier, corollaries connecting tree linear cascades
to cascade regression (Corollary 1) and cascade regression to Gaussian Chow-
Liu approximation (Corollary 2). To our knowledge, none of these results
appears in prior literature.

#### Outline

In Section I-A we review notation and preliminaries. In Section II we discuss
related work. In Section III we introduce tree linear cascades and prove their
maximum spanning tree property. In Section IV we pose and solve the
simultaneous cascade regression problem. In Section V we review the classical
results of Chow and Liu for the density case and give a novel connection to
simultaneous cascade regression. We give the empirical form of cascade
regression and a basic illustration on stock prices in Section VI. We conclude
in Section VII.

###  I-A Notation and preliminaries

As usual, a density on $\mathbb{R}^{d}$ is a function
$f:\mathbb{R}^{d}\to\mathbb{R}$ satisfying $f\geq 0$ and $\int f=1$. For
$j\neq i$ and $i,j\in\left\\{1,2,\dots,d\right\\}$, the marginal densities
$f_{i}:\mathbb{R}\to\mathbb{R}$ and $f_{ij}:\mathbb{R}^{2}\to\mathbb{R}$ are
defined by

$f_{i}(\xi)=\int_{x_{i}=\xi}f(x)dx,\quad
f_{ij}(\xi,\gamma)=\int_{(x_{i},x_{j})=(\xi,\gamma)}f(x)dx.$

The conditional density $f_{i\mid j}:\mathbb{R}^{2}\to\mathbb{R}$ is defined
to satisfy $f_{ij}=f_{i\mid j}f_{j}$ for $j\neq i$ and
$i,j\in\left\\{1,2,\dots,d\right\\}$. As usual, a Gaussian density $f$ on
$\mathbb{R}^{d}$ has mean $\mu\in\mathbb{R}^{d}$ and positive definite
covariance $\Sigma\in\mathbb{R}^{d\times d}$. As usual, the Kullback-Liebler
divergence of a density $f$ relative to a density $g$ is
$d_{kl}(g,f)=h(g,f)-h(g)$ where $h(g)=-\int_{g(x)>0}g(x)\log g(x)dx$ is the
differential entropy and $h(g,f)=-\int_{f(x)>0}g(x)\log f(x)dx$ is the
differential cross entropy of $f$ relative to $g$. For Gaussian $f$,
$d_{kl}(f_{ij},f_{i}f_{j})=-(\nicefrac{{1}}{{2}})\log(1-\Sigma_{ij}^{2}/\left(\Sigma_{ii}\Sigma_{jj}\right))$.

As usual, we fix a probability space $(\Omega,\mathcal{A},\mathbb{P})$. A
random variable is a measurable function $x:\Omega\to\mathbb{R}^{d}$. The
expectation of $x$ is $\mathbb{E}(x)=\int xd\mathbb{P}$. The covariance of $x$
is
$\text{cov}(x)=\mathbb{E}\left(x-\mathbb{E}x\right)\left(x-\mathbb{E}x\right)^{\top}$.
The correlation between components $i$ and $j$ of $x$ is
$\mathbb{E}(x_{i}x_{j})/\sqrt{\mathbb{E}(x_{i}^{2})\mathbb{E}(x_{j}^{2})}$.

As usual, a tree is a connected acyclic undirected graph. The key property is
that there is a unique path between any two vertices. A rooted tree is a tree
and a distinguished vertex which we call the root. The first vertex $j$ on the
path from $i$ to the root is the parent of $i$ and $i$ is the child of $j$.
Since each nonroot vertex has one parent, we write $\text{pa}_{i}=j$ to mean
that the parent of the nonroot vertex $i$ is vertex $j$. A vertex $j$ is an
ancestor of $i$ if there is a directed path from $j$ to $i$. We denote the set
of ancestors of a vertex $i$ by $\mathop{\mathrm{anc}}(i)$.

A density $f$ factors according to a tree $T$ rooted at vertex $i$ on
$\left\\{1,2,\dots,d\right\\}$ if $f=f_{i}\prod_{j\neq
i}f_{j\mid\text{pa}_{j}}.$ It happens that if $f$ factors according to a tree
rooted at some vertex, it factors according to that same tree rooted at any
vertex, and we can therefore say $f$ factors according to $T$ without
ambiguity (see [19]). We call such densities tree densities.

A weighted graph $(G,W)$ is an undirected graph $G=(V,E)$ along with a weight
function $W:E\to\mathbb{R}$. The weight of a subgraph $(V,F)$ where $F\subset
E$ is $\sum_{e\in F}W(e)$. A subgraph of $G$ spans $G=(V,E)$ if all vertices
in $V$ are connected. A graph is a forest if it has no cycles. If a forest $F$
spans a graph $G=(V,E)$ then $(V,F)$ is a tree. A maximum spanning tree of $G$
with respect to $W$ is one whose weight is at least as large as that of all
other trees which span $G$.

##  II Related Work

There is an extensive literature using graphs to describe joint probability
distributions and model functional relationships between multivariate data.
Standard texts on probabilistic graphical models include [20], [12], [9], and
[19]. In this setting, one uses the graph to describe the factoring properties
of a distribution. There are two variants of models. The first uses directed
acyclic graphs and the models are called Bayesian networks. The second uses
undirected graphs and the models are called Markov random fields. For trees,
these coincide. A distribution factors according to an (undirected) tree $T$
if and only if it factors according to every rooted (directed) tree $(T,r)$
for $r$ a vertex of $T$ [19].

In both cases, one associates the component random variables with nodes of the
graph. The graphical structure encodes the conditional independence relations
of the variables. It is a basic task of machine learning to learn a graph $G$
along with a distribution factoring according to $G$ from data. This task,
called structure learning, is often posed as a maximum likelihood problem. In
general, it is intractable [9]. The case when $G$ is a tree, however, is a
notable exception.

The use of trees to describe the factorization of a joint distribution $p$ can
be traced to the celebrated work of Chow and Liu [3]. The authors posed and
solved a problem to approximate an arbitrary distribution $q$ by a
distribution $p$ which factors according to a tree. The key quantity is the
mutual information between pairs of variables, and the solution method
involves finding a maximal spanning tree of a graph whose edges are weighted
by mutual informations.

The results of Chow and Liu also solved the structure learning problem in the
case of trees. The approximation criterion used is the Kullback-Leibler
divergence of $p$ with respect to $q$. In the case that $q$ is an empirical
distribution of some dataset, the K-L divergence is the likelihood plus a
constant. This result has had widespread application [6, 7, 17]. Later authors
considered learning the tree structure specifically for discrimination [30] or
using the Akaike information criterion [5]. Recent work has compared these and
other techniques for selecting the tree structure [22].

A closely related approach is structural equation models [21]. A structural
equation model associates each random variable with a node in a directed
acyclic graph and models each variable as a function of its parents (if any)
in the graph and noise. These models can be interpreted as Bayesian networks.
It is common in the literature to model the noise as Gaussian and additive. As
with graphical models, one is interested in simultaneously learning the
graphical structure along with the functional relations.

Structural equation models are useful when one suspects the functional
relations to be causal. For this reason, the task of estimating the structure
and functions from observational data is called causal inference. Causal
inference is fundamental in many disciplines [8, 24, 28]. The identifiability
of these models, however, is nontrivial [25].

In the context of control and decision problems, recent work has looked to
extend the ideas of graphical models to stochastic processes [1, 14, 30, 23].
Our work is closest in spirit to that of Materassi and Innocenti [14]. They
study a stochastic process variant of tree linear cascades and give
theoretical results concerning identification. Related to this work, Tan and
Willsky study a stochastic process variant of the Chow-Liu algorithm [31]. The
key object in both of these papers is a particular maximum spanning tree.

##  III Tree linear cascades

Since structural equation models are generally not identifiable, it is natural
to look for classes of them which have properties leading to partial
identifiability. In this section we introduce a class of tree linear
structural equation models with an interesting maximum spanning tree property.

The subtlety of our results is that we make weak assumptions on the
distributions of the error variables. We do not assume that the error
variables are independent. Nor do we assume that they have a Gaussian
distribution. Both of these assumptions are common in the literature [20, 25].

The novelty here is that we can obtain interesting results with the weaker
assumption that the error variables are uncorrelated. To our knowledge, this
definition of tree linear cascades and Theorem 1 do not appear in prior
literature. The development is partially similar to a stochastic process
variant of tree linear cascades studied in [14].

###  III-A Definition

Throughout this section let $(T,r)$ be a rooted tree on
$\left\\{1,2,\dots,d\right\\}$. Define $\mathop{\mathrm{path}}(i,j)$ to be the
set of directed edges on the path from $i$ to $j$ if
$i\in\mathop{\mathrm{anc}}(j)$, and the empty set otherwise. Define

$\mathop{\mathrm{sparse}}(T,r)=\left\\{A\in\mathbb{R}^{d\times d}\mid
A_{ij}=0\text{ if }j\neq\text{pa}_{i}\right\\}.$ (1)

Elements of $\mathop{\mathrm{sparse}}(T,r)\subset\mathbb{R}^{d\times d}$ have
the same sparsity as the directed adjacency matrix of $(T,r)$. Given a zero-
mean random vector $e:\Omega\to\mathbb{R}^{d}$, with diagonal positive
definite covariance, and a matrix $A\in\mathop{\mathrm{sparse}}(T,r)$, we say
that $x$ is a tree linear cascade on $e$ with respect to $A$ if

$x=Ax+e.$ (2)

Notice the uncorrelated assumption on $e$, which is weaker than the often-made
independence assumption.

One can interpret Equation (2) as a particular linear recursive equation [33].
Alternatively, by adding a joint independence assumption on $e$, one can
interpret Equation (2) as a usual linear structural equation model [25] or as
a directed graphical model [19]. The directed graph in both cases corresponds
to a rooted tree. It is common when using structural equation models like 2 to
make causal assumptions. In this case, one can interpret Equation (2) as a
structural (also known as functional) causal model [21].

A special case of this class is the familiar tree linear Gaussian densities.
It is easy to show that if $e$ has a Gaussian distribution, then $x$ is
Gaussian and factors according to a tree. Conversely, if a Gaussian density
$f$ factors according to tree $T$, its inverse covariance matrix has the
sparsity pattern of $T$ [12]. Using a sparse Cholesky factorization [32], one
can show that there is an uncorrelated Gaussian random vector $e$, vertex $i$
of $T$, and $A\in\mathop{\mathrm{sparse}}(T,i)$ so that if $x=Ax+e$, then $x$
has density $f$. In other words, one can obtain a tree structural equation
model in which $e$ is Gaussian.

On the other hand, if $e$ does not have a Gaussian density, then $x$ is not
Gaussian. Consequently, the tree Gaussians are a strict subset of the
densities representable by tree linear cascades. In other words, we are
considering a more general class of distributions than the tree linear
Gaussians. Herein lies the challenge and interest of our results.

###  III-B Tree, not root, of tree linear cascade is identifiable

The key property of tree linear cascades is that the undirected tree structure
is identifiable (Theorem 1). The novelty and particular interest of this work
is that we can show this property regardless of the distribution of each
individual $e_{i}$.

Regardless of distributional assumptions, there is always an identifiability
caveat when working with tree linear cascades. For a tree linear cascade $x$
on $e$ with respect to $A\in\mathop{\mathrm{sparse}}(T,r)$, one can show that
there exists $e^{\prime}$ and $A^{\prime}\in\mathop{\mathrm{sparse}}(T,i)$
where $i\neq r$ is any other vertex of $T$ and $x$ is a tree linear cascade on
$e^{\prime}$ with respect to $A^{\prime}$. Therefore only the tree $T$ is
identifiable, not the root.

In practice, this difficulty is alleviated by extra knowledge. We are often
modeling measurements from a system and we know the input’s identity. The
input might be the load on a computer system and the other quantities might be
various resource or application-specific metrics. Such knowledge enables one
to select the root and orient the edges.

###  III-C Identifying the tree

The tree of a tree linear cascade can be identified as the maximum spanning
tree of a graph using squared correlations as weights. It is worth restating
that this result holds regardless of distributional assumptions on $e$.

We require a progression of algebraic and graphical lemmas to show this
result. To streamline the presentation, these appear in the Appendix. Although
we have structured them so that the proof here appears short and
straightforward, a glance at the Appendix indicates the work involved. The
algebraic properties of Equation (2) and the uncorrelated components of $e$
give the following. The hypothesis that $\mathbb{E}(x_{i}^{2})=1$ is not
substantial to the result, and is made for convenience of the proofs.

###### Theorem 1

Let $e:\Omega\to\mathbb{R}^{d}$ be a random vector with zero mean and diagonal
positive definite covariance. Let $x:\Omega\to\mathbb{R}^{d}$ be a tree linear
cascade on $e$ with respect to $A\in\mathop{\mathrm{sparse}}(T,r)$ and suppose
$\mathbb{E}(x_{i}^{2})=1$. Then $T$ is the unique maximum spanning tree of the
complete graph on $\left\\{1,2,\dots,d\right\\}$ with edge
$\left\\{i,j\right\\}$ weighted by $\mathbb{E}(x_{i}x_{j})^{2}$.

###### Proof:

Define
$C=\text{cov}(x)=\text{cov}((I-A)^{-1}e)=(I-A)^{-1}\text{cov}(e)(I-A)^{-\top}$.
Then
$\left\lvert{C_{ij}}\right\rvert=\left\lvert{\mathbb{E}(x_{i}x_{j})}\right\rvert$
and $\text{cov}(e)$ is diagonal positive definite. Use Lemma 12 to see that
the conditions of Lemma 5 are satisfied, and so conclude that $T$ is a minimum
spanning tree of the complete graph on $\left\\{1,2,\dots,d\right\\}$ where
edge $\left\\{i,j\right\\}$ is weighted by $\left\lvert{C_{ij}}\right\rvert$.
Since squaring the correlation magnitudes $\left\lvert{C_{ij}}\right\rvert$ is
a monotonic transformation of the weights, a tree is a maximum spanning tree
with edges weighted by $\left\lvert{C_{ij}}\right\rvert$ if and only if it is
the maximum spanning tree with edges weighted by $C_{ij}^{2}$ (using Lemma 3).
∎

##  IV Simultaneous cascade regression

Structural equation and causal models are useful when one is working with
multivariate data and believes that some of the variables are functionally
related to others[21]. In some cases, extra knowledge enables one to specify
the graphical structure of the model [11]. In practice, however, one
frequently wants to learn the model structure. Unfortunately, these models are
not always identifiable[25].

In practice, one does have data. It is natural to simultaneously search for a
directed graph and estimate the functions involved by regressing variables on
their parents in the graph. Beyond difficulty in estimating the functional
relations, such problems are difficult because the number of directed acyclic
graphs (even directed acyclic trees) is exponential in the number of
variables.

It is pleasantly surprising, therefore, that if we restrict to linear
functions and directed trees (as we do in Problem 1), one can analytically
solve the problem. Although the statement of this problem and its solution
remind one of the more specialized result of Chow and Liu for Gaussian
densities, it is important to note here that we make no distributional
assumptions on $x$. To our knowledge, this problem and its solution do not
appear in the prior literature.

######  Problem 1 (Simultaneous cascade regression)

Suppose $x:\Omega\to\mathbb{R}^{d}$ is a random vector with $\mathbb{E}(x)=0$
and $\mathbb{E}(x_{i}^{2})=1$. Find a rooted tree $(T,r)$ on
$\left\\{1,2,\dots,d\right\\}$ and $A\in\mathbb{R}^{d\times d}$ to

minimize $\displaystyle\quad\mathbb{E}\left\lVert{Ax-x}\right\rVert$ subject
to $\displaystyle\quad A\in\mathop{\mathrm{sparse}}(T,r).$

We call a solution $T^{\star}$ an optimal cascade tree of $x$.

Problem 1 finds a rooted tree which, if we estimated each component of $x$
using only its parent in the tree, gives the smallest expected sum of squared
errors. Notice that the sparsity constraint on $A$ ensures that the diagonal
of $A$ is 0, and so $A=I$ is not a solution.

It is natural to ask that, if $x$ is a tree linear cascade with respect to
$T$, any problem (like Problem 1) which proposes to select a tree by which to
model $x$ should recover $T$. This statement is the content of Corollary 1 in
Section IV-B. In the case that $x$ is not a tree linear cascade, we can still
use our solution to Problem 1, and interpret Problem 1 as a variational
principle for selecting a tree when modeling a random vector.

In practice, we are interested in the empirical risk minimization form of
Problem 1 (see Section VI). In that setting, we do not expect data generated
by a tree linear cascade. Instead, we view Problem 1 as a fitting method.

###  IV-A Solution of simultaneous cascade regression

We solve Problem 1 in two pieces. First, we find the optimal cascade
coefficients for a rooted tree $(T,r)$ (Lemma 1). Then we find the optimal
tree (Theorem 2).

###### Lemma 1

Suppose $x:\Omega\to\mathbb{R}^{d}$ is a random vector with $\mathbb{E}(x)=0$
and $\mathbb{E}(x_{i}^{2})=1$. Let $(T,r)$ be a rooted tree on
$\left\\{1,2,\dots,d\right\\}$. Define
$A^{\star}\in\mathop{\mathrm{sparse}}(T,r)$ by

$A^{\star}_{ij}=\begin{cases}\mathbb{E}(x_{i}x_{j})&j=\text{pa}_{i}\\\
0&\text{otherwise.}\end{cases}$

Then $A^{\star}$ minimizes $\left\lVert{Ax-x}\right\rVert$ among all
$A\in\mathop{\mathrm{sparse}}(T,r)$.

###### Proof:

Let $A\in\mathop{\mathrm{sparse}}(T,r)$. Express

$\mathbb{E}\left\lVert{Ax-x}\right\rVert^{2}=\mathbb{E}(x_{r}^{2})+\sum_{i\neq
r}\mathbb{E}\left(A_{i\text{pa}_{i}}x_{\text{pa}_{i}}-x_{i}\right)^{2}.$

The first term does not depend on $A$ and the second sum separates across $i$.
For $i\neq r$ we find $A_{i\text{pa}_{i}}$ to minimize
$\mathbb{E}\left(A_{i\text{pa}_{i}}x_{\text{pa}_{i}}-x_{i}\right)^{2}$. A
solution is
$A^{\star}_{i\text{pa}_{i}}=\mathbb{E}(x_{i}x_{\text{pa}_{i}})\mathbb{E}(x_{\text{pa}_{i}}^{2})^{-1}=\mathbb{E}(x_{i}x_{\text{pa}_{i}})$.
∎

###### Theorem 2

Suppose $x:\Omega\to\mathbb{R}^{d}$ is a random vector with $\mathbb{E}(x)=0$
and $\mathbb{E}(x_{i}^{2})=1$. A tree $T$ on $\left\\{1,2,\dots,d\right\\}$ is
an optimal cascade tree of $x$ if and only if it is a maximum spanning tree of
the complete graph on $\left\\{1,2,\dots,d\right\\}$ with edge
$\left\\{i,j\right\\}$ weighted by $\mathbb{E}(x_{i}x_{j})^{2}$.

###### Proof:

Let $r\in\left\\{1,2,\dots,d\right\\}$. By Lemma 1, there exists
$A^{\star}\in\mathop{\mathrm{sparse}}(T,r)$ which minimizes
$\left\lVert{Ax-x}\right\rVert$ among $A\in\mathop{\mathrm{sparse}}(T,r)$. We
have

$\displaystyle\mathbb{E}\left\lVert{A^{\star}x-x}\right\rVert^{2}$
$\displaystyle=\mathbb{E}(x_{r}^{2})+\sum_{i\neq
r}\mathbb{E}\left(\mathbb{E}\left(x_{i}x_{\text{pa}_{i}}\right)x_{\text{pa}_{i}}-x_{i}\right)^{2}$
$\displaystyle=\mathbb{E}(x_{r}^{2})+\sum_{i\neq
r}\mathbb{E}(x_{i}^{2})-\mathbb{E}(x_{i}x_{j})^{2}$
$\displaystyle=d-\sum_{i\neq r}\mathbb{E}(x_{i}x_{j})^{2}.$

Here $d$ is a constant, and the second term is a sum over the edges of $T$
(and does not depend on the root). To minimize the sum, we choose $T$ to be a
maximum spanning tree with weights $\mathbb{E}(x_{i}x_{j})^{2}$. ∎

Two aspects of this derivation stand out. First, the proof of this theorem
reminds one of the classical Chow-Liu result for Gaussians [3, 29]. We make a
connection for the special case of a Gaussian tree linear cascade to the Chow-
Liu algorithm in Section V. For now, we reiterate that so far we have made no
Gaussian distributional assumptions. Second, the solution of Problem 1 does
not depend on the choice of root. We address this in the next section.

###  IV-B Problem 1 recovers tree of tree linear cascade

It is natural to expect that if the vector $x$ in Problem 1 is a tree linear
cascade on $e$ with respect to $A\in\mathop{\mathrm{sparse}}(T,r)$, then
$(T,r)$ should be a solution. As discussed in Section III-B, however, we can
not hope to identify the root. Equipped with Theorem 1, one can show the
following.

###### Corollary 1

Let $(T,r)$ be a rooted tree on $\left\\{1,2,\dots,d\right\\}$ and
$e:\Omega\to\mathbb{R}^{d}$ a random vector with zero-mean and diagonal
positive definite covariance. Suppose $x:\Omega\to\mathbb{R}^{d}$ is a tree
linear cascade on $e$ with respect to $A\in\mathop{\mathrm{sparse}}(T,r)$ and
that $\mathbb{E}(x_{i}^{2})=1$. Then $T$ is the unique optimal cascade tree of
$x$.

###### Proof:

Express $\mathbb{E}(x)=(I-A)^{-1}\mathbb{E}(e)=0$. Use Theorem 2 to conclude
that an optimal cascade tree is a maximum spanning tree of the complete graph
on $\left\\{1,2,\dots,d\right\\}$ weighted by $\mathbb{E}(x_{i}x_{j})^{2}$.
Use Theorem 1 to conclude that $T$ is the only maximum spanning tree. ∎

##  V Connections to Gaussian Chow-Liu

Sections III and IV present the primary theoretical contributions of this
paper. These results remind one of the classical results for approximating a
density by one which factors according to a tree [3]. In this section, we
briefly state these well-known results and then show how they connect to our
results for the special case of Gaussian densities.

###  V-A Review of well-known Chow-Liu results

We include formal statements to make precise our treatment in Section V-B. The
following problem and its solution are well-known [29].

######  Problem 2 (Tree density approximation)

Given a density $g:\mathbb{R}^{d}\to\mathbb{R}$, find a tree $T$ on
$\left\\{1,2,\dots,d\right\\}$ and a density $f:\mathbb{R}^{d}\to\mathbb{R}$
to

minimize $\displaystyle d_{kl}(g,f)$ subject to $\displaystyle f\text{ factors
according to }T.$

We call a solution $T^{\star}$ an optimal approximator tree of $g$.

###### Lemma 2

Let $g$ be a density on $\mathbb{R}^{d}$. A tree $T$ on
$\left\\{1,2,\dots,d\right\\}$ is an optimal approximator tree of $g$ if and
only if it is a maximum spanning tree of the complete undirected graph on
$\left\\{1,2,\dots,d\right\\}$ with edge $\left\\{i,j\right\\}$ weighted by
$d_{kl}(g_{ij},g_{i}g_{j})$.

###  V-B Novel connection to cascade regression

Chow-Liu for densities is computationally feasible if one makes a Gaussian
assumption. Unsurprisingly, therefore, this assumption is extremely common in
the literature. In this case, Problem 2 reduces to finding the maximum
spanning tree of a graph weighted by
$-\nicefrac{{1}}{{2}}\log(1-\rho_{ij}^{2})$. This quantity is the mutual
information between two components of a Gaussian.

In this Gaussian assumption lies the connection to tree linear cascades and to
cascade regression (Problem 1). With the results of Section IV and brief
reflection on the properties of maximum spanning trees, one can show that the
spanning tree found by Chow and Liu is the same as that in Section IV.

###### Corollary 2

Let $x:\Omega\to\mathbb{R}^{d}$ be a random vector with $\mathbb{E}(x_{i})=0$
and $\mathbb{E}(x_{i}^{2})=1$ for $i\in\left\\{1,2,\dots,d\right\\}$. Suppose
$x$ has a Gaussian density $f:\mathbb{R}^{d}\to\mathbb{R}$. A tree $T$ is an
optimal cascade tree of $x$ if and only if it is an optimal approximator tree
of $f$.

###### Proof:

By Lemma 2, an optimal approximator tree of $f$ is a maximal spanning tree of
the complete graph on $\left\\{1,2,\dots,d\right\\}$ with edge
$\left\\{i,j\right\\}$ weighted by
$d_{kl}(f_{ij},f_{i}f_{j})=-(\nicefrac{{1}}{{2}})\log(1-\mathbb{E}(x_{i}x_{j})^{2})$.
By Theorem 2, an optimal cascade tree of $x$ is a maximal spanning tree of the
complete graph on $\left\\{1,2,\dots,d\right\\}$ weighted by
$\mathbb{E}(x_{i}x_{j})^{2}$. The sets of maximal spanning trees coincide
because the first quantity $d_{kl}(f_{ij},f_{i}f_{j})$ is a monotonic
transformation of the squared correlations $\mathbb{E}(x_{i}x_{j})^{2}$.∎

In Section IV-B, Corollary 1 says that cascade regression identifies the tree
for all tree linear cascades. Of course, the special case of Gaussian tree
linear cascades is included. Corollary 2, therefore, can be roughly
interpreted as strengthening the justification for the Gaussian version of the
classical Chow-Liu result. One has theoretical recourse to Corollary 2, which
says that one may interpret the approach as making a linear assumption while
avoiding a Gaussian assumption.

This is intuitively reminiscent of, but distinct from, a result in classical
estimation. An estimator for a random $m$-vector $y$ from a random $n$-vector
$x$ is a function $\phi:\mathbb{R}^{n}\to\mathbb{R}^{m}$. If we select $\phi$
to minimize $\mathbb{E}\left\lVert{\phi(x)-y}\right\rVert$, the solution
$\phi^{\star}$ is the conditional expectation of $y$ given $x$. On one hand,
if we assume that the joint density of $x$ and $y$ is Gaussian, the
conditional expectation of $y$ given $x$ is $\phi(x)=Ax+b$ for some $A$ and
$b$. On the other hand, if we constrain $\phi(x)=Cx+d$ for some $C$ and $d$,
$C$ and $d$ are expressible in terms of the covariance and means of $x$ and
$y$.

It is well-known that if one takes the latter approach, and $x$ and $y$ are
jointly Gaussian, then $C^{\star}=A$ and $d^{\star}=b$. Roughly speaking,
Gaussian Chow-Liu and cascade regression are linked in a similar war. In one
case we impose a linear constraint. In the other we make a distributional
assumption that reduces to a linear constraint. Instead of the conditional
expectation, the central quantity is the pairwise mutual informations between
pairs of random variables.

##  VI Empirical Cascade Regression

Figure 1:  The optimal cascade tree for a dataset of stock prices.

In practice, we have data and want to fit a structural equation model. Cascade
regression (Problem 1) has a natural instantiation as empirical risk
minimization. The quantities involved are easily computable, and we give a
straightforward example on stock prices.

###  VI-A Cascade regression as empirical risk minimization

Let $x^{1},\dots,x^{n}$ be a dataset in $\mathbb{R}^{d}$. For empirical
cascade regression, one finds a rooted tree $(T,r)$ on
$\left\\{1,2,\dots,d\right\\}$ and coefficients $A$ to minimize
$\sum_{k=1}^{n}\left\lVert{Ax^{k}-x^{k}}\right\rVert$ subject to
$A\in\mathop{\mathrm{sparse}}(T,r)$.

The key quantity for finding the optimal cascade tree is the squared empirical
correlations. We use any standard maximum spanning tree algorithm (e.g.,
[10]). As discussed in Section V-B, the tree found is the same as if one used
the Chow-Liu algorithm with a Gaussian assumption.

###  VI-B Simple stock price movement example

To illustrate our theoretical results and show that it is straightforward to
compute the quantities involved, we include a small example on stock prices.
Our implementation (using Julia [2]) is short and requires trivial
computation. We collect daily price changes (for the past decade) of the
thirty stocks of the Dow Jones Industrial Average from the public market data
page of the Wall Street Journal. For simplicity, we ignore time dependence. We
make the dataset and code available.

We visualize the tree structure recovered in Figure 1. Stocks are colored by
their industry according to the Dow Jones & Company’s classification. Roughly,
stocks in similar industries are connected in the graph. A well-known and
natural clustering method for $k\geq 2$ clusters is to delete the $k-1$
lightest edges from this tree. Of course, this technique is not sufficient to
obtain state of the art predictions for the stock market. The applicability of
tree linear cascades for a particular data set must be evaluated on a case by
case basis.

##  VII Conclusion

We define tree linear cascades and show that their tree structure is
identifiable as the solution of a maximum spanning tree problem (Theorem 1).
In a parallel vein, we discuss a natural regression problem for fitting
structural equation models, and show that a constrained form of this problem
(Problem 1) has an analytical solution (Theorem 2). We connect these results
to the more specialized results of Chow and Liu for Gaussian densities. We
conclude with a simple data-based example demonstrating that the quantities
involved are easy to compute.

#### Limitations and future work

The upside of tree linear cascades is that they are amenable to mathematical
analysis. The downside, as usual, is that they can not model all
distributions. The restriction on the distributions represented has two
components. One is the linearity and one is the assumption of tree structure.
We plan to alleviate the former of these limitations by extending these
results to the block case. One can embed measurements using features and so
approximate nonlinear relationships between the variables with linear
functions of nonlinear features. Another limitation is that the root of tree
linear cascades is not identifiable. In practice, however, one often has extra
information about which variable should be the input. Future theoretical work
may analyze sample complexity. Future applied work may look at particular
application domains (e.g., genetics and computer system modeling).

## APPENDIX

###  VII-A Graphical results relating to maximum spanning trees

Let $(G,W)$ be a weighted graph with vertex set
$\left\\{1,2,\dots,d\right\\}$. As usual, a function
$h:\mathbb{R}\to\mathbb{R}$ is monotone increasing if $h(x)<h(y)$ whenever
$x<y$ for all $x,y\in\mathbb{R}$. We use the following in Theorem 1 and
Corollary 2.

###### Lemma 3

Suppose $h:\mathbb{R}\to\mathbb{R}$ is monotone increasing. Define
$H_{e}=h(W_{e})$ for each edge $e$. A tree $T$ is a maximum spanning tree of
$(G,W)$ if and only if it is a maximum spanning tree of $(G,H)$.

###### Proof:

See Section 1.1.12 of [13]. ∎

The following construction handles nonunique weights. Let
$\beta_{1},\beta_{2},\dots$ be a sequence of edges of $G$. $\beta$ is
consistent with $W$ if $W_{\beta_{a}}\geq W_{\beta_{b}}$ whenever $a<b$ for
integers $a$ and $b$. The Kruskal edge of a forest $F$ with respect to $\beta$
is the first edge in $\beta$ which is not in $F$ and whose addition to $F$
creates no cycles. The Kruskal sequence corresponding to $\beta$ is the
sequence of forests $F_{0}^{\beta}\subset F_{1}^{\beta}\subset\dots\subset
F^{\beta}_{d-1}$ where $F_{0}^{\beta}=\emptyset$ and each forest differs with
the subsequent one only by its Kruskal edge. The following is a
straightforward variant of [10].

###### Lemma 4

Let $T$ be a maximum spanning tree of $(G,W)$. There exists an ordering
$\beta$ consistent with $W$ whose Kruskal sequence
$F^{\beta}_{0},F^{\beta}_{1},\dots,F^{\beta}_{d-1}$ satisfies
$F^{\beta}_{d-1}=T$.

We use Lemma 4 to get the uniqueness piece of Lemma 5. The hypothesis of Lemma
5 corresponds to the conclusion of Lemma 12.

###### Lemma 5

Let $T$ be a tree on $\left\\{1,2,\dots,d\right\\}$. Suppose that for every
two distinct nonadjacent vertices $i$ and $j$ of $T$, and $k$ the first vertex
on the path from $i$ to $j$,

$W_{ij}<\min\left\\{W_{ik},W_{kj}\right\\}.$ (3)

Then $T$ is the unique maximum spanning tree of $G$.

###### Proof:

Let $\tilde{T}$ be a maximum spanning tree of $G$. We will show that
$\tilde{T}=T$. By Lemma 4, there exists an order $\beta$ of edges of $G$ so
that the Kruskal sequence $F_{0}^{\beta}\subset
F_{1}^{\beta}\subset\dots\subset F_{d-1}^{\beta}$ satisfies
$F_{d-1}^{\beta}=\tilde{T}$. Define $\tilde{t}_{1},\dots,\tilde{t}_{d-1}$ to
be the corresponding sequence of Kruskal edges. Suppose, toward contradiction,
that there is an edge of $\tilde{T}$ not in $T$. Let
$\tilde{t}_{s}=\left\\{i,j\right\\}$ be the first such edge and let $k$ be the
first vertex on the path from $i$ to $j$ in $T$. By hypothesis,
$W_{ik}>W_{ij}$ and $W_{kj}>W_{ij}$. So by construction these edges are either
in $F^{\beta}_{s-1}$ or were skipped because the vertices involved were
already connected. Either way, $i$ is connected to $k$ and $k$ is connected to
$j$ in in $F^{\beta}_{s-1}$. But then there is a cycle in $\tilde{T}$. $i$ to
$k$, $k$ to $j$ and $j$ to $i$. So $\tilde{T}$ is not a tree, a contradiction.
∎

We can interpret the condition in Equation 3 by way of a variant of the
algorithm in [10]. This variant constructs a Kruskal forest by considering the
edges in decreasing order of weight. The condition says, roughly, that before
the algorithm considers connecting nonadjacent vertices $i$ and $j$, it will
already have considered connecting $i$ with $k$, the first vertex on the path
to $j$, and $k$ with $j$.

###  VII-B Algebraic structure of tree linear cascades

Since Equation 2 implies $(I-A)x=e$, we analyze $(I-A)^{-1}$. The following
two lemmas are special cases of standard results [18].

###### Lemma 6

Suppose $A\in\mathop{\mathrm{sparse}}(T,r)$. Let $p\geq 1$. Then $A^{p}_{ij}$
is $\prod_{(s,t)\in\mathop{\mathrm{path}}(j,i)}A_{ts}$ if
$\left\lvert{\mathop{\mathrm{path}}(j,i)}\right\rvert=p$ and $0$ otherwise.

###### Lemma 7

Suppose $A\in\mathop{\mathrm{sparse}}(T,r)$. Then $(I-A)^{-1}$ exists and
$((I-A)^{-1})_{ij}$ is
$A_{ij}^{\left\lvert{\mathop{\mathrm{path}}(j,i)}\right\rvert}$ if there is a
directed path from $j$ to $i$, 1 if $i=j$, and 0 otherwise.

###### Proof:

From Lemma 6 it follows that $A$ is nilpotent, and so $(I-A)^{-1}$ exists and
is given by its Neumann series $\sum_{k=0}^{\infty}A^{k}$ (see p. 126 of
[18]). ∎

An immediate result of Lemma 7 is a useful path-factoring property of elements
of $(I-A)^{-1}$.

###### Lemma 8

Suppose $A\in\mathop{\mathrm{sparse}}(T,r)$. Define $B=(I-A)^{-1}$. If there
is a directed path from $j$ to $i$ and $k$ is a vertex on it, then
$B_{ij}=B_{ik}B_{kj}$.

The next four lemmas are motivated by
$\text{cov}(x)=(I-A)^{-1}\text{cov}(e)(I-A)^{-\top}$. The first two give the
covariance between two components of $x$. First when one component is an
ancestor of the other (Lemma 9) and second when neither is an ancestor of the
other (Lemma 10). We then bound the magnitude of the elements of $A$ by 1
(Lemma 11). Finally, we use these to show a result (Lemma 12) which says,
roughly, that a component of a tree linear cascade is most correlated with its
neighbors in the tree. The unit diagonal hypothesis matches the unit variance
assumption in Theorem 1.

###### Lemma 9

Let $A\in\mathop{\mathrm{sparse}}(T,r)$ and $D$ diagonal positive definite.
Define $B=(I-A)^{-1}$ and $C=BDB^{\top}$. Suppose $\text{diag}(C)=1$. If
$i\in\mathop{\mathrm{anc}}(j)$, then $C_{ij}=C_{ji}=B_{ji}$.

###### Proof:

Define $F=BD^{1/2}$. The sparsity pattern of $F$ is the same as that of $B$.
Define
$\mathop{\mathrm{anc}}^{+}(i)=\mathop{\mathrm{anc}}(i)\cup\left\\{i\right\\}$.
Use Lemma 7 to express

$\displaystyle C_{ij}=\sum_{k=1}^{d}F_{ik}F_{jk}$
$\displaystyle=\sum_{k\in\mathop{\mathrm{anc}}^{+}(i)}F_{ik}F_{jk}$
$\displaystyle=\sum_{k\in\mathop{\mathrm{anc}}^{+}(i)}F_{ik}\left(B_{jk}D_{kk}^{1/2}\right).$

Since there is a directed path from every vertex in
$\mathop{\mathrm{anc}}^{+}(i)$ to $j$, and $i$ is on it, use Lemma 8 to
express

$\displaystyle\sum_{k\in\mathop{\mathrm{anc}}^{+}(i)}F_{ik}\left(B_{jk}D_{kk}^{1/2}\right)$
$\displaystyle=\sum_{k\in\mathop{\mathrm{anc}}^{+}(i)}F_{ik}\left(B_{ji}B_{ik}D_{kk}^{1/2}\right)$
$\displaystyle=B_{ji}\sum_{k\in\mathop{\mathrm{anc}}^{+}(i)}F_{ik}^{2}.$

Since $\sum_{k\in\mathop{\mathrm{anc}}^{+}(i)}F_{ik}^{2}=C_{ii}=1$ and $C$ is
symmetric, $C_{ij}=C_{ji}=B_{ji}$. ∎

###### Lemma 10

Let $A\in\mathop{\mathrm{sparse}}(T,r)$ and $D$ diagonal positive definite.
Define $B=(I-A)^{-1}$ and $C=BDB^{\top}$. Suppose $\text{diag}(C)=1$. If $i,j$
are two distinct vertices and $i\not\in\mathop{\mathrm{anc}}(j)$ and
$j\not\in\mathop{\mathrm{anc}}(i)$, then $C_{ij}=B_{im}B_{jm}$ where $m$ is
the last coinciding vertex on the directed paths $r$ to $i$ and $r$ to $j$.

###### Proof:

Define
$\mathop{\mathrm{canc}}(i,j)=\mathop{\mathrm{anc}}(i)\cap\mathop{\mathrm{anc}}(j)$:
Since neither $i$ nor $j$ is the root, $r\in\mathop{\mathrm{canc}}(i,j)$.
Since $m$ is on the path from $r$ to $i$ and $r$ to $j$,
$m\in\mathop{\mathrm{canc}}(i,j)$. In fact,
$\mathop{\mathrm{canc}}(i,j)=\left\\{m\right\\}\cup\mathop{\mathrm{anc}}(m)$.
Define $F=BD^{1/2}$. The sparsity pattern of $F$ is the same as that of $B$.
Use Lemma 7 and Lemma 8 to express

$\displaystyle C_{ij}=\sum_{k=1}^{d}F_{ik}F_{jk}$
$\displaystyle=\sum_{k\in\mathop{\mathrm{canc}}(i,j)}F_{ik}F_{jk}$
$\displaystyle=\sum_{k\in\mathop{\mathrm{canc}}(i,j)}B_{im}F_{mk}B_{jm}F_{mk}.$

From $\sum_{k\in\mathop{\mathrm{canc}}(i,j)}F_{mk}^{2}=C_{mm}=1$, conclude
that $C_{ij}=B_{im}B_{jm}$. ∎

###### Lemma 11

Let $A\in\mathop{\mathrm{sparse}}(T,r)$ and $D$ diagonal positive definite.
Define $B=(I-A)^{-1}$ and $C=BDB^{\top}$. Suppose $\text{diag}(C)=1$. Then
$\left\lvert{A_{ij}}\right\rvert<1$.

###### Proof:

Define $F=BD^{1/2}$. The sparsity pattern of $F$ is the same as that of $B$.
For any $i\in\left\\{1,2,\dots,d\right\\}$, use this sparsity (see Lemma 7) to
express

$C_{ii}=\sum_{s=1}^{d}F_{is}^{2}=\sum_{s\in\mathop{\mathrm{anc}}(i)}F_{is}^{2}+D_{ii}.$
(4)

Use Lemma 8 and $F_{is}=B_{is}D^{1/2}_{ss}$ to express
$\sum_{s\in\mathop{\mathrm{anc}}(i)}F_{is}^{2}$ as

$\sum_{s\in\mathop{\mathrm{anc}}(s)}\left(A_{i\text{pa}_{i}}B_{\text{pa}_{i}s}D_{ss}\right)^{2}=A_{i\text{pa}_{i}}^{2}\sum_{s\in\mathop{\mathrm{anc}}(i)}F_{is}^{2}.$

Since
$\mathop{\mathrm{anc}}(i)=\mathop{\mathrm{anc}}(\text{pa}_{i})\cup\left\\{\text{pa}_{i}\right\\}$,
$\sum_{s\in\mathop{\mathrm{anc}}(i)}F_{is}^{2}=C_{\text{pa}_{i}\text{pa}_{i}}=1$.
Use these facts and Equation 4 to conclude
$C_{ii}=A_{i\text{pa}_{i}}^{2}+D_{ii}$. Since $C_{ii}=1$, and $D_{ii}>0$, the
foregoing expression implies $\left\lvert{A_{i\text{pa}_{i}}}\right\rvert<1$.
∎

###### Lemma 12

Let $A\in\mathop{\mathrm{sparse}}(T,r)$ and $D$ diagonal positive definite.
Define $B=(I-A)^{-1}$ and $C=BDB^{\top}$. Suppose $\text{diag}(C)=1$. If $i$
and $j$ are two distinct nonadjacent vertices in $T$, then the first vertex
$k$ on the undirected path from $i$ to $j$ satisfies
$\left\lvert{C_{ij}}\right\rvert<\min\left\\{\left\lvert{C_{ik}}\right\rvert,\left\lvert{C_{kj}}\right\rvert\right\\}$.

###### Proof:

By cases:

First, suppose $i\in\mathop{\mathrm{anc}}(j)$. In this case, $k$ is a child of
$i$ in $(T,r)$. Deduce

$\displaystyle\left\lvert{C_{ij}}\right\rvert\overset{(a)}{=}\left\lvert{B_{ji}}\right\rvert\overset{(b)}{=}\left\lvert{B_{jk}B_{ki}}\right\rvert\overset{(c)}{<}\left\lvert{B_{ki}}\right\rvert\overset{(d)}{=}\left\lvert{C_{ik}}\right\rvert.$
(5)

where (a) uses Lemma 9, (b) uses Lemma 8, (c) uses
$\left\lvert{B_{jk}}\right\rvert<1$ from Lemma 7 and Lemma 11, and (d) uses
Lemma 9. Similarly, $\left\lvert{B_{ki}}\right\rvert<1$ and so
$\left\lvert{C_{ij}}\right\rvert<\left\lvert{B_{jk}}\right\rvert=\left\lvert{C_{kj}}\right\rvert$.

Second, suppose $j\in\mathop{\mathrm{anc}}(i)$. In this case, $k$ is the
parent of $i$ in $(T,r)$. Use the symmetry of $C$ and the previous case to
conclude

$\left\lvert{C_{ij}}\right\rvert=\left\lvert{C_{ji}}\right\rvert<\min\left\\{\left\lvert{C_{jk}}\right\rvert,\left\lvert{C_{ki}}\right\rvert\right\\}=\min\left\\{\left\lvert{C_{kj}}\right\rvert,\left\lvert{C_{ik}}\right\rvert\right\\}.$

Finally, suppose $i\not\in\mathop{\mathrm{anc}}(j)$ and
$j\not\in\mathop{\mathrm{anc}}(i)$. In this case, $k$ is the parent of $i$ in
$(T,r)$. Let $m$ be the last coinciding vertex on the paths from $r$ to $i$
and $r$ to $j$. Express

$\left\lvert{C_{ij}}\right\rvert\overset{(a)}{=}\left\lvert{B_{im}B_{jm}}\right\rvert\overset{(b)}{=}\left\lvert{B_{ik}B_{km}B_{jm}}\right\rvert\overset{(c)}{<}\left\lvert{B_{ik}}\right\rvert\overset{(d)}{=}\left\lvert{C_{ik}}\right\rvert.$

where (a) uses Lemma 10, (b) uses Lemma 8, (c) uses
$\left\lvert{B_{km}B_{jm}}\right\rvert<1$ from Lemma 7 and Lemma 11, and (d)
uses Lemma 9. To show
$\left\lvert{C_{ij}}\right\rvert<\left\lvert{C_{kj}}\right\rvert$, first
suppose $k=m$. Then

$\left\lvert{C_{ij}}\right\rvert\overset{(a)}{=}\left\lvert{B_{ik}B_{jk}}\right\rvert\overset{(b)}{<}\left\lvert{B_{jk}}\right\rvert\overset{(c)}{=}\left\lvert{C_{kj}}\right\rvert.$

where (a) uses Lemma 10, (b) uses $\left\lvert{B_{ik}}\right\rvert<1$ from
Lemma 11, (c) uses Lemma 9. Next suppose $k\neq m$: then
$k\not\in\mathop{\mathrm{anc}}(j)$. Also, $j\not\in\mathop{\mathrm{anc}}(i)$
implies $j\not\in\mathop{\mathrm{anc}}(k)$. Express

$\left\lvert{C_{ij}}\right\rvert\overset{(a)}{=}\left\lvert{B_{ik}B_{km}B_{jm}}\right\rvert\overset{(b)}{<}\left\lvert{B_{km}B_{jm}}\right\rvert\overset{(c)}{=}\left\lvert{C_{kj}}\right\rvert.$

where (a) uses Lemma 10 and Lemma 8, (b) uses
$\left\lvert{B_{ik}}\right\rvert<1$ from Lemma 11 and (c) uses Lemma 10. ∎

## ACKNOWLEDGMENT

We thank our reviewers for helping us to improve the paper. N. C. Landolfi is
supported by a National Defense Science and Engineering Graduate Fellowship
and a Stanford Graduate Fellowship. S. Lall was partially supported by the
National Science Foundation under grant 1544199.

## References

  * [1] F. R. Bach and M. I. Jordan, “Learning graphical models for stationary time series,” _IEEE transactions on signal processing_ , vol. 52, no. 8, pp. 2189–2199, 2004.
  * [2] J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, “Julia: A fresh approach to numerical computing,” _SIAM Review_ , vol. 59, no. 1, pp. 65–98, 2017.
  * [3] C. Chow and C. Liu, “Approximating discrete probability distributions with dependence trees,” _IEEE transactions on Information Theory_ , vol. 14, no. 3, pp. 462–467, 1968.
  * [4] M. Dimovska and D. Materassi, “Granger-causality meets causal inference in graphical models: Learning networks via non-invasive observations,” in _2017 IEEE 56th CDC_. IEEE, 2017, pp. 5268–5273.
  * [5] D. Edwards, G. C. De Abreu, and R. Labouriau, “Selecting high-dimensional mixed graphical models using minimal aic or bic forests,” _BMC bioinformatics_ , vol. 11, no. 1, pp. 1–13, 2010.
  * [6] N. Friedman, D. Geiger, and M. Goldszmidt, “Bayesian network classifiers,” _Machine learning_ , vol. 29, no. 2, pp. 131–163, 1997.
  * [7] N. Friedman, M. Goldszmidt, and T. J. Lee, “Bayesian network classification with continuous attributes: Getting the best of both discretization and parametric fitting.” in _ICML_ , vol. 98, 1998, pp. 179–187.
  * [8] T. A. Glass, S. N. Goodman, M. A. Hernán, and J. M. Samet, “Causal inference in public health,” _Annual review of public health_ , vol. 34, pp. 61–75, 2013.
  * [9] D. Koller and N. Friedman, _Probabilistic graphical models: principles and techniques_. MIT press, 2009.
  * [10] J. B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem,” _Proceedings of the American Mathematical society_ , vol. 7, no. 1, pp. 48–50, 1956.
  * [11] N. C. Landolfi, D. C. O’Neill, and S. Lall, “Cloud telemetry modeling via residual gauss-markov random fields,” in _2021 24th Conference on Innovation in Clouds, Internet and Networks and Workshops (ICIN)_. IEEE, 2021, pp. 49–56.
  * [12] S. L. Lauritzen, _Graphical models_. Clarendon Press, 1996, vol. 17.
  * [13] M. Mareš, “The saga of minimum spanning trees,” _Computer Science Review_ , vol. 2, no. 3, pp. 165–221, 2008.
  * [14] D. Materassi and G. Innocenti, “Topological identification in networks of dynamical systems,” _IEEE Transactions on Automatic Control_ , vol. 55, no. 8, pp. 1860–1871, 2010.
  * [15] D. Materassi and M. V. Salapaka, “Reconstruction of directed acyclic networks of dynamical systems,” in _2013 American Control Conference_. IEEE, 2013, pp. 4687–4692.
  * [16] ——, “Signal selection for estimation and identification in networks of dynamic systems: a graphical model approach,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 10, pp. 4138–4153, 2019.
  * [17] M. Meila and M. I. Jordan, “Learning with mixtures of trees,” _Journal of Machine Learning Research_ , vol. 1, no. Oct, pp. 1–48, 2000.
  * [18] C. D. Meyer, _Matrix analysis and applied linear algebra_. Siam, 2000, vol. 71.
  * [19] K. P. Murphy, _Machine learning: a probabilistic perspective_. MIT press, 2012.
  * [20] J. Pearl, _Probabilistic reasoning in intelligent systems: networks of plausible inference_. Morgan Kaufmann, 1988\.
  * [21] ——, _Causality_. Cambridge university press, 2009.
  * [22] G. Perez-de-la Cruz and G. Eslava-Gomez, “Discriminant analysis with gaussian graphical tree models,” _AStA Advances in Statistical Analysis_ , vol. 100, no. 2, pp. 161–187, 2016.
  * [23] C. J. Quinn, N. Kiyavash, and T. P. Coleman, “Directed information graphs,” _IEEE Tr. info. theory_ , vol. 61, no. 12, pp. 6887–6909, 2015.
  * [24] J. D. Ramsey, S. J. Hanson, C. Hanson, Y. O. Halchenko, R. A. Poldrack, and C. Glymour, “Six problems for causal inference from fmri,” _neuroimage_ , vol. 49, no. 2, pp. 1545–1558, 2010.
  * [25] D. Rothenhäusler, J. Ernest, P. Bühlmann, _et al._ , “Causal inference in partially linear structural equation models,” _Annals of Statistics_ , vol. 46, no. 6A, pp. 2904–2938, 2018.
  * [26] J. Saunderson, V. Chandrasekaran, P. A. Parrilo, and A. S. Willsky, “Tree-structured statistical modeling via convex optimization,” in _2011 50th IEEE CDC_. IEEE, 2011, pp. 2883–2888.
  * [27] F. Sepehr and D. Materassi, “Noninvasive approximation of linear dynamic system networks using polytrees,” _IEEE Transactions on Control of Network Systems_ , vol. 8, no. 3, pp. 1314–1323, 2021.
  * [28] A. Statnikov, M. Henaff, N. I. Lytkin, and C. F. Aliferis, “New methods for separating causes from effects in genomics data,” _BMC genomics_ , vol. 13, no. 8, pp. 1–16, 2012.
  * [29] V. Y. Tan, A. Anandkumar, and A. S. Willsky, “Learning gaussian tree models: Analysis of error exponents and extremal structures,” _IEEE Tr. on Sig. Pro._ , vol. 58, no. 5, pp. 2701–2714, 2010.
  * [30] V. Y. Tan, S. Sanghavi, J. W. Fisher, and A. S. Willsky, “Learning graphical models for hypothesis testing and classification,” _IEEE Tr. Sig. Pro._ , vol. 58, no. 11, pp. 5481–5495, 2010.
  * [31] V. Y. Tan and A. S. Willsky, “Sample complexity for topology estimation in networks of lti systems,” _IFAC Proceedings Volumes_ , vol. 44, no. 1, pp. 9079–9084, 2011.
  * [32] L. Vandenberghe and M. S. Andersen, “Chordal graphs and semidefinite optimization,” _Foundations and Trends in Optimization_ , vol. 1, no. 4, pp. 241–433, 2015.
  * [33] N. Wermuth, “Linear recursive equations, covariance selection, and path analysis,” _Journal of the American Statistical Association_ , vol. 75, no. 372, pp. 963–972, 1980.


# contact structure on 2-step nilpotent lie groups

babak hasanzadeye seyedi  young researchers and elit club islamic azad
university tabriz branch, iran<EMAIL_ADDRESS>
###### Abstract.

In this paper we study contact structure on 2-step nilpotent Lie groups. We
conside properties of normal subgroups and center of Lie groups while
cosymplectic and Sasakian structure defined on Lie group.

###### Key words and phrases:

contact structure, Lie group, nonsingular, skew adjoint

###### 1991 Mathematics Subject Classification:

Primary 53B40 , Secondary 53C60

##  1\. Introduction

let $\tilde{M}$ be an odd dimentional Riemannian manifold with a Riemannian
metric $g$ and Riemannian connection $\tilde{\nabla}$. Denote by $T\tilde{M}$
the Lie algebra of vector fields on $\tilde{M}$. Then $\tilde{M}$ is said to
be an almost contact metric manifold if there exist on $\tilde{M}$ a tensor
$\phi$ of type $(1,1)$, a vector field $\xi$ called structure vector field and
$\eta$, the dual 1-form of $\xi$ satisfying the following

(1.1) $\displaystyle\phi^{2}X=-X+\eta(X)\xi,g(X,\xi)=\eta(X)$ (1.2)
$\displaystyle\eta(\xi)=1,\phi(\xi)=0,\eta\circ\phi=0$ (1.3) $\displaystyle
g(\phi X,\phi Y)=g(X,Y)-\eta(X)\eta(Y)$

For any $X,Y\in T\tilde{M}$. In this case

(1.4) $\displaystyle g(\phi X,Y)=-g(X,\phi Y)$

Now, let $M$ be a submanifold immersed in $\tilde{M}$. A normal almost contact
manifold is called a cosymplectic manidfold if

(1.5) $\displaystyle(\tilde{\nabla}_{X}\phi)(Y)=0,\tilde{\nabla}_{X}\xi=0$

Theorem 1.1 An almost contact metric struture $(\phi,\xi,\eta,g)$ is Sasakian
if and only if

(1.6) $\displaystyle(\nabla_{X}\phi)Y=g(X,Y)\xi-\eta(Y)X$

The Riemannian metric induced on $M$ is denoted by the same symbol $g$. Let
$TM$ and $T^{\perp}M$ be the Lie algebras of vector fields tangential and
normal to $M$ respectively, and $\nabla$ be the induced Levi-Civita connection
on $M$, then the Gauss and Weingarten formulas are given by

(1.7) $\displaystyle\tilde{\nabla}_{X}Y=\nabla_{X}Y+h(X,Y)$ (1.8)
$\displaystyle\tilde{\nabla}_{X}V=-A_{V}X+\nabla^{\perp}_{X}V$

for any $X,Y\in TM$ and $V\in T^{\perp}M$. Where $\nabla^{\perp}$ is the
connection on the normal bundle $T^{\perp}M$, $h$ is the second fundamental
form and $A_{V}$ is the Weingarten map associated with $V$ as

(1.9) $\displaystyle g(A_{V}X,Y)=g(h(X,Y),V)$

For any $x\in M$ and $X\in T_{x}M$, we write

(1.10) $\displaystyle\phi X=\Psi X+\Gamma X$

where $\Psi X\in T_{x}M$ and $\Gamma X\in T^{\perp}_{x}M$. Similary, for $V\in
T^{\perp}_{x}M$, we have

(1.11) $\displaystyle\phi V=\psi V+\gamma V$

where $\psi V$ (resp. $\gamma$v ) is the tangential componenet (resp. normal
component) of $\phi V$. From (1.4) and (1.9), it is easy to observe that for
each $x\in M$, and $X,Y\in T_{x}M$

(1.12) $\displaystyle g(\Psi X,Y)=-g(X,\Psi Y)$

and therefore $g(\Psi^{2}X,Y)=g(X,\Psi^{2}Y)$ which implies that the
endomorphism $\Psi^{2}=Q$ is self adjoint. Moreover, it can be seen that the
eignvalues of $Q$ belong to $\left[-1,0\right]$ and that each non-vanishing
eigenvalue of $Q$ has even multiplicity. We define $\nabla\Psi$,$\nabla Q$ and
$\nabla N$ by

(1.13) $\displaystyle(\nabla_{X}\Psi)Y=\nabla_{X}\Psi Y-\Psi\nabla_{X}Y$
(1.14) $\displaystyle(\nabla_{X}Q)Y=\nabla_{X}QY-Q\nabla_{X}Y$ (1.15)
$\displaystyle(\nabla_{X}N)Y=\nabla^{\perp}_{X}NY-N\nabla_{X}Y$

for any $X,Y\in TM$.

##  2\. preliminaries

Difination 1.1. A Lie group G is a smooth manifold with group structure such
that

(2.1) $\displaystyle(i)G\times G\mapsto G\quad(ii)G\mapsto G$
$\displaystyle(x,y)\mapsto xy\quad x\mapsto x^{-1}$

Are smooth.
Difination 1.2. Let G is a Lie group and $a\in G$, thus

(2.2) $\displaystyle L_{a}:G\rightarrow G$ $\displaystyle x\mapsto ax$

is called left translation with a. Also map

(2.3) $\displaystyle R_{a}:G\rightarrow G$ $\displaystyle x\mapsto xa$

Is called right translation with a.Let G is a Lie group. Vector field $X$ on G
is left invariant if

(2.4) $\displaystyle L_{a}(X)=X\quad\forall a\in G$

And that is right invariant if

(2.5) $\displaystyle R_{a}(X)=X\quad\forall a\in G$

Difination 1.3. A Lie group H of a Lir group G is a subgroup which is also a
submanifold.
Difination 1.4. Here $F=\mathcal{R}$ or $\mathcal{C}$. A Lie algebra over F is
pair $(\mathfrak{g},[.,.])$, where $\mathfrak{g}$ is a vector space over F and

(2.6)
$\displaystyle[.,.]:\mathfrak{g}\times\mathfrak{g}\rightarrow\mathfrak{g}$

is an F-bilinear map satisfying the following properties

(2.7) $\displaystyle[X,Y]=-[Y,X]$ (2.8)
$\displaystyle[X,[Y,Z]]+[Z,[X,Y]]+[Y,[Z,X]]=0$

The latter is the Jacobi identity. In this paper for any $X,Y\in\mathfrak{g}$
we have

(2.9) $\displaystyle[X,Y]=\nabla_{X}Y-\nabla_{Y}X$

A Lie subalgebra of a Lie algebra is a vector space that is closed under
bracket.
Theorem 1.1. Let G is a Lie group and $\mathfrak{g}$ is a set of left
invariant vector field on G. We have
(i) $\mathfrak{g}$ is a vector space and map

$\displaystyle E:\mathfrak{g}\rightarrow T_{e}G$ $\displaystyle X\mapsto
X_{e}$

Is a linear isomorphism and therefore $dim\mathfrak{g}=dimT_{e}G=dimG$.(e is
identity element)
(ii) Left invariant vectro fields necessity are differentiable.
(iii) $(\mathfrak{g},[.,.])$ is Lie algebra.[6]
Difination 5.1. Lie algebra made of left invariant vector field on Lie group G
is called Lie algebras Lie group G. This Lie algebra is isomorphism with
$T_{e}G$, and we have

(2.10) $\displaystyle[X_{e},Y_{e}]=[X,Y]_{e}$

X and Y are unique left invariant vector field.
Theorem 2.1. Let G be a Lie group.[6]
(a) If H is a Lie subgroup of G, then $\mathfrak{h}\simeq T_{e}H\subset
T_{e}G\simeq\mathfrak{g}$ g is a Lie subalgebra.
(b) If $\mathfrak{h}\subset\mathfrak{g}$ a Lie subalgebra, there exists a
unique connected Lie subgroup $H\subset G$ with Lie algebra $\mathfrak{h}$.

For each nonzero vector field $X\in\mathfrak{g}$ , the angle $\theta(X)$;
$0\leq\theta(X)\leq\dfrac{\pi}{2}$ ; between $\phi X$ and $\mathfrak{g}$ is
called the Wirtinger angle of X. If the Wirtinger angle $\theta$ is a constant
its called slant angle of $\mathfrak{g}$. Let $H\subset G$ is a Lie subgroup
and $\mathfrak{h}$ is their Lie algebra, thus $\mathfrak{h}$ is Lie subalgebra
of $\mathfrak{g}$ and if $\mathfrak{h}$ is a slant Lie subalgebra, H is called
slant Lie subgroup.
If (G,g) be a Lie group equipted by Riemannian metric, ad is skew adjoint if
for $X,Y,Z\in\mathfrak{g}$, if

$\displaystyle g(adX(Y),Z)=-g(Y,adX(Z))$

If $X\in Z(\mathfrak{g})$ and $Y,z\in\mathfrak{g}$ we have

$\displaystyle X\langle Y,Z\rangle=\langle\nabla_{Y+Z}X,Y\rangle$

Theorem 2.3. Let g be a left invariant metric on a connected Lie group G. This
metric will also be right invariant if and only if ad(X) is skew-adjoint for
every $X\in\mathfrak{g}$.[2]

Definition 3.1. A nilpotent Lie group is a Lie group G which is connected and
whose Lie algebras is nilpotent Lie algebra $\mathfrak{g}$, that is, its Lie
algebra have a sequence of ideals of $\mathfrak{g}$ by
$\mathfrak{g}^{0}=\mathfrak{g}$,
$\mathfrak{g}^{1}=[\mathfrak{g},\mathfrak{g}]$,$\mathfrak{g}^{2}=[\mathfrak{g},\mathfrak{g}^{1}]$,…,
$\mathfrak{g}^{i}=[\mathfrak{g},\mathfrak{g}^{i-1}]$. $\mathfrak{g}$ is called
nilpotent if $\mathfrak{g}^{n}=0$ for some n.

Proposition 3.1.[3] Let $\mathfrak{g}$ be a Lie algebra.
(i)If $\mathfrak{g}$ is a nilpotent, then so are all subalgebras and
homomorphic images of $\mathfrak{g}$.
(ii) If $\dfrac{\mathfrak{g}}{Z(\mathfrak{g})}$ is nilpotent, then so is
$\mathfrak{g}$.
(iii)If $\mathfrak{g}$ is nilpotent and nonzero, then $Z(\mathfrak{g})\neq 0$.

Definition 3.2. A finite dimensional Lie algebra $\mathfrak{g}$ is 2-step
nilpotent if $\mathfrak{g}$ is not abelian and
$[\mathfrak{g},[\mathfrak{g},\mathfrak{g}]]=0$. A Lie group G is 2-step
nilpotent if its Lie algebra $\mathfrak{g}$ is 2-step nilpotent. In the other
word A Lie algebra $\mathfrak{g}$ is 2-step nilpotent if
$[\mathfrak{g},\mathfrak{g}]$ is non zero and Lies in the center of
$\mathfrak{g}$.
We may identify an element of $\mathfrak{g}$ witha left invariant vector field
on G since $T_{e}G$ may be identified with $\mathfrak{g}$. If X,y are left
invariant vector field on G, then $\nabla_{X}Y$ is left invariant also. for
$X,Y\in Z^{\perp}(\mathfrak{g})$ we have following formula:[7]

(2.11) $\displaystyle\nabla_{X}Y=\dfrac{1}{2}[X,Y]$

Definition 3.3. A 2-step nilpotent Lie algebra $\mathfrak{g}$ is nonsingular
if $adX:\mathfrak{g}\rightarrow Z(\mathfrak{g})$ is surjective for each $X\in
Z^{\perp}(\mathfrak{g})$. A 2-step nilpotent Lie group G is nonsingular if its
Lie algebra $\mathfrak{g}$ is nonsingular.

Let G denote a simply connected, 2-step nilpotent Lie group with a left
invariant metric $\langle.,.\rangle$ and let $\mathfrak{g}$ denote the Lie
algebra of G. Write $\mathfrak{g}=Z(\mathfrak{g})\oplus
Z^{\perp}(\mathfrak{g})$ where $Z^{\perp}(\mathfrak{g})$ its orthogonal
complement of center $Z(\mathfrak{g})$.

##  3\. cosymplectic and sasakian

In this section we study cosymplectic structure on 2-step nilpotent Lie
groups. Let G is a 2-step nilpotent Lie group with cosymplectic structure,
from (1.5) for any $X,Y\in\mathfrak{g}$ we have

(3.1) $\displaystyle[\phi X,Y]=[X,\phi Y]=\phi[X,Y]$

and

(3.2) $\displaystyle[X,\xi]=0$

Let G be a 2-step nilpotent nonsingular cosymplectic Lie group. if ad is skew
adjoint for any $X,Y\in\mathfrak{g}$ we have

(3.3) $\displaystyle\eta([X,Y])=g([X,Y],\xi)=-g([X,\xi],Y)$

From() we conclude $\eta(Z(\mathfrak{g}))=0$, thus $\xi$ is normal to
$Z(\mathfrak{g})$ and $\xi\in Z^{\perp}(\mathfrak{g})$, therefore
$Z(\mathfrak{g})$ is integral Lie subgroup and

(3.4) $\displaystyle\phi^{2}([X,Y])=[Y,X]$

## References

  * [1] David E. blair, _Riemannian Geometry of contact and symplectic manifolds._ department of mathematics Michigan state University, USA.
  * [2] J. Milnor, _Curvatures of Left Invariant Metrics on Lie Groups._ Advances in Math. 21 (1976),293-329.
  * [3] James. E Humphreys, _Introduction to Lie algebras and representation theory._ Springer-Verlag New york Hiedlberg Berlin (1972)
  * [4] Patrick Eberlein, _Geometry of 2-step nilpotent groups with a left invariant metric._ Ann. Sci. Ecole Norm. Sup. No. 27, p. 611-660(1994).
  * [5] S. Helgason, _Differential geometry and symmetric spaces._ Academic press, New York, (1962)
  * [6] Wolfgang Ziller, _Lie Groups. Representation Theory and Symmetric Spaces_ University of Pennsylvania, Fall 2010
  * [7] Patrick Eberlein, _Geometry of 2-step nilpotent groups with a left invariant metric II._ Transaction of the American mathematical society, volume 343, 805-828,(1994)
  * [8] Yu. Khakimdjanov, M. Gozea, A. Medinab _Symplectic or contact structures on Lie groups_ Differential Geometry and its Applications 21 (2004) 41–54
  * [9] André Diatta, _Left invariant contact structures on Lie groups_ Differential Geometry and its Applications 26 (2008) 544–552
  * [10] Brendan J. Foreman, _K-contact Lie groups of dimension five or greater._ arXiv:1006.1531v1
  * [11] Luis A. Cordero, Phillip E. Parker. _pseudo Riemannian 2-step nilpotent Lie groups._ arXiv:math/9905188v1
  * [12] André Diatta, _Riemannian geometry on contact Lie groups._ Geom Dedicata (2008) 133:83–94