mathx”17

# Generative Modeling via Tree Tensor Network States

Xun Tang  ,  YoonHaeng Hur  ,  Yuehaw Khoo  and  Lexing Ying  Institute for
Computational and Mathematical Engineering, Stanford, CA 94305, USA.
<EMAIL_ADDRESS>Department of Statistics, Chicago, IL 60637, USA.
<EMAIL_ADDRESS>Computational and Applied Mathematics Initiative,
Department of Statistics, University of Chicago, IL 60637, USA
<EMAIL_ADDRESS>Department of Mathematics and Institute for Computational
and Mathematical Engineering, Stanford, CA 94305, USA<EMAIL_ADDRESS>
###### Abstract.

In this paper, we present a density estimation framework based on tree tensor-
network states. The proposed method consists of determining the tree topology
with Chow-Liu algorithm, and obtaining a linear system of equations that
defines the tensor-network components via sketching techniques. Novel choices
of sketch functions are developed in order to consider graphical models that
contain loops. Sample complexity guarantees are provided and further
corroborated by numerical experiments.

##  1\. Introduction

Generative modeling of a probability distribution is one of the most important
tasks in machine learning, engineering and science. In a nutshell, the goal of
generative modeling is to approximate a high-dimensional distribution without
the curse of dimensionality. There are generally several properties one would
like to have for a generative model: (1) Can it be stored with a low memory
complexity as the dimension grows? (2) Can it be determined from the given
input with a low computational complexity? (3) Can it be used to generate
samples with a low computational complexity? In this paper, we propose using a
tree tensor network states as a generative model that enjoys these properties.

We focus on the problem of _density estimation_. More precisely, given $N$
independent samples

$(y_{1}^{(1)},\ldots,y_{d}^{(1)}),\ \ldots\
,(y_{1}^{(N)},\ldots,y_{d}^{(N)})\sim p^{\star}$

drawn from some ground truth density
$p^{\star}\colon\mathbb{R}^{d}\rightarrow\mathbb{R}$, our goal is to estimate
$p^{\star}$ from the empirical distribution

(1)
$\hat{p}(x_{1},\ldots,x_{d})=\frac{1}{N}\sum_{i=1}^{N}\delta_{(y_{1}^{(i)},\ldots,y_{d}^{(i)})}(x_{1},\ldots,x_{d}),$

where $\delta_{(y_{1},\ldots,y_{d})}$ is the $\delta$-measure supported on
$(y_{1},\ldots,y_{d})\in\mathbb{R}^{d}$. It is hard to give a comprehensive
survey of the broad field of density estimation, for this we refer readers to
[silverman2018density]. Here we review several popular generative models that
are related to our work. Energy based model [hinton2002training,
lecun2006tutorial, song2019generative] such as graphical models represents a
density by parameterizing it as the Gibbs measure of some energy function.
Mixture models approximate the distribution via a composition of simple
distributions. On the other hand, deep learning methods based on generative
adversarial networks [goodfellow2014generative], variational auto-encoders
[kingma2013auto] and normalizing flows [tabak2010density,
rezende2015variational] have gained tremendous popularity recently. Generally,
obtaining the parameter of these parameterizations in a density estimation
setting involves solving optimization problems that are often non-convex.
Therefore frequently theoretical consistency guarantees of a density estimator
cannot be achieved in practice. Furthermore, generating new samples from
optimized model could be difficult (for example in energy based model) and
requires running a Markov Chain Monte-Carlo.

Very recently, tensor-network methods, in particular matrix product
state/tensor train, have emerged as an alternative paradigm for generative
modeling [glasser2019expressive, 2202.11788, han2018unsupervised,
bradley2020modeling]. Such methods represent the exponentially size
$d$-dimensional tensor as a network of $d$ small tensors, achieving polynomial
storage complexity in $d$. Moreover, for networks that can be contracted
easily (e.g. tensor train), there exists an efficient strategy based on
conditional distribution method to generate independently and identically
distributed samples [dolgov2020approximation]. The question is then whether
one can determine the underlying tensor-network efficiently for the task of
density estimation. In [glasser2019expressive, han2018unsupervised,
bradley2020modeling], non-convex optimization approaches are applied to
determine the tensor cores. Unlike these previous approaches, in [2202.11788],
sketching is used to set up a set of parallel core determining system of
equations to determine the tensor cores of a tensor train without the use of
optimization. We propose several extensions that generalizes this work in
terms of its practicality and reach.

We emphasize that there is another line of works in tensor literature that
constructs low-rank tensor representations from sensing the entries of an
order $d$-tensor. These includes matrix completion [candes2010matrix] and its
generalizations to tensor completion problem (e.g. [khoo2017efficient,
gandy2011tensor, richard2014statistical]). Furthermore, cross-approximations
[oseledets2011tensor] has been applied to the cases where one gets to choose
the sensing pattern. The input data considered in these works are partial
observation of the entries of the $d$-dimensional function, which is different
from the case of density estimation, where empirical samples of the underlying
distribution is given.

We now give a discussion which compares our method with other existing
generative modelling methods. In Section 1.1, we compare TTNS with other
potential tensor network architectures for generative modelling. In Section
1.2, we discuss the connection between TTNS and tree-based graphical models.
In Section 1.3, we give a discussion on tensor network generative models which
are based on iterative training.

###  1.1. Extending tensor train to tree-based tensor networks

For the case where the underlying density $p^{\star}$ has a tensor train (TT)
format, an algorithm termed Tensor Train via Recursive Sketching (TT-RS)
[2202.11788] has been introduced. In this paper, we start from the more
general model assumption that $p^{\star}$ is in a Tree Tensor Network States
(TTNS) format [nakatani2013efficient], which is more suitable when the random
variables have a natural graph structure that is either a tree or locally
tree-like. In terms of representation power, there is a natural hierarchy

$\mathrm{TT}\subset\mathrm{TTNS}\subset\mathrm{TNS},$

where TNS stands for Tensor Network States, which includes more general models
such as projected entangled-pair states (PEPS) [verstraete2006criticality].
The generalization from TT to TTNS is an extension from a path-based tensor
network to a tree-based tensor network. TTNS is a generalized model which
still allows for efficient and scalable tensor contraction, a task in general
intractable for the TNS ansatz. See Figure 1 for an illustration of a tree and
its corresponding TTNS tensor diagram.

In the current literature, there is also another notion of Tree Tensor Network
(TTN) [cheng2019tree], which has been used for the task of generative
modeling. In [cheng2019tree], the TTN model is obtained by solving a non-
convex optimization problem, which is similar to [han2018unsupervised]. In
contrast, our algorithm allows the tensor components of a TTNS to be directly
solved, which leads to sample complexity guarantees that are hard to obtain
for iterative methods. Despite similarities, the same technique cannot easily
extend to TTN. The reason is due to the structural difference between TTN and
TTNS, which is that the latter does not involve internal nodes, i.e. each
tensor component in a TTNS ansatz has exactly one physical index, as shown in
Figure 1. In conclusion, TTN and TTNS are under quite different model
assumptions for the underlying density $p^{\star}$, and model inference of the
two models involve quite different numerical tools.

###  1.2. Extending model inference of tree-based graphical models to tree-
based tensor networks

Model inference for distributions with a TTNS ansatz is deeply related to the
model inference problem of tree-based graphical model. The Chow-Liu algorithm
[chow1968approximating] efficiently compresses a target density to the best
tree-based graphical model in the sense of Maximum Likelihood Estimation
(MLE). In terms of representational power, if the underlying distribution
$p^{\star}$ is a tree-based graphical model, then $p^{\star}$ is guaranteed to
have a tractable TTNS representation. On the other hand, the extra
representation power of TTNS over tree-based graphical models allows the model
to account for longer range interactions between variables. To the best of our
knowledge, this paper is the first instance where model inference of TTNS
ansatz has been implemented.

After the model inference step, in terms of downstream tasks such as
likelihood computation and sampling, both TTNS and tree-based graphical models
scales linearly in the dimension $d$. Importantly, the samples produced from
the TTNS ansatz have no auto-correlations and are i.i.d., which is a desirable
property for generative modeling.

We call our main method Tree Tensor Network State via Sketching (TTNS-Sketch).
By the sketching technique [woodruff2014sketching], the tensor components of
the ansatz can be computed entirely with conventional linear algebraic
equations, which results in a sample complexity which is quadratic in the
dimension $d$. In terms of computational complexity scaling, the cost is
linear in the sample size $N$, and at most quadratic in $d$. The method is
proven to be a consistent estimator under reasonable technical assumptions.

###  1.3. Comparison between TTNS-Sketch and iterative algorithms

In contrast to a direct method such as TTNS-Sketch, iterative algorithm for
tensor network methods (e.g. [han2018unsupervised, glasser2019expressive,
cheng2019tree]) typically optimizes for the tensor components in the sense of
minimal negative log likelihood, with the the maximum likelihood estimation
(MLE) estimator as the optimizer. Despite the well-known Cramer-Rao bound for
MLE estimators, the training in such iterative methods is non-convex, which
prevents one from establishing theoretical guarantees, e.g. consistency and
sample complexity. For example, [mcclean2018barren] identifies the issue of
vanishing gradient in randomly initialized quantum circuits for large qubit
size. Due to the representational equivalence between tensor train and quantum
circuits (see [glasser2019expressive] for a discussion), the same issue also
faces randomly initialized tensor train. This observation is also corroborated
by numerical experiment in Section 8, where we show training failure of
iterative methods under a setting far more modest than discussed in
[mcclean2018barren].

###  1.4. Main contribution

We list our main contribution as follows:

  1. (1)

We provide a simple notational system that can work well for arbitrary tree
structures for TTNS ansatz. This structural flexibility is helpful for samples
with an underlying tree structure but no practical path structure.

  2. (2)

We introduce perturbative sketching, motivated by randomized SVD
[lin2011fast]. We show that TTNS-Sketch with perturbative sketching performs
well for models with short-range non-local interactions, thus exhibiting
significant improvement over the graphical model given by Chow-Liu, which is
only suitable for tree-based graphical models.

  3. (3)

We derive a general upper bound on sample complexity of TTNS-Sketch. Based on
the Wedin theorem and Matrix Bernstein inequality, we obtain a non-asymptotic
sample complexity upper bound for TTNS-Sketch under recursive sketching
functions. Up to log factors and condition numbers, the sample complexity of
the method scales by $N=O\left(\Delta(T)^{2}d^{2}\right)$, where $d$ is the
number of nodes in the tree structure $T$, and $\Delta(T)$ stands for the
maximal degree of $T$. This shows that TTNS-Sketch converges reasonably fast
to the true model.

  4. (4)

We also identify a failure mode for iterative generative modeling methods
based on the tensor train ansatz. For Born Machine (BM) [han2018unsupervised]
under periodic spin system, we show that the training will fail unless one
significantly increases the internal bond dimension. When the tensor train is
of a correctly-sized internal bond dimension, the model learned by BM closely
resembles that of a non-periodic spin system. In comparison, with a simple
high-order Markov sketching function, TTNS-Sketch is successful at converging
to $p^{\star}$ without over-parameterization. See Section 8 for detail.

###  1.5. Outline

The outline for the rest of this paper is as follows. Section 2 is an
introduction to notations and to the basics of TTNS ansatz. Section 3 derives
the essential linear equation to be used for TTNS-Sketch. Section 4 introduces
the Chow-Liu algorithm for finding a tree structure using samples. Section 5
provides the main Algorithm and the condition for TTNS-Sketch to be a
consistent estimator. Section 6 gives examples of sketch functions. Section 7
provides a sample complexity upper bound. Section 8 gives the numerical
result.

##  2\. Introduction to TTNS

The aim in this section is to introduce the notation to describe a function
with a TTNS ansatz. We first introduce some important notations frequently
used. The letter $d$ is reserved for the dimension of the joint distribution
of interest, $N$ is reserved for sample size, and $T$ without subscript is
reserved for a tree graph. For any integer $q\in\mathbb{N}$, set
$[q]:=\\{1,\ldots,q\\}$.

For the TTNS ansatz, we use specific letters to label its indices. The letter
$x$ is reserved for the physical index (external bond) of the tensor core, and
the letters $\alpha,\beta,\gamma$ are reserved for the internal bond of the
tensor core.

Crucial equations are illustrated with a tensor diagram representation for
reader’s convenience. To provide a concrete example, all tensor diagrams are
plotted based on the specific tree structure set in Figure 1a.

Figure 1. (A) A tree structure $T=(V,E)$ with $V=\\{1,\ldots,10\\}$. (B)
Tensor Diagram representation of TTNS over $T$.

###  2.1. Notation for distribution

First we introduce notations related to probabilistic distributions.

######  Definition 1.

(Probability distribution notation) Fix a generic joint distribution $p$ on
$d$ variables. We use $X:=\left(X_{1},\ldots,X_{d}\right)$, where $X\sim p$,
to denote a random vector in $d$ dimension. Each $X_{k}$ is assumed to be a
discrete random variable over $\\{1,\ldots,n_{k}\\}$. Set
$n:=\max_{k\in[d]}n_{k}$.

######  Definition 2.

(Probability distribution for TTNS-Sketch) Suppose the distribution of
interest is for the random vector $X:=\left(X_{1},\ldots,X_{d}\right)$ in $d$
dimension, and moreover suppose one is given samples of $X$. The symbol
$\hat{p}$ denotes the _empirical distribution_ over samples of $X$. The symbol
$p^{\star}$ denotes the _underlying distribution_ of $X$.

For this paper, we only consider discrete variables. Hence a distribution
function such as $p^{\star}$ can be considered as a $d$-dimensional tensor.

###  2.2. Notation for tree structure

Next we introduce notations for a tree graph. A tree graph $T=(V,E)$ is a
connected undirected graph without cycles. Throughout this paper, $V=[d]$.
Moreover $T$ is specified with a root node, and vertices will have a partial
topological ordering generated by the child-parent relationship. For an
undirected edge $\\{w,k\\}$ in $T$, we write it interchangeably as $(w,k)$ or
$(k,w)$. If $k$ is the parent of $w$, we also write $\\{w,k\\}$ as $w\to k$
with the aim of signaling the child-parent hierarchy.

The following Definition 3 contains the notation for the graph-theoretic
concept one needs to define a TTNS. See Figure 2 for an illustration.

######  Definition 3.

(Tree topology notation) For a rooted tree structure $T$ with nodes $V=[d]$
and any $k\in[d]$, define $\mathcal{C}(k),\mathcal{P}(k),\mathcal{N}(k)$
respectively as the children, parent, and neighbors of $k$. In particular, one
has $|\mathcal{P}(k)|\leq 1$ and
$\mathcal{N}(k)=\mathcal{C}(k)\cup\mathcal{P}(k)$. Moreover, define
$\mathcal{E}(k)$ as the set of edges incident to $k$. Define
$\mathcal{L}(k),\mathcal{R}(k)$ respectively as the descendant, non-descendant
of node $k$ in $T$. In particular, $\mathcal{L}(k)$ and $\mathcal{R}(k)$ are
respectively called the _left_ and the _right_ of node $k$.

Importantly, in Definition 4, we introduce several short-hands in order to
write joint variables compactly.

######  Definition 4.

(Joint variable notation) For variables indexed by nodes on $T$, we write
$x_{\mathcal{S}}$ to denote the joint variable $(x_{i_{1}},\ldots,x_{i_{k}})$,
where $\mathcal{S}=\\{i_{1},\ldots,i_{k}\\}\subset V$.

Likewise, for variables indexed by edges on $T$, we write
$\alpha_{\mathcal{U}}$ to denote the joint index
$(\alpha_{e_{i_{1}}},\ldots,\alpha_{e_{i_{k}}})$, where
$\mathcal{U}=\\{e_{i_{1}},\ldots,e_{i_{k}}\\}\subset E$. In particular,
$\mathcal{U}\subset E$ is typically all incident to one node $w$, and we write
$\alpha_{(w,\mathcal{S})}$ to denote the joint variable
$(\alpha_{(w,i_{1})},\ldots,\alpha_{(w,i_{k})})$, where
$\mathcal{S}=\\{i_{1},\ldots,i_{k}\\}\subset V$. For compactness, we write
$x_{\mathcal{S}\cup k}:=x_{\mathcal{S}\cup\\{k\\}}$, where the element $k$ is
used in place of the singleton set $\\{k\\}$.

Frequently used symbols include $x_{\mathcal{L}(k)}$, $x_{\mathcal{R}(k)}$,
$x_{\mathcal{C}(k)}$, which respectively denote the joint variable
corresponding to the left, the right, and the children of $k$. Moreover, we
use $x_{\mathcal{L}(k)\cup k}$ to denote the joint variable corresponding to
nodes which are not on the right-side of $k$. For edge-indexed variables, we
use $\alpha_{(k,\mathcal{C}(k))}$ to denote the joint variables corresponding
to the edges between $k$ and its children.

Figure 2. Illustration of tree topology notation. For the tree in Figure 1a,
if 7 is the root, then $\mathcal{C}(4)=\\{2,5\\}$, $\mathcal{P}(4)=6$,
$\mathcal{L}(4)=\\{1,2,3,5\\}$, and $\mathcal{R}(4)=\\{6,7,8,9,10\\}$. In this
graph, one also has $\mathcal{N}(4)=\\{2,5,6\\}$ and
$\mathcal{E}(4)=\\{(4,2),(4,5),(4,6)\\}$.

###  2.3. Notation for TTNS ansatz

We introduce condition and notation for a generic tensor with TTNS ansatz. We
will prove that having a TTNS ansatz is equivalent to satisfying the TTNS
condition, i.e. having a low rank factorization structure along a tree. See
Figure 3 for an illustration.

######  Condition 1.

(TTNS condition) Let $T=(V,E)$ be a rooted tree graph, and let
$\\{r_{e}\\}_{e\in E}$ be a collection of positive integers, where $r_{(w,k)}$
denotes internal bond rank at the edge $(w,k)$.

A function $p\colon\prod_{k=1}^{d}[n_{k}]\rightarrow\mathbb{R}$ is said to
satisfy the TTNS ansatz condition if for every edge $(w,k)\in E$, there exists
a rank $r_{(w,k)}$ decomposition $\Phi_{w\to
k}\colon\prod_{i\in\mathcal{L}(w)\cup w}[n_{i}]\times[r_{(w,k)}]\to\mathbb{R}$
and $\Psi_{w\to
k}\colon[r_{(w,k)}]\times\prod_{i\in\mathcal{R}(w)}[n_{i}]\to\mathbb{R}$ such
that

(2) $p(x_{1},\ldots,x_{d})=\sum_{\alpha_{(w,k)}=1}^{r_{(w,k)}}\Phi_{w\to
k}(x_{\mathcal{L}(w)\cup w},\alpha_{(w,k)})\Psi_{w\to
k}(\alpha_{(w,k)},x_{\mathcal{R}(w)}).$

Figure 3. Tensor diagram representation of the TTNS ansatz assumption in
Condition 1. The illustration is over the rooted tree in Figure 2 with
$(w,k)=(4,6)$. The symbol $x_{\mathcal{L}(4)}=(x_{1},x_{2},x_{3},x_{5})$ and
$x_{\mathcal{R}(4)}=(x_{6},x_{7},\ldots,x_{10})$ is a short-hand for joint
variables as defined in Definition 4.

More explicitly, a TTNS ansatz can be defined in terms of tensor cores.
Definition 5 shows a construction in terms of tensor cores. For illustration,
see Figure 1b.

######  Definition 5.

(TTNS tensor core and TTNS ansatz notation) Given a tree structure $T=([d],E)$
and corresponding ranks $\\{r_{e}:e\in E\\}$. The _TTNS tensor core_ at $k$ is
denoted by $G_{k}$. Let $d_{k}$ stand for the degree of $k$ in $T$, and then
$G_{k}$ is defined as an $(d_{k}+1)$-tensor of the following shape:

$G_{k}:[n_{k}]\times\prod_{e\in\mathcal{E}(k)}[r_{e}]\rightarrow\mathbb{R}.$

We say that a function $p$ admits a TTNS ansatz over tensor cores
$\\{G_{i}\\}_{i=1}^{d}$ over $k=1,\ldots,d$ if

(3) $p(x_{1},\ldots,x_{d})=\sum_{\begin{subarray}{c}\alpha_{e}\in[r_{e}]\\\
e\in
E\end{subarray}}\left(\prod_{k=1}^{d}G_{k}\left(x_{k},\alpha_{\left(k,\mathcal{N}(k)\right)}\right)\right).$

For an example, when $T=(V,E)$ is a chain with $E=\\{(k,k+1)\\}_{k=1}^{d-1}$,
a TTNS ansatz is a tensor train ansatz. In Figure 1a, we show a tree structure
over $10$ vertices, and the corresponding tensor diagram for TTNS is given in
Figure 1b. For instance,
$G_{4}\colon[n_{4}]\times[r_{(4,2)}]\times[r_{(4,5)}]\times[r_{(4,6)}]\to\mathbb{R}$
in Figure 1b, and the tensor network defines a $d$-dimensional function after
the contraction of internal bonds.

Importantly, when working with high-dimensional functions, it is often
convenient to group the variables into two subsets and think of the resulting
object as a matrix. The notion is referred to as unfolding matrix, and defined
as follows:

######  Definition 6.

(Unfolding matrix notation) For a generic $D$-dimensional tensor
$f\colon[n_{1}]\times\cdots\times[n_{D}]\to\mathbb{R}$ and for two disjoint
subsets $\mathcal{U},\mathcal{V}$ with $\mathcal{U}\cup\mathcal{V}=[D]$, we
define the corresponding _unfolding matrix_ by
$f(x_{\mathcal{U}};x_{\mathcal{V}})$. Namely, group the variables indexed by
$\mathcal{U}$ and the ones indexed by $\mathcal{V}$ to form rows and columns,
respectively. The matrix $f(x_{\mathcal{U}};x_{\mathcal{V}})$ is of size
$\left(\prod_{i\in\mathcal{U}}n_{i}\right)\times\left(\prod_{j\in\mathcal{V}}n_{j}\right)$.

As an example, for a function $p$ satisfying TTNS assumption in Condition 1,
define the unfolding matrix of $p$ at the edge $w\to k\in E$ as
$p(x_{\mathcal{L}(w)\cup w};x_{\mathcal{R}(w)})$, which is of size
$\left(\prod_{i\in\mathcal{L}(w)\cup
w}n_{i}\right)\times\left(\prod_{j\in\mathcal{R}(w)}n_{j}\right)$. Viewed in
this context, Condition 1 exactly means that the unfolding matrix of $p$ at
any edge $(w,k)\in E$ is a matrix of rank $r_{(w,k)}$.

###  2.4. Equation for TTNS ansatz

We now show that Condition 1 implies the existence of a TTNS ansatz in the
sense of Definition 5. With the information for every $\Phi_{w\to k}$ in
Condition 1, there exists an equation for obtaining the TTNS tensor cores
exactly. We summarize this result in Theorem 7, which shows that one can
obtain cores of a TTNS by solving a recursive system of linear equations. See
Figure 6(a) for an illustration.

######  Theorem 7.

Suppose Condition 1 holds for a rooted tree structure $T=([d],E)$ and bond
information $\\{r_{e}\\}_{e\in E}$. For non-leaf $k$, define

$\Phi_{\mathcal{C}(k)\to k}=\bigotimes_{w\in\mathcal{C}(k)}\Phi_{w\to k},$

and in terms of entries one has $\Phi_{\mathcal{C}(k)\to
k}\colon\prod_{w\in\mathcal{L}(k)}[n_{w}]\times\prod_{w\in\mathcal{C}(k)}[r_{(w,k)}]\to\mathbb{R}$,
and

(4) $\Phi_{\mathcal{C}(k)\to
k}(x_{\mathcal{L}(k)},\alpha_{(k,\mathcal{C}(k))})=\prod_{w\in\mathcal{C}(k)}\Phi_{w\to
k}(x_{\mathcal{L}(w)},\alpha_{(k,w)}).$

Then
$G_{k}\colon[n_{k}]\times\prod_{w\in\mathcal{N}(k)}[r_{(w,k)}]\to\mathbb{R}$
satisfies the following linear Core Determining Equations (CDE) for
$k=1,\ldots,d$:

(5) $\displaystyle G_{k}$
$\displaystyle=\Phi_{k\to\mathcal{P}(k)}\quad\text{if}~{}k~{}\text{is a
leaf},$
$\displaystyle\sum_{\alpha_{(k,\mathcal{C}(k))}}\Phi_{\mathcal{C}(k)\to
k}(x_{\mathcal{L}(k)},\alpha_{(k,\mathcal{C}(k))})G_{k}(x_{k},\alpha_{(k,\mathcal{N}(k))})$
$\displaystyle=p(x_{1},\ldots,x_{d})\quad\text{if}~{}k~{}\text{is the root},$
$\displaystyle\sum_{\alpha_{(k,\mathcal{C}(k))}}\Phi_{\mathcal{C}(k)\to
k}(x_{\mathcal{L}(k)},\alpha_{(k,\mathcal{C}(k))})G_{k}(x_{k},\alpha_{(k,\mathcal{N}(k))})$
$\displaystyle=\Phi_{k\to\mathcal{P}(k)}(x_{\mathcal{L}(k)\cup
k},\alpha_{(k,\mathcal{P}(k))})\quad\text{otherwise}.$

Then, each equation of (5) has a unique solution, and $p$ has a TTNS ansatz
over the cores $\\{G_{i}\\}_{i=1}^{d}$ in the sense of Definition 5.

The proof is deferred to the Appendix, but we will give a rough idea on why
$p$ admits a TTNS ansatz over $\\{G_{i}\\}_{i=1}^{d}$. Equation (5) for when
$k$ is not root essentially shows that each $\Phi_{w\to k}$ can be represented
by tensor contractions of cores in $\\{G_{i}\\}_{i\in\mathcal{L}(w)\cup w}$,
and the proof is based on simple mathematical induction. From this
observation, one can work with Equation (5) for when $k$ is the root, and
replace all of the $\Phi_{w\to k}$ terms by $\\{G_{i}\\}_{i\not=\text{root}}$,
and the obtained equation will be exactly (3) in Definition 5.

In summary, Theorem 7 shows how Condition 1 leads to existence of a TTNS
ansatz, and the our previous remark on the construction of $\Phi_{w\to k}$
from $\\{G_{i}\\}_{i\in\mathcal{L}(w)\cup w}$ also shows a TTNS ansatz also
leads to Condition 1. However, from a computational point of view, the linear
system (5) in Theorem 7 is intractable and we shall address this issue using
sketching in the next section.

##  3\. Main idea of TTNS-Sketch

In the setting of this section, $p^{\star}$ admits a TTNS ansatz over $T$ and
$\\{r_{e}\\}_{e\in E}$ in the sense of Definition 5. We show the derivation of
the linear equation which are used to solve for the TTNS tensor cores in TTNS-
Sketch. However, obtaining terms in the derived linear system rely on access
to $p^{\star}$, an assumption which we will later relax by sample
approximation. To emphasize this point, all of the intermediate terms from
this algorithm will be labelled with the upper-index $\star$ if it assumes
access to or is derived from $p^{\star}$.

###  3.1. Gauge degree of freedom for a TTNS ansatz

By Theorem 7, a function $p^{\star}$ having a TTNS ansatz is equivalent to the
condition that its unfolding matrix along each edge of a tree has a low rank
structure. Moreover, the ansatz is non-unique. This notion is typically called
the gauge degree of freedom, which we will introduce here.

Let us view $p^{\star}$ by the unfolding matrix
$p^{\star}(x_{\mathcal{L}(w)\cup w};x_{\mathcal{R}(w)})$. For any edge $w\to
k$, the TTNS condition assumes that there exists $\Phi^{\star}_{w\to
k}\colon\prod_{i\in\mathcal{L}(w)\cup w}[n_{i}]\times[r_{(w,k)}]\to\mathbb{R}$
and $\Psi^{\star}_{w\to
k}\colon[r_{(w,k)}]\times\prod_{i\in\mathcal{R}(w)}[n_{i}]\to\mathbb{R}$ such
that

$p^{\star}(x_{\mathcal{L}(w)\cup
w},x_{\mathcal{R}(w)})=\sum_{\alpha_{(w,k)}}\Phi^{\star}_{w\to
k}(x_{\mathcal{L}(w)\cup w},\alpha_{(w,k)})\Psi^{\star}_{w\to
k}(\alpha_{(w,k)},x_{\mathcal{R}(w)}).$

One can view $p^{\star}$ as the unfolding matrix structure
$p^{\star}(x_{\mathcal{L}(w)\cup w};x_{\mathcal{R}(w)})$. Likewise,
$\Phi^{\star}_{w\to k}$ as $\Phi^{\star}_{w\to k}(x_{\mathcal{L}(w)\cup
w};\alpha_{(w,k)})$ and $\Psi^{\star}_{w\to k}$ as $\Psi^{\star}_{w\to
k}(\alpha_{(w,k)};x_{\mathcal{R}(w)})$. Then, by using the usual matrix
product notation, the TTNS assumption along the edge $w\to k$ is
$p^{\star}=\Phi^{\star}_{w\to k}\Psi^{\star}_{w\to k}.$ Then, for any $R$
being a nonsingular $r_{(w,k)}\times r_{(w,k)}$ matrix, one has

$p^{\star}=\Phi^{\star}_{w\to k}\Psi^{\star}_{w\to k}=(\Phi^{\star}_{w\to
k}R)(R^{-1}\Psi^{\star}_{w\to k}).$

Given the information of $\\{\Phi^{\star}_{w\to k}\\}_{w\to k\in E}$, solving
for the tensor core $G^{\star}_{k}$ follows from (5) in Theorem 7. Multiplying
any $\Phi^{\star}_{w\to k}$ by a matrix $R$ will thus result in a different
TTNS ansatz for $p^{\star}$. In summary, a gauge degree of freedom in the low-
rank decomposition of $p^{\star}$ leads to a gauge degree of freedom in the
TTNS ansatz of $p^{\star}$.

The collection $\\{\Phi^{\star}_{w\to k},\Psi^{\star}_{w\to k}\\}_{w\to k\in
E}$ will later be chosen to have an explicit gauge, but currently it suffices
to understand gauge as fixed. The desired TTNS ansatz
$\\{G^{\star}_{i}\\}_{i=1}^{d}$ as solution to (5) is also fixed.

###  3.2. Sketching down core determining equation

Without loss of generality, we consider the equation for $G^{\star}_{k}$ in
Theorem 7 where $k$ is neither a root nor a leaf node. We can rewrite the
corresponding equation for $G^{\star}_{k}$ by substituting
$\Phi^{\star}_{\mathcal{C}(k)\rightarrow k}$ according to definition:

(6) $\sum_{\begin{subarray}{c}\alpha_{(w,k)}\\\
w\in\mathcal{C}(k)\end{subarray}}\left(\prod_{w\in\mathcal{C}(k)}\Phi^{\star}_{w\to
k}(x_{\mathcal{L}(w)\cup
w},\alpha_{(w,k)})\right)G^{\star}_{k}(x_{k},\alpha_{(k,\mathcal{C}(k))},\alpha_{(k,\mathcal{P}(k))})=\Phi^{\star}_{k\to\mathcal{P}(k)}(x_{\mathcal{L}(k)\cup
k},\alpha_{(k,\mathcal{P}(k))}),$

which is an over-determined linear system on $G_{k}^{\star}$, and the number
of linear equations for $G_{k}^{\star}$ grows exponentially in $d$. Hence the
above equation is not tractable.

The TTNS-Sketch algorithm applies the sketching operation to (6) and projects
tensors of the form $\Phi_{w\to k}$ in (6) to a tensor of tractable size,
which makes the equation tractable. In TTNS-Sketch, for each edge $w\to k$, we
define a series of linear projection operators of the form

$S_{w\to k}\colon[l_{(w,k)}]\times\prod_{v\in\mathcal{L}(w)\cup
w}[n_{v}]\rightarrow\mathbb{R},$

and they globally form an function which we call the _left-sketch function_
$S_{k}$ of the form

$S_{k}\colon\prod_{w\in\mathcal{C}(k)}[l_{(w,k)}]\times\prod_{i\in\mathcal{L}(k)}[n_{i}]\to\mathbb{R}.$

The definition of $S_{k}$ is by the simple formula
$S_{k}=\bigotimes_{w\in\mathcal{C}(k)}S_{w\to k}$, or equivalently

(7)
$S_{k}(\beta_{(k,\mathcal{C}(k))},x_{\mathcal{L}(k)})=\prod_{w\in\mathcal{C}(k)}S_{w\to
k}(\beta_{(w,k)},x_{\mathcal{L}(w)\cup w}).$

We remark that the factorization structure of $S_{k}$ in (7) depends on a
simple topological fact on trees, which is that
$\left(\mathcal{L}(w)\cup\\{w\\}\right)_{w\in\mathcal{C}(k)}$ are pairwise
disjoint and their union forms $\mathcal{L}(k)$.

Now, we can apply the usual projection to (6) using $S_{k}$, i.e. multiplying
both sides by $S_{k}$ and summing over $x_{\mathcal{L}(k)}$. For the RHS of
(6) after projection, we define a tensor
$B^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k},\alpha_{(k,\mathcal{P}(k))})$
to represent this result, i.e.

(8)
$B^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k},\alpha_{(k,\mathcal{P}(k))}):=\sum_{x_{\mathcal{L}(k)}}S_{k}(\beta_{(k,\mathcal{C}(k))},x_{\mathcal{L}(k)})\Phi^{\star}_{k\to\mathcal{P}(k)}(x_{\mathcal{L}(k)\cup
k},\alpha_{(k,\mathcal{P}(k))}).$

For the LHS of of (6), we define a tensor
$A^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},\alpha_{(k,\mathcal{C}(k))})$ to
represent the coefficient term for $G^{\star}_{k}$ under projection:

(9)
$A^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},\alpha_{(k,\mathcal{C}(k))}):=\sum_{x_{\mathcal{L}(k)}}S_{k}(\beta_{(k,\mathcal{C}(k))},x_{\mathcal{L}(k)})\prod_{w\in\mathcal{C}(k)}\Phi^{\star}_{w\to
k}(x_{\mathcal{L}(w)\cup w},\alpha_{(w,k)})$

The equation (6) then projects to the linear equation:

(10)
$\sum_{\alpha_{(k,\mathcal{C}(k))}}A^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},\alpha_{(k,\mathcal{C}(k))})G^{\star}_{k}(x_{k},\alpha_{(k,\mathcal{C}(k))},\alpha_{(k,\mathcal{P}(k))})=B^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k},\alpha_{(k,\mathcal{P}(k))}),$

which is an equation of the simple form of
$A^{\star}_{k}G^{\star}_{k}=B^{\star}_{k}$ when viewing each tensor by
appropriate unfolding matrix structures. This linear equation is illustrated
in Figure 6(b).

In the sketched down linear system, the number of linear equations for
$G^{\star}_{k}$ no longer scales with $d$, and one can check that it is
tractable. Moreover, due to the factorization structure of $S_{k}$ using
$S_{w\to k}$, it follows that $A^{\star}_{k}$ simplifies to

(11)
$A^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},\alpha_{(k,\mathcal{C}(k))})=\prod_{w\in\mathcal{C}(k)}\sum_{x_{\mathcal{L}(w)\cup
w}}S_{w\to k}(\beta_{(w,k)},x_{\mathcal{L}(w)\cup w})\Phi^{\star}_{w\to
k}(x_{\mathcal{L}(w)\cup w},\alpha_{(w,k)}),$

which can be readily seen from the diagram in Figure 6(b).

###  3.3. Derivation of $A^{\star}_{k}$ and $B^{\star}_{k}$ in TTNS-Sketch

For the time being, $A^{\star}_{k}$ and $B^{\star}_{k}$ is defined from
$\Phi^{\star}_{w\to k}$, and we now show how one can lift this requirement. We
define the _right-sketch function_ $T_{k}$, which is a linear operator of the
form

$T_{k}\colon\prod_{i\in\mathcal{R}(k)}[n_{i}]\times[m_{(k,\mathcal{P}(k))}]\to\mathbb{R}.$

Using $T_{k}$ and $S_{k}$, one can jointly form a linear projection of
$p^{\star}$, with the result referred to as $Z^{\star}_{k}$, as follows:

(12)
$Z^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k},\gamma_{(k,\mathcal{P}(k))})=\sum_{x_{\mathcal{L}(k)\cup\mathcal{R}(k)}}S_{k}(\beta_{(k,\mathcal{C}(k))},x_{\mathcal{L}(k)})p^{\star}(x_{\mathcal{L}(k)},x_{k},x_{\mathcal{R}(k)})T_{k}(x_{\mathcal{R}(k)},\gamma_{(k,\mathcal{P}(k))}).$

One then performs singular value decomposition (SVD) to $Z^{\star}_{k}$
according to the unfolding
$Z^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k};\gamma_{(k,\mathcal{P}(k))})$.
Due to the low rank structure of $p^{\star}$ at $k\to\mathcal{P}(k)$, the
following rank $r_{(k,\mathcal{P}(k))}$ decomposition is exact:

(13)
$Z^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k};\gamma_{(k,\mathcal{P}(k))})=U^{\star}_{k}\Sigma^{\star}_{k}\left(V^{\star}_{k}\right)^{\top}.$

Figure 4. Tensor diagram of the sketching step in (12) and the SVD step in
(13). The illustration is over the rooted tree in Figure 2.

Set $Q^{\star}_{k}=V^{\star}_{k}\left(\Sigma^{\star}_{k}\right)^{-1}$ and
$\left(Q_{k}^{\star}\right)^{\top}=\Sigma^{\star}_{k}\left(V_{k}^{\star}\right)^{\top}$.
Note that $\left(Q_{k}^{\star}\right)^{\top}$ is the pseudo-inverse of
$Q^{\star}_{k}$. In particular, one has

$Z^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k};\gamma_{(k,\mathcal{P}(k))})=U^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k};\alpha_{(k,\mathcal{P}(k))})\left(Q^{\star}_{k}\right)^{\top}(\alpha_{(k,\mathcal{P}(k))};\gamma_{(k,\mathcal{P}(k))}).$

As a summary of $Z_{k}^{\star},U_{k}^{\star},Q_{k}^{\star}$, see illustration
in Figure 4.

One can naturally shape
$U^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k};\alpha_{(k,\mathcal{P}(k))})$
as a tensor of the index
$U^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k},\alpha_{(k,\mathcal{P}(k))})$,
i.e.
$U^{\star}_{k}\colon\prod_{w\in\mathcal{C}(k)}[l_{(w,k)}]\times[n_{k}]\times[m_{(k,\mathcal{P}(k))}]\rightarrow\mathbb{R}$.
We now write out our choice of gauge and its consequences in Condition 2:

######  Condition 2.

(TTNS-Sketch gauge choice) The gauge for $\Phi^{\star}_{k\to\mathcal{P}(k)}$
is chosen so that the following holds:

(14)
$U^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k},\alpha_{(k,\mathcal{P}(k))})=\sum_{x_{\mathcal{L}(k)}}S_{k}(\beta_{(k,\mathcal{C}(k))},x_{\mathcal{L}(k)})\Phi^{\star}_{k\to\mathcal{P}(k)}(x_{\mathcal{L}(k)\cup
k},\alpha_{(k,\mathcal{P}(k))}).$

As a consequence of (14) and (8), one has:

(15) $B^{\star}_{k}=U^{\star}_{k}.$

As a consequence of (13), the matrix $\left(Q^{\star}_{k}\right)^{\top}$ is a
projection of $\Psi^{\star}_{k\to\mathcal{P}(k)}$ by $T_{k}$, i.e.

(16)
$\left(Q^{\star}_{k}\right)^{\top}(\alpha_{(k,\mathcal{P}(k))},\gamma_{(k,\mathcal{P}(k))})=\sum_{x_{\mathcal{R}(k)}}\Psi^{\star}_{k\to\mathcal{P}(k)}(\alpha_{(k,\mathcal{P}(k))},x_{\mathcal{R}(k)})T_{k}(x_{\mathcal{R}(k)},\gamma_{(k,\mathcal{P}(k))}).$

Likewise, we now show how $A^{\star}_{k}$ can be obtained. By the choice of
gauge in Condition 2, one forms Corollary 8. In Figure 5, we include an short
proof using tensor diagram. As a consequence of Corollary 8, one can form a
linear system for $G_{k}^{\star}$ completely in terms of the sketches
$\\{Z^{\star}_{w\to k}\\}_{w\to k\in E},\\{Z^{\star}_{i}\\}_{i=1}^{d}$, which
can be reasonably approximated by samples. As an illustration, one can rewrite
the tensor diagram in Figure 6(b) as the new diagram illustrated in Figure
6(c).

Figure 5. Proof of Corollary 8 in terms of tensor diagram. Both equality holds
due to (17). Then, the tensors enclosed in red box coincide due to (16), and
so the tensors enclosed in blue box coincide, which is what we need to show.

######  Corollary 8.

Define the intermediate terms $Z^{\star}_{w\to k}$ and $A^{\star}_{w\to k}$ as
follows:

(17) $\displaystyle Z^{\star}_{w\to k}(\beta_{(w,k)},\gamma_{(w,k)})$
$\displaystyle=\sum_{x_{[d]}}S_{w\to k}(\beta_{(w,k)},x_{\mathcal{L}(w)\cup
w})p^{\star}(x_{\mathcal{L}(w)\cup
w},x_{\mathcal{R}(w)})T_{w}(x_{\mathcal{R}(w)},\gamma_{(w,k)})$ $\displaystyle
A^{\star}_{w\to k}(\beta_{(w,k)},\alpha_{(w,k)})$
$\displaystyle=\sum_{\gamma_{(w,k)}}Z^{\star}_{w\to
k}(\beta_{(w,k)},\gamma_{(w,k)})Q^{\star}_{w}(\gamma_{(w,k)},\alpha_{(w,k)}),$

Then $A^{\star}_{k}$ satisfies the following equation

(18)
$A^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},\alpha_{(k,\mathcal{C}(k))})=\prod_{w\in\mathcal{C}(k)}A^{\star}_{w\to
k}(\beta_{(w,k)},\alpha_{(w,k)}).$

###### Proof.

By the factorization structure of $A^{\star}_{k}$, it suffices to show that

$A^{\star}_{w\to k}(\beta_{(w,k)},\alpha_{(w,k)})=\sum_{x_{\mathcal{L}(w)\cup
w}}S_{w\to k}(\beta_{(w,k)},x_{\mathcal{L}(w)\cup w})\Phi^{\star}_{w\to
k}(x_{\mathcal{L}(w)\cup w},\alpha_{(w,k)}).$

We use a unfolding matrix structure for $Z^{\star}_{w\to k},S_{w\to k},T_{w}$
in the following rewrite of (17):

$Z^{\star}_{w\to k}(\beta_{(w,k)};\gamma_{(w,k)})=S_{w\to
k}(\beta_{(w,k)};x_{\mathcal{L}(w)\cup w})p^{\star}(x_{\mathcal{L}(w)\cup
w};x_{\mathcal{R}(w)})T_{w}(x_{\mathcal{R}(w)};\gamma_{(w,k)})$

Likewise, we use the unfolding matrix structure of
$p^{\star},\Phi^{\star}_{w\to k},\Psi^{\star}_{w\to k}$ in

$p^{\star}(x_{\mathcal{L}(w)\cup w};x_{\mathcal{R}(w)})=\Phi^{\star}_{w\to
k}(x_{\mathcal{L}(w)\cup w};\alpha_{(w,k)})\Psi^{\star}_{w\to
k}(\alpha_{(w,k)};x_{\mathcal{R}(w)}).$

Using the unfolding matrix structure as just suggested, it suffices to prove

$A^{\star}_{w\to k}=S_{w\to k}\Phi^{\star}_{w\to k}.$

The definition for the intermediate term $Z^{\star}_{w\to k}$ simplifies to
$Z^{\star}_{w\to k}=S_{w\to k}p^{\star}T_{w}$ and more importantly,

$A^{\star}_{w\to k}=Z^{\star}_{w\to k}Q^{\star}_{w}=S_{w\to
k}p^{\star}T_{w}Q^{\star}_{w}.$

Note that one can expand according to $p^{\star}=\Phi_{w\to
k}^{\star}\Psi^{\star}_{w\to k}$ and get

$A^{\star}_{w\to k}=S_{w\to k}\Phi_{w\to k}^{\star}\Psi^{\star}_{w\to
k}T_{w}Q^{\star}_{w}=S_{w\to k}\Phi_{w\to
k}^{\star}\left(Q^{\star}_{w}\right)^{\top}Q^{\star}_{w}=S_{w\to k}\Phi_{w\to
k}^{\star},$

where the second equality uses (16) and last equality uses that
$\left(Q^{\star}_{w}\right)^{\top}Q^{\star}_{w}$ is an identity matrix. ∎

###  3.4. Sample estimation of $A^{\star}_{k}$ and $B^{\star}_{k}$ in TTNS-
Sketch

Practically, one only has access to the empirical distribution $\hat{p}$ via
samples $\\{(y_{1}^{(i)},\ldots,y_{d}^{(i)})\\}_{i=1}^{N}$. A finite sample
approximation of $Z^{\star}_{k}$ is tractable and can be obtained by function
evaluations of $T_{k}$ and $S_{k}$. One has

(19)
$\hat{Z}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k},\gamma_{(k,\mathcal{P}(k))})=\sum_{i=1}^{N}S_{k}(\beta_{(k,\mathcal{C}(k))},y_{\mathcal{L}(k)}^{(i)})\mathbf{1}(y_{k}^{(i)}=x_{k})T_{k}(y_{\mathcal{R}(k)}^{(i)},\gamma_{(k,\mathcal{P}(k))}).$

Similarly, $Z^{\star}_{w\to k}$ can be approximated by

(20) $\hat{Z}_{w\to k}(\beta_{(w,k)},\gamma_{(w,k)})=\sum_{i=1}^{N}S_{w\to
k}(\beta_{(w,k)},y_{\mathcal{L}(w)\cup
w}^{(i)})T_{w}(y_{\mathcal{R}(w)}^{(i)},\gamma_{(w,k)}).$

One can then form $\hat{U}_{k},\hat{Q}_{k}$ by replacing $Z^{\star}_{k}$ with
$\hat{Z}_{k}$ in (13), noting that in this case the rank
$r_{(k,\mathcal{P}(k))}$ SVD decomposition is not exact due to the presence of
noise. We now explain why this algorithm is practical in the sample case. It
suffices to see the linear equation in Figure 6(c). If one replaces every
tensor block by a finite sample approximation in the sense discussed above
(e.g. replace $Z^{\star}_{w\to k}$ by $\hat{Z}_{w\to k}$), then one can indeed
form a linear equation, with accuracy increasing with sample size. The full
algorithm for empirical distributions will be described in Section 5.

(a) Tensor diagram representation of the Core Determining Equation (5) for
$k=4$ in Theorem 7. The left side uses $\Phi_{2\to 4}$ and $\Phi_{5\to 4}$
instead of $\Phi_{\mathcal{C}(4)\to 4}$, which is allowed due to (4).

(b) Tensor diagram representation of the sketched-down Core Determining
Equation (10) for $k=4$. The diagram can be thought of as a linear equation
for $G_{4}^{\star}$. Note that the tensors enclosed in blue box can be thought
of as the coefficient, and the tensors enclosed in red box can be thought of
as the right hand side. One can see that the tensor diagram equation is
obtained from that of Figure 6(a) by a contraction according to $S_{4}$ to
both sides. The left side of the diagram uses blocks corresponding to $S_{2\to
4},S_{5\to 4}$, which is a consequence of (7).

(c) With $\\{Z^{\star}_{w\to k}\\}_{w\to k\in
E},\\{Z^{\star}_{i}\\}_{i=1}^{d}$ from the sketch step and
$\\{U^{\star}_{i},Q^{\star}_{i}\\}_{i=1}^{d}$ from the SVD step, one can
rewrite the tensor diagram in Figure 6(b) into a tractable linear equation for
$G^{\star}_{k}$. Note that the diagram is equivalent to that in Figure 6(b)
due to Corollary 8.

Figure 6. Tensor diagram representation of equations for TTNS tensor cores in
TTNS-Sketch. The illustration is over the rooted tree in Figure 2. The
equation in Figure 6(a) implies the rest. The diagram in Figure 6(c) is
derived from the diagram in Figure 6(b) with a specific choice of gauge
according to Condition 2. Importantly, the equation in Figure 6(c) allows for
finite sample approximation.

##  4\. Topology finding

###  4.1. The Chow-Liu algorithm for topology finding

For an arbitrary distribution $p^{\star}$, we discuss the tree topology
specification problem. It could happen that one has no access to a pre-
selected candidate tree topology, but one wishes to test if there is a tree
topology to reasonably capture the structure for $p^{\star}$. Our main
algorithm for tree topology specification is the Chow-Liu algorithm, for which
we now give a brief description.

The input is a $d$-dimensional distribution $p$ with its random vector denoted
by $X:=\left(X_{1},\ldots,X_{d}\right)$. Typically, $p$ is the empirical
distribution $\hat{p}$ over given samples. In the first step, one computes the
pairwise mutual information $I(X_{i},X_{j})$ over any distinct pair of
$(i,j)\in[d]\times[d]$. In the second step, one forms a graph $G$, which is a
complete graph on $V:=[d]$ with edge weight given by $I(X_{i},X_{j})$. In the
third step, Kruskal’s algorithm is used to obtain the maximal spanning tree on
$G$, i.e. a spanning tree over $d$ nodes that maximizes the sum of mutual
information over all of its edges. This maximal mutual information spanning
tree is the Chow-Liu tree $T_{\mathrm{CL}}$.

The Chow-Liu algorithm also outputs a graphical model over $T_{\mathrm{CL}}$.
After specifying certain marginal and conditional probabilities to match that
of $p$, one uniquely determines the Chow-Liu model $p_{\mathrm{CL}}$, which is
a graphical model based on $T_{\mathrm{CL}}$.

We will discuss the rationale for using $T_{\mathrm{CL}}$ for our TTNS
algorithm in three cases.

In the first case, if $p^{\star}$ is indeed a graphical model over a tree
$T^{\star}$, then the Chow-Liu tree $T_{\mathrm{CL}}$ will be $T^{\star}$ with
high probability (see below). Moreover, it is well-known that
$p_{\mathrm{CL}}$ is the tree graphical model with minimum KL divergence to
the input distribution. With mild constraint on bond dimension, the class of
functions representable by a TTNS format strictly covers density representable
by a graphical model, and the performance of TTNS-Sketching with
$T_{\mathrm{CL}}$ has a performance which is on par with $p_{\mathrm{CL}}$.

In the second case, if $p^{\star}$ has a TTNS ansatz over a tree $T^{\star}$,
then it is typically true that farther-away nodes in $T^{\star}$ are less
correlated. By the maximal spanning tree procedure in Chow-Liu, variables that
are far away in $T_{\mathrm{CL}}$ are also typically less correlated. If
$T_{\mathrm{CL}}$ and $T^{\star}$ differs locally, then the TTNS-sketching
algorithm still performs well empirically. For a important example in this
category, suppose $p^{\star}$ is given by a graphical model over a graph with
loops. In this case, $T_{\mathrm{CL}}$ will converge to a spanning tree of the
graph, and one can form a TTNS ansatz with $T_{\mathrm{CL}}$ by choosing
appropriately large bond dimension.

In the third case, it may happen that $p^{\star}$ cannot be represented by a
TTNS anstaz. In this case, one can quickly reject the TTNS model assumption by
looking at the mutual information $I(X_{i},X_{j})$ used in the Chow-Liu
algorithm. For any node $k\in[d]$, removing $k$ will separate
$T_{\mathrm{CL}}$ into two connected components. If one sees several pairs of
strong correlation between nodes separated by $k$, then the density
$p^{\star}$ most likely fails the TTNS model assumption, and more general
tensor networks might be more applicable.

###  4.2. Sample complexity for successful tree topology recovery

We discuss the amount of samples required for Chow-Liu to pick the “correct”
tree topology. By a correct tree topology, we will mean that the Chow-Liu Tree
$T_{\mathrm{CL}}$ equals to the tree one would have obtained if one forms the
maximal spanning tree based on the exact mutual information. If $p^{\star}$ is
a graphical model over $T^{\star}$, then this notion of correctness coincides
with the intuitive notion of $T_{\mathrm{CL}}=T^{\star}$.

There has been considerable recent work in the past few years on the sample
complexity of the Chow-Liu algorithm to infer the correct tree topology in the
sample case. [bhattacharyya2021near] shows that the sample complexity is
bounded by $O(\frac{n^{3}d}{\epsilon}\log{1/\delta})$ to ensure a $1-\delta$
success rate, where $\epsilon$ is the gap in the sum of mutual information
between the two best tree models. For tree-based Ising model with zero
external field, [bresler2020learning] proves an upper bound that is
$O(\log{(d/\delta)})$.

##  5\. TTNS-Sketch for empirical distributions

We now give the main Algorithm 1-3 for the TTNS ansatz with empirical
distribution as input, which is the main use case. We include it separately
from Section 3 due to corner cases such as when $k$ is a leaf or root node. To
emphasize the sample estimation procedure, all of the intermediate terms will
be labelled with $\hat{}$ if it assumes access to $\hat{p}$. Importantly,
Algorithm 3 only takes in the sketches $\\{Z_{w\to k}\\}_{w\to k\in
E},\\{Z_{i}\\}_{i=1}^{d}$ as input, which can be either noiseless or
estimated, and so we do not label terms inside this subroutine.

Figure 7. Schematic of Algorithm 1 Algorithm 1 TTNS-Sketch for empirical
distribution $\hat{p}$.

0: Empirical distribution $\hat{p}$ formed by samples
$\\{(y_{1}^{(i)},\ldots,y_{d}^{(i)})\\}_{i=1}^{N}$.

0: A rooted tree structure $T=([d],E)$, and
$\mathcal{C},\mathcal{P},\mathcal{L},\mathcal{R}$ as in Definition 3.

0: Target ranks $\\{r_{e}:e\in E\\}\subset\mathbb{N}$.

0:
$T_{k}\colon\prod_{i\in\mathcal{R}(k)}[n_{i}]\times[m_{(k,\mathcal{P}(k))}]\to\mathbb{R}$
for all non-root $k\in[d]$ and $T_{k}=1$ if $k$ is the root.

0: $S_{1},\ldots,S_{d}$ formed by $S_{w\to k}$’s as in (7).

1: $\\{\hat{Z}_{w\to k}\\}_{w\to k\in
E},\\{\hat{Z}_{i}\\}_{i=1}^{d}\leftarrow\textsc{Sketching}(\hat{p},T_{1},\ldots,T_{d},S_{1},\ldots,S_{d})$.

2:
$\\{\hat{A}_{i},\hat{B}_{i}\\}_{i=1}^{d}\leftarrow\textsc{SystemForming}(\\{\hat{Z}_{w\to
k}\\}_{w\to k\in E},\\{\hat{Z}_{i}\\}_{i=1}^{d}).$

3: Solve the following $d$ equations via least-squares for the variables
$\hat{G}_{1},\ldots,\hat{G}_{d}$:  (21) $\displaystyle\hat{G}_{k}$
$\displaystyle=\hat{B}_{k}\quad\text{if}~{}k~{}\text{is a leaf},$
$\displaystyle\textstyle\sum_{\alpha_{(k,\mathcal{C}(k))}}\hat{A}_{k}(\beta_{(k,\mathcal{C}(k))},\alpha_{(k,\mathcal{C}(k))})\hat{G}_{k}(x_{k},\alpha_{(k,\mathcal{N}(k))})$
$\displaystyle=\hat{B}_{k}\quad\text{otherwise},$ where
$\hat{G}_{k}\colon[n_{k}]\times\prod_{w\in\mathcal{N}(k)}[r_{(w,k)}]\to\mathbb{R}$.

4: return $\hat{G}_{1},\ldots,\hat{G}_{d}$

Algorithm 2 Sketching.

0: $\hat{p}$, $T_{1},\ldots,T_{d}$, and $S_{1},\ldots,S_{d}$ as given in
Algorithm 1.

0: $T=([d],E)$ as given in Algorithm 1.

for $k=1$ to $d$ do

if $k$ is root then

Define
$\hat{Z}_{k}\colon\prod_{w\in\mathcal{C}(k)}[l_{(w,k)}]\times[n_{k}]\to\mathbb{R}$
as
$\hat{Z}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k})=\sum_{i=1}^{N}S_{k}(\beta_{(k,\mathcal{C}(k))},y_{\mathcal{L}(k)}^{(i)})\mathbf{1}(y_{k}^{(i)}=x_{k}).$

else if $k$ is leaf then

Define $\hat{Z}_{k}\colon[n_{k}]\times[m_{(k,\mathcal{P}(k))}]\to\mathbb{R}$
as
$\hat{Z}_{k}(x_{k},\gamma_{(k,\mathcal{P}(k))})=\sum_{i=1}^{N}\mathbf{1}(y_{k}^{(i)}=x_{k})T(y_{\mathcal{R}(k)}^{(i)},\gamma_{(k,\mathcal{P}(k))}).$

Define $\hat{Z}_{k\to\mathcal{P}(k)}$ according to (20)

else

Define
$\hat{Z}_{k}\colon\prod_{w\in\mathcal{C}(k)}[l_{(w,k)}]\times[n_{k}]\times[m_{(k,\mathcal{P}(k))}]\to\mathbb{R}$
according to (19).

Define
$\hat{Z}_{k\to\mathcal{P}(k)}\colon[l_{(k,\mathcal{P}(k))}]\times[m_{(k,\mathcal{P}(k))}]\to\mathbb{R}$
according to (20).

end if

end for

return $\\{\hat{Z}_{w\to k}\\}_{w\to k\in E},\\{\hat{Z}_{i}\\}_{i=1}^{d}$.

Algorithm 3 SystemForming.

0: Sketches $\\{Z_{w\to k}\\}_{w\to k\in E},\\{Z_{i}\\}_{i=1}^{d}$.

0: Tree structure $T=([d],E)$ as given in Algorithm 1.

0: Target rank $r$ as given in Algorithm 1.

for $k=1$ to $d$ do

$\beta_{k}\leftarrow\beta_{(k,\mathcal{C}(k))}$.

$\gamma_{k}\leftarrow\gamma_{\mathcal{P}(k)}$.

$r_{k}\leftarrow r_{(\mathcal{P}(k),k)}$.

$l_{k}\leftarrow\prod_{w\in\mathcal{C}(k)}l_{(w,k)}$.

$m_{k}\leftarrow m_{(k,\mathcal{P}(k))}$.

if $k$ is a leaf then

Let $U_{k}\Sigma_{k}V^{\top}_{k}$, where $U_{k}\in\mathbb{R}^{n_{k}\times
r_{k}}$, $V_{k}\in\mathbb{R}^{m_{k}\times r_{k}}$,
$\Sigma_{k}\in\mathbb{R}^{r_{k}\times r_{k}}$, be the best rank-$r_{k}$
approximation to the matrix $Z_{k}(x_{k};\gamma_{k})$ via SVD. Define
$B_{k}\colon[n_{k}]\times[r_{k}]\to\mathbb{R}$ where
$B_{k}(x_{k},\alpha_{k})=U_{k}(x_{k};\alpha_{k})$. Set $A_{k}=1$.

else if $k$ is root then

Let $B_{k}=Z_{k}$. Set $Q_{k}=1$.

else

Let $U_{k}\Sigma_{k}V^{\top}_{k}$, where $U_{k}\in\mathbb{R}^{l_{k}n_{k}\times
r_{k}}$, $V_{k}\in\mathbb{R}^{m_{k}\times r_{k}}$,
$\Sigma_{k}\in\mathbb{R}^{r_{k}\times r_{k}}$, be the best rank-$r_{k}$
approximation to the matrix $Z_{k}(\beta_{k},x_{k};\gamma_{k})$ via SVD.
Define
$B_{k}\colon\prod_{w\in\mathcal{C}(k)}[l_{(w,k)}]\times[n_{k}]\times[r_{k}]\to\mathbb{R}$
where $B_{k}(\beta_{k},x_{k},\alpha_{k})=U_{k}(\beta_{k},x_{k};\alpha_{k})$.

end if

if $k$ is non-root then

Let $Q_{k}=V_{k}\Sigma_{k}^{-1}$.

end if

end for

for $k=1$ to $d$ do

if $k$ is non-leaf then

Compute
$A_{k}\colon\prod_{w\in\mathcal{C}(k)}[l_{(w,k)}]\times\prod_{w\in\mathcal{C}(k)}[r_{(w,k)}]\to\mathbb{R}$:

$A_{k}(\beta_{(k,\mathcal{C}(k))},\alpha_{(k,\mathcal{C}(k))})=\prod_{w\in\mathcal{C}(k)}\sum_{\gamma_{(w,k)}}Z_{w\to
k}(\beta_{(w,k)},\gamma_{(w,k)})Q_{w}(\gamma_{(w,k)},\alpha_{(w,k)}).$

end if

end for

return $\\{A_{i},B_{i}\\}_{i=1}^{d}$.

###  5.1. Condition for consistency of TTNS-Sketch

We introduce Condition 3 on the choice of sketch functions. Essentially,
Theorem 7 shows that (5) is an over-determined linear system with a unique
exact solution, and one needs the “sketched-down” version of (5) to still have
a unique solution:

######  Condition 3.

Let $p^{\star}$ be a function which satisfies Condition 1. Moreover, let
$\\{\Phi^{\Delta}_{(w,k)},\Psi^{\Delta}_{(w,k)}\\}_{(w,k)\in E}$ be an
arbitrary collection of tensors forming the low-rank decomposition of
$p^{\star}$ in the sense of Condition 1, with gauge chosen arbitrarily. Let
$\\{T_{i},S_{i}\\}_{i=1}^{d}$ be the sketch functions in Algorithm 1. Define
two intermediate terms $A^{\Delta}_{k}\colon\prod_{w\in\mathcal{C}(k)}[l_{w\to
k}]\times\prod_{w\in\mathcal{C}(k)}[r_{w\to k}]\to\mathbb{R}$ and
$B^{\Delta}_{k}\colon\prod_{w\in\mathcal{C}(k)}[l_{w\to
k}]\times[n_{k}]\times[\gamma_{k\to\mathcal{P}(k)}]\to\mathbb{R}$ by

(22) $\displaystyle
A^{\Delta}_{k}(\beta_{(k,\mathcal{C}(k))},\alpha_{(k,\mathcal{C}(k))}):=\prod_{w\in\mathcal{C}(k)}\sum_{x_{\mathcal{L}(w)\cup
w}}S_{w\to k}(\beta_{(w,k)},x_{\mathcal{L}(w)\cup w})\Phi^{\Delta}_{w\to
k}(x_{\mathcal{L}(w)\cup w},\alpha_{(w,k)}),$ $\displaystyle
B^{\Delta}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k},\alpha_{(k,\mathcal{P}(k))}):=\sum_{x_{\mathcal{L}(k)}}S_{k}(\beta_{(k,\mathcal{C}(k))},x_{\mathcal{L}(k)})\Phi^{\Delta}_{k\to\mathcal{P}(k)}(x_{\mathcal{L}(k)\cup
k},\alpha_{(k,\mathcal{P}(k))}).$

Moreover, define an intermediate term
$\bar{\Phi}^{\star}_{k}\colon\prod_{i\in\mathcal{L}(k)\cup
k}[n_{i}]\times[m_{(k,\mathcal{P}(k))}]\to\mathbb{R}$ by

$\bar{\Phi}^{\star}_{k}(x_{\mathcal{L}(k)\cup
k},\gamma_{(k,\mathcal{P}(k))})=\sum_{x_{\mathcal{R}(k)}}p^{\star}(x_{1},\ldots,x_{d})T_{k}(x_{\mathcal{R}(k)},\gamma_{(k,\mathcal{P}(k))}).$

Then, $\\{T_{i},S_{i}\\}_{i=1}^{d}$ in Algorithm 1 is chosen to be such that
the following conditions hold:

  * (i)

$\bar{\Phi}^{\star}_{k}(x_{\mathcal{L}(k)\cup k};\gamma_{(k,\mathcal{P}(k))})$
and $\Phi^{\Delta}_{k\to\mathcal{P}(k)}(x_{\mathcal{L}(k)\cup
k};\alpha_{(k,\mathcal{P}(k))})$ have the same
$r_{(k,\mathcal{P}(k))}$-dimensional column space for every non-root $k$.

  * (ii)

$Z^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k};\gamma_{(k,\mathcal{P}(k))})$
defined in (12) is of rank $r_{(k,\mathcal{P}(k))}$ for every non-leaf and
non-root $k$.

  * (iii)

$A^{\Delta}_{k}(\beta_{(k,\mathcal{C}(k))};\alpha_{(k,\mathcal{C}(k))})$ has
full column rank for every non-leaf $k$.

If one has oracle access access to $p^{\star}$, and moreover suppose that
computing $Z^{\star}_{w\to k}$ and $Z^{\star}_{k}$ are tractable, then one can
directly start with the SystemForming step in Algorithm 1 with the noiseless
terms $Z^{\star}_{w\to k}$ and $Z^{\star}_{k}$ as input. Similar to Theorem 7,
under a technical condition for the given sketch functions, one can solve for
the tensor cores exactly. We give out the condition in Theorem 9.

######  Theorem 9.

(Exact recovery of TTNS-Sketch) For an underlying distribution $p^{\star}$
satisfying Condition 1, suppose its tree structure $T$ and internal bond $r$
coincides with the input for Algorithm 1. Let $\\{T_{i},S_{i}\\}_{i=1}^{d}$
satisfy Condition 3. Then, in Algorithm 1, assume one has oracle access to
$\\{Z^{\star}_{w\to k}\\}_{w\to k\in E},\\{Z^{\star}_{i}\\}_{i=1}^{d}$. Then,
let

$\\{A^{\star}_{i},B^{\star}_{i}\\}_{i=1}^{d}\leftarrow\textsc{SystemForming}(\\{Z^{\star}_{w\to
k}\\}_{w\to k\in E},\\{Z^{\star}_{i}\\}_{i=1}^{d}),$

and let the $\\{G_{i}^{\star}\\}_{i=1}^{d}$ be the least-squares solution the
following linear system for the variables $G_{1},\ldots,G_{d}$:

(23) $\displaystyle G_{k}$
$\displaystyle=B^{\star}_{k}\quad\text{if}~{}k~{}\text{is a leaf},$
$\displaystyle\textstyle\sum_{\alpha_{(k,\mathcal{C}(k))}}A^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},\alpha_{(k,\mathcal{C}(k))})G_{k}(x_{k},\alpha_{(k,\mathcal{N}(k))})$
$\displaystyle=B^{\star}_{k}\quad\text{otherwise},$

Then linear system (23) has a unique exact solution
$\\{G^{\star}_{i}\\}_{i=1}^{d}$, which forms the cores of the TTNS ansatz of
$p^{\star}$ given $T=([d],E)$ and $\\{r_{e}:e\in E\\}$. As a consequence, the
output of Algorithm 1 given an empirical distribution $\hat{p}$ as input
satisfies $\lim_{N\to\infty}\hat{G}_{k}=G^{\star}_{k}$, i.e. $\hat{G}_{k}$ is
a consistent estimator of $G^{\star}_{k}$.

###  5.2. Introduction to recursive sketch functions

Storing generic $S_{i}$ is not possible as its number of possible inputs is
exponential in $d$. As an example, one can consider cases where sketch
functions $\\{S_{i},T_{i}\\}_{i=1}^{d}$ have explicit formula, which makes its
evaluation easy. Alternatively, one can also use sketch functions which are
themselves derived by a TTNS ansatz. We introduce a nice special case called
_recursive sketch functions_ , which allows for sketch functions more general
than those with an analytic formula, but is still tractable for computation.

For recursive sketch functions, there is a natural notion of subgraph TTNS
function. We will define it here:

######  Definition 10.

(Subgraph TTNS function) Suppose that $f$ is a function satisfying Condition 1
with tree $T$, and moreover suppose $f$ admits tensor cores
$\\{s_{i}\\}_{i=1}^{d}$ for its TTNS ansatz. Let $\mathcal{S}\subset V$ and
let $T_{\mathcal{S}}=(\mathcal{S},E_{\mathcal{S}})$ be the subgraph of $T$
with vertex set $\mathcal{S}$. Then $\\{s_{i}\\}_{i=1}^{d}$ and
$T_{\mathcal{S}}$ jointly defines the _subgraph TTNS function_
$f_{\mathcal{S}}\colon\prod_{i\in\mathcal{S}}[n_{i}]\times\prod_{e\in\partial\mathcal{S}}[r_{e}]\to\mathbb{R}$
by

$f_{\mathcal{S}}(x_{\mathcal{S}},\alpha_{\partial\mathcal{S}})=\sum_{\begin{subarray}{c}\alpha_{e}\\\
e\in
E_{\mathcal{S}}\end{subarray}}\prod_{k\in\mathcal{S}}G_{k}\left(x_{k},\alpha_{(k,\mathcal{N}(k))}\right).$

where $\partial\mathcal{S}:=\\{(v,w)\in E\mid
v\in\mathcal{S},w\not\in\mathcal{S}\\}$.

In the recursive sketching regime, each sketch function $T_{k}$ and $S_{k}$
has a TTNS structure, and is recursively defined by the collection of sketch
cores $\\{(t_{i},s_{i})\\}_{i=1}^{d}$. We specify such a relationship. Given
the convention in section 5, one can easily define as follows:

######  Condition 4.

(Recursive sketching condition) Let $T=(V,E)$ be a tree. Assume $f$ (resp.
$g$) are two functions with a TTNS ansatz over $T$ in the sense of Condition
1, with internal bond $l$ (resp. $m$) and sketch cores $\\{s_{i}\\}_{i=1}^{d}$
(resp. $\\{t_{i}\\}_{i=1}^{d}$). Then $S_{k}=f_{\mathcal{L}(k)}$ and
$T_{k}=g_{\mathcal{R}(k)}$.

In particular, $S_{k}$ satisfies a recursive relation

(24)
$S_{k}(\beta_{(k,\mathcal{C}(k))},x_{\mathcal{L}(k)})=\prod_{w\in\mathcal{L}(k)}\sum_{\beta_{(w,\mathcal{C}(w))}}s_{w}(x_{w},\beta_{(w,k)},\beta_{(w,\mathcal{C}(w))})S_{w}(\beta_{(w,\mathcal{C}(w))},x_{\mathcal{L}(w)}),$

and so $S_{k}$ satisfies the factorization structure (7) with its $S_{w\to k}$
defined by

$S_{w\to
k}(\beta_{(w,k)},x_{\mathcal{L}(w)})=\sum_{\beta_{(w,\mathcal{C}(w))}}s_{w}(x_{w},\beta_{(w,k)},\beta_{(w,\mathcal{C}(w))})S_{w}(\beta_{(w,\mathcal{C}(w))},x_{\mathcal{L}(w)}).$

Moreover, the recursive definition over the left sketch functions leads to a
simplified equation for $\hat{A}_{k}$. As a consequence of (24), the terms
$\hat{Z}_{w\to k}$ and $\hat{Z}_{w}$ are now connected:

(25) $\hat{Z}_{w\to
k}(\beta_{(w,k)},\gamma_{(w,k)})=\sum_{x_{w}}\sum_{\begin{subarray}{c}\gamma_{(w,k)}\end{subarray}}s_{w}(\beta_{(w,k)};\beta_{(w,\mathcal{C}(w))},x_{w})\hat{Z}_{w}(\beta_{(w,\mathcal{C}(w))},x_{w};\gamma_{(w,k)}).$

Define an intermediate term $\hat{A}_{w\to k}$ similar to (17). As a
consequence of (25),

$\displaystyle\hat{A}_{w\to k}(\beta_{(w,k)},\alpha_{(w,k)})=$
$\displaystyle\sum_{\beta_{(w,\mathcal{C}(w))}}\sum_{x_{w}}\sum_{\begin{subarray}{c}\gamma_{(w,k)}\end{subarray}}s_{w}(\beta_{(w,k)};\beta_{(w,\mathcal{C}(w))},x_{w})\hat{Z}_{w}(\beta_{(w,\mathcal{C}(w))},x_{w};\gamma_{(w,k)})\hat{Q}_{w}(\gamma_{(w,k)},\alpha_{(w,k)})$
$\displaystyle=$
$\displaystyle\sum_{x_{w}}\sum_{\beta_{(w,\mathcal{C}(w))}}s_{w}(\beta_{(w,k)};\beta_{(w,\mathcal{C}(w))},x_{w})\hat{B}_{w}(\beta_{(w,\mathcal{C}(w))},x_{w};\alpha_{(w,k)}),$

where the second equality is a consequence of Algorithm 3.

As a consequence, we conclude that for recursive sketching one can compute the
left-hand side by

(26)
$\hat{A}_{k}(\beta_{(k,\mathcal{C}(k))},\alpha_{(k,\mathcal{C}(k))})=\prod_{w\in\mathcal{C}(k)}\sum_{(\beta_{(w,\mathcal{C}(w))},x_{w})}s_{w}(\beta_{(w,k)};\beta_{(w,\mathcal{C}(w))},x_{w})\hat{B}_{w}(\beta_{(w,\mathcal{C}(w))},x_{w};\alpha_{(w,k)}).$

Note that the above result is solely due to the property of the left sketch
function. Hence, (26) holds true if one replaces $\hat{A}_{k},\hat{B}_{k}$
with $A^{\star}_{k},B^{\star}_{k}$. Moreover, the equation (26) is
mathematically equivalent to the formula for $\hat{A}_{k}$ in Algorithm 3.
Nevertheless, it will simplify our subsequent error analysis for Markov sketch
function, as one only needs to account for the error in $\hat{B}_{k}$.

###  5.3. Estimation of target rank $r$

If one has access to a tree $T$ but not a target rank $r$, then one can define
a noise threshold $\delta$, and determine $r_{(k,\mathcal{P}(k))}$ from the
SVD result in Algorithm 3 directly. Namely, one checks the singular values in
$\Sigma_{k}$, and sets $r_{(k,\mathcal{P}(k))}$ to be the number of singular
values above the level set by $\delta$.

Hence, for samples from a distribution $p^{\star}$ with no known structure,
one can set $T=T_{\mathrm{CL}}$ as in Section 4, and set the internal bond
rank by thresholding with $\delta$ in the sense described above. The result
should be reasonable if $p^{\star}$ satisfies Condition 1 with tractable bond
dimension, or if $p^{\star}$ can be well approximated by a TTNS ansatz.
Analysis with approximated target rank is beyond the scope of this paper.

##  6\. Choice of sketch function

We begin with Section 6.1, which explains that the differences in sketch
functions conceptually leads to matching different statistical moments. The
rest of the subsections give concrete examples of sketch functions.

###  6.1. Connection of sketching to moment matching

In this subsection, we give the sketched-down linear equation another
interpretation as enforcing a match between the statistical moment of the
output TTNS ansatz to that of the empirical distribution. Essentially,
different sketch functions lead to different statistical moments to match,
which conceptually leads to different optimization objectives.

First, any algorithm for solving for tensor components of a TTNS boils down to
attempting to fit the following equation over $\\{G_{i}\\}_{i=1}^{d}$ to the
sample, with the end goal of approximating $p^{\star}$. In terms of an
equation, one can write

(27) $\sum_{\begin{subarray}{c}\alpha_{e}\\\ e\in
E\end{subarray}}\prod_{i=1}^{d}G_{i}(x_{i},\alpha_{(i,\mathcal{N}(i))})\approx\hat{p}(x_{1},\ldots,x_{d})\approx
p^{\star}(x_{1},\ldots,x_{d}),\quad\forall(x_{1},\ldots,x_{d}).$

In practical settings, $\hat{p}\approx p^{\star}$ only weakly. Moreover, the
above equation relates to the equivalence of two tensors of $n^{d}$ entries,
but the number of unknown parameters involved is only $O(d)$. To apply
sketching, one defines a sketch function $f(\mu,x_{1},\ldots,x_{d})$. One then
multiplies (27) by $f$ and then sum over the joint $x_{[d]}$ variable. The
sketched down equation becomes

(28)
$\sum_{x_{[d]}}f(\mu,x_{1},\ldots,x_{d})\left(\sum_{\begin{subarray}{c}\alpha_{e}\\\
e\in
E\end{subarray}}\prod_{i=1}^{d}G_{i}(x_{i},\alpha_{(i,\mathcal{N}(i))})\right)=\sum_{i=1}^{N}f\left(\mu,y_{1}^{(i)},\ldots,y_{d}^{(i)}\right)\approx\mathbb{E}_{X\sim
p^{\star}}\left[f\left(\mu,X\right)\right],\quad\forall\mu.$

where the first approximation sign in (27) is swapped with an equality sign,
which is meant to signal that one then solves for the tensor cores using this
equation. As for the approximate sign in (28), the design of $f$ will be
typically such that the variance $f\left(\mu,X\right)$ is $O(1)$ or grows
slowly with $d$, which is why the approximation will be reasonable according
to the law of large numbers.

Moreover, one can let $\theta$ stand for the TTNS tensor cores
$\\{G_{i}\\}_{i=1}^{d}$, and let $p_{\theta}$ stand for the probability
distribution obtained from the TTNS ansatz under such cores. The equation (28)
is equivalent to

(29) $\mathbb{E}_{X\sim
p_{\theta}}\left[f\left(\mu,X\right)\right]=\mathbb{E}_{X\sim\hat{p}}\left[f\left(\mu,X\right)\right]\approx\mathbb{E}_{X\sim
p^{\star}}\left[f\left(\mu,X\right)\right],\quad\forall\mu.$

In summary, the solution is such that $p_{\theta}$ is close to $\hat{p}$ in
terms of statistical moments $\mathbb{E}_{X}\left[f\left(\mu,X\right)\right]$.
For the connection to TTNS-Sketch, we consider a simple case where one has
already solved for $\\{G_{i}\\}_{i\not=k}$. Consider a sketch function $f_{k}$
by first defining its corresponding joint variable $\mu$ by
$\mu=(\beta_{(k,\mathcal{C}(k))},\gamma_{(k,\mathcal{P}(k))},\iota)$. Then,
let

$f_{k}(\beta_{(k,\mathcal{C}(k))},\gamma_{(k,\mathcal{P}(k))},\iota,x_{[d]})=S_{k}(\beta_{(k,\mathcal{C}(k))},x_{\mathcal{L}(k)})\mathbf{1}\left[\iota=x_{k}\right]T_{k}(x_{\mathcal{R}(k)},\gamma_{(k,\mathcal{P}(k))}).$

As a result, one has

$\mathbb{E}_{X\sim\hat{p}}\left[f_{k}\left(\mu,X\right)\right]=\hat{Z}_{k}(\beta_{(k,\mathcal{C}(k))},\iota,\gamma_{(k,\mathcal{P}(k))}),$

and so the sketched-down equation (29) tries to enforce a match between
$\mathbb{E}_{X\sim p_{\theta}}\left[f_{k}\left(\mu,X\right)\right]$ and
$Z^{\star}_{k}$. Different sketch functions thus leads to different sketches
$Z^{\star}_{k}$ to match.

###  6.2. Markov sketch function

A Markov sketch function allows the TTNS procedure to essentially solve for
marginal distribution information for each node $k$ around its neighbors,
which we will show with the definition of its sketch function.

For the Markov sketch function, one has $l_{k}:=n_{\mathcal{P}(k)}$, and the
right-sketch function $T_{k}$ is defined by

(30)
$T_{k}(x_{\mathcal{R}(k)},\gamma_{(k,\mathcal{P}(k))})=\mathbf{1}\left[x_{\mathcal{P}(k)}=\gamma_{(k,\mathcal{P}(k))}\right].$

As for the left-sketch function, the form is similar, but it is complicated by
the fact that a tree node can have multiple child nodes. Likewise,
$m_{(w,k)}:=n_{w}$, and

(31)
$S_{k}(\beta_{(k,\mathcal{C}(k))},x_{\mathcal{L}(k)})=\prod_{w\in\mathcal{C}(k)}\mathbf{1}\left[x_{w}=\beta_{(w,k)}\right].$

By applying left-sketch and right sketch, one has

(32)
$Z^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k},\gamma_{(k,\mathcal{P}(k))})=\mathbb{P}_{X\sim
p^{\star}}\left[X_{w}=\beta_{(w,k)}\forall
w\in\mathcal{C}(k),X_{k}=x_{k},X_{\mathcal{P}(k)}=\gamma_{k}\right],$

which is then the marginal distribution on the subset of nodes
$\mathcal{N}(k)\cup\\{k\\}=\\{v\in V\mid\mathrm{dist}(v,k)\leq 1\\}$.

We also use

(33) $(\mathcal{M}_{\mathcal{S}}p)(x_{\mathcal{S}}):=\mathbb{P}_{X\sim
p}\left[X_{v}=x_{v},\forall v\in\mathcal{S}\right]$

to denote the marginalization of $p$ to the variables given by the index set
$\mathcal{S}$, which is a $|\mathcal{S}|$-dimensional function.

Due to the construction, the joint variables
$(\beta_{(k,\mathcal{C}(k))},\gamma_{(k,\mathcal{P}(k))})$ each has a natural
correspondence to a node neighboring $k$. By identifying $\beta_{(w,k)}=x_{w}$
and $\gamma_{(k,\mathcal{P}(k))}=x_{\mathcal{P}(k)}$, one has the following
entry-wise equality

$Z^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},x_{k},\gamma_{(k,\mathcal{P}(k))})=\mathcal{M}_{\mathcal{S}_{k}}p^{\star}(x_{\mathcal{C}(k)},x_{k},x_{\mathcal{P}(k)}),$

where $\mathcal{S}_{k}=\mathcal{N}(k)\cup\\{k\\}$.

By the description in Section 6.1, with Markov sketch function, TTNS-Sketch
essentially tries to fit $\mathcal{M}_{\mathcal{N}(k)\cup k}\hat{p}$ over all
$k\in V$. One can show that the Markov sketch function allows exact recovery
for tree-based graphical models. We summarize the result in Lemma 11.

######  Lemma 11.

Assume that $p^{\star}$ is a graphical model over the tree structure
$T=([d],E)$. Then $p^{\star}$ satisfies Condition 1 with the tree structure
$T$ and $r_{e}=n$ for any $e\in E$. Moreover, sketches in (30) and (31)
satisfies the condition in Theorem 9.

###  6.3. Higher order Markov sketch function

One can use high-order Markov sketch functions to solve for marginal
probability information over more nodes than in the previous cases. Let
$\mathcal{S}_{k}\subset V$ be a choice of nodes of interest to $k$. By a
suitable change of the sketch functions $T_{k}$ and $S_{k}$ in Section 6.2,
one can make it so that one has the following entry-wise equality

$\displaystyle Z_{k}^{\star}=\mathcal{M}_{\mathcal{S}_{k}}p^{\star};\quad
Z_{w\to
k}^{\star}=\mathcal{M}_{(\mathcal{S}_{k}\cup\mathcal{L}(k))\cup(\mathcal{S}_{w}\cap\mathcal{R}(w))}p^{\star}$

If one wishes to ensure the high-order Markov sketching function satisfies
recursive sketching, one needs the following constraint:

(34)
$\\{k\\}\subset\mathcal{S}_{k}\subset\cup_{w\in\mathcal{C}(k)}\mathcal{S}_{w}.$

For an example, for any integer $L\geq 1$, one sets $L$ as a distance cutoff
and let

(35) $\mathcal{S}_{k}=\\{v\in V\mid\mathrm{dist}(v,k)\leq L\\}.$

By triangle inequality, the construction in (35) satisfies (34), and one
obtains the Markov sketching function when $L=1$. For the choice of
neighborhood in (35), we refer to the corresponding sketch function as
$L$-Markov sketch function. In particular, $2$-Markov sketch function will
play an important role in numerical experiments.

###  6.4. Perturbative sketching

The idea of perturbative sketching is to use recursive random projection to
form the sketch functions. In Condition 5-6, we define the structural
assumption of perturbative sketching. In Theorem 12, we give a structural
theorem for perturbative sketching, which shows that the sketch
$Z_{k}^{\star}$ is a power series of tensors. Moreover, each term in the power
series corresponds to a random projection of a marginal distribution of
$p^{\star}$, i.e. tensor of the form $\mathcal{M}_{\mathcal{S}}p^{\star}$ for
a subset $\mathcal{S}\subset[d]$.

In Condition 5, we make a significant simplification to recursive sketching by
unifying left and right sketching to an equal footing, which allows for a
cleaner structural analysis. In Condition 6, we make the assumption that each
sketch core is made up of an all one tensor plus a perturbation term.

######  Condition 5.

(Directional symmetry for perturbative sketching) Assume the sketch functions
$\\{T_{i},S_{i}\\}$ satisfies Condition 4. Furthermore, one lets $l_{e}=m_{e}$
for any $e\in E$ and $t_{i}=s_{i}$ for any $i\in[d]$.

######  Condition 6.

(perturbative structure for sketch cores) Fix a constant $\epsilon>0$ as the
_perturbative scale_. The tensor core $s_{k}$ is defined by tensors $O_{k}$
and $\Delta_{k}$ of the form:

(36)
$s_{k}(x_{k},\beta_{(k,\mathcal{N}(k))})=O_{k}(x_{k},\beta_{(k,\mathcal{N}(k))})+\epsilon\Delta_{k}(x_{k},\beta_{(k,\mathcal{N}(k))}),$

and moreover $O_{k}$ is the all one tensor satisfying

$O_{k}(x_{k},\beta_{(k,\mathcal{N}(k))})=1.$

For a concrete example, if the perturbation is formed by entry-wise i.i.d.
random variable, one can use the following line in MATLAB to define a
perturbative sketch core:

        s_k = ones(size(s_k)) + epsilon*rand(size(s_k)).

Due to Condition 5, it follows that $Z^{\star}_{k}$ only depends on the sketch
cores $\\{s_{i}\\}_{i\not=k}$. Therefore, one can identify
$\gamma_{(k,\mathcal{P}(k))}$ with $\beta_{(k,\mathcal{P}(k))}$. By simple
algebra, one can derive the following result:

######  Theorem 12.

(Structure theorem of perturbative sketching) Assume that Condition 5-6 are
satisfied for the chosen sketch function. For $k\in[d]$ and
$\mathcal{S}\subset[d]-\\{k\\}$, let
$T_{\mathcal{S}}=(\mathcal{S},E_{\mathcal{S}})$ be the subgraph of $T$ with
vertex set $\mathcal{S}$. As in Definition 10, define $\Delta_{\mathcal{S}}$
by

(37)
$\Delta_{\mathcal{S}}(x_{\mathcal{S}},\beta_{\partial\mathcal{S}}):=\sum_{\begin{subarray}{c}\beta_{e}\\\
e\in
E_{\mathcal{S}}\end{subarray}}\prod_{i\in\mathcal{S}}\Delta_{i}(x_{i},\beta_{(i,\mathcal{N}(i))}).$

Then the following equation holds for $Z_{k}^{\star}$:

(38)
$Z^{\star}_{k}(x_{k},\beta_{(k,\mathcal{N}(k))})=\sum_{l=0}^{d-1}\epsilon^{l}\sum_{\mathcal{S}\subset[d]-\\{k\\},|\mathcal{S}|=l}Z^{\star}_{k;\mathcal{S}}(x_{k},\beta_{(k,\mathcal{N}(k))}),$

where

(39)
$Z^{\star}_{k;\mathcal{S}}(x_{k},\beta_{(k,\mathcal{N}(k))})=\sum_{\beta_{e},k\not\in
e}\left(\sum_{x_{\mathcal{S}}}\mathcal{M}_{\mathcal{S}\cup\\{k\\}}p^{\star}(x_{k},x_{\mathcal{S}})\Delta_{\mathcal{S}}(x_{\mathcal{S}},\beta_{\partial\mathcal{S}})\right).$

The proof is simple and left in the Appendix. There are a few consequence of
Theorem 12. First, each $Z^{\star}_{k;\mathcal{S}}$ is a projection of the
marginal distribution tensor $\mathcal{M}_{\mathcal{S}\cup\\{k\\}}p^{\star}$.
Second, in (38), terms corresponding to $\mathcal{S}$ is scaled by
$\epsilon^{|\mathcal{S}|}$, which itself means that contribution of
$\mathcal{S}$ with large cardinality is insignificant. By the description in
Section 6.1, with perturbative sketching function, TTNS-Sketch essentially
tries to fit over all $\mathcal{M}_{\mathcal{S}}p^{\star}$, and a
$\epsilon^{|\mathcal{S}|}$ factor is placed to ensure $\hat{Z}_{k}$ stabilizes
quickly.

Moreover, if $\mathcal{S}\cup\\{k\\}$ is not a connected component of $T$,
then according to (39), $Z^{\star}_{k;\mathcal{S}}$ does not vary with $x_{s}$
or $\beta_{(k,\mathcal{N}(k))}$. Such $Z^{\star}_{k;\mathcal{S}}$ has no
contribution to $Z^{\star}_{k}$ except for on a linear subspace spanned by an
all-one tensor. Hence, the subsets $\mathcal{S}$ with nontrivial contribution
has a one-to-one correspondence with connected components of $T$ which
contains $k$.

Importantly, the number of connected components of $T$ both containing $k$ and
having a small cardinality only depends on the local topology of $T$ around
$k$. In the numerical examples, one can see that perturbative sketching
performs quite well if the interaction is local, and it is more adaptable than
Markov sketch functions or high-order Markov sketch functions.

In our numerical experiments, we keep a fixed design on the the perturbative
scale $\epsilon$, but there is slight numerical benefit in tuning $\epsilon$.
In general, the parameter $\epsilon$ should decrease with sample size. The
decay rate in $N$ depends on how much marginal distribution information is
needed to determine $G_{k}^{\star}$. In practice, one can simply choose a
decay rate of $\epsilon:=cN^{-f}$, with the parameter $c,f$ determined by
cross validation.

As a remark, theoretically by applying Section 7, one would be able to derive
the dependence of sample complexity on $\epsilon$, and tune $\epsilon$
accordingly. To capture the dependence on $\epsilon$ accurately, the reader is
advised to use the tighter original version of the Matrix Bernstein inequality
(cf. Theorem 6.1.1 in [tropp2015introduction]). The rigorous account on the
choice of $\epsilon$ will be left for future works.

##  7\. Sample complexity bound of TTNS-Sketch

This section gives an upper bound for the sample complexity of TTNS-Sketch.
Within this section, we only consider the case where the sketch functions
satisfies recursive sketching in the sense of Condition 4. In this simplified
case, one can use the alternative definition of $A_{k}$ in (26). As an
application, we obtain a sample complexity bound to the simple case where
$p^{\star}$ is a graphical model over a tree $T$, and the sketching function
is the Markov sketch function. Here is an informal version of the obtained
generalized sample complexity theorem:

######  Theorem 13.

(Informal statement of Theorem 30)

Let $p^{\star}\colon[n_{1}]\times\cdots\times[n_{d}]\to\mathbb{R}$ satisfy the
TTNS assumption in Condition 1. Let sketch function
$\\{T_{i},S_{i}\\}_{i=1}^{d}$ which satisfy recursive sketching in Condition
4. Let $\\{\hat{G}_{i}\\}_{i=1}^{d}$ be the output of Algorithm 1, and let
$\hat{p}_{\mathrm{TS}}$ denote the TTNS ansatz formed by
$\\{\hat{G}_{i}\\}_{i=1}^{d}$. There exists problem-dependent constant
$\zeta,L$ such that, for $\eta\in(0,1)$ and $\epsilon\in(0,1)$, if

$N\geq\frac{18L^{2}d^{2}+4L\epsilon\zeta
d}{\zeta^{2}\epsilon^{2}}\log{\left(\frac{(ln+m)d}{\eta}\right)},$

and the constants are defined as follows:

  * •

$l=\max_{k\in[d]}l_{k}$, where $l_{k}=\prod_{w\in\mathcal{C}(k)}l_{(w,k)}$

  * •

$m=\max_{k\in[d]}m_{k}$, where $m_{k}=m_{(k,\mathcal{P}(k))}$.

  * •

$n=\max_{k\in[d]}n_{k}$.

Then with probability at least $1-\eta$ one has

$\frac{\|\hat{p}_{\mathrm{TS}}-p^{\star}\|_{\infty}}{\vvvert
G_{1}^{\star}\vvvert\cdots\vvvert G_{d}^{\star}\vvvert}\leq\epsilon,$

where the notation $\vvvert G^{\star}_{i}\vvvert$ is to be defined later.
Moreover, the sample complexity upper bound for $N$ does not explicitly depend
on $\\{n_{k}\\}_{k\in[d]},\\{m_{e},n_{e}\\}_{e\in E}$ except in the log
factor.

We give a summary of organization of this section. In Section 7.1, we
introduce notations and conventions which are important for sample complexity
analysis. In Section 7.2, we prove small perturbations of the cores lead to
small perturbations of the obtained TTNS ansatz. In Section 7.3, we prove that
small error in the estimator $\hat{Z}_{k}$ leads to small perturbation of the
cores, leading to an upper bound for the sample complexity of TTNS-Sketch in
Theorem 30. In Section 7.5, we give a proof of all the lemmas and corollaries.
In Section 7.4, we remark how our derived results can be extended sample
complexity bounds for total variation distance.

###  7.1. Preliminaries

In what follows, for a given vector $v$, let $\|v\|$ and $\|v\|_{\infty}$
denote its Euclidean norm and its supremum norm, respectively. For any matrix
$M$, denote its spectral norm, Frobenius norm, and the $r$-th singular value
by $\|M\|$, $\|M\|_{F}$, and $\sigma_{r}(M)$, respectively. Also, for a
generic tensor $p$, let $\|p\|_{\infty}$ denote the largest absolute value of
the entries of $p$. Lastly, the orthogonal group in dimension $r$ is denoted
by $\operatorname{O}(r)$.

A mathematical structure important in this section is 3-tensors. Similar to
unfolding matrix in Definition 6, the 3-tensors we typically use come from
viewing high-dimensional tensors in terms of $3$-tensors by grouping joint
variables:

######  Definition 14.

(Unfolding 3-tensor Notation) For a generic $d$-dimensional tensor
$p\colon[n_{1}]\times\cdots\times[n_{d}]\to\mathbb{R}$ and for three disjoint
subsets $\mathcal{U},\mathcal{V},\mathcal{W}$ with
$\mathcal{U}\cup\mathcal{V}\cup\mathcal{W}=[d]$, we define the corresponding
_unfolding 3-tensor_ by $p(x_{\mathcal{U}};x_{\mathcal{V}};x_{\mathcal{W}})$.
The 3-tensor $p(x_{\mathcal{U}};x_{\mathcal{V}};x_{\mathcal{W}})$ is of size
$\left[\prod_{i\in\mathcal{U}}n_{i}\right]\times\left[\prod_{j\in\mathcal{V}}n_{j}\right]\times\left[\prod_{k\in\mathcal{W}}n_{k}\right]\to\mathbb{R}$.

It is helpful to introduce a slice of the 3-tensor. In our convention, we only
need to consider taking slice at the second component:

######  Definition 15.

(Middle index slice of 3-tensor) For any 3-tensor
$G\colon[r_{1}]\times[n_{1}]\times[r_{2}]\to\mathbb{R}$, we use
$G(\cdot,x,\cdot)\colon[r_{1}]\times[r_{2}]\to\mathbb{R}$ to denote an
$r_{1}\times r_{2}$ matrix obtained by fixing the second slot of $G$ to be
$x$.

In Definition 16-18, we introduce a new norm and two operations for
$3$-tensors.

######  Definition 16.

($\vvvert\cdot\vvvert$ norm for 3-tensors) Define the norm $\vvvert G\vvvert$
by

(40) $\vvvert G\vvvert:=\max_{x\in[n_{1}]}\|G(\cdot,x,\cdot)\|.$

######  Definition 17.

(contraction operator for 3-tensors) Let
$G\colon[r_{1}]\times[n_{1}]\times[r_{2}]\to\mathbb{R},G^{\prime}\colon[r_{3}]\times[n_{2}]\times[r_{4}]\to\mathbb{R}$
be two 3-tensors. Under the assumption $r_{2}=r_{3}$, define the 3-tensor
$G\circ G^{\prime}\colon[r_{1}]\times[n_{1}\times
n_{2}]\times[r_{4}]\to\mathbb{R}$ by

(41) $G\circ
G^{\prime}(\alpha;(x,y);\gamma)=\sum_{\beta\in[r_{2}]}G(\alpha,x,\beta)G^{\prime}(\beta,y,\gamma).$

######  Definition 18.

(tensor product operator for 3-tensors) Let
$G\colon[r_{1}]\times[n_{1}]\times[r_{2}]\to\mathbb{R},G^{\prime}\colon[r_{3}]\times[n_{2}]\times[r_{4}]\to\mathbb{R}$
be two 3-tensors. Define the 3-tensor $G\otimes G^{\prime}\colon[r_{1}\times
r_{3}]\times[n_{1}\times n_{2}]\times[r_{2}\times r_{4}]\to\mathbb{R}$ by

(42) $G\otimes
G^{\prime}((\alpha,\beta);(x,y);(\gamma,\theta))=G(\alpha,x,\beta)G^{\prime}(\gamma,y,\theta).$

We summarize the simple properties of the defined operation in Lemma 19, which
will be useful for our derivations:

######  Lemma 19.

The following results hold:

  1. (i)

Associativity of $\circ$ holds:

(43) $(G\circ G^{\prime})\circ G^{\prime\prime}=G\circ(G^{\prime}\circ
G^{\prime\prime}).$

  2. (ii)

Associativity of $\otimes$ holds:

(44) $(G\otimes G^{\prime})\otimes G^{\prime\prime}=G\otimes(G^{\prime}\otimes
G^{\prime\prime}).$

  3. (iii)

Inequality of $\circ$ under $\vvvert\cdot\vvvert$ norm:

(45) $\vvvert G\circ G^{\prime}\vvvert\leq\vvvert G\vvvert\cdot\vvvert
G^{\prime}\vvvert$

  4. (iv)

Equality of $\otimes$ under $\vvvert\cdot\vvvert$ norm:

(46) $\vvvert G\otimes G^{\prime}\vvvert=\vvvert G\vvvert\cdot\vvvert
G^{\prime}\vvvert$

  5. (v)

For a three tensor
$G(\alpha,x,\beta)\colon[r_{1}]\times[n]\times[r_{2}]\to\mathbb{R}$, denote
$G(\alpha,x;\beta)\colon[r_{1}n]\times[r_{2}]\to\mathbb{R}$ as the unfolding
matrix by grouping the first and second index of $G$. One has

(47) $\vvvert G\vvvert\leq\|G(\alpha,x;\beta)\|\leq n\vvvert G\vvvert$

As a consequence of associativity, given any collection of 3-tensors
$\\{G_{i}\\}_{i=1}^{d}$, one can define $G_{1}\otimes
G_{2}\otimes\ldots\otimes G_{d}$. Moreover, if the collection is such that the
size of the third index of $G_{i}$ coincides with the first index of
$G_{i+1}$, then one can naturally define the 3-tensor $G_{1}\circ
G_{2}\circ\ldots\circ G_{d}$.

###  7.2. 3-tensor structure for TTNS

For cleaner analysis, one often gives unfolding matrices a 3-tensor structure:

######  Definition 20.

(3-tensor structure for unfolding matrix) Consider a generic $D$-dimensional
tensor $f\colon[n_{1}]\times\cdots\times[n_{D}]\to\mathbb{R}$. Moreover,
suppose one picks a disjoint union $\mathcal{U}\cup\mathcal{V}=[D]$ and forms
an unfolding matrix $f(x_{\mathcal{U}};x_{\mathcal{V}})$ in the sense of
Definition 6. Define $f(x_{\mathcal{U}};1;x_{\mathcal{V}})$ as the 3-tensor of
size
$\left[\prod_{i\in\mathcal{U}}n_{i}\right]\times\left\\{1\right\\}\times\left[\prod_{j\in\mathcal{V}}n_{j}\right]\to\mathbb{R}$.
One likewise defines 3-tensor structure of
$f(1;x_{\mathcal{U}};x_{\mathcal{V}})$, whose first index is of size $1$, and
$f(x_{\mathcal{U}};x_{\mathcal{V}};1)$, whose third index is of size $1$.

A tensor core from a TTNS ansatz has a default 3-tensor view, whereby the
indices are grouped according to tree topology:

######  Definition 21.

(3-tensor structure for TTNS tensor cores) Suppose a tensor $p$ is defined by
a collection of tensor cores $\\{G_{i}\\}_{i=1}^{d}$ in the sense of
Definition 5.

If $k$ is neither a root node nor a leaf node, then $G_{k}$ is viewed with the
3-tensor unfolding structure

$G_{k}(\alpha_{(k,\mathcal{C}(k))};x_{k};\alpha_{(k,\mathcal{P}(k))})\colon\left[\prod_{w\in\mathcal{C}(k)}r_{(w,k)}\right]\times[n_{k}]\times[r_{(k,\mathcal{P}(k))}]\to\mathbb{R}.$

If $k$ is a leaf node, then $G_{k}$ is viewed with the 3-tensor unfolding
structure

$G_{k}(1;x_{k};\alpha_{(k,\mathcal{P}(k))})\colon\left\\{1\right\\}\times[n_{k}]\times[r_{(k,\mathcal{P}(k))}]\to\mathbb{R}.$

If $k$ is the root node, then $G_{k}$ is viewed with the 3-tensor unfolding
structure

$G_{k}(\alpha_{(k,\mathcal{C}(k))};x_{k};1)\colon\left[\prod_{w\in\mathcal{C}(k)}r_{(w,k)}\right]\times[n_{k}]\times\left\\{1\right\\}\to\mathbb{R}.$

With this design of norms, one can prove the following result by simple
algebra:

######  Lemma 22.

Suppose a generic tensor
$p\colon[n_{1}]\times\cdots\times[n_{d}]\to\mathbb{R}$ is defined by a
collection of tensor cores $\\{G_{i}\\}_{i=1}^{d}$ in the sense of Definition
5. Moreover, suppose the tensor cores are viewed by 3-tensor structures as in
Definition 21. Then

$\|p\|_{\infty}\leq\prod_{i=1}^{d}\vvvert G_{i}\vvvert.$

Using Lemma 22, one can bound global errors by errors in tensor cores:

######  Lemma 23.

In Lemma 22, let $\Delta G_{k}$ be a perturbation of $G_{k}$. Define a tensor
$p^{\prime}\colon[n_{1}]\times\cdots\times[n_{d}]\to\mathbb{R}$ by tensor
cores $\\{G_{k}+\Delta G_{k}\\}_{k=1}^{d}$ in the sense of Definition 5, with
the tree topology $T$ and the internal rank $\\{r_{e}\\}_{e\in E}$ the same as
that of $p$. Suppose $\vvvert\Delta G_{k}\vvvert\leq\delta_{k}\vvvert
G_{k}\vvvert$ for all $k\in[d]$, and set $\Delta p:=p^{\prime}-p$. Then,

$\|\Delta p\|_{\infty}\leq\vvvert G_{1}\vvvert\cdots\vvvert
G_{d}\vvvert\left(\sum_{i=1}^{d}\delta_{i}\right)\exp\left(\sum_{i=1}^{d}\delta_{i}\right).$

If $\max_{k\in[d]}\delta_{k}\leq\epsilon/(3d)$ for some fixed
$\epsilon\in(0,1)$,

(48) $\frac{\|\Delta p\|_{\infty}}{\vvvert G_{1}\vvvert\cdots\vvvert
G_{d}\vvvert}\leq\epsilon.$

###  7.3. Derivation for sample complexity of TTNS-Sketch

We first give a lemma which bounds the perturbation of solutions of a linear
equation $AX=B$, where in particular $X,B$ are two 3-tensors viewed under an
unfolding matrix. This result will be the main building block to form our
subsequent error analysis:

######  Lemma 24.

Consider a matrix $A^{\star}(\beta,\alpha)\in\mathbb{R}^{l\times r}$ with
$\mathrm{rank}(A^{\star})=r\leq l$ and a 3-tensor
$B^{\star}(\beta,x,\gamma)\in\mathbb{R}^{l\times n\times m}$ with unfolding
matrix structure $B^{\star}(\beta;(x,\gamma))\in\mathbb{R}^{l\times(nm)}$. Let
$X^{\star}(\alpha,x,\gamma)\in\mathbb{R}^{r\times n\times m}$ be the 3-tensor
with an unfolding matrix view
$X^{\star}(\alpha;(x,\gamma))\in\mathbb{R}^{r\times(nm)}$ which uniquely
solves the linear equation $A^{\star}X=B^{\star}$ in the sense of least
squares:

$\sum_{\alpha}A^{\star}(\beta,\alpha)X(\alpha,(x,\gamma))=B^{\star}(\beta,(x,\gamma)).$

Moreover, let $\Delta B^{\star}\in\mathbb{R}^{l\times n\times m}$ be a
perturbation of $B^{\star}$, and let $\Delta A^{\star}\in\mathbb{R}^{l\times
n\times m}$ be a perturbation of $A^{\star}$ with
$\|\left(A^{\star}\right)^{\dagger}\|\|\Delta A^{\star}\|<1$ so that
$\mathrm{rank}(A^{\star}+\Delta A^{\star})=n$. Then, let $\Delta X^{\star}$ be
a 3-tensor so that $X^{\star}+\Delta X^{\star}$ which uniquely solves the
linear equation $(A^{\star}+\Delta A^{\star})X=(B^{\star}+\Delta B^{\star})$
in the sense of least squares:

$\sum_{\alpha}(A^{\star}+\Delta
A^{\star})(\beta,\alpha)X(\alpha,(x,\gamma))=(B^{\star}+\Delta
B^{\star})(\beta,(x,\gamma))$

Under the unfolding matrix structure, suppose the column space of $B^{\star}$
is contained in that of $A^{\star}$, i.e. $X^{\star}$ solves
$A^{\star}X=B^{\star}$ exactly, one has

(49) $\vvvert\Delta
X^{\star}\vvvert\leq\frac{\|\left(A^{\star}\right)^{\dagger}\|}{1-\|\left(A^{\star}\right)^{\dagger}\|\|\Delta
A^{\star}\|}\left(\|\Delta A^{\star}\|\vvvert X^{\star}\vvvert+\vvvert\Delta
B^{\star}\vvvert\right).$

In particular, if $\vvvert X^{\star}\vvvert\geq\chi>0$ for some constant
$\chi,$ and $\Delta A^{\star}$ satisfies
$\|\left(A^{\star}\right)^{\dagger}\|\|\Delta A^{\star}\|\leq 1/2,$ then

(50) $\frac{\vvvert\Delta X^{\star}\vvvert}{\vvvert
X^{\star}\vvvert}\leq{2\|\left(A^{\star}\right)^{\dagger}\|}\,\left(\|\Delta
A^{\star}\|+\chi^{-1}\vvvert\Delta B^{\star}\vvvert\right).$

For our use case of Lemma 24, the coefficient matrix is viewed as a Kronecker
product of some smaller matrices, e.g. $A^{\star}_{k}$ is formed by
$\\{A^{\star}_{w\to k}\\}_{w\in\mathcal{C}(k)}$. One can bound the $\|\Delta
A^{\star}\|$ in this case, as the following lemma shows:

######  Lemma 25.

Consider a collection of matrices $\\{E_{i},C_{i}\\}_{i\in[n]}$ such that
$E_{i},C_{i}$ are of the same shape. Moreover, let $\|C_{i}\|\leq
1,\|E_{i}\|\leq\delta_{i}$. Then

$\left\|\bigotimes_{i=1}^{n}(C_{i}+E_{i})-\bigotimes_{i=1}^{n}C_{i}\right\|\leq\left(\sum_{i=1}^{n}\delta_{i}\right)\exp\left(\sum_{i=1}^{n}\delta_{i}\right).$

Lemma 24 and 25 leads to the proof strategy for obtaining sample complexity.
With the particular perturbation $\Delta p^{\star}:=\hat{p}-p^{\star}$, the
terms $\hat{A}_{k}$ and $\hat{B}_{k}$ from the Algorithm 1 satisfies
$B_{k}^{\star}+\Delta B^{\star}_{k}=\hat{B}_{k}$ and $A_{k}^{\star}+\Delta
A^{\star}_{k}=\hat{A}_{k}$. The least-squares solution $G^{\star}_{k}+\Delta
G^{\star}_{k}$ to the perturbed equation is thus the actual output
$\hat{G}_{k}$ from Algorithm 1.

However, due to the SVD step that is involved in obtaining $\hat{A}_{k}$ and
$\hat{B}_{k}$, one can only bound the sample estimation error in terms of the
following alternative metric:

######  Definition 26.

($\mathrm{dist}(\cdot,\cdot)$ operator for matrices) For any matrices
$B,B^{\star}\in\mathbb{R}^{n\times m}$, define

$\mathrm{dist}(B,B^{\star}):=\min_{R\in\operatorname{O}(m)}\|B-B^{\star}R\|.$

In other words, the finite sample estimate of $\hat{A}_{k},\hat{B}_{k}$ could
be closer to a rotation of $A^{\star}_{k},B^{\star}_{k}$, which we will denote
as $A^{\circ}_{k},B^{\circ}_{k}$. An error bound for of the type
$\mathrm{dist}(B,B^{\star})$ exists through Wedin theorem, and thus the
magnitude of $B^{\circ}_{k}-\hat{B}_{k}$ can be bounded, and
$A^{\circ}_{k}-\hat{A}_{k}$ is bounded via (26). In Corollary 27-28, we write
out relaxed version of Wedin theorem and the Matrix Bernstein inequality,
which we will use to analyze error terms of the type $\|\Delta
Z_{k}^{\star}\|,\|\Delta B_{k}^{\circ}\|$, respectively. As a summary of all
previous result, in Theorem 29, we form a quite technical proof bounding the
error on the rotated cores by the sample estimation error in sketching. In
Theorem 30, we form the sample complexity of TTNS-Sketch.

######  Corollary 27.

(Corollary to Wedin theorem, cf. Theorem 2.9 in [ccfm_2021]) Let
$Z^{\star}\in\mathbb{R}^{n\times m}$ be a matrix of rank $r$ and $\Delta
Z^{\star}\in\mathbb{R}^{n\times m}$ be its perturbation with
$Z:=Z^{\star}+\Delta Z^{\star}$. Moreover, let
$B^{\star},B\in\mathbb{R}^{n\times r}$ respectively be the first $r$ left
singular vectors of $Z^{\star},Z$. If $\|\Delta
Z^{\star}\|\leq(1-1/\sqrt{2})\sigma_{r}(Z^{\star})$, then

$\mathrm{dist}(B,B^{\star})\leq\frac{2\|\Delta
Z^{\star}\|}{\sigma_{r}(Z^{\star})}$

######  Corollary 28.

(Corollary to Matrix Bernstein inequality, cf. Corollary 6.2.1 in
[tropp2015introduction]) Let $Z^{\star}\in\mathbb{R}^{n\times m}$ be a matrix,
and let $\\{Z^{(i)}\in\mathbb{R}^{n\times m}\\}_{i=1}^{N}$ be a sequence of
i.i.d. matrices with $\mathbb{E}\left[Z^{(i)}\right]=Z^{\star}$. Denote
$\hat{Z}=\frac{1}{N}\sum_{i=1}^{N}Z^{(i)}$ and $\Delta
Z^{\star}=\hat{Z}-Z^{\star}$. Let the distribution of $Z^{(i)}$ be such that
there exists a constant $L$ with $||Z^{(i)}||\leq L$.

Let
$\gamma:=\max{\left(\left\|\mathbb{E}\left[Z^{(i)}\left(Z^{(i)}\right)^{\top}\right]\right\|,\left\|\mathbb{E}\left[\left(Z^{(i)}\right)^{\top}Z^{(i)}\right]\right\|\right)}$,
and then

$\mathbb{P}\left[\|\Delta Z^{\star}\|\geq
t\right]\leq(m+n)\exp{\left(\frac{-Nt^{2}/2}{\gamma+2Lt/3}\right)}.$

Using Jensen’s inequality, one has $\gamma\leq L^{2}$, and

(51) $\mathbb{P}\left[\|\Delta Z^{\star}\|\geq
t\right]\leq(m+n)\exp{\left(\frac{-Nt^{2}/2}{L^{2}+2Lt/3}\right)}.$

######  Theorem 29.

(Error bound over TTNS tensor cores) Let
$p^{\star}\colon[n_{1}]\times\cdots\times[n_{d}]\to\mathbb{R}$ be a density
function satisfy the TTNS assumption in Condition 1. Fix a sketch function
$\\{T_{i},S_{i}\\}_{i=1}^{d}$ which satisfies the recursive sketching
assumption in Condition 4. Let
$\\{A_{i}^{\star},B_{i}^{\star},G_{i}^{\star},Z_{i}^{\star}\\}_{i=1}^{d}$ be
as in Theorem 9. Moreover, let
$\\{\hat{A}_{i},\hat{B}_{i},\hat{G}_{i},\hat{Z}_{i}\\}_{i=1}^{d}$ be as in
Algorithm 1 with $\hat{p}$ as input. Suppose further that for some fixed
$\delta\in(0,1)$, one has

(52) $\|Z^{\star}_{k}-\hat{Z}_{k}\|\leq\zeta_{k}\delta,$

where $\zeta_{k}$ is defined by a series of constants as follows:

(53)
$\zeta_{k}:=\left(6\frac{c_{\mathcal{C}}}{c_{k;Z}}\right)^{-1}\xi,\quad\xi:=1\wedge\min_{i\in[d]}\left(2c_{i;A}\left(c_{i;S}+c_{i;G}\right)\right)^{-1},$

and the constants are defined as follows:

  * •

$c_{\mathcal{C}}=\max_{i\in[d]}|\mathcal{C}(i)|$,

  * •

$c_{k;Z}=1$ when $k=\text{root}$, and
$c_{k;Z}=\sigma_{r_{(k,\mathcal{P}(k))}}(Z_{k}^{\star}(\beta_{(k,\mathcal{C}(k))},x_{k};\gamma_{(k,\mathcal{P}(k))}))$
otherwise.

  * •

$c_{k;G}=1/\vvvert G^{\star}_{k}\vvvert$,

  * •

$c_{k;A}=1$ when $k=\text{leaf}$, and
$c_{k;A}=\|\left(A^{\star}_{k}\right)^{\dagger}\|$ otherwise,

  * •

$c_{k;S}=1$ when $k=\text{leaf}$, and
$c_{k;S}=\prod_{w\in\mathcal{C}(k)}||s_{w}(\beta_{(w,\mathcal{P}(w))};\beta_{(w,\mathcal{C}(w))},x_{w})||$
otherwise.

Then, there exists a TTNS tensor core $\\{G_{i}^{\circ}\\}_{i=1}^{d}$ for
$p^{\star}$ in the sense of Definition 5, such that $\vvvert
G_{i}^{\circ}\vvvert=\vvvert G_{i}^{\star}\vvvert$, and the following holds:

(54) $\frac{\vvvert\hat{G}_{k}-G_{k}^{\circ}\vvvert}{\vvvert
G^{\circ}_{k}\vvvert}\leq\delta.$

We defer the proof of Theorem 29 to the end of this subsection. As a direct
application, one obtain the sample complexity of TTNS-Sketch:

######  Theorem 30.

(Sample Complexity of TTNS-Sketch) Assume the setting and notation of Theorem
29. Let $\hat{p}_{\mathrm{TS}}$ denote the TTNS tensor formed by the TTNS
tensor core $\\{\hat{G}_{i}\\}_{i=1}^{d}$. In particular,
$\\{\hat{G}_{i}\\}_{i=1}^{d}$ is the output of Algorithm 1 with the empirical
distribution $\hat{p}$ formed by $N$ i.i.d. samples
$(y_{1}^{(i)},\ldots,y_{d}^{(i)})_{i=1}^{N}$. Let $Z_{k}^{(i)}$ be the $i$-th
sample estimate of $Z_{k}^{\star}$, i.e.

$Z_{k}^{(i)}(\beta_{(k,\mathcal{C}(k))},x_{k},\gamma_{(k,\mathcal{P}(k))}):=S_{k}(\beta_{(k,\mathcal{C}(k))},y^{(i)}_{\mathcal{L}(k)})\mathbf{1}(y^{(i)}_{k}=x_{k})T_{k}(y^{(i)}_{\mathcal{R}(k)},\gamma_{(k,\mathcal{P}(k))}),$

and set $L_{k}$ as an upper bound of
$\|Z_{k}^{(i)}(\beta_{(k,\mathcal{C}(k))},x_{k};\gamma_{(k,\mathcal{P}(k))})\|$.
Define $L=\max_{k\in[d]}L_{k}$.

For $\eta\in(0,1)$ and $\epsilon\in(0,1)$, suppose

$N\geq\frac{18L^{2}d^{2}+4L\epsilon\zeta
d}{\zeta^{2}\epsilon^{2}}\log{\left(\frac{(ln+m)d}{\eta}\right)},$

and the constants are defined as follows:

  * •

$\zeta=\max_{k\in[d]}\zeta_{k}$, with $\zeta_{k}$ as in Theorem 29.

  * •

$l=\max_{k\in[d]}l_{k}$, where $l_{k}=\prod_{w\in\mathcal{C}(k)}l_{(w,k)}$

  * •

$m=\max_{k\in[d]}m_{k}$, where $m_{k}=m_{(k,\mathcal{P}(k))}$.

  * •

$n=\max_{k\in[d]}n_{k}$.

Then with probability at least $1-\eta$ one has

(55) $\frac{\|\hat{p}_{\mathrm{TS}}-p^{\star}\|_{\infty}}{\vvvert
G_{1}^{\star}\vvvert\cdots\vvvert G_{d}^{\star}\vvvert}\leq\epsilon.$

###### Proof.

(of Theorem 30) Suppose that the inequality (52) holds with
$\delta=\frac{\epsilon}{3d}$. In the setting of Theorem 29, note that
$p^{\star}$ is formed by $\\{G_{i}^{\circ}\\}_{i=1}^{d}$, and
$\hat{p}_{\mathrm{TS}}$ is formed by $\\{G_{i}^{\circ}+\Delta
G_{i}^{\circ}\\}_{i=1}^{d}$ with $\vvvert\Delta
G_{i}^{\circ}\vvvert\leq\frac{\epsilon}{3d}\vvvert G_{i}^{\circ}\vvvert$.
Moreover, one has $\vvvert G_{i}^{\star}\vvvert=\vvvert G_{i}^{\circ}\vvvert$.
Applying (48) in Lemma 23, one thus has

$\frac{\|\hat{p}_{\mathrm{TS}}-p^{\star}\|_{\infty}}{\vvvert
G^{\star}_{1}\vvvert\cdots\vvvert
G^{\star}_{d}\vvvert}=\frac{\|\hat{p}_{\mathrm{TS}}-p^{\star}\|_{\infty}}{\vvvert
G^{\circ}_{1}\vvvert\cdots\vvvert G^{\circ}_{d}\vvvert}\leq\epsilon.$

By a simple union bound argument, it suffices to find a sample size that (52)
is guaranteed for each individual $k\in[d]$ with $\delta=\frac{\epsilon}{3d}$
and with probability $1-\frac{\eta}{d}$. We apply (51) in Corollary 28, where
$Z^{\star}_{k}$ is a matrix of size $\mathbb{R}^{l_{k}n_{k}\times m_{k}}$.
With the choice of $(l,n,m,L)$ as set in the theorem statement, one has

$\mathbb{P}\left[\|\Delta Z^{\star}_{k}\|\geq
t\right]\leq(ln+m)\exp{\left(\frac{-Nt^{2}/2}{L^{2}+2Lt/3}\right)}.$

It then suffices for one to find a lower bound for $N$ so that for
$t=\zeta\frac{\epsilon}{3d}$ one has

$(ln+m)\exp{\left(\frac{-Nt^{2}/2}{L^{2}+2Lt/3}\right)}\leq\eta/d.$

By simple algebra, it suffices to lower bound $N$ by the following quantity:

$N\geq\frac{2L^{2}+4Lt/3}{t^{2}}\log{\left(\frac{(ln+m)d}{\eta}\right)}=\frac{18L^{2}d^{2}+4L\epsilon\zeta
d}{\zeta^{2}\epsilon^{2}}\log{\left(\frac{(ln+m)d}{\eta}\right)}.$

∎

As a corollary, for a Markov sketch function, note that each $Z^{(i)}_{k}$ is
a tensor with one entry being of value one, the rest being zero. Under this
setting, note that $\|Z^{(i)}_{k}\|\leq\|Z^{(i)}_{k}\|_{F}=1$, and hence one
can set $L=1$. Let $\Delta(T)$ denote the maximal degree of a tree $T$. One
has $l\leq n^{\Delta(T)-1}$ and $m=n\leq ln$. Thus one obtains a sample
complexity for TTNS-Sketch under Markov sketching:

######  Corollary 31.

(Sample Complexity of TTNS-Sketch for Markov Sketch function) Suppose that
$p^{\star}$ is a graphical model over a tree $T$, with the sketching function
being the Markov sketch function specified in Lemma 11. Suppose

$N\geq\frac{18d^{2}+4\epsilon\zeta
d}{\zeta^{2}\epsilon^{2}}\log{\left(\frac{2n^{\Delta(T)}d}{\eta}\right)}.$

Then, with probability at least $1-\eta$, one has

(56) $\frac{\|\hat{p}_{\mathrm{TS}}-p^{\star}\|_{\infty}}{\vvvert
G_{1}^{\star}\vvvert\cdots\vvvert G_{d}^{\star}\vvvert}\leq\epsilon.$

In the remainder of this subsection, we give the proof of Theorem 29, which is
a culmination of all previous statements, the proof of which are of secondary
interest and are included in Section 7.5. For some intuition of Theorem 29,
the factors in $\zeta_{k}$ is set such that $\xi$ can bound the sample
estimation error of the sketched down core determining equation in Algorithm
1. One then uses Lemma 24 to derive (54). As a sanity check of the defined
constants, note that
$\xi_{i}:=\left(2c_{i;A}\left(c_{i;S}+c_{i;G}\right)\right)^{-1}$ can be
thought of as a homogeneous constant. That is, for any non-zero scaling
constant $\\{q_{i}\\}_{i=1}^{d}$, changing the sketch cores from
$\\{s_{i}\\}_{i=1}^{d}$ to $\\{q_{i}s_{i}\\}_{i=1}^{d}$ won’t affect
$\xi_{i}$, which is because the resultant multiplicative change to
$\\{c_{i;A},c_{i;S},c_{i;G}\\}$ will be cancelled out in $\xi_{i}$. One can
think of $\xi=1\wedge\min_{i}\xi_{i}$ in Theorem 29 as serving the role of
condition number. Moreover, because $(Z^{\star}_{k}-\hat{Z}_{k})\propto
c_{k;Z}$ by definition, it follows the condition in (52) will not be affected
if a scaling constant is applied to sketch cores.

###### Proof.

(of Theorem 29) Following the short-hand in Algorithm 3, for the joint
variables we write
$\beta_{k}\leftarrow\beta_{(k,\mathcal{C}(k))},\gamma_{k}\leftarrow\gamma_{\mathcal{P}(k)},\alpha_{k}\leftarrow\alpha_{(k,\mathcal{P}(k))}$,
and for the bond dimensions we write $r_{k}\leftarrow
r_{(\mathcal{P}(k),k)},l_{k}\leftarrow\prod_{w\in\mathcal{C}(k)}l_{(w,k)},m_{k}\leftarrow
m_{(k,\mathcal{P}(k))}$. Moreover, if $k$ is leaf, then we understand
$\beta_{k}$ as a joint variable taking value in $\\{1\\}$, and $l_{k}=1$.
Likewise, if $k$ is root, then we understand $\alpha_{k},\gamma_{k}$
respectively as a joint variable taking value in $\\{1\\}$, and
$r_{k}=m_{k}=1$. In this notation, when $k$ is leaf or root, the joint
variables sketch $Z_{k}$ is conveniently written as
$Z_{k}(\beta_{k},x_{k};\gamma_{k})$.

For this proof, we will fix a canonical unfolding matrix structure for the
tensors used. For $Z_{k}(\beta_{k},x_{k},\gamma_{k})$ being one of
$\\{Z^{\star}_{k},\hat{Z}_{k},\Delta Z^{\star}_{k}\\}$, we reshape it as
$Z_{k}(\beta_{k},x_{k};\gamma_{k})$. For $B_{k}(\beta_{k},x_{k},\alpha_{k})$
being one of $\\{B^{\star}_{k},B^{\circ}_{k},\hat{B}_{k},\Delta
B^{\star}_{k},\Delta B^{\circ}_{k}\\}$, we reshape it as
$B_{k}(\beta_{k},x_{k};\alpha_{k})$. For
$A_{k}(\beta_{k},\alpha_{(k,\mathcal{C}(k))})$ being one of
$\\{A^{\star}_{k},A^{\circ}_{k},\hat{A}_{k},\Delta A^{\star}_{k},\Delta
A^{\circ}_{k}\\}$, we reshape it as
$A_{k}(\beta_{k};\alpha_{(k,\mathcal{C}(k))})$. For
$s_{k}(\beta_{(k,\mathcal{P}(k))},\beta_{k},x_{k})$, we reshape it as
$s_{k}(\beta_{(k,\mathcal{P}(k))};\beta_{k},x_{k})$. For
$G_{k}(\alpha_{(k,\mathcal{C}(k))},x_{k},\alpha_{k})$ being one of
$\\{G^{\star}_{k},G^{\circ}_{k},\hat{G}_{k},\Delta G^{\star}_{k},\Delta
G^{\circ}_{k}\\}$, we reshape it as
$G_{k}(\alpha_{(k,\mathcal{C}(k))};x_{k},\alpha_{k})$.

Fix a non-root $k$, recall that $B_{k}^{\star}$ and $\hat{B}_{k}$ are the
first $r_{k}$ left singular vectors of $Z^{\star}_{k}$ and $\hat{Z}_{k}$,
respectively. One applies Corollary 27: if $\|\Delta
Z_{k}^{\star}\|\leq(1-1/\sqrt{2})\sigma_{r_{k}}(Z^{\star}_{k})$, then one can
find $R_{k}\in\operatorname{O}(r_{k})$ such that one can define
$B^{\circ}_{k}:=B^{\star}_{k}R_{k}$ so that

$\hat{B}_{k}=B_{k}^{\circ}+\Delta B^{\circ}_{k},\quad\|\Delta
B^{\circ}_{k}\|\leq\frac{2\|\Delta
Z_{k}^{\star}\|}{\sigma_{r_{k}}(Z^{\star}_{k})}$

and by (v) in Lemma 19, one has

(57) $\vvvert\Delta B^{\circ}_{k}\vvvert\leq\frac{2\|\Delta
Z_{k}^{\star}\|}{\sigma_{r_{k}}(Z^{\star}_{k})}.$

Meanwhile, if $k$ is the root, there is no SVD step. In this case, the
perturbation $\Delta B_{k}^{\star}$ is simply $\Delta Z_{k}^{\star}$. For
consistency, when $k$ is the root, we set $B_{k}^{\circ}=B_{k}^{\star}$, and
the corresponding perturbation $\Delta B^{\circ}_{k}$ is just $\Delta
Z_{k}^{\star}$.

In summary, $B_{k}^{\circ}$ is a rotation of $B_{k}^{\star}$, and
$\hat{B}_{k}$ differs from $B_{k}^{\circ}$ by a perturbation $\Delta
B^{\circ}_{k}$, for which one has an error bound. For a “rotated” version of
$A_{k}^{\star}$, define

(58)
$A^{\circ}_{k}(\beta_{(k,\mathcal{C}(k))},\alpha_{(k,\mathcal{C}(k))}):=\prod_{w\in\mathcal{C}(k)}\sum_{(\beta_{w},x_{w})}s_{w}(\beta_{(w,k)},\beta_{w},x_{w})B^{\circ}_{w}(\beta_{w},x_{w},\alpha_{(w,k)})$

Viewed in the unfolding matrix structure fixed in the beginning of proof, one
can write $A_{k}^{\circ}=\bigotimes_{w\in\mathcal{C}(k)}s_{w}B_{w}^{\circ}$.
Likewise, one has
$\hat{A}_{k}=\bigotimes_{w\in\mathcal{C}(k)}s_{w}\hat{B}_{w}=\bigotimes_{w\in\mathcal{C}(k)}\left(s_{w}B_{w}^{\circ}+s_{w}\Delta
B^{\circ}_{w}\right)$.

Now, with the chosen unfolding matrix structure, consider the following
“rotated” versions of (21):

(59) $\displaystyle G_{k}^{\circ}$
$\displaystyle=B_{k}^{\circ}(\beta_{k};x_{k},\alpha_{k})\quad\text{if}~{}k~{}\text{is
a leaf},$ $\displaystyle\textstyle A_{k}^{\circ}G_{k}^{\circ}$
$\displaystyle=B_{k}^{\circ}(\beta_{k};x_{k},\alpha_{k})\quad\text{otherwise}.$

We will first prove that $\\{G_{i}^{\circ}\\}_{i=1}^{d}$ forms a TTNS tensor
core for $p^{\star}$ in the sense of Definition 5. Suppose one has
$\\{\Phi^{\star}_{k\to\mathcal{P}(k)}\\}_{\text{$k\not=$ root}}$ defined
according to Condition 2. Then, Theorem 9 proves that
$\\{G_{i}^{\star}\\}_{i=1}^{d}$ solves the CDE (5) in Theorem 7 for the choice
of gauge as $\\{\Phi^{\star}_{k\to\mathcal{P}(k)}\\}_{\text{$k\not=$ root}}$.
Now consider (5) for a rotated choice of gauge
$\\{\Phi^{\circ}_{k\to\mathcal{P}(k)}:=\Phi^{\star}_{k\to\mathcal{P}(k)}R_{k}\\}_{\text{$k\not=$
root}}$. One can directly check that the sketched down equation coincides with
(59), and Theorem 9 ensures that the solution $\\{G_{i}^{\circ}\\}_{i=1}^{d}$
is unique and forms a TTNS tensor core for $p^{\star}$.

Next, we prove that $\vvvert G_{k}^{\circ}\vvvert=\vvvert
G^{\star}_{k}\vvvert$, with the 3-tensor view for
$G_{k}^{\circ},G^{\star}_{k}$ as in Definition 21. As the coefficients
$A_{k}^{\circ}$’s and right-hand sides $B_{k}^{\circ}$’s are simply the
rotations of $A_{k}^{\star}$’s and $B_{k}^{\star}$’s of (21), one can verify
that $G_{k}^{\circ}$ is a rotation of $G_{k}^{\star}$. If $k$ is not leaf nor
root, the equation for $G^{\circ}_{k}$ can be rewritten as

(60)
$\left(\bigotimes_{w\in\mathcal{C}(k)}s_{w}B_{w}^{\star}R_{w}\right)G_{k}^{\circ}=B^{\star}_{k}R_{k},$

whereas the equation for $G_{k}^{\star}$ is

$\left(\bigotimes_{w\in\mathcal{C}(k)}s_{w}B_{w}^{\star}\right)G_{k}^{\star}=B^{\star}_{k}.$

For the rotation matrix $R_{k}(\alpha;\beta)\in\operatorname{O}(r_{k})$, one
gives it a 3-tensor view as $R_{k}(\alpha;1;\beta)$ in the sense of Definition
20. One can directly verify that the following equation for $G_{k}^{\circ}$
solves (60):

(61)
$G_{k}^{\circ}=\left(\bigotimes_{w\in\mathcal{C}(k)}R_{w}^{\top}\right)\circ
G^{\star}_{k}\circ R_{k}.$

Likewise, $G_{k}^{\circ}=G^{\star}_{k}\circ R_{k}$ if $k$ is leaf, and
$G_{k}^{\circ}=\left(\bigotimes_{w\in\mathcal{C}(k)}R_{w}^{\top}\right)\circ
G^{\star}_{k}$ if $k$ is root. Then $\vvvert G_{k}^{\circ}\vvvert=\vvvert
G^{\star}_{k}\vvvert$ as a consequence. The constructive form in (61) also
gives a more intuitive sense of why $\\{G_{i}^{\circ}\\}_{i=1}^{d}$ forms a
TTNS tensor core in the same way as $\\{G_{i}^{\star}\\}_{i=1}^{d}$. The
reason is that each $R_{k}$ and $R_{k}^{\top}$ comes in pairs, which does not
change the formed TTNS tensor itself.

Next, we prove that, for $\Delta B_{k}^{\circ}:=\hat{B}_{k}-B_{k}^{\circ}$ and
$\Delta A_{k}^{\circ}:=\hat{A}_{k}-A_{k}^{\circ}$, the assumption (52) leads
to the the following bound:

(62) $\|\Delta B_{k}^{\circ}\|\leq\xi\delta,\quad\|\Delta A_{k}^{\circ}\|\leq
c_{k;S}\xi\delta.$

First, for $\Delta B_{k}^{\circ}$’s, we will derive a tighter bound

(63) $\|\Delta B_{k}^{\circ}\|\leq\frac{\xi\delta}{3c_{\mathcal{C}}},$

which implies $\|\Delta B_{k}^{\circ}\|\leq\xi\delta$ as $3c_{\mathcal{C}}\geq
1$. To see this, using (57), one has for any non-root $k$,

$\|\Delta B_{k}^{\circ}\|\leq\frac{2\|\Delta
Z_{k}^{\star}\|}{\sigma_{r_{k}}(Z^{\star}_{k})}\leq\frac{2\zeta_{k}\delta}{c_{k;Z}}=\frac{2}{c_{k;Z}}\frac{c_{k;Z}}{6c_{\mathcal{C}}}\xi\delta\leq\frac{\xi\delta}{3c_{\mathcal{C}}}.$

If $k$ is the root, recall that $\Delta B_{k}^{\circ}=\Delta Z_{k}^{\star}$,
hence using $c_{k;Z}=1$,

$\|\Delta B_{k}^{\circ}\|=\|\Delta
Z_{k}^{\star}\|\leq\zeta_{k}\delta=\frac{c_{k;Z}}{6c_{\mathcal{C}}}\xi\delta\leq\frac{\xi\delta}{3c_{\mathcal{C}}}.$

Therefore, (63) holds.

Next, for a non-leaf $k$, recall that

$\displaystyle\Delta A_{k}^{\circ}$
$\displaystyle=\bigotimes_{w\in\mathcal{C}(k)}(s_{w}B_{w}^{\circ}+s_{w}\Delta
B^{\circ}_{w})-\bigotimes_{w\in\mathcal{C}(k)}s_{w}B_{w}^{\circ}$
$\displaystyle=\left(\bigotimes_{w\in\mathcal{C}(k)}{s_{w}}\right)\left(\bigotimes_{w\in\mathcal{C}(k)}(B_{w}^{\circ}+\Delta
B^{\circ}_{w})-\bigotimes_{w\in\mathcal{C}(k)}B_{w}^{\circ}\right)$

By definition, one has $\|\bigotimes_{w\in\mathcal{C}(k)}{s_{w}}\|=c_{k;S}$.
Note that $\|B_{w}^{\circ}\|=1$ and $\|\Delta
B_{w}^{\circ}\|\leq\frac{\xi}{3c_{\mathcal{C}}}\delta$. Hence, one can apply
Lemma 25, which shows

$\|\Delta A_{k}^{\circ}\|\leq c_{k;S}\left(\sum_{w\in\mathcal{C}(k)}\|\Delta
B^{\circ}_{w}\|\right)\exp\left(\sum_{w\in\mathcal{C}(k)}\|\Delta
B^{\circ}_{w}\|\right),$

Using (63),

$\sum_{w\in\mathcal{C}(k)}\|\Delta B^{\circ}_{w}\|\leq
c_{\mathcal{C}}\cdot\max_{w\in[d]}\|\Delta B^{\circ}_{w}\|\leq
c_{\mathcal{C}}\frac{\xi\delta}{3c_{\mathcal{C}}}\leq\frac{\xi\delta}{3}.$

Hence,

$\displaystyle\|\Delta A_{k}^{\circ}\|$ $\displaystyle\leq
c_{k;S}\left(\sum_{w\in\mathcal{C}(k)}\|\Delta
B^{\circ}_{w}\|\right)\exp\left(\sum_{w\in\mathcal{C}(k)}\|\Delta
B^{\circ}_{w}\|\right)$ $\displaystyle\leq c_{k;S}\frac{\xi\delta}{3}\exp(1)$
$\displaystyle\leq c_{k;S}\xi\delta,$

where the last two steps hold because $\frac{\xi\delta}{3}<1$ and $\exp(1)<3$.

It remains to show how (62) lead to (54).

If $k$ is a leaf,

$\frac{\vvvert\Delta G_{k}^{\circ}\vvvert}{\vvvert
G^{\circ}_{k}\vvvert}=\frac{\vvvert\Delta B^{\circ}_{k}\vvvert}{\vvvert
G^{\circ}_{k}\vvvert}\leq\frac{\|\Delta B^{\circ}_{k}\|}{\vvvert
G^{\circ}_{k}\vvvert}\leq c_{k;G}\xi\delta\leq\delta,$

where the first equation follows from $\Delta G_{k}^{\circ}=\Delta
B_{k}^{\circ}$ in (61), the first inequality comes from (v) in Lemma 19, and
the last inequality uses $c_{k;A}=c_{k;S}=1$ and
$\xi\leq\left(2c_{k;A}\left(c_{k;S}+c_{k;G}\right)\right)^{-1}=\frac{1}{2}\left(1+c_{k;G}\right)^{-1}$.

Importantly, note that

$A_{k}^{\circ}=\left(\bigotimes_{w\in\mathcal{C}(k)}s_{w}B_{w}^{\star}\right)\left(\bigotimes_{w\in\mathcal{C}(k)}R_{w}\right),$

and so the fact that each $R_{w}$ is orthogonal implies
$\|\left(A_{k}^{\circ}\right)^{\dagger}\|=\|\left(A_{k}^{\star}\right)^{\dagger}\|=c_{k;A}$.
For any non-leaf $k$, note that $\xi,\delta\leq 1$ leads to
$\|\left(A_{k}^{\circ}\right)^{\dagger}\|\|\Delta A_{k}^{\circ}\|\leq
c_{k;A}c_{k;S}\xi\delta\leq 1/2$. From Lemma 24 and (v) in Lemma 19, it
follows that

$\begin{split}\frac{\vvvert\Delta G_{k}^{\circ}\vvvert}{\vvvert
G^{\circ}_{k}\vvvert}&\leq
2\|\left(A^{\circ}_{k}\right)^{\dagger}\|\left(\|\Delta
A^{\circ}_{k}\|+\|\Delta B^{\circ}_{k}\|c_{k;G}\right)\\\ &\leq
2c_{k;A}\left(c_{k;S}+c_{k;G}\right)\xi\delta\\\ &\leq\delta,\end{split}$

and so we are done.

∎

###  7.4. Remarks on sample complexity bound for total variation distance

Using the proof technique as outline before, one can derive a sample
complexity upper bound on the total variation norm via the $l_{1}$ distance
between $p^{\star}$ and $\hat{p}_{\mathrm{TS}}$. Note that one can define a
new norm $\vvvert\cdot\vvvert_{1}$ by

$\vvvert G(\alpha;x;\beta)\vvvert_{1}:=\sum_{x}\|G(\cdot,x,\cdot)\|,$

which is a similar definition to $\vvvert\cdot\vvvert$.

The proofs in Section 7.5 are also written such that the adaptation to
$\vvvert\cdot\vvvert_{1}$ is straightforward. First, all of the results in
Lemma 19 will hold in this new norm, with only a change in the constant in
(v). Second, from the $\vvvert\cdot\vvvert_{1}$ version of Lemma 19, one can
bound the global $\|\cdot\|_{1}$ error by the core-wise
$\vvvert\cdot\vvvert_{1}$ error by an adaptation of Lemma 23. Finally, for
local $\vvvert\cdot\vvvert_{1}$ error on cores, the proof of Lemma 24 also
proves that Lemma 24 holds if one replaces $\vvvert\cdot\vvvert$ by the new
$\vvvert\cdot\vvvert_{1}$ norm. Importantly, the $N=O(d^{2})$ scaling will
still hold under the $l_{1}$-norm.

###  7.5. Proof of results

###### Proof.

(of Lemma 19)

In the notation of Definition 15, one can write the definition of $\circ$ by

$G\circ
G^{\prime}(\cdot,(x,y),\cdot)=G(\cdot,x,\cdot)G^{\prime}(\cdot,y,\cdot).$

Associativity of $\circ$ thus follows from associativity of matrix product,
and likewise the inequality for $\circ$ comes from submultiplicativity of
matrix product under spectral norm:

$\max_{(x,y)}\|G\circ
G^{\prime}(\cdot,(x,y),\cdot)\|=\max_{(x,y)}\|G(\cdot,x,\cdot)G^{\prime}(\cdot,y,\cdot)\|\leq\left(\max_{x}\|G(\cdot,x,\cdot)\|\right)\left(\max_{y}\|G^{\prime}(\cdot,y,\cdot)\|\right)$

Likewise, by abuse of notation, also use $\otimes$ as the Kronecker product
operation over matrices. Then one can simplify and write the definition of
$\otimes$ by

$G\otimes G^{\prime}(\cdot,(x,y),\cdot)=G(\cdot,x,\cdot)\otimes
G^{\prime}(\cdot,y,\cdot).$

Associativity of $\otimes$ likewise follows from associativity of Kronecker
product over matrices. Likewise, the equality for $\otimes$ comes from
multiplicativity of matrix product under spectral norm:

$\|G\otimes
G^{\prime}(\cdot,(x,y),\cdot)\|=\|G(\cdot,x,\cdot)\|\cdot\|G^{\prime}(\cdot,y,\cdot)\|$

We now prove (v). For a vector $v\in\mathbb{R}^{r_{2}}$, one can view the
vector $G(\alpha,x;\beta)v$ as the concatenation of $n$ smaller vectors of the
form $G(\cdot,x;\cdot)v$. For the upper bound, one has

$\displaystyle\|G(\alpha,x;\beta)v\|=\sum_{x\in[n]}\|G(\cdot,x;\cdot)v\|\leq
n\max_{x\in[n]}\|G(\cdot,x;\cdot)\|\|v\|=n\vvvert G\vvvert\|v\|,$

where is done after taking supremum over $v$ with $\|v\|=1$.

For the lower bound, one has

$\displaystyle\|G(\alpha,x;\beta)v\|=\sum_{x\in[n]}\|G(\cdot,x;\cdot)v\|\geq\max_{x\in[n]}\|G(\cdot,x;\cdot)\|\|v\|=\vvvert
G\vvvert\|v\|,$

and likewise one is done after taking supremum over $v$ with $\|v\|=1$.

∎

###### Proof.

(of Lemma 22) Suppose that in $T$, the maximum distance from the root node is
$L$. At a level $l\in\\{1,\ldots,L\\}$, suppose there are $d_{l}$ nodes in $T$
which are of distance $l$ to the root, denoted by the set
$\\{v^{l}_{i}\\}_{i=1}^{d_{l}}$. Then, if one views $p$ as a 3-tensor of size
$\\{1\\}\times\left[\prod_{i=1}^{d}n_{i}\right]\times\\{1\\}\to\mathbb{R}$,
then one has

(64)
$p=G_{\text{root}(T)}\circ\bigotimes_{i\in[d_{1}]}G_{v^{1}_{i}}\circ\bigotimes_{k\in[d_{2}]}G_{v^{2}_{j}}\circ\ldots\circ\bigotimes_{k\in[d_{L}]}G_{v^{L}_{k}},$

which is only a consequence of the structure of the TTNS ansatz and the
3-tensor structure of TTNS tensor core in Definition 21. Then, by the chosen
3-tensor structure of $p$, one has $\|p\|_{\infty}=\vvvert p\vvvert$. By Lemma
19, one has

(65) $\|p\|_{\infty}=\vvvert p\vvvert\leq\vvvert
G_{\text{root}(T)}\vvvert\prod_{l=1}^{L}\vvvert\bigotimes_{i\in[d_{l}]}G_{v^{l}_{i}}\vvvert=\vvvert
G_{\text{root}(T)}\vvvert\prod_{l=1}^{L}\prod_{i\in[d_{l}]}\vvvert
G_{v^{l}_{i}}\vvvert=\prod_{i\in[d]}\vvvert G_{i}\vvvert,$

where the first inequality and the second equality follows from (45) and (46)
in Lemma 19.

∎

###### Proof.

(of Lemma 23) Let $p_{0},\ldots,p_{d}$ be a sequence of tensors such that
$p_{0}=p$, and $p_{k}$ is the tensor formed by the TTNS tensor core
$\\{G_{i}+\Delta G_{i}\\}_{i=1}^{k}\cup\\{G_{j}\\}_{j\not\in[k]}$. One is
interested in the error $\|p_{d}-p_{0}\|_{\infty}$, and one can bound by

$\|p_{d}-p_{0}\|_{\infty}\leq\sum_{k=1}^{d}\|p_{k}-p_{k-1}\|_{\infty}.$

One can then bound the magnitude of each term in this telescoping sum. Note
that $p_{k}-p_{k-1}$ is a TTNS ansatz formed by cores $\\{G_{i}+\Delta
G_{i}\\}_{i=1}^{k-1}\cup\\{\Delta G_{k}\\}\cup\\{G_{j}\\}_{j=k+1}^{d}$, and
thus by Lemma 22

$\|p_{k}-p_{k-1}\|_{\infty}\leq\prod_{i=1}^{k-1}\vvvert G_{i}+\Delta
G_{i}\vvvert\vvvert\Delta G_{k}\vvvert\prod_{j=k+1}^{d}\vvvert
G_{j}\vvvert\leq\delta_{k}\prod_{i=1}^{d}(1+\delta_{i})\prod_{i=1}^{d}\vvvert\Delta
G_{i}\vvvert.$

Therefore, using $1+x\leq\exp(x)$, one has

$\|p_{d}-p_{0}\|_{\infty}\leq\left(\sum_{i=1}^{d}\delta_{i}\right)\prod_{i=1}^{d}(1+\delta_{i})\prod_{i=1}^{d}\vvvert\Delta
G_{i}\vvvert\leq\left(\sum_{i=1}^{d}\delta_{i}\right)\exp\left(\sum_{i=1}^{d}\delta_{i}\right)\prod_{i=1}^{d}\vvvert\Delta
G_{i}\vvvert$

∎

###### Proof.

(of Lemma 24) Note that (50) is only a corollary of (49). To prove (49), it
suffices to prove that for any $i\in[n]$, one has

(66) $\|\Delta
X^{\star}(\cdot,i,\cdot)\|\leq\frac{\|\left(A^{\star}\right)^{\dagger}\|}{1-\|\left(A^{\star}\right)^{\dagger}\|\|\Delta
A^{\star}\|}\left(\|\Delta A^{\star}\|\|X^{\star}(\cdot,i,\cdot)\|+\|\Delta
B^{\star}(\cdot,i,\cdot)\|\right),$

whereby (49) is obtained by taking maximum over $i\in[n]$ on both sides.

Based on the above observation, one can simplify notation and reduce argument
over $\vvvert\cdot\vvvert$ to regular spectral norm over matrices. For a fixed
$i\in[n]$, define $C^{\star}:=B^{\star}(\cdot,i,\cdot)$. Let $Y^{\star}$ be
the matrix which is the unique _exact_ solution the linear equation
$A^{\star}Y=C^{\star}$. Naturally, one has
$Y^{\star}=X^{\star}(\cdot,i,\cdot)$.

Likewise, define $\Delta C^{\star}=\Delta B^{\star}(\cdot,i,\cdot)$ as the
corresponding perturbation to $C^{\star}$, and let $Y^{\star}+\Delta
Y^{\star}$ be the matrix which is the unique solution the linear equation
$(A^{\star}+\Delta A^{\star})Y=(C^{\star}+\Delta C^{\star})$ in the sense of
least squares. As before, one has $Y^{\star}+\Delta
Y^{\star}=X^{\star}(\cdot,i,\cdot)+\Delta X^{\star}(\cdot,i,\cdot)$. Then,
(66) is equivalent to the following inequality:

(67) $\|\Delta
Y^{\star}\|\leq\frac{\|\left(A^{\star}\right)^{\dagger}\|}{1-\|\left(A^{\star}\right)^{\dagger}\|\|\Delta
A^{\star}\|}\left(\|\Delta A^{\star}\|\|X^{\star}\|+\|\Delta
C^{\star}\|\right).$

To reduce further, for an arbitrary $v\in\mathbb{R}^{m}$, note that it
suffices to prove the following result

(68) $\|\Delta
Y^{\star}v\|\leq\frac{\|\left(A^{\star}\right)^{\dagger}\|}{1-\|\left(A^{\star}\right)^{\dagger}\|\|\Delta
A^{\star}\|}\left(\|\Delta A^{\star}\|\|Y^{\star}v\|+\|\Delta
C^{\star}v\|\right),$

and (67) follows by taking supremum over $v$ with $\|v\|=1$.

To simplify further, define $b^{\star}:=C^{\star}v\in\mathbb{R}^{l}$, and let
$x^{\star}:=Y^{\star}v\in\mathbb{R}^{r}$ be the unique _exact_ solution to
$A^{\star}x=b^{\star}$. Moreover, let $\Delta b^{\star}:=\Delta C^{\star}v$
and let $\Delta x^{\star}:=\Delta Y^{\star}v$, and then $x^{\star}+\Delta
x^{\star}$ solves the linear equation $(A^{\star}+\Delta
A^{\star})x=(b^{\star}+\Delta b^{\star})$ in the sense of least squares. This
is exactly the setting of Theorem 3.48 in [wendland_2017], because of which
(68) holds as a corollary. Thus we are done. ∎

###### Proof.

(of Lemma 25 )

Let $C^{\prime}_{i}=C_{i}+E_{i}$, then

(69)
$\begin{split}\bigotimes_{i=1}^{n}(C_{i}+E_{i})-\bigotimes_{i=1}^{n}C_{i}&=(C^{\prime}_{1}\otimes\cdots\otimes
C^{\prime}_{n})-(C_{1}\otimes C^{\prime}_{2}\otimes\cdots\otimes
C^{\prime}_{n})\\\ &\quad+(C_{1}\otimes C^{\prime}_{2}\otimes\cdots\otimes
C^{\prime}_{n})-(C_{1}\otimes C_{2}\otimes C^{\prime}_{3}\otimes\cdots\otimes
C^{\prime}_{n})\\\ &\quad+\cdots\\\ &\quad+(C_{1}\otimes\cdots\otimes
C_{n-1}\otimes C^{\prime}_{n})-(C_{1}\otimes\cdots\otimes C_{n}).\end{split}$

The first line on the right-hand side of (69) reduces to $E_{1}\otimes
C^{\prime}_{2}\otimes\cdots\otimes C^{\prime}_{n}$. Since
$\|C^{\prime}_{i}\|\leq\|C_{i}\|+\|E_{i}\|\leq 1+\delta_{i}$,

$\|E_{1}\otimes C^{\prime}_{2}\otimes\cdots\otimes
C^{\prime}_{n}\|=\|E_{1}\|\|C^{\prime}_{2}\|\cdots\|C^{\prime}_{n}\|\leq\delta_{1}(1+\delta_{2})\cdots(1+\delta_{n})\leq\delta_{1}\cdot\prod_{i=1}^{n}(1+\delta_{i}).$

The norm of the $j$-th line on the right-hand side of (69) is upper bounded by
$\delta_{j}\cdot\prod_{i=1}^{n}(1+\delta_{i})$. Therefore, using
$1+x\leq\exp(x)$, one has

$\left\|\bigotimes_{i=1}^{n}(C_{i}+E_{i})-\bigotimes_{i=1}^{n}C_{i}\right\|\leq\left(\sum_{i=1}^{n}\delta_{i}\right)\cdot\prod_{i=1}^{n}(1+\delta_{i})\leq\left(\sum_{i=1}^{n}\delta_{i}\right)\exp\left(\sum_{i=1}^{n}\delta_{i}\right).$

∎

###### Proof.

(of Corollary 27 and Corollary 28)

For Corollary 27, we apply Theorem 2.9, (2.26a) in [ccfm_2021]: if $\|\Delta
Z^{\star}\|\leq(1-1/\sqrt{2})\sigma_{r}(Z^{\star})$, then

$\mathrm{dist}(B,B^{\star})\leq\frac{2\|\left(B^{\star}\right)^{\top}\Delta
Z^{\star}\|}{\sigma_{r}(Z^{\star})-\sigma_{r+1}(Z^{\star})}\leq\frac{2\|\left(B^{\star}\right)^{\top}\|\|\Delta
Z^{\star}\|}{\sigma_{r}(Z^{\star})-\sigma_{r+1}(Z^{\star})},$

and we are done by applying $\sigma_{r+1}(Z^{\star})=0$ and $\|B^{\star}\|=1$.

For Corollary 28, only (51) is new, and one only needs to justify $\gamma\leq
L^{2}$. By Jensen’s theorem and sub-multiplicativity of spectral norm, one has

$\displaystyle\left\|\mathbb{E}\left[Z^{(i)}\left(Z^{(i)}\right)^{\top}\right]\right\|\leq\mathbb{E}\left[\left\|Z^{(i)}\left(Z^{(i)}\right)^{\top}\right\|\right]\leq\mathbb{E}\left[\left\|Z^{(i)}\right\|^{2}\right]\leq
L^{2}.$

∎

##  8\. Numerical result

In this section, we perform comparison of different modeling methods. There
are four models of interest. The symbol $\hat{p}_{\mathrm{TS}}$ stands for the
model obtained from the TTNS-Sketch method. The symbol $\hat{p}_{\mathrm{GM}}$
stands for the model one obtains from direct graphical modeling over a given
tree structure $T$. Specifically, the $\hat{p}_{\mathrm{GM}}$ model with tree
structure $T$ refers to the graphical model over $T$ where the parameters are
chosen by maximum likelihood estimation. The symbol $\hat{p}_{\mathrm{CL}}$
stands for the Chow-Liu model, which is obtained by direct graphical modeling
with the Chow-Liu tree $T_{\mathrm{CL}}$. The symbol $\hat{p}_{\mathrm{BM}}$
stands for the model one obtains from modeling with Born Machine (BM). The
training of BM is done by optimizing Negative Log Likelihood (NLL), with
details of the training following from that of [han2018unsupervised].

In what follows, the _error_ of a model $p$ refers to the relative $l_{2}$
error:

$\mathrm{Error}(p):=\frac{\|p-p^{\star}\|}{\|p\|}.$

For BM training, we will use Negative log likelihood level of the model as a
performance metric:

$\mathrm{NLL}(p):=\sum_{i=1}^{N}p(y_{1}^{(i)},\ldots,y_{d}^{(i)}).$

###  8.1. Numerical case study: tree graphical model with different input tree
topology

(a) Trident Graph, $d=10$

(b) Dendrimer Graph, $d=10$

(c) Bipartite Graph, $d=10$

Figure 8. The black solid line stands for edges on $T$ and the dashed brown
line stands for edges on $T_{\mathrm{path}}$. The graph is plotted in layout
that is respectively natural for $T$ and for $T_{\mathrm{path}}$. Error plot
for each case of $T$ are also included. One can see that convergence to true
model only occurs with true tree specification.

In this numerical experiment, we aim to exhibit the importance of using a
correct tree topology. We will focus on testing the TTNS-Sketch algorithm on a
tree-based graphical model under input tree topology mis-specification.
Specifically, given any fixed tree structure $T=(V,E)$, we consider the
following graphical model over $T$:

(70) $p^{\star}(x_{1},\ldots,x_{d})=\exp{\left(-\beta\sum_{(i,j)\in
E}f_{i,j}(x_{i},x_{j})\right)},$

where $\beta>0$ is the temperature parameter. We test a simple binary model
where $\beta=1/2$ and $f_{i,j}(x_{i},x_{j})=-x_{i}x_{j}$ with each
$x_{i}\in\\{-1,1\\}$, which is the setting of standard ferromagnetic Ising
model.

First, consider the case where $T$ is a 10-node trident, see illustration in
Figure 8(a). Even in such a simple example, one can see that there is not a
good way to choose a path to fit the tree model. Suggested by our deliberate
choice in ordering the variables, one reasonable candidate is a path graph
$T_{\mathrm{path}}$ that traverses from node 1 to 10 in numerical order.
Indeed, with only one exception of the edge $(4,8)$, the tree
$T_{\mathrm{path}}$ is almost made up of edges from $T$.

Likewise, we include the 10-node dendrimer graph in Figure 8(b) and a
bipartite graph in Figure 8(c), where we also use the numerical order to
indicate the chosen $T_{\mathrm{path}}$ structure. While the dendrimer case
also uses a reasonable path structure, one can see that the bipartite graph
case uses a $T_{\mathrm{path}}$ structure very different from $T$. In Figure
8, the natural layout draws $T$ and $T_{\mathrm{path}}$ in a layout natural to
$T$, where one can see how often $T_{\mathrm{path}}$ uses edge from $T$.

For the three tree structures, we will compare three methods (i)-(iii): (i)
TTNS-Sketch over $T_{\mathrm{path}}$, (ii) Graphical modeling over
$T_{\mathrm{path}}$, (iii) TTNS-Sketch over $T$. In (i) and (iii), we choose
the Markov sketch function. The results are listed in Figure 8. One can see
that the error for (iii) always converge to zero with large $N$, which is
consistent with Lemma 11. However, both (i) and (ii) does not converge to
$p^{\star}$, with the performance being worst in the bipartite graph case.

In the path layout, one can more naturally “count” the internal bond dimension
necessary to let $p^{\star}$ admit a TTNS ansatz under $T_{\mathrm{path}}$.
Let $E_{\mathrm{path}}$ stand for the edge set for $T_{\mathrm{path}}$, which
is essentially $E_{\mathrm{path}}=\\{(i,i+1)\\}_{i=1}^{d-1}$. In this case,
for any edge $e=(i,i+1)$, one can calculate the internal bond $r_{e}$ by
counting the number of edges one would “cut” if one places a vertical line in
between node $i$ and $i+1$. If one counts $q_{i}$ edges, then one has the
upper bound $r_{e}\leq 2^{q_{i}}$ for the Ising model. More generally, suppose
$X\sim p^{\star}$, and let each entry of $X$ be a discrete variable over
$\\{1,\ldots,n\\}$, then $r_{e}$ is upper bounded by $n^{q_{i}}$. The
description of $q_{i}$ exactly coincides the number of edges across the
partition $[d]=\\{1,\ldots,i\\}\cup\\{i+1,\ldots,d\\}$, i.e. the cardinality
of the cut from the partition.

Thus, one can easily extend Figure 8 to cases with more nodes, and then the
three models will have quite different behavior. The cut number $q_{i}$ for
the trident case is upper bounded by $q_{i}\leq 2$, but largest $q_{i}$ for
the bipartite graph is $d-1$ when $d$ is even. Hence, in the bipartite case,
the TTNS ansatz of $p^{\star}$ under $T_{\mathrm{path}}$ is not practical to
compute, while the TTNS ansatz of $p^{\star}$ under $T$ is simple.
Importantly, the bipartite graph $T$ is itself a path graph, and so the
$p^{\star}$ is not complicated.

Thus, while modest tree structure mis-specification can be treated with higher
bond dimension, a large structural deviation may lead to an intractable bond
dimension penalty. We also note that in all of these cases, one has
$T_{\mathrm{CL}}=T$ with overwhelmingly high probability. Due to the $O(d)$
sample complexity to recover $T$, we will henceforth assume that one has
access to the true tree model $T$.

###  8.2. Numerical case study: 1D spin system with non-local interactions

In this example, we consider a more complicated Markov random field model.
Given a fixed tree structure $T=(V,E)$, we denote the shortest-path distance
on $T$ as $\operatorname{dist}_{T}$. For any fixed positive integer $l$, we
propose the following model

(71)
$p^{\star}(x_{1},\ldots,x_{d})=\exp{\left(-\beta\sum_{\operatorname{dist}_{T}{(i,j)}\leq
l}f_{i,j}(x_{i},x_{j})\right)}.$

This is also a graphical model over $G_{T}=(V,E^{\prime})$ by letting
$E^{\prime}=\\{(i,j)\mid\operatorname{dist}_{T}{(i,j)}\leq l\\}$. In
particular, we set $l:=2$. Moreover, we consider the case where $T$ is a path
graph with $d=32$. See the illustration in Figure 10.

Moreover, to demonstrate our algorithm under more general situations than
binary data, we consider the 4-state clock model with
$f_{i,j}(x_{i},x_{j})=\cos{(x_{i}-x_{j})}$ and
$x_{i}\in\\{0,\frac{1}{2}\pi,\pi,\frac{3}{2}\pi\\}$. In this case, we set
$\beta=1/4$ to ensure the spin-spin correlation strength is at an appropriate
level.

Figure 9. Illustration of the graphical model in Section 8.2. The solid black
line indicates edges for true graphical model $G_{T}$. The dashed brown line
indicates edges for $T$, the tree model to be used for TTNS-Sketch.

Figure 10. Error comparison for the graphical model in Figure 10. The model
$\hat{p}_{\mathrm{CL}}$ stands for the result of direct graphical modeling
with the tree structure $T$ in Figure 10. TTNS-Sketch with perturbative sketch
function converges to the true model. The sign (*) stands for a truncation of
the internal bond $r_{e}$. One can see that, even with truncation, TTNS-Sketch
with 2-Markov still performs worse than perturbative sketching without
truncation. Moreover, due to the pre-selected internal bond truncation, the
2-Markov model cannot converge to the true model in the limit of samples.

If one applies Chow-Liu algorithm to the model in (71), one could obtain any
one of the spanning tree of $G_{T}$. Hence, for the sake of fair comparison,
we fix the path graph $T$ as the input tree graph to TTNS-Sketch. We test
TTNS-Sketch under the following sketch function (i) perturbative sketching
function, (ii) Markov sketch function, and (iii) 2-Markov sketch function
(defined in Section 6.3). For the perturbative sketch function, we pick
$\epsilon=0.05$ and a sketch core size of $l_{e}=20$ for any $e\in E$.

We observe convergence for TTNS-Sketch under the perturbative sketching
function. On the other hand, TTNS-Sketch with Markov and 2-Markov sketch
function both encounter numerical blow-up for sample size up to $N=2^{17}$. To
provide further comparison, we will include a “truncated” version of both the
Markov and 2-Markov model. For Markov model, we truncate to the target
internal bond dimension $r_{e}=2$, down from $r_{e}=n=4$. For 2-Markov model,
we truncate to the target internal bond dimension $r_{e}=6$, down from
$r_{e}=n^{2}=16$. In particular, the 2-Markov sketch function with
$r_{e}=n^{2}$ actually satisfies the exact recovery property, but the
truncated $r_{e}=6$ version performs better and converges to a reasonable
error. For benchmark, we also include direct graphical modeling. The result is
shown in Figure 10.