#  Cost-efficient Gaussian tensor network embeddings for tensor-structured
inputs

Linjian Ma, Edgar Solomonik
Department of Computer Science, University of Illinois at Urbana-Champaign
{lma16<EMAIL_ADDRESS>

###### Abstract

This work discusses tensor network embeddings, which are random matrices ($S$)
with tensor network structure. These embeddings have been used to perform
dimensionality reduction of tensor network structured inputs $x$ and
accelerate applications such as tensor decomposition and kernel regression.
Existing works have designed embeddings for inputs $x$ with specific
structures, such as the Kronecker product or Khatri-Rao product, such that the
computational cost for calculating $Sx$ is efficient. We provide a systematic
way to design tensor network embeddings consisting of Gaussian random tensors,
such that for inputs with more general tensor network structures, both the
sketch size (row size of $S$) and the sketching computational cost are low.

We analyze general tensor network embeddings that can be reduced to a sequence
of sketching matrices. We provide a sufficient condition to quantify the
accuracy of such embeddings and derive sketching asymptotic cost lower bounds
using embeddings that satisfy this condition and have a sketch size lower than
any input dimension. We then provide an algorithm to efficiently sketch input
data using such embeddings. The sketch size of the embedding used in the
algorithm has a linear dependence on the number of sketching dimensions of the
input. Assuming tensor contractions are performed with classical dense matrix
multiplication algorithms, this algorithm achieves asymptotic cost within a
factor of $O(\sqrt{m})$ of our cost lower bound, where $m$ is the sketch size.
Further, when each tensor in the input has a dimension that needs to be
sketched, this algorithm yields the optimal sketching asymptotic cost. We
apply our sketching analysis to inexact tensor decomposition optimization
algorithms. We provide a sketching algorithm for CP decomposition that is
asymptotically faster than existing work in multiple regimes, and show
optimality of an existing algorithm for tensor train rounding.

##  1 Introduction

Sketching techniques, which randomly project high-dimensional data onto lower
dimensional spaces while still preserving relevant information in the data
[40], have been widely used in numerical linear algebra, including for
regression, low-rank approximation, and matrix multiplication [47]. One key
step of sketching algorithms is to design an embedding matrix
${S}\in\mathbb{R}^{m\times n}$ with $m\ll n$, such that for any input (also
called data throughout the paper) ${x}\in\mathbb{R}^{n}$, the projected vector
norm is $(1\pm\epsilon)$-close to the input vector,
$\|{S}{x}\|_{2}=(1\pm\epsilon)\|{x}\|_{2}$, with probability at least
$1-\delta$ (defined as $(\epsilon,\delta)$-accurate embedding throughout the
paper), and the multiplication ${S}{x}$ can be computationally efficient.
${S}$ is commonly chosen as a random matrix with each element being an i.i.d.
Gaussian variable when ${x}$ is dense, or a random sparse matrix when ${x}$ is
sparse, etc.

In this work, we focus on the case where ${x}$ has a tensor network structure.
A tensor network [32] uses a set of (small) tensors, where some or all of
their dimensions are contracted according to some pattern, to implicitly
represent a tensor. Tensor network structured data is commonly seen in
multiple applications, including kernel based statistical learning [35, 1, 48,
29], machine learning and data mining via tensor decomposition methods [3, 43,
22, 43], and simulation of quantum systems [46, 26, 41, 15, 16]. Commonly used
embedding matrices are sub-optimal for sketching many such data. For example,
consider the case where ${x}\in\mathbb{R}^{s^{N}}$ is a chain of Kronecker
products, ${x}={x}_{1}\otimes\cdots\otimes{x}_{N},$ where
${x}_{i}\in\mathbb{R}^{s}$ for $i\in\\{1,\ldots,N\\}$. If
${S}\in\mathbb{R}^{m\times s^{N}}$ is a Gaussian matrix, the multiplication
${S}{x}$ has a computational cost of $\Omega\left(ms^{N}\right)$, and the
exponential dependence on the tensor order $N$ makes the calculation
impractical when $N$ or $s$ is large.

The computational cost of the multiplication ${S}{x}$ can be reduced when
${S}$ has a structure that can be easily multiplied with the target data. One
example is when ${S}$ has a Kronecker product structure,
${S}={S}_{1}\otimes\cdots\otimes{S}_{N}$ and each
${S}_{i}\in\mathbb{R}^{m^{1/N}\times s}$. When
${x}={x}_{1}\otimes\cdots\otimes{x}_{N}$, ${S}{x}$ can then be calculated
efficiently via $({S}_{1}{x}_{1})\otimes\cdots\otimes({S}_{N}{x}_{N})$,
reducing the cost to ${O}\left(Nm^{1/N}s+m\right)$. Another example is when
${S}$ has a Khatri-Rao product structure,
${S}=({S}_{1}\odot\cdots\odot{S}_{N})^{T}$ and each
${S}_{i}\in\mathbb{R}^{s\times m}$. ${S}{x}$ can then be calculated
efficiently via $({S}_{1}^{T}{x}_{1})*\cdots*({S}_{N}^{T}{x}_{N})$, where $*$
denotes the Hadamard product, which reduces the cost to ${O}\left(Nms\right)$.
However, tensor-network-structured embedding matrices that can be easily
multiplied with data may not necessarily minimize computational cost, since
the sketch size sufficient for accurate embedding can also increase. For
example, the sketch size necessary for both Kronecker product and Khatri-Rao
product embeddings to be $(\epsilon,\delta)$-accurate is at least exponential
in $N$, which is inefficient for large tensor order $N$ [1]. To find
embeddings that are both accurate and computationally efficient, it is
therefore of interest to investigate tensor network structures that can both
yield small sketch size and be multiplied with data efficiently.

Existing works discuss tensor network embeddings with more efficient sketch
size than Kronecker and Khatri-Rao product structure, such as tensor train
[38] and balanced binary tree [1]. In particular, Ahle et al. [1] designed a
balanced binary tree structured embedding and showed that the sketch size
sufficient for $(\epsilon,\delta)$-accurate embedding can have only linear
dependence on $N$. Using this embedding to sketch Kronecker product structured
data yields a sketching cost that only has a polynomial dependence on both $N$
and $s$. However, for data with other tensor network structures, these
embeddings may not be the most computationally efficient.

#### Our contributions

Figure 1: Illustration of target data and embedding. Blue edges have larger
weights than the red edge.

In this work, we design algorithms to efficiently sketch more general data
tensor networks such that each dimension to be sketched has size lower bounded
by the sketch size and is a dimension of only one tensor. One of such data
tensor networks is shown in Fig. 1. In particular, we look at the following
question.

For arbitrary data with a tensor network structure of interest, can we
automatically sketch the data into one tensor with Gaussian tensor network
embeddings that are accurate, have low sketch size, and also minimize the
sketching asymptotic computational cost?

Different from existing works [1, 17, 25] that construct the embedding based
on fast sketching techniques, including Countsketch [8], Tensorsketch [34],
and fast Johnson-Lindenstraus (JL) transform using fast Fourier transform [2],
we discuss the case where each tensor in the embedding contains i.i.d.
Gaussian random elements. Gaussian-based embeddings yield larger computational
cost, but have the most efficient sketch size for both unconstrained and
constrained optimization problems [9, 37]. This choice also enables us use a
simple computational model to analyze the sketching cost, where tensor
contractions are performed with classical dense matrix multiplication
algorithms.

While we allow for the data tensor network to be a hypergraph, we consider
only graph embeddings, (detailed definition in Section 2), which include tree
embeddings that have been previously studied [1, 10, 4]. Each one of these
embeddings consisting of $N_{E}$ tensors can be reduced to a sequence of
$N_{E}$ sketches (random sketching matrices). In Section 3, we show that if
each of these sketches is $(\epsilon/\sqrt{N_{E}},\delta)$-accurate, then the
embedding is at least ($\epsilon,\delta$)-accurate.

In Section 4, we provide an algorithm to sketch input data with an embedding
that not only satisfies the $(\epsilon,\delta)$-accurate sufficient condition,
but is computationally efficient and has low sketch size. Given a data tensor
network and one data contraction tree $T_{0}$, this algorithm outputs a
sketching contraction tree that is constrained on $T_{0}$. This setting is
useful for application of sketching to alternating optimization in tensor-
related problems, such as tensor decompositions. In alternating optimization,
multiple contraction trees of the data $x$ are chosen in an alternating order
to form multiple optimization subproblems, each updating part of the variables
[36, 24, 27]. Designing embeddings under the constraint can help reuse
contracted intermediates across subproblems.

The sketch size of the embedding used in the algorithm has a linear dependence
on the number of sketching dimensions of the input. As to the sketching
asymptotic computational cost, within all constrained sketching contraction
trees with embeddings satisfying the $(\epsilon,\delta)$-accurate sufficient
condition and only have one output sketch dimension, this algorithm achieves
asymptotic cost within a factor of $O(\sqrt{m})$ of the lower bound, where $m$
is the sketch size. When the input data tensor network structure is a graph,
the factor improves to $O(m^{0.375})$. In addition, when each tensor in the
input data has a dimension to be sketched, such as Kronecker product input and
tensor train input, this algorithm yields the optimal sketching asymptotic
cost.

At the end of Section 4, we look at cases where the widely discussed tree
tensor network embeddings are efficient in terms of the sketching
computational cost. We show for input data graphs such that each data tensor
has a dimension to be sketched and each contraction in the given data
contraction tree $T_{0}$ contracts dimensions with size being at least the
sketch size, sketching with tree embeddings can achieve the optimal asymptotic
cost.

In Section 5, we apply our sketching algorithm to two applications,
CANDECOMP/PARAFAC (CP) tensor decomposition [14, 13] and tensor train rounding
[33]. We present a new sketching-based alternating least squares (ALS)
algorithm for CP decomposition. Compared to existing sketching-based ALS
algorithm, this algorithm yields better asymptotic computational cost under
several regimes, such as when the CP rank is much lower than each dimension
size of the input tensor. We also provide analysis on the recently introduced
randomized tensor train rounding algorithm [10]. We show that the tensor train
embedding used in that algorithm satisfies the accuracy sufficient condition
in Section 3 and yields the optimal sketching asymptotic cost, implying that
this is an efficient algorithm, and embeddings with other structures cannot
achieve lower asymptotic cost.

##  2 Definitions

Figure 2: An example of tensor diagram notation.

We introduce some tensor network notation here, and provide additional
definitions and background in Appendix A. The structure of a tensor network
can be described by an undirected hypergraph $G=(V,E,w)$, also called tensor
diagram. Each hyperedge $e\in E$ may be adjacent to either one or at least two
vertices, and we refer to hyperedges with a dangling end (one end not adjacent
to any vertex) as uncontracted hyperedges, and those without dangling end as
contracted hyperedges. We refer to the cardinality of a hyperedge as its
number of ends. An example is shown in Fig. 2. We use $w$ to denote a function
such that for each $e\in E$, $w(e)=\log(s)$ is the natural logarithm of the
dimension sizes represented by hyperedge $e$. For a hyperedge set $E$, we use
$w(E)=\sum_{e\in E}w(e)$ to denote the weighted sum of the hyperedge set.

A tensor network embedding is the matricization of a tensor described by a
tensor network, and each embedding can be described by $S=(G_{E},\bar{E})$,
where $G_{E}=(V_{E},E_{E},w)$ shows the embedding graph structure and
$\bar{E}\subseteq E_{E}$ is the edge set connecting data and the embedding. In
this work we only discuss the case where $G_{E}$ is a graph, such that each
uncontracted edge in $E_{E}$ is adjacent to one vertex and contracted edge in
$E_{E}$ is adjacent to two vertices. Let $E_{1}\subset E_{E}$ be the subset of
uncontracted edges, $S$ is a matricization such that uncontracted dimensions
in $\bar{E}$ are grouped into the column of the matrix, and dimensions in
$E_{1}$ are grouped into the row. We use $N=|\bar{E}|$ to denote the order of
the embedding, and $m=\exp(w(E_{1}))$ denotes the output sketch size. We use
$G_{D}=(V_{D},E_{D},w)$ to represent the data tensor network structure, and
use $G=(G_{D},G_{E})$ to denote the overall tensor network structure.

Within the tensor network $G=(V,E,w)$, the contraction between two tensors
represented by $v_{i},v_{j}\in V$ is denoted by $(v_{i},v_{j})$. The
contraction between two tensors that are the contraction outputs of
$W_{i}\subset V$, $W_{j}\subset V$, respectively, is denoted by
$(W_{i},W_{j})$. A contraction tree on the tensor network $G=(V,E,w)$ is a
rooted binary tree $T_{B}=(V_{B},E_{B})$ showing how the tensor network is
fully contracted. Each vertex in $V_{B}$ can be represented by a subset of the
vertices, $W\subseteq V$, and denotes the contraction output of $W$. The two
children of $W$, denoted as $W_{1}$ and $W_{2}$, must satisfy $W_{1}\cup
W_{2}=W$. Each leaf vertex must have $|W|=1$, and the root vertex is
represented by $V$. Any topological sort of the contraction tree represents a
contraction path (order) of the tensor network.

##  3 Sufficient condition for accurate embedding

Figure 3: Illustration of embedding linearization. Each gray vertex denotes a
tensor of the embedding, each white vertex denotes an identity matrix, and
each white box denotes a permutation matrix.

We consider tensor network embeddings that have a graph structure, thus some
embeddings, such as those with a Khatri-Rao product structure [38, 9], are not
considered in this work. Such embeddings can be linearized to a sequence of
sketches. Let $N_{E}=|V_{E}|$ denote the number of vertices in the embedding,
in each linearization, each vertex is given an unique index
$i\in[N_{E}]$111Throughout the paper we use $[N]$ to denote
$\\{1,\ldots,N\\}$. and denoted $v_{i}$. The $i$th tensor is denoted by
${\mathcal{A}}_{i}$, and ${A}_{i}$ denotes its matricization where we combine
all uncontracted dimensions and contracted dimensions connected to
${\mathcal{A}}_{j}$ with $j>i$ into the row, and other dimensions into the
column. The embedding can then be represented as a chain of multiplications,
${S}={M}_{N_{E}}{P}_{N_{E}}\cdots{M}_{1}{P}_{1},$ where ${M}_{i}$ is the
Kronecker product of identity matrices with ${A}_{i}$ for $i\in[N_{E}]$, and
${P}_{i}$ is a permutation matrix. We illustrate the linearization in Fig. 3
using a fully connected tensor network embedding. We show in Theorem 3.1 a
sufficient condition for embeddings to be $(\epsilon,\delta)$-accurate.

######  Theorem 3.1 (($\epsilon,\delta$)-accurate sufficient condition).

Consider a Gaussian tensor network embedding where there exists a
linearization such that each ${A}_{i}$ for $i\in[N_{E}]$ has row size
$\Omega(N_{E}\log(1/\delta)/\epsilon^{2})$. Then the tensor network embedding
is ($\epsilon,\delta$)-accurate.

###### Proof.

Based on the composition rules of JL moment [18, 19] in Lemma A.2 and Lemma
A.3 in the appendix, in the linearization all ${M}_{i}{P}_{i}$ satisfy the
strong $\left(\frac{\epsilon}{L\sqrt{2N}},\delta\right)$-JL moment property so
${S}$ satisfies the strong $\left({\epsilon},\delta\right)$-JL moment
property. This implies the embedding is $(\epsilon,\delta$)-accurate. ∎

Theorem 3.1 is a sufficient (but not necessary) condition for constructing
($\epsilon,\delta$)-accurate embedding. It also implies that specific tree
embeddings are $(\epsilon,\delta)$-accurate, as we show below.

######  Corollary 3.2.

Consider a Gaussian embedding containing a tree tensor network structure,
where there is only one output sketch dimension with size
$m=\Theta\left(N_{E}\log(1/\delta)/\epsilon^{2}\right)$, and each dimension
within the embedding has size $m$. Then the embedding is
$(\epsilon,\delta)$-accurate.

###### Proof.

Consider the linearization such that vertices are labelled based on the
reversed ordering of a breath-first search from the vertex adjacent to the
edge associated with the output sketch dimension. Each ${A}_{i}$ has row size
$m=\Theta\left(N_{E}\log(1/\delta)/\epsilon^{2}\right)$ thus the embedding
satisfies Theorem 3.1. ∎

One special case of Corollary 3.2 is the tensor train [33] (also called matrix
product states (MPS) [42]) embedding, where the embedding tensor network has a
1D structure along with an output dimension adjacent to one of the endpoint
tensors. Tensor train is widely used to efficiently represent high dimensional
tensors in multiple applications, including numerical PDEs [12, 39], quantum
physics [41], high-dimensional data analysis [20, 21] and machine learning [6,
44, 30]. Since the tensor train embedding contains $N$ vertices, Corollary 3.2
directly implies that a sketch size of
$m=\Theta\left(N\log(1/\delta)/\epsilon^{2}\right)$ is sufficient for the MPS
embedding to be $(\epsilon,\delta)$-accurate. This embedding has already been
used in applications including tensor train rounding [10] and low rank
approximation of matrix product operators [4].

Note that the tensor train embedding introduced in this work and [10] adds an
output sketch dimension to the standard tensor train, and restricts the tensor
train rank to be the sketch size $m$. This is different from the recent work
by Rakhshan and Rabusseau [38], where they construct an embedding consisting
of $m$ independent tensor trains, each one with a tensor train rank of $R$. A
sketch size upper bound of
$m=\Theta\left(1/\epsilon^{2}\cdot(1+2/R)^{N}\log^{2N}(1/\delta)\right)$ is
derived for that embedding to be $(\epsilon,\delta)$-accurate. However, this
bound has an exponential dependence on $N$.

##  4 A sketching algorithm with efficient computational cost and sketch size

We find Gaussian tensor network embeddings $G_{E}$ that both have efficient
sketch size and yield efficient computational cost. We are given a specific
data tensor network $G_{D}$ that implicitly represents a matrix
${M}\in\mathbb{R}^{s_{1}s_{2}\ldots s_{N}\times t}$, and want to sketch the
row dimension of the matrix. We assume that size of each dimension to be
sketched, $s_{i}$ for $i\in[N]$, is greater than the sketch size $m$, and each
one of these dimensions is adjacent to only one tensor. The goal is to find a
Gaussian embedding $G_{E}$ satisfying the following properties.

Figure 4: Illustration of the embedding. The black box includes the Kronecker
product embedding and the orange box includes the embedding containing a
binary tree of small tensor networks.

  * •

$G_{E}\in\mathcal{G}^{(\epsilon,\delta)}$, where
$\mathcal{G}^{(\epsilon,\delta)}$ contains all embeddings not only satisfying
the ($\epsilon,\delta$)-accurate sufficient condition in Theorem 3.1, but also
only have one output sketch dimension ($|E_{1}|=1$) with size
$m=\Theta\left(N_{E}\log(1/\delta)/\epsilon^{2}\right)$. This guarantees that
the embedding is accurate and the output sketch size is linear w.r.t. the
number of vertices in $G_{E}$. Note that although the data can be a
hypergraph, the embeddings considered in $\mathcal{G}^{(\epsilon,\delta)}$ are
defined on graphs.

  * •

To fully contract the tensor network system $({G_{D},G_{E}})$, this embedding
yields a contraction tree with the optimal asymptotic contraction cost under a
fixed data contraction tree. The data contraction tree constraint is useful
for application of sketching to alternating optimization algorithms, as we
will discuss in Section 5. This can be written as an optimization problem
below,

$\displaystyle\min_{G_{E}}\min_{T_{B}}C_{a}(T_{B}({G_{D},G_{E}})),\quad\text{s.t.
}G_{E}\in\mathcal{G}^{(\epsilon,\delta)},\quad T_{0}({G_{D}})\subset
T_{B}({G_{D},G_{E}}),$ (4.1)

where $T_{B}(G_{D},G_{E})$ denotes a contraction tree of the tensor network
$(G_{D},G_{E})$, $C_{a}$ denotes the asymptotic computational cost, and
$T_{0}({G_{D}})\subset T_{B}({G_{D},G_{E}})$ means the contraction tree
$T_{B}$ is constrained on $T_{0}$ (detailed definition in Definition 1).

######  Definition 1 (Constrained contraction tree).

Given $G=(G_{E},G_{D})$ and a contraction tree $T_{0}$ of $G_{D}$, the
contraction tree $T_{B}$ for $G$ is constrained on $T_{0}$ if for each
contraction $(A,B)\in T_{0}$, there must exist one contraction
$(\hat{A},\hat{B})\in T_{B}$, such that $\hat{A}\cap V_{D}=A$ and $\hat{B}\cap
V_{D}=B$.

#### Algorithm

We propose an algorithm to sketch tensor network data with an embedding
containing two parts, a Kronecker product embedding and an embedding
containing a binary tree of small tensor networks. The embedding is
illustrated in Fig. 4. The Kronecker product embedding consists of $N$
Gaussian random matrices and is used to reduce the weight of each edge in
$\bar{E}$, the set of edges to be sketched. The binary tree structured
embedding consists of $N-1$ small tensor networks, each represented by one
binary tree vertex. Each small tensor network is used to effectively sketch
the contraction of pairs of tensors adjacent to edges in $\bar{E}$. The
embedding with a binary tree structure may not be a binary tree tensor
network, since each tree vertex is not restricted to represent one tensor. The
binary tree is chosen to be consistent with the dimension tree of the data
contraction tree $T_{0}$, which is a directed binary tree showing the way
edges in $\bar{E}$ are merged onto the same tensor in $T_{0}$. The detailed
definition of dimension tree is in Section B.1.

We first introduce some notation before presenting the algorithm. Consider a
given input data tensor network $G_{D}=(V_{D},E_{D},w)$ and its given data
contraction tree, $T_{0}$. Below we let
$\bar{E}=\\{e_{1},e_{2},\ldots,e_{N}\\}$ to denote the edges to be sketched.
Let $N_{D}=|V_{D}|$. Based on the definition we have $N\leq N_{D}$ and $T_{0}$
contains $N_{D}-1$ contractions. Let one contraction path of $T_{0}$, which is
a topological sort of the contractions in $T_{0}$, be expressed as

$\left\\{(U_{1},V_{1}),\ldots,(U_{N_{D}-1},V_{N_{D}-1})\right\\}.$ (4.2)

The $N_{D}-1$ contractions can be categorized into $N+2$ sets,
$\mathcal{D}(e_{1}),\ldots,\mathcal{D}(e_{N}),\mathcal{S},\mathcal{I}$, as
follows,

  * •

Consider contractions $(U_{i},V_{i})$ such that both $U_{i}$ and $V_{i}$ are
adjacent to edges in $\bar{E}$. $\mathcal{S}$ contains all contractions with
this property.

  * •

Consider contractions $(U_{i},V_{i})$ such that the only edge in $\bar{E}$
that is adjacent to the contraction output is $e_{j}$, $\bar{E}(U_{i}\cup
V_{i})=\\{e_{j}\\}$. We let $\mathcal{D}(e_{j})$ contains contractions with
this property. When $\mathcal{D}(e_{j})$ is not empty, we let $X(e_{j})\subset
V$ represent the sub network contracted by $\mathcal{D}(e_{j})$. When
$\mathcal{D}(e_{j})$ is empty, we let $X(e_{j})=v_{j}$, where $v_{j}$ is the
vertex in the data graph adjacent to $e_{j}$.

  * •

The remaining contractions in the contraction tree include $(U_{i},V_{i})$
such that both $U_{i}$ and $V_{i}$ are not adjacent to $\bar{E}$, and
contractions where $U_{i}$ or $V_{i}$ is adjacent to at least two edges in
$\bar{E}$, and the other one is not adjacent to any edge in $\bar{E}$. We let
$\mathcal{I}$ contain these contractions.

Algorithm 1 Sketching algorithm

1: Input:  Input data tensor network $G_{D}$, data contraction tree $T_{0}$
expressed in (4.2)

2: for each $e_{i}\in\bar{E}$ do

3: // Sketch with Kronecker product embedding

4: $W\leftarrow\text{contract and sketch }X(e_{j})$

5: Replace the contraction output of $X(e_{j})$ by $W$ in $T_{0}$

6: end for

7: for each contraction $(U_{i},V_{i})$ in $\mathcal{S}\cup\mathcal{I}$ do

8: if $i\in\mathcal{S}$ then

9: // Sketch with binary tree embedding

10: $W_{i}\leftarrow\text{contract and sketch }(U_{i},V_{i})$ (detailed in
Section C.1)

11: else

12: $W_{i}\leftarrow\text{contract}(U_{i},V_{i})$

13: end if

14: Replace the contraction output of $(U_{i},V_{i})$ by $W_{i}$ in $T_{0}$

15: end for

16: return $W_{N_{D}-1}$

The sketching algorithm is shown in Algorithm 1, and the details are as
follows,

  * •

One matrix in the Kronecker product embedding is used to sketch the sub data
network $X(e_{j})$, which guarantees that two sketch dimensions to be merged
onto one tensor will both have size $\Theta(N\log(1/\delta)/\epsilon^{2})$.
For the case where $\mathcal{D}(e_{j})=\emptyset$, we directly sketch
$X(e_{j})=v_{j}$ using an embedding matrix. For the case where
$\mathcal{D}(e_{j})\neq\emptyset$, we select $k(e_{j})\in\mathcal{D}(e_{j})$
and apply the sketching matrix during the contraction
$(U_{k(e_{j})},V_{k(e_{j})})$. The value of $k(e_{j})$ is selected via an
exhaustive search over all $|\mathcal{D}(e_{j})|$ contractions, so that
sketching $X(e_{j})$ has the lowest asymptotic cost.

  * •

One small tensor network (denoted as $Z_{i}$) represented by a binary tree
vertex in the binary tree structured embedding is used to sketch the
contraction $(U_{i},V_{i})$ when $i\in\mathcal{S}$, which means that both
$U_{i}$ and $V_{i}$ are adjacent to $\bar{E}$. Let $\hat{U}_{i},\hat{V}_{i}$
denote the sketched $U_{i}$ and $V_{i}$ formed in previous contractions in the
sketching contraction tree $T_{B}$, such that $\hat{U}_{i}\cap V_{D}=U_{i}$
and $\hat{V}_{i}\cap V_{D}=V_{i}$, the structure of $Z_{i}$ is determined so
that the asymptotic cost to sketch $(\hat{U}_{i},\hat{V}_{i})$ is minimized
under the constraint that $Z_{i}$ is in
$\mathcal{G}^{(\epsilon/\sqrt{N},\delta)}$, so that it satisfies the
$(\epsilon/\sqrt{N},\delta)$-accurate sufficient condition and only has one
output dimension. In Section C.1, we provide an algorithm to construct $Z_{i}$
containing 2 tensors, so that the output sketch size of $Z_{i}$ is
$\Theta(N\log(1/\delta)/\epsilon^{2})$.

#### Analysis of the algorithm

The embedding constructed during Algorithm 1 contains $\Theta(N)$ vertices,
and the output sketch size is $m=\Theta(N\log(1/\delta)/\epsilon^{2})$.
Therefore, the sketching result both has low sketch size and is
$(\epsilon,\delta)$-accurate. Below we discuss the optimality of Algorithm 1
in terms of the sketching asymptotic computational cost. We first discuss the
case when each vertex in the data tensor network is adjacent to an edge in
$\bar{E}$.

######  Theorem 4.1.

For data tensor networks where each vertex is adjacent to an edge in
$\bar{E}$, the asymptotic cost of Algorithm 1 is optimal w.r.t. the
optimization problem in (4.1).

We show the detailed proof of the theorem above in Section D.1. Therefore,
Algorithm 1 is efficient in sketching multiple widely used tensor network
data, including tensor train, Kronecker product, and Khatri-Rao product. As we
will discuss in Section 5, Algorithm 1 can be used to design efficient
sketching-based ALS algorithm for CP tensor decomposition.

Note that the embedding in Algorithm 1 may not be a tree embedding. As we will
show in Section 6, for cases including sketching a Kronecker product data,
Algorithm 1 is more efficient than sketching with tree embeddings. On the
other hand, for some data tensor networks, sketching with a tree embedding
also yields the optimal asymptotic cost, which we will show in Theorem 4.3.

For general input data where each data vertex may not adjacent to an edge in
$\bar{E}$, Algorithm 1 may not yield the optimal sketching asymptotic cost,
but is within a factor of at most $O(\sqrt{m})$ from the cost lower bound.
Below we show the theorem, and the detailed proof is in Section D.2.

######  Theorem 4.2.

For any data tensor network $G_{D}$, the asymptotic cost of Algorithm 1
(denoted as $c$) satisfy $c=O\left(\sqrt{m}\cdot c_{\text{opt}}\right)$, where
$c_{\text{opt}}$ is the optimal asymptotic computational cost for the
optimization problem (4.1) and $m=\Theta(N\log(1/\delta)/\epsilon^{2})$. When
$G_{D}$ is a graph, $c=O\left(m^{0.375}\cdot c_{\text{opt}}\right)$.

#### Efficiency of tree tensor network embedding

We discuss cases where tree tensor network embeddings can be optimal w.r.t.
the optimization problem in (4.1). Tree embeddings, in particular the tensor
train embedding, have been widely discussed and used in prior work [38, 10,
4]. We design an algorithm to sketch with tree embeddings. The algorithm is
similar to Algorithm 1, and the only difference is that for each contraction
$(U_{i},V_{i})$ with $i\in\mathcal{S}$, such that both $U_{i}$ and $V_{i}$ are
adjacent to edges in $\bar{E}$, we sketch it with one tensor rather than a
small network. Below, we present the optimality of the algorithm in terms of
sketching asymptotic cost.

######  Theorem 4.3.

Consider $G_{D}$ with each vertex adjacent to an edge to be sketched and its
given contraction tree $T_{0}$. If each contraction in $T_{0}$ contracts
dimensions with size being at least the sketch size, then sketching with tree
embedding would yield the optimal asymptotic cost for (4.1).

We present the proof of Theorem 4.3 in Appendix E. As we will show in Section
6, for tensor network data with relatively large contracted dimension sizes
such that the condition in Theorem 4.3 is satisfied, sketching with tree
embedding yields a similar performance as Algorithm 1. However, for data where
the condition in Theorem 4.3 is not satisfied, Algorithm 1 is more efficient.
For example, when the data is a vector with a Kronecker product structure,
sketching with Algorithm 1 yields a cost of
$\Theta(\sum_{j=1}^{N}s_{j}m+Nm^{2.5})$ and sketching with a tree embedding
yields a cost of $\Theta(\sum_{j=1}^{N}s_{j}m+Nm^{3})$. We present the
detailed analysis in Section C.2 and Appendix E.

##  5 Applications

#### Alternating least squares for CP decomposition

On top of Algorithm 1, we propose a new sketching-based ALS algorithm for CP
tensor decomposition. Throughout analysis we assume the input tensor is dense,
and has order $N$ and size $s\times\cdots\times s$, and the CP rank is $R$.
The goal of CP decomposition is to minimize the objective function,
$f({A}_{1},\ldots,{A}_{N})=\left\|{\mathcal{X}}-\sum_{r=1}^{R}{A}_{1}(:,r)\circ\cdots\circ{A}_{N}(:,r)\right\|_{F}^{2},$
where ${A}_{i}\in\mathbb{R}^{s\times R}$ for $i\in[N]$ are called factor
matrices, and ${\mathcal{X}}$ denotes the input tensor. In each iteration of
ALS, $N$ subproblems are solved sequentially, and the $i$th subproblem can be
formulated as
${A}_{i}=\arg\min_{{A}}\left\|L_{i}{A}{}^{T}-R_{i}\right\|^{2}_{F},$ where
$L_{i}={A}_{1}\odot\cdots\odot{A}_{i-1}\odot{A}_{i+1}\odot\cdots\odot{A}_{N}$
consists of a chain of Khatri-Rao products, and $R_{i}={X}_{(i)}^{T}$ is the
transpose of $i$th matricization of ${\mathcal{X}}$.

Multiple sketching-based randomized algorithms are proposed to accelerate each
subproblem in CP-ALS [5, 23, 28]. The sketched problem can be formulated as
${A}_{i}=\underset{{A}}{\arg\\!\min}\left\|S_{i}L_{i}A^{T}-S_{i}R_{i}\right\|_{F}^{2},$
where $S_{i}$ is an embedding. The goal is to design $S_{i}$ such that the
sketched subproblem can be solved efficiently and accurately. In Table 1, we
summarize two state-of-the-art sketching methods for CP-ALS. Larsen and Kolda
[23] propose a method that sketches the subproblem based on (approximate)
leverage score sampling (LSS), but both the per-iteration computational cost
and the sketch size sufficient for $(\epsilon,\delta)$-accurate solution has
an exponential dependence on $N$, which is inefficient for decomposing high
order tensors. Malik [28] proposes a method called recursive leverage score
sampling for CP-ALS, where the embedding contains two parts,
$S_{i}=S_{i,1}S_{i,2}$, and $S_{i,2}$ is an embedding with a binary tree
structure proposed in [1] with sketch size $\Theta(NR^{2}/\delta)$, and
$S_{i,1}$ performs approximate leverage score sampling on $S_{i,2}L_{i}$ with
sketch size $\tilde{\Theta}(NR/\epsilon^{2})$. This sketching method has a
better dependence on $R$ in terms of per-iteration cost. For both algorithms,
the preparation cost shown in Table 1 denotes the cost to go over all elements
in the tensor and initialize factor matrices using randomized range finder. As
is shown in [23, 25], randomized range finder based initialization is critical
for achieving accurate CP decomposition with sampling-based sketched ALS.

CP-ALS algorithm | Per-iteration cost |  Sketch size ($m$) | Prep cost
---|---|---|---
Standard ALS | $\Theta(s^{N}R)$ | / | /
LSS [23] | $\tilde{\Theta}(N(R^{N+1}+sR^{N})/\epsilon^{2})$ | $\tilde{\Theta}(R^{N-1}/\epsilon^{2})$ | $\Theta(s^{N})$
Recursive LSS [28] | $\tilde{\Theta}(N^{2}(R^{4}+NsR^{3}/\epsilon)/\delta)$ |  $\Theta(NR^{2}/\delta)$ and $\tilde{\Theta}(R/(\epsilon\delta))$ | $\Theta(s^{N})$
Algorithm 1 | $\tilde{\Theta}(N^{2}(N^{1.5}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}R^{3.5}}/\epsilon^{3}+s{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}R^{2}})/\epsilon^{2})$ | $\tilde{\Theta}(NR/\epsilon^{2})$ | $\Theta(s^{N}m)$
Table 1: Comparison of asymptotic algorithmic complexity between standard CP-
ALS, CP-ALS with leverage score sampling (LSS), CP-ALS with recursive leverage
score sampling (recursive LSS), and sketching CP-ALS with Algorithm 1. The
third column shows the sketch size sufficient for the sketched linear least
squares to be $(1+\epsilon)$-accurate with probability at least $1-\delta$. By
using $\tilde{\Theta}$, we neglect logarithmic factors, including $\log(R)$
and $\log(1/\delta)$.

We propose a new sketching algorithm for CP-ALS based on Algorithm 1. Each
$S_{i}$ is generated on top of the data tensor network $L_{i}$ and its given
data contraction tree $T_{i}$, with the sketch size being
$m=\Theta(NR\log(1/\delta)/\epsilon^{2})=\tilde{\Theta}(NR/\epsilon^{2})$. The
contraction trees $T_{i}$ for $i\in[N]$ are chosen in a fixed alternating
order, such that the resulting embeddings $S_{i}$ for $i\in[N]$ have common
parts and allow reusing contraction intermediates. We leave the detailed
analysis in Section F.2.

The ALS per-iteration cost is
$\Theta(N(m^{2.5}R+smR))=\tilde{\Theta}(N^{2}(N^{1.5}R^{3.5}/\epsilon^{3}+sR^{2})/\epsilon^{2})$.
We present the detailed sketching algorithm and its cost analysis in Section
F.3. When performing a low-rank CP decomposition with $s\gg R^{1.5}$ and
$\epsilon$ is not too small so that $\epsilon=\Theta(1)$222As is shown in
[25], in practice, setting $\epsilon$ to be 0.1-0.2 will result in accurate
sketched least squares with relative residual norm error less than 0.05., the
per-iteration cost is dominated by the term
$\tilde{\Theta}(N^{2}sR^{2}/\epsilon^{2})$, which is
$\Theta(NR\epsilon/\delta)=\Omega(NR)$ times better than the per-iteration
cost of the recursive LSS algorithm. For another case of a high-rank CP
decomposition with $R\gg s$, which happens when one wants a high-accuracy CP
decomposition of high order tensors, the per-iteration cost of our sketched
CP-ALS algorithm is dominated by the term
$\tilde{\Theta}(N^{3.5}R^{3.5}/\epsilon^{5})$, and the cost ratio between this
algorithm and the recursive LSS algorithm is
$\tilde{\Theta}(N^{1.5}\delta/(\epsilon^{5}R^{0.5}))$. For this case, our
algorithm is only preferable when $N^{1.5}\delta/\epsilon^{5}$ is not too
large compared to $R^{0.5}$.

Although our proposed sketching algorithm yields better per-iteration
asymptotic cost in multiple regimes compared to existing leverage score based
sketching algorithms, some preparation computations are needed to sketch
right-hand-sides $S_{i}R_{i}$ for $i\in[N]$ before ALS iterations, and this
cost is non-negligible. On the other hand, this algorithm has better
parallelism, since it involves a sequence of matrix multiplications rather
than sampling the matrix. We leave the detailed experimental comparison of
computational efficiency of different sketching techniques for future work.

#### Tensor train rounding

Given a tensor train, tensor train rounding finds a tensor train with a lower
rank to approximate the original representation. Throughout analysis we assume
the tensor train has order $N$ with the output dimension sizes equal $s$, the
tensor train rank is $R<s$, and the goal is to round the rank to $r<R$. The
standard tensor train rounding algorithm [33] consists of a right-to-left
sweep of QR decompositions of the input tensor train (also called
orthogonalization), and another left-to-right truncated singular value
decompositions (SVD) sweep to perform rank reduction. The orthogonalization
step is the bottleneck of the rounding algorithm, and costs $\Theta(NsR^{3})$.
Recently, [10] has introduced a randomized rounding algorithm called
“Randomize-then-Orthogonalize”. Let ${X}$ denote a matricization of the tensor
train data with all except one dimension at the end grouped into the row, the
algorithm first sketches $X$ with a tensor train embedding $S$, then performs
a sequence of truncated SVDs on top of $SX$. The sketch size $m$ of $S$ is $r$
plus some constant, and is assumed to be smaller than $R$. The bottleneck is
to compute $SX$, which costs $\Theta(NsR^{2}m)$.

We can recast the problem as finding an embedding satisfying the linearization
sufficient condition with sketch size $m$, such that the asymptotic cost of
computing $SX$ is optimal given the data contraction tree that contracts the
tensor train from one end to another. Our analysis (detailed in Appendix G)
shows that the sketching cost for the problem is lower bounded by
$\Omega(NsR^{2}m)$, thus the sketching algorithm in [10] attains the
asymptotic cost lower bound and is efficient. Note that sketching with
Algorithm 1 yields the same asymptotic cost, despite using a different
embedding.

##  6 Experiments

We compare our proposed embeddings with embeddings discussed in the reference.
The experiments are used to justify the theoretical analysis in Theorem 4.1
and Theorem 4.3. We test the sketching performance on tensor train inputs and
Kronecker product inputs. Our experiments are carried out on an Intel Core i7
2.9 GHz Quad-Core machine using NumPy [31] routines in Python.

Figure 5: Results for sketching tensor train inputs. Each point denotes the
mean value across 25 experiments, and each error bar shows the 25th-75th
quartiles.

We compare the performance of general tensor network embedding used in
Algorithm 1 (called TN embedding), tree embedding discussed in Theorem 4.3,
and tensor train embedding [10] in sketching tensor train input data in Fig.
5. The input tensor train data has order 6, and the dimension size is 500. We
test the sketching performance under different tensor train ranks. For a given
rank, we randomly generate 25 different inputs, with each element in each
tensor being an i.i.d. variable uniformly distributed within $[0,1]$. For each
input $x$ and a specific embedding structure, we calculate the relative
sketching error twice under different sketch sizes, and record the smallest
sketch size such that both of its relative sketching errors are within 0.2,
$\frac{\|Sx\|_{2}}{\|x\|_{2}}\leq 0.2$. We also calculate the number of
floating point operations (FLOPs) for computing $Sx$ under the smallest sketch
size based on the classical dense matrix multiplication algorithm. As can be
seen, tree and tensor train embeddings are as efficient as TN embedding in
terms of number of FLOPs under relatively high tensor train rank (when rank is
at least 32), but are less efficient than TN embedding when the tensor train
rank is lower than 32. The results are consistent with the theoretical
analysis in Theorem 4.3, which shows that tree embeddings yield the optimal
asymptotic cost when the input tensor train rank is at least the output sketch
size, but the asymptotic cost is not optimal when the tensor train rank is
low.

Figure 6: Results for sketching Kronecker product inputs.

We also compare the performance of TN, tree, tensor train and Khatri-Rao
product embeddings in sketching Kronecker product inputs in Fig. 6. Each
dimension size of the Kronecker product input is fixed to be 1000, and we test
the sketching performance under different tensor orders. For each input $x$
and a specific embedding structure, we record the smallest sketch size such
that its relative sketching error is within 0.1. As can be seen, compared to
Khatri-Rao product embedding, the sketch size of TN, tree and tensor train
embeddings all increase slowly with the increase of tensor order, consistent
with the theoretical analysis that these embeddings have efficient sketch
size. In addition, the cost in FLOPs of TN embedding is smaller than tree and
tensor train embeddings. This is consistent with the analysis in Theorem 4.1
and its following discussions, showing that TN embedding yields the optimal
asymptotic cost for Kronecker product inputs, but tree and tensor train
embeddings do not.

##  7 Conclusions

We provide detailed analysis of general tensor network embeddings. For input
data such that each dimension to be sketched has size greater than the sketch
size, we provide an algorithm to efficiently sketch such data using Gaussian
embeddings that can be linearized into a sequence of sketching matrices and
have low sketch size. Our sketching method is then used to design state-of-
the-art sketching algorithms for CP tensor decomposition and tensor train
rounding. We leave the analysis for more general embeddings for future work,
including those with each tensor representing fast sketching techniques, such
as Countsketch and fast JL transform using fast Fourier transform, and those
containing structures cannot be linearized, such as Khatri-Rao product
embedding. It would also be of interest to look at other tensor-related
applications that could benefit from tensor network embedding, including
tensor ring decomposition and simulation of quantum circuits.

## Acknowledgments

This work is supported by the US NSF OAC via award No. 1942995.

## References

  * [1] T. D. Ahle, M. Kapralov, J. B. Knudsen, R. Pagh, A. Velingker, D. P. Woodruff, and A. Zandieh.  Oblivious sketching of high-degree polynomial kernels.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 141–160. SIAM, 2020.
  * [2] N. Ailon and B. Chazelle.  Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform.  In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 557–563, 2006.
  * [3] A. Anandkumar, R. Ge, D. Hsu, S. M. Kakade, and M. Telgarsky.  Tensor decompositions for learning latent variable models.  Journal of Machine Learning Research, 15:2773–2832, 2014.
  * [4] K. Batselier, W. Yu, L. Daniel, and N. Wong.  Computing low-rank approximations of large-scale matrices with the tensor network randomized SVD.  SIAM Journal on Matrix Analysis and Applications, 39(3):1221–1244, 2018.
  * [5] C. Battaglino, G. Ballard, and T. G. Kolda.  A practical randomized CP tensor decomposition.  SIAM Journal on Matrix Analysis and Applications, 39(2):876–901, 2018.
  * [6] G. Beylkin, J. Garcke, and M. J. Mohlenkamp.  Multivariate regression and machine learning with sums of separable functions.  SIAM Journal on Scientific Computing, 31(3):1840–1857, 2009.
  * [7] J. C. Bridgeman and C. T. Chubb.  Hand-waving and interpretive dance: an introductory course on tensor networks.  Journal of Physics A: Mathematical and Theoretical, 50(22):223001, 2017.
  * [8] M. Charikar, K. Chen, and M. Farach-Colton.  Finding frequent items in data streams.  In International Colloquium on Automata, Languages, and Programming, pages 693–703. Springer, 2002.
  * [9] K. Chen and R. Jin.  Tensor-structured sketching for constrained least squares.  SIAM Journal on Matrix Analysis and Applications, 42(4):1703–1731, 2021.
  * [10] H. A. Daas, G. Ballard, P. Cazeaux, E. Hallman, A. Miedlar, M. Pasha, T. W. Reid, and A. K. Saibaba.  Randomized algorithms for rounding in the tensor-train format.  arXiv preprint arXiv:2110.04393, 2021.
  * [11] C. Damm, M. Holzer, and P. McKenzie.  The complexity of tensor calculus.  computational complexity, 11(1-2):54–89, 2002.
  * [12] S. V. Dolgov, B. N. Khoromskij, and I. V. Oseledets.  Fast solution of parabolic problems in the tensor train/quantized tensor train format with initial application to the Fokker–Planck equation.  SIAM Journal on Scientific Computing, 34(6):A3016–A3038, 2012.
  * [13] R. A. Harshman.  Foundations of the PARAFAC procedure: models and conditions for an explanatory multimodal factor analysis.  University of California at Los Angeles Los Angeles, CA, 1970.
  * [14] F. L. Hitchcock.  The expression of a tensor or a polyadic as a sum of products.  Studies in Applied Mathematics, 6(1-4):164–189, 1927.
  * [15] E. G. Hohenstein, R. M. Parrish, and T. J. Martínez.  Tensor hypercontraction density fitting. I. quartic scaling second-and third-order Møller-Plesset perturbation theory.  The Journal of chemical physics, 137(4):044103, 2012.
  * [16] F. Hummel, T. Tsatsoulis, and A. Grüneis.  Low rank factorization of the Coulomb integrals for periodic coupled cluster theory.  The Journal of chemical physics, 146(12):124105, 2017.
  * [17] R. Jin, T. G. Kolda, and R. Ward.  Faster Johnson-Lindenstrauss transforms via Kronecker products.  arXiv preprint arXiv:1909.04801, 2019.
  * [18] D. Kane, R. Meka, and J. Nelson.  Almost optimal explicit Johnson-Lindenstrauss families.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 628–639. Springer, 2011.
  * [19] D. M. Kane and J. Nelson.  Sparser Johnson-Lindenstrauss transforms.  Journal of the ACM (JACM), 61(1):1–23, 2014.
  * [20] S. Klus, P. Gelß, S. Peitz, and C. Schütte.  Tensor-based dynamic mode decomposition.  Nonlinearity, 31(7):3359, 2018.
  * [21] S. Klus, P. Koltai, and C. Schütte.  On the numerical approximation of the Perron-Frobenius and Koopman operator.  arXiv preprint arXiv:1512.05997, 2015.
  * [22] T. G. Kolda and B. W. Bader.  Tensor decompositions and applications.  SIAM review, 51(3):455–500, 2009.
  * [23] B. W. Larsen and T. G. Kolda.  Practical leverage-based sampling for low-rank tensor decomposition.  arXiv preprint arXiv:2006.16438, 2020.
  * [24] L. Ma and E. Solomonik.  Efficient parallel CP decomposition with pairwise perturbation and multi-sweep dimension tree.  In 2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 412–421. IEEE, 2021.
  * [25] L. Ma and E. Solomonik.  Fast and accurate randomized algorithms for low-rank tensor decompositions.  In Advances in Neural Information Processing Systems, 2021.
  * [26] L. Ma and C. Yang.  Low rank approximation in simulations of quantum algorithms.  Journal of Computational Science, page 101561, 2022.
  * [27] L. Ma, J. Ye, and E. Solomonik.  AutoHOOT: Automatic high-order optimization for tensors.  In Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques, pages 125–137, 2020.
  * [28] O. A. Malik.  More efficient sampling for tensor decomposition.  arXiv preprint arXiv:2110.07631, 2021.
  * [29] M. Meister, T. Sarlos, and D. P. Woodruff.  Tight dimensionality reduction for sketching low degree polynomial kernels.  In NeurIPS, pages 9470–9481, 2019.
  * [30] A. Obukhov, M. Rakhuba, A. Liniger, Z. Huang, S. Georgoulis, D. Dai, and L. Van Gool.  Spectral tensor train parameterization of deep learning layers.  In International Conference on Artificial Intelligence and Statistics, pages 3547–3555. PMLR, 2021.
  * [31] T. E. Oliphant.  A guide to NumPy, volume 1.  Trelgol Publishing USA, 2006.
  * [32] R. Orús.  A practical introduction to tensor networks: Matrix product states and projected entangled pair states.  Annals of Physics, 349:117–158, 2014.
  * [33] I. V. Oseledets.  Tensor-train decomposition.  SIAM Journal on Scientific Computing, 33(5):2295–2317, 2011.
  * [34] R. Pagh.  Compressed matrix multiplication.  ACM Transactions on Computation Theory (TOCT), 5(3):1–17, 2013\.
  * [35] N. Pham and R. Pagh.  Fast and scalable polynomial kernels via explicit feature maps.  In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 239–247, 2013.
  * [36] A.-H. Phan, P. Tichavskỳ, and A. Cichocki.  Fast alternating LS algorithms for high order CANDECOMP/PARAFAC tensor factorizations.  IEEE Transactions on Signal Processing, 61(19):4834–4846, 2013\.
  * [37] M. Pilanci and M. J. Wainwright.  Randomized sketches of convex programs with sharp guarantees.  IEEE Transactions on Information Theory, 61(9):5096–5115, 2015\.
  * [38] B. Rakhshan and G. Rabusseau.  Tensorized random projections.  In International Conference on Artificial Intelligence and Statistics, pages 3306–3316. PMLR, 2020.
  * [39] L. Richter, L. Sallandt, and N. Nüsken.  Solving high-dimensional parabolic PDEs using the tensor train format.  In International Conference on Machine Learning, pages 8998–9009. PMLR, 2021.
  * [40] T. Sarlos.  Improved approximation algorithms for large matrices via random projections.  In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 143–152. IEEE, 2006.
  * [41] U. Schollwöck.  The density-matrix renormalization group.  Reviews of modern physics, 77(1):259, 2005.
  * [42] U. Schollwöck.  The density-matrix renormalization group in the age of matrix product states.  Annals of physics, 326(1):96–192, 2011.
  * [43] N. D. Sidiropoulos, L. De Lathauwer, X. Fu, K. Huang, E. E. Papalexakis, and C. Faloutsos.  Tensor decomposition for signal processing and machine learning.  IEEE Transactions on Signal Processing, 65(13):3551–3582, 2017\.
  * [44] E. Stoudenmire and D. J. Schwab.  Supervised learning with tensor networks.  Advances in Neural Information Processing Systems, 29, 2016.
  * [45] L. G. Valiant.  The complexity of computing the permanent.  Theoretical computer science, 8(2):189–201, 1979.
  * [46] G. Vidal.  Efficient classical simulation of slightly entangled quantum computations.  Physical review letters, 91(14):147902, 2003.
  * [47] D. P. Woodruff.  Sketching as a tool for numerical linear algebra.  Theoretical Computer Science, 10(1-2):1–157, 2014.
  * [48] D. P. Woodruff and A. Zandieh.  Leverage score sampling for tensor product matrices in input sparsity time.  arXiv preprint arXiv:2202.04515, 2022.

##  Appendix A Background

###  A.1 Tensor algebra and tensor diagram notation

Our analysis makes use of tensor algebra for tensor operations [22]. Vectors
are denoted with lowercase Roman letters (e.g., ${v}$), matrices are denoted
with uppercase Roman letters (e.g., ${M}$), and tensors are denoted with
calligraphic font (e.g., ${\mathcal{T}}$). An order $N$ tensor corresponds to
an $N$-dimensional array. For an order $N$ tensor
${\mathcal{T}}\in\mathbb{R}^{s_{1}\times\cdots\times s_{N}}$, the size of
$i$th dimension is $s_{i}$. The $i$th column of the matrix ${M}$ is denoted by
${M}(:,i)$, and the $i$th row is denoted by ${M}(i,:)$. Subscripts are used to
label different vectors, matrices and tensors (e.g. ${\mathcal{T}}_{1}$ and
${\mathcal{T}}_{2}$ are unrelated tensors). The Kronecker product of two
vectors/matrices is denoted with $\otimes$, and the outer product of two or
more vectors is denoted with $\circ$. For matrices ${A}\in\mathbb{R}^{m\times
k}$ and ${B}\in\mathbb{R}^{n\times k}$, their Khatri-Rao product results in a
matrix of size $(mn)\times k$ defined by
${A}\odot{B}=[{A}(:,1)\otimes{B}(:,1),\ldots,{A}(:,k)\otimes{B}(:,k)].$
Matricization is the process of unfolding a tensor into a matrix. The
dimension-$n$ matricized version of ${\mathcal{T}}$ is denoted by
${T}_{(n)}\in\mathbb{R}^{s_{n}\times K}$ where $K=\prod_{m=1,m\neq
n}^{N}s_{m}$.

We introduce the graph representation for tensors, which is also called tensor
diagram [7]. A tensor is represented by a vertex with hyperedges adjacent to
it, each corresponding to a tensor dimension. A matrix ${M}$ and an order four
tensor ${\mathcal{T}}$ are represented as follows,

$\displaystyle{M}\implies\begin{array}[]{cc}{\leavevmode\hbox to28.85pt{\vbox
to14.63pt{\pgfpicture\makeatletter\hbox{\hskip 14.42638pt\lower-7.31319pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}
{}{{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{14.22638pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{-14.22638pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{0.8,0.8,0.8}\pgfsys@color@gray@fill{0.8}\pgfsys@invoke{
}{}\pgfsys@moveto{7.11319pt}{0.0pt}\pgfsys@curveto{7.11319pt}{3.92854pt}{3.92854pt}{7.11319pt}{0.0pt}{7.11319pt}\pgfsys@curveto{-3.92854pt}{7.11319pt}{-7.11319pt}{3.92854pt}{-7.11319pt}{0.0pt}\pgfsys@curveto{-7.11319pt}{-3.92854pt}{-3.92854pt}{-7.11319pt}{0.0pt}{-7.11319pt}\pgfsys@curveto{3.92854pt}{-7.11319pt}{7.11319pt}{-3.92854pt}{7.11319pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\end{array}\quad\quad\quad{\mathcal{T}}\implies\begin{array}[]{cc}{\leavevmode\hbox
to14.63pt{\vbox to28.85pt{\pgfpicture\makeatletter\hbox{\hskip
7.31319pt\lower-14.42638pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}
{}{{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{7.11319pt}{-12.32043pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{-7.11319pt}{-12.32043pt}\pgfsys@stroke\pgfsys@invoke{
} {{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{0.8,0.8,0.8}\pgfsys@color@gray@fill{0.8}\pgfsys@invoke{
}{}\pgfsys@moveto{7.11319pt}{0.0pt}\pgfsys@curveto{7.11319pt}{3.92854pt}{3.92854pt}{7.11319pt}{0.0pt}{7.11319pt}\pgfsys@curveto{-3.92854pt}{7.11319pt}{-7.11319pt}{3.92854pt}{-7.11319pt}{0.0pt}\pgfsys@curveto{-7.11319pt}{-3.92854pt}{-3.92854pt}{-7.11319pt}{0.0pt}{-7.11319pt}\pgfsys@curveto{3.92854pt}{-7.11319pt}{7.11319pt}{-3.92854pt}{7.11319pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>
The Kronecker product of two matrices ${A}$ and ${B}$ can be expressed as

$\displaystyle\begin{array}[]{cc}{\leavevmode\hbox to64.42pt{\vbox
to57.31pt{\pgfpicture\makeatletter\hbox{\hskip
17.98297pt\lower-28.65276pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{0.8,0.8,0.8}\pgfsys@color@gray@fill{0.8}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{7.11319pt}{0.0pt}\pgfsys@curveto{7.11319pt}{3.92854pt}{3.92854pt}{7.11319pt}{0.0pt}{7.11319pt}\pgfsys@curveto{-3.92854pt}{7.11319pt}{-7.11319pt}{3.92854pt}{-7.11319pt}{0.0pt}\pgfsys@curveto{-7.11319pt}{-3.92854pt}{-3.92854pt}{-7.11319pt}{0.0pt}{-7.11319pt}\pgfsys@curveto{3.92854pt}{-7.11319pt}{7.11319pt}{-3.92854pt}{7.11319pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.75pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$A$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{}}{{}}{}{{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{7.11319pt}\pgfsys@lineto{0.0pt}{28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{{}}{}{{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{-7.11319pt}\pgfsys@lineto{0.0pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{0.8,0.8,0.8}\pgfsys@color@gray@fill{0.8}\pgfsys@invoke{
}{}\pgfsys@moveto{28.45276pt}{0.0pt}\pgfsys@moveto{35.56595pt}{0.0pt}\pgfsys@curveto{35.56595pt}{3.92854pt}{32.3813pt}{7.11319pt}{28.45276pt}{7.11319pt}\pgfsys@curveto{24.52422pt}{7.11319pt}{21.33957pt}{3.92854pt}{21.33957pt}{0.0pt}\pgfsys@curveto{21.33957pt}{-3.92854pt}{24.52422pt}{-7.11319pt}{28.45276pt}{-7.11319pt}\pgfsys@curveto{32.3813pt}{-7.11319pt}{35.56595pt}{-3.92854pt}{35.56595pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{24.40936pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$B$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{}}{{}}{}{{}}{}
{}{}{}\pgfsys@moveto{28.45276pt}{7.11319pt}\pgfsys@lineto{28.45276pt}{28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{{}}{}{{}}{}
{}{}{}\pgfsys@moveto{28.45276pt}{-7.11319pt}\pgfsys@lineto{28.45276pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{}{{}}{}{{{}} {}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setdash{3.0pt,3.0pt}{0.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{14.22638pt}{0.0pt}\pgfsys@moveto{46.23573pt}{0.0pt}\pgfsys@curveto{46.23573pt}{7.8571pt}{31.90488pt}{14.22638pt}{14.22638pt}{14.22638pt}\pgfsys@curveto{-3.45212pt}{14.22638pt}{-17.78297pt}{7.8571pt}{-17.78297pt}{0.0pt}\pgfsys@curveto{-17.78297pt}{-7.8571pt}{-3.45212pt}{-14.22638pt}{14.22638pt}{-14.22638pt}\pgfsys@curveto{31.90488pt}{-14.22638pt}{46.23573pt}{-7.8571pt}{46.23573pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{14.22638pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\end{array}=\begin{array}[]{cc}{\leavevmode\hbox
to74.74pt{\vbox to57.31pt{\pgfpicture\makeatletter\hbox{\hskip
17.98297pt\lower-28.65276pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{{}}{}{{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{7.11319pt}\pgfsys@lineto{0.0pt}{28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{{}}{}{{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{-7.11319pt}\pgfsys@lineto{0.0pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{{}}{}{{}}{}
{}{}{}\pgfsys@moveto{28.45276pt}{7.11319pt}\pgfsys@lineto{56.55515pt}{4.45094pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{{}}{}{{}}{}
{}{}{}\pgfsys@moveto{28.45276pt}{-7.11319pt}\pgfsys@lineto{28.45276pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{0.8,0.8,0.8}\pgfsys@color@gray@fill{0.8}\pgfsys@invoke{
}{}\pgfsys@moveto{14.22638pt}{0.0pt}\pgfsys@moveto{46.23573pt}{0.0pt}\pgfsys@curveto{46.23573pt}{7.8571pt}{31.90488pt}{14.22638pt}{14.22638pt}{14.22638pt}\pgfsys@curveto{-3.45212pt}{14.22638pt}{-17.78297pt}{7.8571pt}{-17.78297pt}{0.0pt}\pgfsys@curveto{-17.78297pt}{-7.8571pt}{-3.45212pt}{-14.22638pt}{14.22638pt}{-14.22638pt}\pgfsys@curveto{31.90488pt}{-14.22638pt}{46.23573pt}{-7.8571pt}{46.23573pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{14.22638pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.3219pt}{-3.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$A\otimes B$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>
Connecting two edges means two tensor dimensions are contracted or summed
over. One example is shown in Fig. 7.

Figure 7: An example of tensor diagram notation.

###  A.2 Background on sketching

In this section, we introduce definitions for sketching used throughout the
paper.

######  Definition 2 (Gaussian embedding).

A matrix ${S}=\frac{1}{\sqrt{m}}{M}\in\mathbb{R}^{m\times n}$ is a Gaussian
embedding if each element of ${M}$ is a normalized Gaussian random variable,
${M}(i,j)\sim N(0,1)$.

One key property we would like the tensor network embedding to satisfy is the
($\epsilon$, $\delta$)-accurate property. To achieve this, one central
property each tensor in the tensor network embedding needs to satisfy is the
Johnson-Lindenstrauss (JL) moment property. The JL moment property captures a
bound on the moments of the difference between the vector Euclidean norm and
the norm after sketching. We introduce both definitions below.

######  Definition 3 (($\epsilon$, $\delta$)-accurate embedding).

A random matrix $S\in\mathbb{R}^{m\times n}$ has the
$(\epsilon,\delta)$-accurate embedding property if for every
${x}\in\mathbb{R}^{n}$ with $\|{x}\|_{2}=1$,

$\operatorname*{{\text{Pr}}}_{{S}}\left(\left|\left\|{Sx}\right\|_{2}^{2}-1\right|>\epsilon\right)<\delta.$

######  Definition 4 (($\epsilon$, $\delta$, $p$)-JL moment [18, 19]).

A random matrix $S\in\mathbb{R}^{m\times n}$ has the $(\epsilon,\delta,p)$-JL
moment property if for every ${x}\in\mathbb{R}^{n}$ with $\|{x}\|_{2}=1$,

$\operatorname*{{\mathbb{E}}}_{{S}}\left|\left\|{Sx}\right\|_{2}^{2}-1\right|^{p}<\epsilon^{p}\delta\quad\text{and}\quad\operatorname*{{\mathbb{E}}}\left[\left\|{Sx}\right\|_{2}^{2}\right]=1.$

######  Definition 5 (Strong ($\epsilon$, $\delta$)-JL moment [18, 1]).

A random matrix $S\in\mathbb{R}^{m\times n}$ has the strong
$(\epsilon,\delta)$-JL moment property if for every ${x}\in\mathbb{R}^{n}$
with $\|{x}\|_{2}=1$, and every integer $p\in[2,\log(1/\delta)]$,

$\operatorname*{{\mathbb{E}}}_{{S}}\left|\left\|{Sx}\right\|_{2}^{2}-1\right|^{p}<\left(\frac{\epsilon}{e}\right)^{p}\left(\frac{p}{\log(1/\delta)}\right)^{p/2}$
(A.1)

and $\operatorname*{{\mathbb{E}}}\left[\left\|{Sx}\right\|_{2}^{2}\right]=1$.

Note that the strong $(\epsilon,\delta)$-JL moment property directly reveals
the $(\epsilon,\delta,\log(1/\delta))$-JL moment property, since letting
$p=\log(1/\delta)$, (A.1) becomes

$\operatorname*{{\mathbb{E}}}_{{S}}\left|\left\|{Sx}\right\|_{2}^{2}-1\right|^{\log(1/\delta)}<\left(\frac{\epsilon}{e}\right)^{\log(1/\delta)}=\epsilon^{p}\delta.$

Both the strong ($\epsilon$, $\delta$)-JL moment property and the ($\epsilon$,
$\delta$, $p$)-JL moment property directly imply ($\epsilon$,
$\delta$)-accurate embedding via Markov’s inequality,

$\operatorname*{{\text{Pr}}}_{{S}}\left(\left|\left\|{Sx}\right\|_{2}^{2}-1\right|>\epsilon\right)<\frac{\operatorname*{{\mathbb{E}}}\left|\left\|{Sx}\right\|_{2}^{2}-1\right|^{p}}{\epsilon^{p}}<\delta.$

The lemmas below show that Gaussian embeddings can be used to construct
embeddings with the JL moment property.

######  Lemma A.1 (Strong JL moment of Gaussian embeddings [18]).

Gaussian embeddings with $m=\Omega(\log(1/\delta)/\epsilon^{2})$ satisfy the
$(\epsilon,\delta)$-strong JL moment property.

Below we review the composition rules of JL moment properties introduced in
[1], which are used to prove the ($\epsilon,\delta$)-accurate sufficient
condition in Theorem 3.1.

######  Lemma A.2 (JL moment with Kronecker product).

If a matrix ${S}$ has the $(\epsilon,\delta,p)$-JL moment property, then the
matrix ${M}={I}_{i}\otimes{S}\otimes{I}_{j}$ also has the
$(\epsilon,\delta,p)$-JL moment property for identity matrices ${I}_{i}$ and
${I}_{j}$ with any size. This relation also holds for the strong
$(\epsilon,\delta)$-JL moment property.

######  Lemma A.3 (Strong JL moment with matrix product).

There exists a universal constant $L$, such that for any constants
$\epsilon,\delta\in[0,1]$ and any integer $k$, if
${M}_{1}\in\mathbb{R}^{d_{2}\times
d_{1}},\cdots,{M}_{k}\in\mathbb{R}^{d_{k+1}\times d_{k}}$ are independent
random matrices, each having the strong
$\left(\frac{\epsilon}{L\sqrt{k}},\delta\right)$-JL moment property, then the
product matrix ${M}={M}_{k}\cdots{M}_{1}$ satisfies the strong
$(\epsilon,\delta)$-JL moment property.

##  Appendix B Definitions and basic properties of tensor network embedding

In this section, we introduce definitions and basic properties of tensor
network embeddings. These properties will be used in Appendix C and Appendix D
for detailed computational cost analysis. The notation defined in the main
text is summarized in Table 2, which is also used in later analysis.

Notations | Meanings
---|---
$S,S_{i}$ | Embedding matrix
$m$ | Sketch size
$G_{E}=(V_{E},E_{E},w)$ | Embedding tensor network
$G_{D}=(V_{D},E_{D},w)$ | Input data tensor network
$\bar{E}=\\{e_{1},\ldots,e_{N}\\}$ | Set of edges to be sketched
$s_{i}$ | Size of $e_{i}$ in $\bar{E}$
$T_{0}$ | Given data contraction tree
$\mathcal{D}(e_{1}),\ldots,\mathcal{D}(e_{N}),\mathcal{S},\mathcal{I}$ | Subsets of contractions in $T_{0}$
$X(e_{i})$ | Sub network contracted by $\mathcal{D}(e_{i})$
Table 2: Notations used throughout the paper.

###  B.1 Graph notation for tensor network and tensor contraction

We use undirected hypergraphs to represent tensor networks. For a given
hypergraph $G=(V,E,w)$, $V$ represents the vertex set, $E$ represents the set
of hyperedges, and $w$ is a function such that $w(e)$ is the natural logarithm
of the tensor dimension size represented by the hyperedge $e\in E$. We use
$E(u,v)$ to denote the set of hyperedges adjacent to both $u$ and $v$, which
includes the edge $(u,v)$ and hyperedges adjacent to $u,v$. We use $E(A,B)$ to
denote the set of hyperedges connecting two subsets $A,B$ of $V$ with $A\cap
B=\emptyset$. We use $E(A,*)$ to denote all uncontracted edges only adjacent
to $A$, $E(A,*)=\\{(u)\in E:u\in A\\}$. we illustrate $E(A,B),E(A,*)$ in Fig.
8. For any set $A\subseteq V$, we let

$\displaystyle E(A)$ $\displaystyle=E(A,V\setminus A)\cup E(A,*).$ (B.1)

A tensor network implicitly represents a tensor with a set of (small) tensors
and a specific contraction pattern. We use $G[A]=(A,E_{A},w)$ to denote a sub
tensor network defined on $A\subseteq V$, where $E_{A}$ contains all
hyperedges in $E$ adjacent to any $v\in A$.

Figure 8: An example of $E(A,*)$ and $E(A,B)$, where both $A,B$ are subset of
vertices.

Our analysis also use directed graphs to represent tensor network
linearizations. We use $E(u,v)$ to denote the edge from $u$ to $v$, and
similarly use $E(A,B)$ to denote the set of edges from $A$ to $B$.

When representing the contraction tree, we use $(v_{1},v_{2})$ to denote the
contraction of $v_{1},v_{2}$. This notation is also used to represent multiple
contractions. For example, we use $(((v_{1},v_{4}),(v_{2},v_{5})),v_{3})$ to
represent the contraction tree shown in Fig. 9. The computational cost of a
contraction tree is the summation of each contraction’s cost. In the
discussion throughout the paper, we assume that all tensors in the network are
dense. Therefore, the contraction of two general dense tensors ${\mathcal{A}}$
and ${\mathcal{B}}$, represented as vertices $v_{a}$ and $v_{b}$ in
$G=(V,E,w)$, can be cast as a matrix multiplication, and the overall
asymptotic cost is

$\Theta\left(\exp\left(w(E(v_{a}))+w(E(v_{b}))-w(E(v_{a},v_{b}))\right)\right)$

with classical matrix multiplication algorithms. In general, contracting
tensor networks with arbitrary structure is #P-hard [11, 45].

(a)

(b)

(c)

Figure 9: Example of a tensor network, its contraction tree and the
corresponding dimension tree.

For a given data $G_{D}$ and its given contraction tree $T_{0}$, its dimension
tree is a directed binary tree showing the way edges in $\bar{E}$ are merged
onto the same tensor. Each vertex in the dimension tree is a subset
$E^{\prime}\subseteq\bar{E}$, and for any two vertices
$E_{1}^{\prime},E_{2}^{\prime}$ of the dimension tree with the same parent,
there is a contraction in $T_{0}$ such that the two input tensors are incident
to $E_{1}^{\prime},E_{2}^{\prime}$, respectively. One example is shown in Fig.
9.

###  B.2 Definitions used in the analysis of tensor network embedding

In this section, we introduce definitions that will be used in later analysis.
For a (hyper)graph $G=(V,E,w)$ and two subsets of $V$ denoted as $A,B$, we
define ${\mathsf{cut}}_{G}(A,B)=\sum_{e\in E(A,B)}w(e)$. Similarly, we define
${\mathsf{cut}}_{G}(A,*)=\sum_{e\in E(A,*)}w(e)$, and define
${\mathsf{cut}}_{G}(A)=\sum_{e\in E(A)}w(e)$, where $E(A)$ is expressed in
(B.1). When $G$ is a directed hypergraph, ${\mathsf{cut}}_{G}(A,B)$ denotes
the sum of the weights of edges from $A$ to $B$. When $G$ is an undirected
graph, ${\mathsf{cut}}_{G}(A,B)$ denotes the sum of the weights of hyperedges
connecting $A$ and $B$.

For two tensors represented by two subsets $A,B\subset V$ and $A\cap
B=\emptyset$, the logarithm of the contraction cost between a tensor
represented by $A$ and a tensor represented by $B$, $(A,B)$, is

${\mathsf{cost}}_{G}(A,B)={\mathsf{cut}}_{G}(A)+{\mathsf{cut}}_{G}(B)-{\mathsf{cut}}_{G}(A,B).$

Note that the function ${\mathsf{cost}}$ is only defined on undirected
hypergraphs.

Consider a given input data $G_{D}=(V_{D},E_{D},w)$ and an embedding
$G_{E}=(V_{E},E_{E},w)$. Below we let $V=V_{E}\cup V_{D}$, $E=E_{E}\cup
E_{D}$, and $G=(V,E,w)$ denote the hypergraph including both the embedding and
the input data. We use $L=(V,E_{E},w)$ to denote the graph including $V$ and
all edges in the embedding, and use $R=(V,E\setminus E_{E},w)$. Note that in
this work we focus on the case where $L$ is a graph, and $R$ can be a general
hypergraph. We illustrate $G,G_{D},G_{E},L,R$ in Fig. 10. For any $A,B\subset
V$ and $A\cap B=\emptyset$, we have

${\mathsf{cut}}_{G}(A)={\mathsf{cut}}_{L}(A)+{\mathsf{cut}}_{R}(A),$ (B.2)

and

${\mathsf{cut}}_{G}(A,B)={\mathsf{cut}}_{L}(A,B)+{\mathsf{cut}}_{R}(A,B).$
(B.3)

Based on (B.2) and (B.3), we have

${\mathsf{cost}}_{G}(A,B)={\mathsf{cost}}_{L}(A,B)+{\mathsf{cost}}_{R}(A,B).$

Our analysis of tensor network embedding is based on the linearization of the
tensor network graph. Linearization casts an undirected graph into a directed
acyclic graph (DAG). We define linearization formally below, then specify
linearizations of the data and embedding graphs that our analysis considers.

######  Definition 6 (Linearization DAG).

A linearization of the undirected graph $G=(V,E,w)$ is defined by the DAG
$G^{\prime}=(V,E^{\prime},w)$ induced by a given choice of vertex ordering in
$V$. For each contracted edge in $E$, $E^{\prime}$ contains an same-weight
edge directing towards the higher indexed vertex. For each uncontracted edge
in $E$, $E^{\prime}$ contains an edge with the same weight that is directed
outward from the vertex it is adjacent to.

Based on Definition 6, we define the sketching linearization DAG,
$G_{S}=(V,E_{S},w)$, as a DAG defined on top of the graph $L=(V,E_{E},w)$,
which includes all vertices in both the embedding and the data and all
embedding edges. For a given vertex ordering of embedding vertices, $G_{S}$ is
the linearization of $L$ based on the ordering with all data vertices being
ordered ahead of embedding vertices.

As discussed in Section 3, for a given sketching linearization, the sketching
accuracy of each tensor ${\mathcal{A}}_{i}$ at $v_{i}$ is dependent on the row
size of its matricization ${A}_{i}$, which is the weighted size of the edge
set adjacent to $v_{i}$ containing all uncontracted edges and contracted edges
also adjacent to $v_{j}$ with $j>i$, which is called effective sketch
dimension of $v_{i}$ throughout the paper. Based on the definition, when $v\in
V_{E}$, ${\mathsf{cut}}_{G_{S}}(v)$ equals the effective sketch dimension size
of $v$. When $v\in V_{D}$, ${\mathsf{cut}}_{G_{S}}(v)$ represents the size of
the sketch dimension adjacent to $v$. We look at embeddings $G_{E}$ not only
satisfying the ($\epsilon,\delta$)-accurate sufficient condition in Theorem
3.1, but also only have one output sketch dimension ($|E_{1}|=1$) with the
output sketch size $m=\Theta\left(N_{E}\log(1/\delta)/\epsilon^{2}\right)$.
For each one of these embeddings, there must exist a linearization $G_{S}$
such that for all $v\in V_{E}$, we have

${\mathsf{cut}}_{G_{S}}(v)=\Omega\left(\log(m)\right).$ (B.4)

(a) $G=(V,E_{E}\cup E_{D},w)$

(b) $G_{E}=(V_{E},E_{E},w)$

(c) $G_{D}=(V_{D},E_{D},w)$

(d) $L=(V,E_{E},w)$

(e) $R=(V,E\setminus E_{E},w)$

(f) $G_{S}=(V,E_{S},w)$

Figure 10: Illustration of graphs and hypergraphs used throughout the paper.

###  B.3 Properties of tensor network embedding

We now derive properties that are used in the sketching computational cost
analysis. In Lemma B.1, we show relations between cuts in the graph $L$ and
cuts in the graph $G_{S}$. In Lemma B.2, we show relations between costs in
the graph $L$ and cuts in the graph $G_{S}$. Lemma B.2 along with cut lower
bounds (B.4) is used to derive lower bounds for ${\mathsf{cost}}_{L}$ and
${\mathsf{cost}}_{G}$ in Appendix D.

######  Lemma B.1.

Consider an embedding $G_{E}=(V_{E},E_{E},w)$ and a data tensor network
$G_{D}=(V_{D},E_{D},w)$, and a given sketching linearization
$G_{S}=(V,E_{S},w)$, where $V=V_{E}\cup V_{D}$. For any $A,B\subset V$ and
$A\cap B=\emptyset$, the following relations hold,

${\mathsf{cut}}_{L}(A)={\mathsf{cut}}_{G_{S}}(A)+{\mathsf{cut}}_{G_{S}}(V\setminus
A,A),$ (B.5)
${\mathsf{cut}}_{L}(A,B)={\mathsf{cut}}_{G_{S}}(A,B)+{\mathsf{cut}}_{G_{S}}(B,A),$
(B.6) $\displaystyle{\mathsf{cut}}_{G_{S}}(A\cup B)$
$\displaystyle={\mathsf{cut}}_{G_{S}}(A)+{\mathsf{cut}}_{G_{S}}(B)-{\mathsf{cut}}_{G_{S}}(A,B)-{\mathsf{cut}}_{G_{S}}(B,A)$
$\displaystyle={\mathsf{cut}}_{G_{S}}(A)+{\mathsf{cut}}_{G_{S}}(B)-{\mathsf{cut}}_{L}(A,B).$
(B.7)

###### Proof.

(B.5) and (B.6) hold directly based on the definition of the linearization
DAG. For (B.1), based on (B.1), we have

$\displaystyle{\mathsf{cut}}_{G_{S}}(A\cup B)$
$\displaystyle={\mathsf{cut}}_{G_{S}}\left(A\cup B,V\setminus(A\cup
B)\right)+{\mathsf{cut}}_{G_{S}}(A\cup B,*)$
$\displaystyle={\mathsf{cut}}_{G_{S}}\left(A,V\setminus(A\cup
B)\right)+{\mathsf{cut}}_{G_{S}}\left(B,V\setminus(A\cup
B)\right)+{\mathsf{cut}}_{G_{S}}(A\cup B,*)$
$\displaystyle={\mathsf{cut}}_{G_{S}}\left(A,V\setminus
A\right)-{\mathsf{cut}}_{G_{S}}\left(A,B\right)+{\mathsf{cut}}_{G_{S}}\left(B,V\setminus
B\right)-{\mathsf{cut}}_{G_{S}}\left(B,A\right)$
$\displaystyle+{\mathsf{cut}}_{G_{S}}(A,*)+{\mathsf{cut}}_{G_{S}}(B,*)$
$\displaystyle={\mathsf{cut}}_{G_{S}}(A)+{\mathsf{cut}}_{G_{S}}(B)-{\mathsf{cut}}_{G_{S}}(A,B)-{\mathsf{cut}}_{G_{S}}(B,A).$
(B.8)

Note that the second and third equalities in (B.3) hold since $A$ and $B$ are
disjoint sets. This finishes the proof. ∎

######  Lemma B.2.

Consider any data $G_{D}=(V_{D},E_{D},w)$ and embedding
$G_{E}=(V_{E},E_{E},w)$, and a sketching linearization $G_{S}=(V,E_{S},w)$,
where $V=V_{D}\cup V_{E}$. For any two subsets $A,B\in V$ such that $A\cap
B=\emptyset$, the contraction of two tensors that are the contraction outputs
of $A$ and $B$ has a logarithm cost of

${\mathsf{cost}}_{L}(A,B)={\mathsf{cut}}_{G_{S}}(A)+{\mathsf{cut}}_{G_{S}}(B)+{\mathsf{cut}}_{G_{S}}(V\setminus(A\cup
B),A\cup B).$

###### Proof.

Based on Lemma B.1, we have

${\mathsf{cut}}_{L}(A)\overset{\eqref{eq:linearization_p1}}{=}{\mathsf{cut}}_{G_{S}}(V\setminus
A,A)+{\mathsf{cut}}_{G_{S}}(A),$ (B.9)
${\mathsf{cut}}_{L}(B)\overset{\eqref{eq:linearization_p1}}{=}{\mathsf{cut}}_{G_{S}}(V\setminus
B,B)+{\mathsf{cut}}_{G_{S}}(B).$ (B.10)

Based on (B.6), we have

$\displaystyle{\mathsf{cut}}_{G_{S}}(V\setminus
A,A)+{\mathsf{cut}}_{G_{S}}(V\setminus B,B)-{\mathsf{cut}}_{L}(A,B)$
$\displaystyle={\mathsf{cut}}_{G_{S}}(V\setminus
A,A)+{\mathsf{cut}}_{G_{S}}(V\setminus
B,B)-{\mathsf{cut}}_{G_{S}}(A,B)-{\mathsf{cut}}_{G_{S}}(B,A)$
$\displaystyle={\mathsf{cut}}_{G_{S}}(V\setminus(A\cup
B),A)+{\mathsf{cut}}_{G_{S}}(V\setminus(A\cup B),B)$
$\displaystyle={\mathsf{cut}}_{G_{S}}(V\setminus(A\cup B),A\cup B).$ (B.11)

Based on (B.9),(B.10), (B.3), we have

$\displaystyle{\mathsf{cost}}_{L}(A,B)$
$\displaystyle={\mathsf{cut}}_{L}(A)+{\mathsf{cut}}_{L}(B)-{\mathsf{cut}}_{L}(A,B)$
$\displaystyle={\mathsf{cut}}_{G_{S}}(A)+{\mathsf{cut}}_{G_{S}}(B)+{\mathsf{cut}}_{G_{S}}(V\setminus(A\cup
B),A\cup B).$

This finishes the proof. ∎

######  Lemma B.3.

Consider any data $G_{D}=(V_{D},E_{D},w)$ and an embedding
$G_{E}=(V_{E},E_{E},w)$, and a sketching linearization $G_{S}=(V,E_{S},w)$
such that the embedding is $(\epsilon,\delta)$-accurate. Then for any
$U\subseteq V$ such that there exists $v\in U$ and
${\mathsf{cut}}_{G_{S}}(v)\geq\log(m)$, we have
${\mathsf{cut}}_{G_{S}}(U)\geq\log(m)$.

###### Proof.

When $U$ is a subset of the data vertices, $U\subseteq V_{D}$, this holds
directly since

${\mathsf{cut}}_{G_{S}}(U)=\sum_{u\in
U}{\mathsf{cut}}_{G_{S}}(u)\geq{\mathsf{cut}}_{G_{S}}(v)\geq\log(m).$

Next we consider the case where $U\cap V_{E}\neq\emptyset$. Let $A=U\cap
V_{E}$ and $B=U\cap V_{D}$. Based on the definition of DAG, there is no
directed cycle in the subgraph $G_{S}[A]$. Therefore, there exists one vertex
$s\in A$, such that ${\mathsf{cut}}_{G_{S}}(s,A\setminus\\{s\\})=0$. Based on
Lemma B.1, we have

$\displaystyle{\mathsf{cut}}_{G_{S}}(A)$
$\displaystyle\overset{\eqref{eq:linearization_p3}}{=}{\mathsf{cut}}_{G_{S}}(s)+{\mathsf{cut}}_{G_{S}}(A\setminus\\{s\\})-{\mathsf{cut}}_{G_{S}}(s,A\setminus\\{s\\})-{\mathsf{cut}}_{G_{S}}(A\setminus\\{s\\},s)$
$\displaystyle\geq{\mathsf{cut}}_{G_{S}}(s)-{\mathsf{cut}}_{G_{S}}(s,A\setminus\\{s\\})$
$\displaystyle={\mathsf{cut}}_{G_{S}}(s)\overset{\eqref{eq:cut_bound_sufficient}}{\geq}\log(m),$

In addition, we have ${\mathsf{cut}}_{G_{S}}(A,B)=0$ since $A\subseteq V_{E}$
and $B\subseteq V_{D}$. Thus we have

$\displaystyle{\mathsf{cut}}_{G_{S}}(U)={\mathsf{cut}}_{G_{S}}(A\cup B)$
$\displaystyle\overset{\eqref{eq:linearization_p3}}{=}{\mathsf{cut}}_{G_{S}}(A)+{\mathsf{cut}}_{G_{S}}(B)-{\mathsf{cut}}_{G_{S}}(A,B)-{\mathsf{cut}}_{G_{S}}(B,A)$
$\displaystyle={\mathsf{cut}}_{G_{S}}(A)+{\mathsf{cut}}_{G_{S}}(B)-{\mathsf{cut}}_{G_{S}}(B,A)$
$\displaystyle\geq{\mathsf{cut}}_{G_{S}}(A)\geq\log(m).$

This finishes the proof. ∎

##  Appendix C Computationally-efficient sketching algorithm

In this section, we introduce the detail of the computationally-efficient
sketching algorithm in Algorithm 1. Consider a given data tensor network
$G_{D}=(V_{D},E_{D},w)$ and a given data contraction tree, $T_{0}$. Also let
$N_{D}=|V_{D}|$, and let $\bar{E}\subseteq E_{D}$ denote the set of edges to
be sketched, and $N=|\bar{E}|$. Below we let
$\bar{E}=\\{e_{1},e_{2},\ldots,e_{N}\\}$, and let each $e_{i}$ has weight
$\log(s_{i})>\log(m)$. Based on the definition we have $N\leq N_{D}$. Let one
contraction path representing $T_{0}$ be expressed as a sequence of $N_{D}-1$
contractions,

$\left\\{(U_{1},V_{1}),\ldots,(U_{N_{D}-1},V_{N_{D}-1})\right\\}.$ (C.1)

Above we use $(U_{i},V_{i})$ to represent the contraction of two intermediate
tensors represented by two subset of vertices $U_{i},V_{i}\subset V_{D}$.
Below we let

$\displaystyle
a_{i}=\exp\left({\mathsf{cut}}_{R}(U_{i})-{\mathsf{cut}}_{R}(U_{i},V_{i})\right),$
$\displaystyle
c_{i}=\exp\left({\mathsf{cut}}_{R}(V_{i})-{\mathsf{cut}}_{R}(U_{i},V_{i})\right),$
$\displaystyle d_{i}=\exp\left({\mathsf{cut}}_{R}(U_{i}\cup
V_{i})\right)/(a_{i}c_{i}),$ $\displaystyle
b_{i}=\exp\left({\mathsf{cut}}_{R}(U_{i},V_{i})\right)/d_{i}.$ (C.2)

Note that $d_{i}$ represents the size of uncontracted dimensions adjacent to
both $U_{i}$ and $V_{i}$, and $b_{i}$ represents the size of contracted
dimensions between $U_{i}$ and $V_{i}$. We also have
${\mathsf{cost}}_{R}(U_{i},V_{i})=\log(a_{i}b_{i}c_{i}d_{i})$, and
${\mathsf{cut}}_{R}(U_{i}\cup V_{i})=\log(a_{i}c_{i}d_{i})$.
$a_{i},b_{i},c_{i},d_{i}$ are visualized in Fig. 11.

###  C.1 Sketching with the embedding containing a binary tree of small tensor
networks

We now present the details of applying the embedding containing a binary tree
of small tensor networks. In Section 4, we define $\mathcal{S}$ as the set
containing contractions $(U_{i},V_{i})$ such that both $U_{i}$ and $V_{i}$ are
adjacent to edges in $\bar{E}$. For each contraction $i\in\mathcal{S}$, one
small embedding tensor network (denoted as $Z_{i}$) is applied to the
contraction. Let $\hat{U}_{i},\hat{V}_{i}$ denote the sketched $U_{i}$ and
$V_{i}$ formed in previous contractions in the sketching contraction tree
$T_{B}$, such that $\hat{U}_{i}\cap V_{D}=U_{i}$ and $\hat{V}_{i}\cap
V_{D}=V_{i}$. The structure of $Z_{i}$ is determined so that the asymptotic
cost to sketch $(\hat{U}_{i},\hat{V}_{i})$ is minimized, under the constraint
that $Z_{i}$ is $(\epsilon/\sqrt{N},\delta)$-accurate and only has one output
sketch dimension.

The structure of $Z_{i}$ is illustrated in Fig. 11. For the case $a_{i}\leq
c_{i}$, the structure is shown in Fig. 11a, and sketching is performed via the
contraction sequence of contracting $\hat{U}_{i}$ and $v_{1}$ first, then with
$\hat{V}_{i}$, and then with $v_{2}$ (also denoted as a contraction sequence
of $(((\hat{U}_{i},v_{1}),\hat{V}_{i}),v_{2})$). For the case $a_{i}>c_{i}$,
the structure of $Z_{i}$ is shown in Fig. 11b, and the sketching is performed
via the contraction sequence of $(((\hat{V}_{i},v_{2}),\hat{U}_{i}),v_{1})$.
With this algorithm, sketching $(\hat{U}_{i},\hat{V}_{i})$ yields a
computational cost proportional to

$y_{i}=a_{i}b_{i}c_{i}d_{i}m^{2}+m^{2}d_{i}\sqrt{a_{i}b_{i}c_{i}m}\cdot\min(\sqrt{a_{i}},\sqrt{c_{i}}).$
(C.3)

We show in Lemma D.6 that the asymptotic cost lower bound to sketch
$(U_{i},V_{i})$ is also $\Omega(y_{i})$.

(a)

(b)

Figure 11: Illustration of the small network in the binary tree structured
embedding. For each edge $e$, we show the dimension size of that edge
(exponential in $w(e)$).

###  C.2 Computational cost analysis

We provide the computational cost analysis of Algorithm 1 in this section.

######  Theorem C.1.

Algorithm 1 has an asymptotic computational cost of

$\Theta\left(\sum_{j=1}^{N}t(e_{j})+\sum_{i\in\mathcal{S}}y_{i}+\sum_{i\in\mathcal{I}}z_{i}\right),$
(C.4)

where $t(e_{j})$ is the optimal asymptotic cost to sketch the sub tensor
network $X(e_{j})$ (defined in Table 2) with a matrix in the Kronecker product
embedding, $y_{i}$ is expressed in (C.3), and

$z_{i}=a_{i}b_{i}c_{i}d_{i}\cdot\min\left(\exp({\mathsf{cut}}_{G_{S}}(U_{i}\cup
V_{i})),m\right),$ (C.5)

where $a_{i},b_{i},c_{i},d_{i}$ are expressed in (C).

###### Proof.

The terms $\sum_{j\in N}t(e_{j})+\sum_{i\in\mathcal{S}}y_{i}$ can be easily
verified based on the analysis in Section 4 and Section C.1.

Consider the contractions in $\mathcal{I}$, which include $(U_{i},V_{i})$ such
that both $U_{i}$ and $V_{i}$ are not adjacent to $\bar{E}$, and contractions
where $U_{i}$ or $V_{i}$ is adjacent to at least two edges in $\bar{E}$. The
first type of contractions in $\mathcal{I}$ would have a cost of
$\Theta(a_{i}b_{i}c_{i}d_{i})$, and not be affected by previous sketching
steps. For the second type, application of the Kronecker product and binary
tree embeddings to $U_{i}$ and $V_{i}$ would reduce all adjacent edges in
$\bar{E}$ to a single dimension of size $m$. Consequently, the contraction
cost would be $\Theta(a_{i}b_{i}c_{i}d_{i}\cdot m)$. Summarizing both cases
prove the cost in (C.5). The cost in (C.4) follows from combining the terms
$\sum_{j\in N}t(e_{j})+\sum_{i\in\mathcal{S}}y_{i}$ and
$\sum_{i\in\mathcal{I}}z_{i}$. ∎

For the special case where each vertex in the data tensor network is adjacent
to an edge to be sketched, we have $\mathcal{D}(e_{j})=\emptyset$ for all
$j\in[N]$ and $\mathcal{I}=\emptyset$, thus all the contractions are in the
set $\mathcal{S}$. Therefore, sketching each $e_{j}$ has an asymptotic cost of
$\Theta(t(e_{j}))=\Theta(\exp({\mathsf{cut}}_{G}(v_{j}))\cdot m)$, where
$v_{j}$ is the vertex in the data graph adjacent to $e_{j}$, and Theorem C.1
implies that the sketching cost would be

$\displaystyle\Theta\left(\sum_{j=1}^{N}t(e_{j})+\sum_{i\in\mathcal{S}}y_{i}+\sum_{i\in\mathcal{I}}z_{i}\right)=\Theta\left(\sum_{j=1}^{N}\exp({\mathsf{cut}}_{G}(v_{j}))\cdot
m+\sum_{j=1}^{N-1}y_{i}\right).$ (C.6)

As we will show in Theorem D.1, this cost matches the asymptotic cost lower
bound, when the embedding satisfies the $(\epsilon,\delta)$-accurate
sufficient condition and only has one output sketch dimension.

When the data has a Kronecker product structure, we have
${\mathsf{cut}}_{G}(v_{j})=w(e_{j})=\log(s_{j})$, and
$a_{i},b_{i},c_{i},d_{i}=1$ for all $i\in\\{1,\ldots,N-1\\}$ for all
contraction trees. Therefore,

$y_{i}=a_{i}b_{i}c_{i}d_{i}m^{2}+m^{2}d_{i}\sqrt{a_{i}b_{i}c_{i}m}\cdot\min(\sqrt{a_{i}},\sqrt{c_{i}})=m^{2}+m^{2.5},$

and the sketching cost is

$\displaystyle\Theta\left(\sum_{j=1}^{N}s_{j}m+Nm^{2.5}\right).$ (C.7)

As we will show in Appendix E, sketching with tree tensor network embeddings
yield an asymptotic cost of $\Theta\left(\sum_{j=1}^{N}s_{j}m+Nm^{3}\right).$
Therefore, Algorithm 1 is more efficient to sketch Kronecker product input
data.

##  Appendix D Lower bound analysis

In this section, we discuss the asymptotic computational lower bound for
sketching with embeddings satisfying the $(\epsilon,\delta)$-accurate
sufficient condition and only have one output sketch edge. In Section D.1, we
discuss the case where the data has uniform sketch dimensions. In this case,
each vertex in the data tensor network is adjacent to an edge to be sketched.
In Section D.2, we discuss the sketching computational lower bound for a more
general case, when the data tensor network can have arbitrary graph structure,
and vertices not adjacent to sketch edges are allowed. For both cases, we
assume that the size of each dimension to be sketched is greater than the
sketch size.

###  D.1 Sketching data with uniform sketch dimensions

We now discuss the sketching asymptotic cost lower bound when the data
$G_{D}=(V_{D},E_{D},w)$ has uniform sketch dimensions, where each $v\in V_{D}$
is adjacent to an edge to be sketched with size lower bounded by the target
sketch size, $m$. We have $N=|\bar{E}|=|V_{D}|$, and we let the size of each
$e_{i}\in\bar{E}$ be denoted $s_{i}>m$. We let $V=V_{E}\cup V_{D}$ denote the
set of all vertices in both the data and the embedding. Below, we show the
main theorem using lemmas and notations introduced in Appendix B.

######  Theorem D.1.

For any embedding $G_{E}$ satisfying the $(\epsilon,\delta)$-accurate
sufficient condition and only has one output sketch dimension, and any
contraction tree $T_{B}$ of $(G_{D},G_{E})$ constrained on the data
contraction tree $T_{0}$ expressed in (4.2), the sketching asymptotic cost is
lower bounded by

$\Omega\left(\sum_{j=1}^{N}\exp({\mathsf{cut}}_{G}(v_{j}))\cdot
m+\sum_{j=1}^{N-1}y_{i}\right),$ (D.1)

where $m=\Omega(N\log(1/\delta)/\epsilon^{2})$ represents the embedding sketch
size, $v_{j}$ is the vertex in $V_{D}$ adjacent to $e_{j}$, and
$\exp({\mathsf{cut}}_{G}(v_{j}))$ denotes the size of the tensor at $v_{j}$,
and $y_{i}$ is expressed in (C.3).

We present the proof of Theorem D.1 at the end of Section D.1. Note that the
first term in (D.1), $\sum_{v\in
V_{D}}\exp\left({\mathsf{cut}}_{G}(v)\right)\cdot m$, is a term independent of
the data contraction tree, while the second term is dependent of the data
contraction tree.

###### Proof of Theorem 4.1.

The asymptotic cost of of Algorithm 1 in (C.6) matches the lower bound shown
in Theorem D.1, thus proving the statement. ∎

Theorem D.1 also yields an asymptotic lower bound for sketching data with a
Kronecker product structure. We state the results below.

######  Corollary D.2.

Consider an input data $G_{D}$ representing a vector with a Kronecker product
structure and each $v_{j}$ for $j\in[N]$ is adjacent to an edge to be sketched
with size $s_{j}$. For any embedding $G_{E}$ satisfying the
$(\epsilon,\delta)$-accurate sufficient condition with only one output sketch
dimension and any contraction tree $T_{B}$ of $(G_{D},G_{E})$, the asymptotic
cost must be lower bounded by

$\Omega\left(\sum_{j=1}^{N}s_{j}m+Nm^{2.5}\right),$

where $m=\Omega(N\log(1/\delta)/\epsilon^{2})$.

Below, we present some lemmas needed to prove Theorem D.1.

######  Lemma D.3.

Consider an $(\epsilon,\delta)$-accurate embedding $G_{E}=(V_{E},E_{E},w)$
with a sketching linearization $G_{S}=(V,E_{S},w)$. Then for any subset of the
embedding and data graph vertex set, $W\subseteq V$, we have
${\mathsf{cut}}_{G_{S}}(W)\geq\log(m)$.

###### Proof.

Since each vertex in the data graph is adjacent to an edge to be sketched, and
the edge dimension size is greater than $m$, we have
${\mathsf{cut}}_{G_{S}}(w)\geq\log(m)$ for all $w\in V_{D}$. Since the
embedding satisfies the $(\epsilon,\delta)$-accurate sufficient condition, we
have ${\mathsf{cut}}_{G_{S}}(w)\geq\log(m)$ for all $w\in V_{E}$. Therefore,
${\mathsf{cut}}_{G_{S}}(w)\geq\log(m)$ for all $w\in V$. Based on Lemma B.3,
${\mathsf{cut}}_{G_{S}}(W)\geq\log(m)$ for all $W\subseteq V$. ∎

######  Lemma D.4.

Consider an $(\epsilon,\delta)$-accurate embedding $G_{E}$ with a sketching
linearization $G_{S}=(V,E_{S},w)$. Consider any contraction tree $T_{B}$ for
$(G_{D},G_{E})$. If there exists a contraction output of $U\subset V$ formed
in $T_{B}$ and ${\mathsf{cut}}_{G_{S}}(U)>\log(m)$, then the asymptotic cost
for the contraction tree $T_{B}$ must be lower bounded by
$\Omega\left(\exp\left({\mathsf{cut}}_{R}(U)+{\mathsf{cut}}_{G_{S}}(U)\right)\cdot
m\right)$.

###### Proof.

Since ${\mathsf{cut}}_{G_{S}}(U)>\log(m)$, there must exist a contraction
$(U,W)\in T_{B}$ with $W$ containing some vertices in $V\setminus U$. Based on
Lemma D.3, ${\mathsf{cut}}_{G_{S}}(W)\geq\log(m)$. Based on Lemma B.2, we have

$\displaystyle{\mathsf{cost}}_{G}(U,W)$
$\displaystyle={\mathsf{cost}}_{R}(U,W)+{\mathsf{cost}}_{L}(U,W)$
$\displaystyle={\mathsf{cost}}_{R}(U,W)+{\mathsf{cut}}_{G_{S}}(U)+{\mathsf{cut}}_{G_{S}}(W)+{\mathsf{cut}}_{G_{S}}(V\setminus(U\cup
W),U\cup W).$

Further, since ${\mathsf{cost}}_{R}(U,W)\geq{\mathsf{cut}}_{R}(U)$,

$\displaystyle{\mathsf{cost}}_{G}(U,W)$
$\displaystyle\geq{\mathsf{cut}}_{R}(U)+{\mathsf{cut}}_{G_{S}}(U)+{\mathsf{cut}}_{G_{S}}(W)$
$\displaystyle\geq{\mathsf{cut}}_{R}(U)+{\mathsf{cut}}_{G_{S}}(U)+\log(m).$

This proves the lemma since the contraction cost is
$\Theta\left(\exp({\mathsf{cost}}_{G}(U,W))\right)$. ∎

In Lemma D.6, we show that when the data contraction tree $T_{0}$ contains the
contraction $(U_{i},V_{i})$, then any contraction tree $T_{B}$ of
$(G_{D},G_{E})$ that is constrained on $T_{0}$ will yield a contraction cost
of $\Omega(y_{i})$. To show that, we first discuss the case where $T_{B}$ also
contains the contraction $(U_{i},V_{i})$ in Lemma D.5. The more general case
where the contraction $(U_{i},V_{i})$ need not be in $T_{B}$ is discussed in
Lemma D.6.

######  Lemma D.5.

Consider a specific contraction tree $T_{0}$ for $G_{D}$, where the
contraction $(U_{i},V_{i})$ is in $T_{0}$. For any embedding $G_{E}$
satisfying the $(\epsilon,\delta)$-accurate sufficient condition with only one
output sketch dimension and any contraction tree $T_{B}$ of $(G_{D},G_{E})$
constrained on $T_{0}$, if $(U_{i},V_{i})$ is also in $T_{B}$, the sketching
asymptotic cost must be lower bounded by
$\Omega\left(a_{i}b_{i}c_{i}d_{i}m^{2}+a_{i}c_{i}d_{i}m^{3}\right)$, where
$a_{i},b_{i},c_{i},d_{i}$ are defined in (C).

###### Proof.

Consider any sketching linearization $G_{S}=(V,E_{S},w)$ such that the
embedding satisfies the $(\epsilon,\delta)$-accurate sufficient condition with
only one output sketch dimension. Based on Lemma D.3, we have
${\mathsf{cut}}_{G_{S}}(U_{i}),{\mathsf{cut}}_{G_{S}}(V_{i})\geq\log(m)$.
Based on Lemma B.2, we have

$\displaystyle{\mathsf{cost}}_{G}(U_{i},V_{i})$
$\displaystyle={\mathsf{cost}}_{R}(U_{i},V_{i})+{\mathsf{cost}}_{L}(U_{i},V_{i})$
$\displaystyle={\mathsf{cost}}_{R}(U_{i},V_{i})+{\mathsf{cut}}_{G_{S}}(U_{i})+{\mathsf{cut}}_{G_{S}}(V_{i})+{\mathsf{cut}}_{G_{S}}(V\setminus(U_{i}\cup
V_{i}),U_{i}\cup V_{i})$
$\displaystyle\geq{\mathsf{cost}}_{R}(U_{i},V_{i})+{\mathsf{cut}}_{G_{S}}(V_{i})+{\mathsf{cut}}_{G_{S}}(V_{i})$
$\displaystyle\geq\log(a_{i}b_{i}c_{i}d_{i})+2\log(m).$

Thus this contraction has a cost of $\Omega\left(a_{i}b_{i}c_{i}d_{i}\cdot
m^{2}\right).$ In addition, since $U_{i},V_{i}$ are subsets of the data
vertices, ${\mathsf{cut}}_{L}(U_{i},V_{i})=0$. Therefore, based on (B.1),

${\mathsf{cut}}_{G_{S}}(U_{i}\cup
V_{i})={\mathsf{cut}}_{G_{S}}(U_{i})+{\mathsf{cut}}_{G_{S}}(V_{i})\geq
2\log(m).$

Based on Lemma D.4, the cost needed to sketch $U_{i}\cup V_{i}$ is
$\Omega\left(a_{i}c_{i}d_{i}m^{3}\right)$. Thus the overall asymptotic cost is
lower bounded by
$\Omega\left(a_{i}b_{i}c_{i}d_{i}m^{2}+a_{i}c_{i}d_{i}m^{3}\right)$. This
finishes the proof. ∎

######  Lemma D.6.

Consider a specific contraction tree $T_{0}$ for $G_{D}$, where the
contraction $(U_{i},V_{i})$ is in $T_{0}$. For any embedding $G_{E}$
satisfying the $(\epsilon,\delta)$-accurate sufficient condition with only one
output sketch dimension and any contraction tree $T_{B}$ of $(G_{D},G_{E})$
constrained on $T_{0}$, the sketching asymptotic cost must be lower bounded by

$\Omega(y_{i})=\Omega\left(a_{i}b_{i}c_{i}d_{i}m^{2}+m^{2}d_{i}\sqrt{a_{i}b_{i}c_{i}m}\cdot\min(\sqrt{a_{i}},\sqrt{c_{i}})\right),$
(D.2)

where $a_{i},b_{i},c_{i},d_{i}$ are defined in (C), and $y_{i}$ is defined in
(C.3).

###### Proof.

Consider any sketching linearization $G_{S}=(V,E_{S},w)$ such that the
embedding satisfies the $(\epsilon,\delta)$-accurate sufficient condition with
only one output sketch dimension. We first consider the case where the
contraction $(U_{i},V_{i})$ exists in $T_{B}$. Based on Lemma D.5, the overall
asymptotic cost is lower bounded by
$\Omega\left(a_{i}b_{i}c_{i}d_{i}m^{2}+a_{i}c_{i}d_{i}m^{3}\right)$. Since

$a_{i}b_{i}c_{i}d_{i}m^{2}+a_{i}c_{i}d_{i}m^{3}=a_{i}c_{i}d_{i}m^{2}(b_{i}+m)\geq
2a_{i}c_{i}d_{i}m^{2}\sqrt{b_{i}m},$

the overall asymptotic cost is lower bounded by

$\Omega\left(a_{i}b_{i}c_{i}d_{i}m^{2}+a_{i}c_{i}d_{i}m^{2}\sqrt{b_{i}m}\right)=\Omega\left(a_{i}b_{i}c_{i}d_{i}m^{2}+a_{i}m^{2}d_{i}\sqrt{b_{i}c_{i}m}\right),$

and hence it satisfies (D.2).

We next consider the other case where the contraction $(U_{i},V_{i})$ is not
performed directly in $T_{B}$. Since $T_{B}$ is constrained on $T_{0}$, there
must exist a contraction $(\hat{U}_{i},\hat{V}_{i})\in T_{B}$ with either
$\hat{U}_{i}$ or $\hat{V}_{i}$ containing embedding vertices, and
$\hat{U}_{i}\cap V_{D}=U_{i}$, $\hat{V}_{i}\cap V_{D}=V_{i}$. Let $x$ be the
last embedding vertex (based on the linearization order) applied in $T_{B}$ to
$\hat{U}_{i}\cup\hat{V}_{i}$, so that
${\mathsf{cut}}_{G_{S}}(x,(\hat{U}_{i}\cup\hat{V}_{i})\setminus\\{x\\})=0.$
For the case where $x\in\hat{U}_{i}\setminus U_{i}$, we show below that the
sketching asymptotic cost is lower bounded by

$\Omega\left(a_{i}b_{i}c_{i}d_{i}m^{2}+a_{i}m^{2}d_{i}\sqrt{b_{i}c_{i}m}\right).$
(D.3)

For the other case where $x\in\hat{V}_{i}\setminus V_{i}$, we have the cost is
lower bounded by
$\Omega\left(a_{i}b_{i}c_{i}d_{i}m^{2}+c_{i}m^{2}d_{i}\sqrt{a_{i}b_{i}m}\right)$
by symmetry. Together, these two results prove the lemma.

#### Detailed proof of (D.3)

Since $|\hat{U}_{i}|>|U_{i}|$, there must exist a contraction $(Y_{1},Y_{2})$,
for which the output is $\hat{U}_{i}=Y_{1}\cup Y_{2}$. Based on Lemma B.2, we
have

$\displaystyle{\mathsf{cost}}_{G}(Y_{1},Y_{2})$
$\displaystyle={\mathsf{cost}}_{R}(Y_{1},Y_{2})+{\mathsf{cost}}_{L}(Y_{1},Y_{2})$
$\displaystyle={\mathsf{cost}}_{R}(Y_{1},Y_{2})+{\mathsf{cut}}_{G_{S}}(Y_{1})+{\mathsf{cut}}_{G_{S}}(Y_{2})+{\mathsf{cut}}_{G_{S}}(V\setminus(Y_{1}\cup
Y_{2}),Y_{1}\cup Y_{2})$
$\displaystyle\geq{\mathsf{cost}}_{R}(Y_{1},Y_{2})+{\mathsf{cut}}_{G_{S}}(Y_{1})+{\mathsf{cut}}_{G_{S}}(Y_{2})+{\mathsf{cut}}_{G_{S}}(\hat{V}_{i},\hat{U}_{i})$
$\displaystyle\geq\log(a_{i}b_{i}d_{i})+2\log(m)+{\mathsf{cut}}_{G_{S}}(\hat{V}_{i},\hat{U}_{i}).$

Thus, the cost of the contraction $(Y_{1},Y_{2})$ is lower bounded by

$\displaystyle\Omega\left(a_{i}b_{i}d_{i}m^{2}\cdot\exp\left({\mathsf{cut}}_{G_{S}}(\hat{V}_{i},\hat{U}_{i})\right)\right).$
(D.4)

In addition, since

$\displaystyle{\mathsf{cost}}_{G}(\hat{U}_{i},\hat{V}_{i})$
$\displaystyle={\mathsf{cost}}_{R}(\hat{U}_{i},\hat{V}_{i})+{\mathsf{cut}}_{G_{S}}(\hat{U}_{i})+{\mathsf{cut}}_{G_{S}}(\hat{V}_{i})+{\mathsf{cut}}_{G_{S}}(V\setminus(\hat{U}_{i}\cup\hat{V}_{i}),\hat{U}_{i}\cup\hat{V}_{i})$
$\displaystyle\geq\log(a_{i}b_{i}c_{i}d_{i})+2\log(m),$

the contraction $(\hat{U}_{i},\hat{V}_{i})$ yields a cost lower bounded by

$\displaystyle\Omega\left(a_{i}b_{i}c_{i}d_{i}\cdot m^{2}\right).$ (D.5)

Combining (D.4) and (D.5), we have that the contractions $(Y_{1},Y_{2})$ and
$(\hat{U}_{i},\hat{V}_{i})$ have a cost of

$\displaystyle\Omega\left(a_{i}b_{i}d_{i}m^{2}\cdot\exp\left({\mathsf{cut}}_{G_{S}}(\hat{V}_{i},\hat{U}_{i})\right)+a_{i}b_{i}c_{i}d_{i}\cdot
m^{2}\right).$ (D.6)

When ${\mathsf{cut}}_{G_{S}}(\hat{V}_{i},\hat{U}_{i})=\log(m)$, (D.6) implies
that the overall asymptotic cost is lower bounded by
$\Omega(a_{i}b_{i}c_{i}d_{i}m^{2}+a_{i}b_{i}d_{i}m^{3})$. Since

$a_{i}b_{i}c_{i}d_{i}m^{2}+a_{i}b_{i}d_{i}m^{3}=a_{i}b_{i}d_{i}m^{2}(c_{i}+m)\geq
2a_{i}b_{i}d_{i}m^{2}\sqrt{c_{i}m},$

the overall asymptotic cost is lower bounded by

$\Omega\left(a_{i}b_{i}c_{i}d_{i}m^{2}+a_{i}b_{i}d_{i}m^{2}\sqrt{c_{i}m}\right)=\Omega\left(a_{i}b_{i}c_{i}d_{i}m^{2}+a_{i}m^{2}d_{i}\sqrt{b_{i}c_{i}m}\right).$

When ${\mathsf{cut}}_{G_{S}}(\hat{V}_{i},\hat{U}_{i})<\log(m)$, based on Lemma
B.1, the effective sketch dimensions of $\hat{U}_{i}\cup\hat{V}_{i}$ satisfy

$\displaystyle{\mathsf{cut}}_{G_{S}}(\hat{U}_{i}\cup\hat{V}_{i})$
$\displaystyle=\left({\mathsf{cut}}_{G_{S}}(\hat{U}_{i})-{\mathsf{cut}}_{G_{S}}(\hat{U}_{i},\hat{V}_{i})\right)+{\mathsf{cut}}_{G_{S}}(\hat{V}_{i})-{\mathsf{cut}}_{G_{S}}(\hat{V}_{i},\hat{U}_{i})$
$\displaystyle\geq{\mathsf{cut}}_{G_{S}}(x)+{\mathsf{cut}}_{G_{S}}(\hat{V}_{i})-{\mathsf{cut}}_{G_{S}}(\hat{V}_{i},\hat{U}_{i})$
$\displaystyle\geq 2\log(m)-{\mathsf{cut}}_{G_{S}}(\hat{V}_{i},\hat{U}_{i}),$
(D.7)

where the first inequality holds since

$\displaystyle{\mathsf{cut}}_{G_{S}}(\hat{U}_{i})-{\mathsf{cut}}_{G_{S}}(\hat{U}_{i},\hat{V}_{i})$
$\displaystyle={\mathsf{cut}}_{G_{S}}(\hat{U}_{i},V\setminus(\hat{U}_{i}\cup\hat{V}_{i}))+{\mathsf{cut}}_{G_{S}}(\hat{U}_{i},*)$
$\displaystyle\geq{\mathsf{cut}}_{G_{S}}(x,V\setminus(\hat{U}_{i}\cup\hat{V}_{i}))+{\mathsf{cut}}_{G_{S}}(x,*)={\mathsf{cut}}_{G_{S}}(x),$

and the second inequality in (D.1) holds since
${\mathsf{cut}}_{G_{S}}(x),{\mathsf{cut}}_{G_{S}}(\hat{V}_{i})\geq\log(m)$
based on Lemma D.3. Based on the condition
${\mathsf{cut}}_{G_{S}}(\hat{V}_{i},\hat{U}_{i})<\log(m)$ as well as (D.1), we
have ${\mathsf{cut}}_{G_{S}}(\hat{U}_{i}\cup\hat{V}_{i})>\log(m)$.

Based on Lemma D.4, since
${\mathsf{cut}}_{G_{S}}(\hat{U}_{i}\cup\hat{V}_{i})>\log(m)$, there must exist
another contraction in $T_{B}$ to sketch $\hat{U}_{i}\cup\hat{V}_{i}$ with a
cost of

$\displaystyle\Omega\left(\exp\left({\mathsf{cut}}_{R}(\hat{V}_{i}\cup\hat{U}_{i})+{\mathsf{cut}}_{G_{S}}(\hat{V}_{i}\cup\hat{U}_{i})\right)\cdot
m\right)$
$\displaystyle=\Omega\left(a_{i}c_{i}d_{i}\cdot\exp\left({\mathsf{cut}}_{G_{S}}(\hat{V}_{i}\cup\hat{U}_{i})\right)\cdot
m\right)$
$\displaystyle\overset{\eqref{eq:lowerbound_gen_sketchsize}}{=}\Omega\left(a_{i}c_{i}d_{i}\cdot\frac{m^{3}}{\exp({\mathsf{cut}}_{G_{S}}(\hat{V}_{i},\hat{U}_{i}))}\right).$

Let $\alpha=\exp\left({\mathsf{cut}}_{G_{S}}(\hat{V}_{i},\hat{U}_{i})\right)$,
the asymptotic cost is then lower bounded by

$\Omega\left(a_{i}b_{i}c_{i}d_{i}m^{2}+a_{i}b_{i}d_{i}m^{2}\cdot\alpha+a_{i}c_{i}d_{i}m^{3}\cdot\frac{1}{\alpha}\right)=\Omega\left(a_{i}b_{i}c_{i}d_{i}m^{2}+a_{i}m^{2}d_{i}\sqrt{b_{i}c_{i}m}\right).$

This finishes the proof.

∎

###### Proof of Theorem D.1.

Based on Lemma D.6, the cost of $\Omega(y_{i})$ is needed to sketch the
contraction $(U_{i},V_{i})$. Since $T_{0}$ contains contractions
$(U_{i},V_{i})$ for $i\in[N-1]$, the asymptotic cost of $T_{B}$ must be lower
bounded by $\Omega\left(\sum_{i=1}^{N-1}y_{i}\right)$. In addition, in the
analysis of Lemma D.6, at least one embedding vertex is needed to sketch each
contraction $(U_{i},V_{i})$, thus $N_{E}=\Omega(N)$ and
$m=\Omega(N\log(1/\delta)/\epsilon^{2})$ for the lower bound
$\Omega\left(\sum_{i=1}^{N-1}y_{i}\right)$ to hold.

In addition, each $v_{j}\in V_{D}$ for $j\in[N]$ is adjacent to $e_{j}$ and
each $w(e_{j})>\log(m)$. Based on Lemma D.4, the asymptotic cost must be lower
bounded by

$\Omega\left(\sum_{j=1}^{N}\exp\left({\mathsf{cut}}_{R}(v_{j})+{\mathsf{cut}}_{G_{S}}(v_{j})\right)\cdot
m\right)=\Omega\left(\sum_{j=1}^{N}\exp\left({\mathsf{cut}}_{G}(v_{j})\right)\cdot
m\right).$

The above holds since $v_{j}$ is a vertex in the data graph, thus
${\mathsf{cut}}_{G_{S}}(v_{j})={\mathsf{cut}}_{L}(v_{j})$ and
${\mathsf{cut}}_{R}(v_{j})+{\mathsf{cut}}_{G_{S}}(v_{j})={\mathsf{cut}}_{G}(v_{j})$.
This finishes the proof. ∎

###  D.2 Sketching general data

In this section, we look at general tensor network data $G_{D}$, where each
vertex in $G_{D}$ can either be adjacent to an edge to be sketched with weight
greater than $\log(m)$ or not adjacent to any edge to be sketched. Below we
consider any data contraction tree $T_{0}$ containing
$\mathcal{D}(e_{1}),\ldots,\mathcal{D}(e_{N}),\mathcal{S},\mathcal{I}$ defined
in Section 4. We also let $X(e_{j})\subset V$ represent the sub network
contracted by $\mathcal{D}(e_{j})$. We present the asymptotic sketching lower
bound in Theorem D.9.

######  Lemma D.7.

Consider $G_{D}$ with a data contraction tree $T_{0}$ containing
$\mathcal{D}(e_{j})$, which is a set containing contractions such that $e_{j}$
is the only data edge adjacent to the contraction output and in $\bar{E}$ (set
of data edges to be sketched). For any embedding $G_{E}$ satisfying the
$(\epsilon,\delta)$-accurate sufficient condition with only one output sketch
dimension and any contraction tree $T_{B}$ of $(G_{D},G_{E})$ constrained on
the data contraction tree $T_{0}$, the sketching asymptotic cost must be lower
bounded by $\Omega(t(e_{j}))$, where $t(e_{j})$ is the optimal asymptotic cost
to sketch the sub tensor network $X(e_{j})$ (defined in Table 2) with an
adjacent matrix in the Kronecker product embedding.

###### Proof.

When $\mathcal{D}(e_{j})=\emptyset$, $X(e_{j})=\\{v_{j}\\}$, where $v_{j}$ is
the vertex in the data graph adjacent to $e_{j}$. As is analyzed in the proof
of Theorem D.1, the asymptotic cost must be lower bounded by
$\Omega\left(\exp\left({\mathsf{cut}}_{G}(v_{j})\right)\cdot m\right)$, which
equals the asymptotic cost to contract $v_{j}$ with the adjacent embedding
matrix.

Now we discuss the case where $\mathcal{D}(e_{j})\neq\emptyset$. We first
consider the case where there is a contraction $(X(e_{j}),W)$ in $T_{B}$. We
show that under this case, the cost is lower bounded by $\Omega(t(e_{j}))$. We
then show that for the case where there is no contraction $(X(e_{j}),W)$ in
$T_{B}$, meaning that some sub network of $X(e_{j})$ is sketched, the cost is
also lower bounded by $\Omega(t(e_{j}))$. Summarizing both cases prove the
lemma.

Consider the case where there exists a contraction $(X(e_{j}),W)$ in $T_{B}$.
Contracting $X(e_{j})$ yields a cost of
$\Omega(\sum_{i\in\mathcal{D}(e_{j})}a_{i}b_{i}c_{i}d_{i}\cdot s_{j})$. Next
we analyze the contraction cost of $(X(e_{j}),W)$. Since $X(e_{j})$ is the
contraction output of $\mathcal{D}(e_{j})$, $W$ must either contain embedding
vertices, or contain some data vertex adjacent to edges in $\bar{E}$ (edges to
be sketched). Therefore, $W$ contains some vertex $v$ with
${\mathsf{cut}}_{G_{S}}(v)\geq\log(m)$. Based on Lemma B.3, we have
${\mathsf{cut}}_{G_{S}}(W)\geq\log(m)$. Therefore,

$\displaystyle{\mathsf{cost}}_{L}(X(e_{j}),W)$
$\displaystyle={\mathsf{cut}}_{G_{S}}(X(e_{j}))+{\mathsf{cut}}_{G_{S}}(W)+{\mathsf{cut}}_{G_{S}}(V\setminus(X(e_{j})\cup
W),X(e_{j})\cup W)$ $\displaystyle\geq\log(s_{j})+\log(m).$

Let $l\in\mathcal{D}(e_{j})$ denote the last contraction in
$\mathcal{D}(e_{j})$, then we have
${\mathsf{cut}}_{R}(X(e_{j}))=\log(a_{l}c_{l}d_{l})$. Thus, we have

$\displaystyle{\mathsf{cost}}_{G}(X(e_{j}),W)$
$\displaystyle={\mathsf{cost}}_{L}(X(e_{j}),W)+{\mathsf{cost}}_{R}(X(e_{j}),W)$
(D.8)
$\displaystyle\geq{\mathsf{cost}}_{L}(X(e_{j}),W)+{\mathsf{cut}}_{R}(X(e_{j}))\geq\log(a_{l}c_{l}d_{l}s_{j}m),$
(D.9)

making the cost lower bounded by
$\Omega\left(\sum_{i\in\mathcal{D}(e_{j})}a_{i}b_{i}c_{i}d_{i}\cdot
s_{j}+a_{l}c_{l}d_{l}s_{j}m\right)$. Note that contracting $X(e_{j})$ and
sketching the contraction output with a matrix in the Kronecker product
embedding yields a cost of
$\Theta\left(\sum_{i\in\mathcal{D}(e_{j})}a_{i}b_{i}c_{i}d_{i}\cdot
s_{j}+a_{l}c_{l}d_{l}s_{j}m\right)$, which upper-bounds the value of
$t(e_{j})$ based on definition. Thus the sketching cost is lower bounded by
$\Omega(t(e_{j}))$.

Below we analyze the case where there is no contraction $(X(e_{j}),W)$ in
$T_{B}$. Without loss of generality, for each contraction $(U_{i},V_{i})$ with
$i\in\mathcal{D}(e_{j})$, assume that $U_{i}$ is adjacent to $e_{j}$. When
$X(e_{j})$ is not formed in $T_{B}$, there must exist $U_{k}$ with
$k\in\mathcal{D}(e_{j})$, and a contraction $(U_{k},X)$ with $X\subset V_{E}$
is in $T_{B}$. All contractions before $k$ yield a cost of

$\Omega\left(\sum_{i\in\mathcal{D}(e_{j}),i<k}a_{i}b_{i}c_{i}d_{i}\cdot
s_{j}\right).$ (D.10)

Similar to the analysis for the contraction $(X(e_{j}),W)$ in (D.8), the
contraction $(U_{k},X)$ yields a cost of

$\Omega(a_{k}b_{k}d_{k}s_{j}m).$ (D.11)

For other contractions in $T_{0}$, $(U_{i},V_{i})$ with
$i\in\mathcal{D}(e_{j}),i\geq k$, there must exist some contractions
$(\hat{U}_{i},\hat{V}_{i})$ in $T_{B}$ with $\hat{U}_{i}\cap V_{D}=U_{i}$,
$\hat{V}_{i}\cap V_{D}=V_{i}$, since $T_{B}$ is constrained on $T_{0}$.
Therefore, we have

$\displaystyle{\mathsf{cost}}_{G}(\hat{U}_{i},\hat{V}_{i})$
$\displaystyle={\mathsf{cost}}_{R}(\hat{U}_{i},\hat{V}_{i})+{\mathsf{cost}}_{L}(\hat{U}_{i},\hat{V}_{i})={\mathsf{cost}}_{R}({U}_{i},{V}_{i})+{\mathsf{cost}}_{L}(\hat{U}_{i},\hat{V}_{i})$
$\displaystyle\geq{\mathsf{cost}}_{R}({U}_{i},{V}_{i})+{\mathsf{cut}}_{G_{S}}(\hat{U}_{i})\geq\log(a_{i}b_{i}c_{i}d_{i}m).$
(D.12)

In the last inequality in (D.2) we use the fact that there exists a vertex
$v\in U_{i}\subseteq\hat{U}_{i}$ with
${\mathsf{cut}}_{G_{S}}(v)=\log(s_{j})\geq\log(m)$, then based on Lemma B.3,
${\mathsf{cut}}_{G_{S}}(\hat{U}_{i})\geq\log(m)$.

Combining (D.10), (D.11) and (D.2), we have the cost is lower bounded by

$\displaystyle\Omega\left(f(k)\right)=\Omega\left(\sum_{i\in\mathcal{D}(e_{j}),i<k}a_{i}b_{i}c_{i}d_{i}\cdot
s_{j}+a_{k}b_{k}d_{k}s_{j}m+\sum_{i\in\mathcal{D}(e_{j}),i\geq
k}a_{i}b_{i}c_{i}d_{i}\cdot m\right),$

where $f(k)$ represents the asymptotic cost to contract $X(e_{j})$ with an
embedding matrix adjacent to $e_{j}$, when sketching is performed at $k$th
contraction with $k\in\mathcal{D}(e_{j})$. Based on the definition of
$t(e_{j})$, we have $f(k)=\Omega(t(e_{j}))$, thus finishing the proof. ∎

######  Lemma D.8.

Consider any data $G_{D}$. For any embedding $G_{E}$ satisfying the
$(\epsilon,\delta)$-accurate sufficient condition with only one output sketch
dimension and any contraction tree $T_{B}$ of $(G_{D},G_{E})$, the sketching
asymptotic cost must be lower bounded by $\Omega(Nm^{2.5})$, where
$m=\Omega(N\log(1/\delta)/\epsilon^{2})$.

###### Proof.

Let $G_{D}^{\prime}$ be the data with the same set of sketching edges
($\bar{E}$) as $G_{D}$, but $G_{D}^{\prime}$ is a Kronecker product data. For
any given contraction tree $T_{B}$ of $(G_{D},G_{E})$, there must exist a
contraction tree of $(G_{D}^{\prime},G_{E})$ whose asymptotic cost is upper
bounded by the cost of $T_{B}$. Therefore, the asymptotic cost lower bound to
contract $(G_{D}^{\prime},G_{E})$ must also be the asymptotic cost lower bound
to contract $(G_{D},G_{E})$. Based on Corollary D.2, the asymptotic cost of
$T_{B}$ must be lower bounded by

$\Omega\left(\sum_{j=1}^{N}s_{j}m+Nm^{2.5}\right)=\Omega(Nm^{2.5}).$

∎

######  Theorem D.9.

For any embedding $G_{E}$ satisfying the $(\epsilon,\delta)$-accurate
sufficient condition and any contraction tree $T_{B}$ of $(G_{D},G_{E})$
constrained on the data contraction tree $T_{0}$ expressed in (4.2), the
sketching asymptotic cost must be lower bounded by

$\Omega\left(\sum_{j=1}^{N}t(e_{j})+\sum_{i\in\mathcal{S}}a_{i}b_{i}c_{i}d_{i}m^{2}+Nm^{2.5}+\sum_{i\in\mathcal{I}}z_{i}\right),$
(D.13)

where $m=\Omega(N\log(1/\delta)/\epsilon^{2})$, $a_{i},b_{i},c_{i},d_{i}$ are
expressed in (C), $t(e_{j})$ is the optimal asymptotic cost to sketch the sub
tensor network $X(e_{j})$ (the sub network contracted by $\mathcal{D}(e_{j})$,
also defined in Table 2) with an adjacent matrix in the Kronecker product
embedding, and $z_{i}$ is expressed in (C.5).

###### Proof.

The term $\sum_{j=1}^{N}t(e_{j})$ can be proven based on Lemma D.7, and the
term $Nm^{2.5}$ with $m=\Omega(N\log(1/\delta)/\epsilon^{2})$ can be proven
based on Lemma D.8. Below we show the asymptotic cost is also lower bounded by
$\Omega(\sum_{i\in\mathcal{S}}a_{i}b_{i}c_{i}d_{i}m^{2}+\sum_{i\in\mathcal{I}}z_{i})$,
thus finishing the proof.

For each contraction $(U_{i},V_{i})$ in $T_{0}$ with
$i\in\mathcal{S}\cup\mathcal{I}$, there must exist a contraction
$(\hat{U}_{i},\hat{V}_{i})$ in $T_{B}$, and $\hat{U}_{i}\cap V_{D}=U_{i}$,
$\hat{V}_{i}\cap V_{D}=V_{i}$. For the case where $i\in\mathcal{S}$, since
both $U_{i}$ and $V_{i}$ contain edges to be sketched, we have
${\mathsf{cut}}_{G_{S}}(\hat{U}_{i})\geq\log(m)$ and
${\mathsf{cut}}_{G_{S}}(\hat{V}_{i})\geq\log(m)$ based on Lemma B.3.
Therefore, we have

$\displaystyle\sum_{i\in\mathcal{S}}{\mathsf{cost}}_{G}(\hat{U}_{i},\hat{V}_{i})$
$\displaystyle=\sum_{i\in\mathcal{S}}{\mathsf{cost}}_{R}(\hat{U}_{i},\hat{V}_{i})+{\mathsf{cost}}_{L}(\hat{U}_{i},\hat{V}_{i})$
$\displaystyle=\sum_{i\in\mathcal{S}}{\mathsf{cost}}_{R}({U}_{i},{V}_{i})+{\mathsf{cost}}_{L}(\hat{U}_{i},\hat{V}_{i})$
$\displaystyle\geq\sum_{i\in\mathcal{S}}{\mathsf{cost}}_{R}({U}_{i},{V}_{i})+{\mathsf{cut}}_{G_{S}}(\hat{U}_{i})+{\mathsf{cut}}_{G_{S}}(\hat{V}_{i})$
$\displaystyle\geq\sum_{i\in\mathcal{S}}\log(a_{i}b_{i}c_{i}d_{i}m^{2}),$
(D.14)

where the first inequality above holds based on Lemma B.2. This shows the cost
is lower bounded by $\Omega(\sum_{i\in\mathcal{S}}a_{i}b_{i}c_{i}d_{i}m^{2})$.

Now consider the case where $i\in\mathcal{I}$. In this case, either
${\mathsf{cut}}_{G_{S}}(U_{i}\cup{V}_{i})=0$ or
${\mathsf{cut}}_{G_{S}}(U_{i}\cup{V}_{i})\geq\log(m)$. When
${\mathsf{cut}}_{G_{S}}(U_{i}\cup{V}_{i})=0$, we have
${\mathsf{cut}}_{G_{S}}(\hat{U}_{i}\cup\hat{V}_{i})\geq{\mathsf{cut}}_{G_{S}}(U_{i}\cup{V}_{i})$.
When ${\mathsf{cut}}_{G_{S}}(U_{i}\cup{V}_{i})\geq\log(m)$, based on Lemma
B.3, we have ${\mathsf{cut}}_{G_{S}}(\hat{U}_{i}\cup\hat{V}_{i})\geq\log(m)$.
To summarize, we have

${\mathsf{cut}}_{G_{S}}(\hat{U}_{i}\cup\hat{V}_{i})\geq\min\left({\mathsf{cut}}_{G_{S}}(U_{i}\cup{V}_{i}),\log(m)\right),$

thus

$\displaystyle\sum_{i\in\mathcal{I}}{\mathsf{cost}}_{G}(\hat{U}_{i},\hat{V}_{i})$
$\displaystyle=\sum_{i\in\mathcal{I}}{\mathsf{cost}}_{R}(\hat{U}_{i},\hat{V}_{i})+{\mathsf{cost}}_{L}(\hat{U}_{i},\hat{V}_{i})$
$\displaystyle\geq\sum_{i\in\mathcal{I}}{\mathsf{cost}}_{R}({U}_{i},{V}_{i})+{\mathsf{cut}}_{G_{S}}(\hat{U}_{i})+{\mathsf{cut}}_{G_{S}}(\hat{V}_{i})$
$\displaystyle\geq\sum_{i\in\mathcal{I}}{\mathsf{cost}}_{R}({U}_{i},{V}_{i})+{\mathsf{cut}}_{G_{S}}(\hat{U}_{i}\cup\hat{V}_{i})$
$\displaystyle\geq\sum_{i\in\mathcal{I}}\log(a_{i}b_{i}c_{i}d_{i})+\min\left({\mathsf{cut}}_{G_{S}}(U_{i}\cup
V_{i}),\log(m)\right)$ $\displaystyle=\sum_{i\in\mathcal{I}}\log(z_{i}).$
(D.15)

This shows the sketching cost is lower bounded by
$\Omega\left(\sum_{i\in\mathcal{I}}z_{i}\right)$, thus finishing the proof. ∎

###### Proof of Theorem 4.2.

Based on Theorem C.1, the computational cost of Algorithm 1 is

$\alpha=\Theta\left(\sum_{j=1}^{N}t(e_{j})+\sum_{i\in\mathcal{S}}y_{i}+\sum_{i\in\mathcal{I}}z_{i}\right).$

Let $\beta$ equals the expression in (D.13). We have

$\displaystyle\frac{\alpha}{\beta}$
$\displaystyle=\frac{\Theta\left(\sum_{j=1}^{N}t(e_{j})+\sum_{i\in\mathcal{S}}y_{i}+\sum_{i\in\mathcal{I}}z_{i}\right)}{\Omega\left(\sum_{j=1}^{N}t(e_{j})+\sum_{i\in\mathcal{S}}(a_{i}b_{i}c_{i}d_{i}m^{2}+m^{2.5})+\sum_{i\in\mathcal{I}}z_{i}\right)}={O}\left(\frac{\sum_{i\in\mathcal{S}}y_{i}}{\sum_{i\in\mathcal{S}}(a_{i}b_{i}c_{i}d_{i}m^{2}+m^{2.5})}\right)$
$\displaystyle={O}\left(\max_{i\in\mathcal{S}}\frac{y_{i}}{a_{i}b_{i}c_{i}d_{i}m^{2}+m^{2.5}}\right)={O}\left(\max_{i\in\mathcal{S}}\frac{a_{i}b_{i}c_{i}d_{i}m^{2}+m^{2}d_{i}\sqrt{a_{i}b_{i}c_{i}m}\cdot\min(\sqrt{a_{i}},\sqrt{c_{i}})}{a_{i}b_{i}c_{i}d_{i}m^{2}+m^{2.5}}\right)$
$\displaystyle=O(1)+{O}\left(\max_{i\in\mathcal{S}}\frac{m^{2}d_{i}\sqrt{a_{i}b_{i}c_{i}m}\cdot\min(\sqrt{a_{i}},\sqrt{c_{i}})}{a_{i}b_{i}c_{i}d_{i}m^{2}+m^{2.5}}\right).$

Below we derive asymptotic upper bound of the term
$\theta=\frac{m^{2}d_{i}\sqrt{a_{i}b_{i}c_{i}m}\cdot\min(\sqrt{a_{i}},\sqrt{c_{i}})}{a_{i}b_{i}c_{i}d_{i}m^{2}+m^{2.5}}$.
We analyze the case below with $a_{i}\leq c_{i}$, and the other case with
$a_{i}>c_{i}$ can be analyzed in a similar way based on the symmetry of
$a_{i},c_{i}$ in $\theta$.

When $a_{i}\leq c_{i}$, we have
$m^{2}d_{i}\sqrt{a_{i}b_{i}c_{i}m}\cdot\min(\sqrt{a_{i}},\sqrt{c_{i}})=a_{i}m^{2}d_{i}\sqrt{b_{i}c_{i}m}$.
We consider two cases, one satisfies $\sqrt{b_{i}c_{i}m}\leq b_{i}c_{i}$ and
the other satisfies $\sqrt{b_{i}c_{i}m}>b_{i}c_{i}$.

When $\sqrt{b_{i}c_{i}m}\leq b_{i}c_{i}$, we have $\theta\leq 1$, thus
$\frac{\alpha}{\beta}=O(1)$, thus satisfying the theorem statement.

When $\sqrt{b_{i}c_{i}m}>b_{i}c_{i}$, which means that ${m}>{b_{i}c_{i}}$, we
have

$\displaystyle\theta$
$\displaystyle=\frac{a_{i}m^{2}d_{i}\sqrt{b_{i}c_{i}m}}{a_{i}b_{i}c_{i}d_{i}m^{2}+m^{2.5}}\leq\min\left(\frac{\sqrt{m}}{\sqrt{b_{i}c_{i}}},a_{i}d_{i}\sqrt{b_{i}c_{i}}\right)\leq\sqrt{m},$

thus $\frac{\alpha}{\beta}\leq O\left(\sqrt{m}\right).$ In addition, when
$G_{D}$ is a graph, we have $d_{i}=1$ for all $i$. Therefore,

$\displaystyle\theta$
$\displaystyle\leq\min\left(\frac{\sqrt{m}}{\sqrt{b_{i}c_{i}}},a_{i}d_{i}\sqrt{b_{i}c_{i}}\right)=\min\left(\frac{\sqrt{m}}{\sqrt{b_{i}c_{i}}},a_{i}\sqrt{b_{i}c_{i}}\right)$
$\displaystyle\leq\min\left(\frac{\sqrt{m}}{\sqrt{b_{i}c_{i}}},c_{i}\sqrt{b_{i}c_{i}}\right)\leq\min\left(\frac{\sqrt{m}}{(b_{i}c_{i})^{1/2}},(b_{i}c_{i})^{3/2}\right)\leq
m^{0.375}.$

Therefore, in this case we have $\frac{\alpha}{\beta}\leq
O\left(m^{0.375}\right),$ thus finishing the proof. ∎

##  Appendix E Analysis of tree tensor network embeddings

In this section, we provide detailed analysis of sketching with tree
embeddings. The algorithm to sketch with tree embedding is similar to
Algorithm 1, and the only difference is that for each contraction
$(U_{i},V_{i})$ with $i\in\mathcal{S}$, such that both $U_{i}$ and $V_{i}$ are
adjacent to edges in $\bar{E}$, we sketch it with one embedding tensor $z_{i}$
rather than a small network. Let $\hat{U}_{i},\hat{V}_{i}$ denote the sketched
$U_{i}$ and $V_{i}$ formed in previous contractions in the sketching
contraction tree $T_{B}$, such that $\hat{U}_{i}\cap V_{D}=U_{i}$ and
$\hat{V}_{i}\cap V_{D}=V_{i}$, we sketch $(\hat{U}_{i},\hat{V}_{i})$ via the
contraction path $((\hat{U}_{i},\hat{V}_{i}),z_{i})$. For the case where each
vertex in the data tensor network is adjacent to an edge to be sketched, the
sketching cost would be

$\displaystyle\Theta\left(\sum_{j=1}^{N}\exp({\mathsf{cut}}_{G}(v_{j}))\cdot
m+\sum_{j=1}^{N-1}(a_{i}b_{i}c_{i}d_{i}m^{2}+a_{i}c_{i}d_{i}m^{3})\right),$
(E.1)

where $v_{j}$ is the vertex in the data graph adjacent to $e_{j}$,
$a_{i},b_{i},c_{i},d_{i}$ are defined in (C), and we replace the term
$y_{i}=a_{i}b_{i}c_{i}d_{i}m^{2}+m^{2}d_{i}\sqrt{a_{i}b_{i}c_{i}m}\cdot\min(\sqrt{a_{i}},\sqrt{c_{i}})$
in (C.6) with $a_{i}b_{i}c_{i}d_{i}m^{2}+a_{i}c_{i}d_{i}m^{3}$.

###### Proof of Theorem 4.3.

Since each contraction in $T_{0}$ contracts dimensions with size being at
least the sketch size $m$, we have $b_{i}\geq m$ for $i\in\mathcal{S}$.
Therefore,

$m^{2}d_{i}\sqrt{a_{i}b_{i}c_{i}m}\cdot\min(\sqrt{a_{i}},\sqrt{c_{i}})\leq
a_{i}m^{2}d_{i}\sqrt{b_{i}c_{i}m}\leq a_{i}b_{i}d_{i}m^{2}\sqrt{c_{i}}\leq
a_{i}b_{i}c_{i}d_{i}m^{2},$

and the asymptotic cost in (C.6) would be

$\Theta\left(\sum_{j=1}^{N}\exp({\mathsf{cut}}_{G}(v_{j}))\cdot
m+\sum_{j=1}^{N-1}a_{i}b_{i}c_{i}d_{i}m^{2}\right).$ (E.2)

Based on Theorem D.1, (E.2) matches the sketching asymptotic cost lower bound
for this data. Since $a_{i}c_{i}d_{i}m^{3}\leq a_{i}b_{i}c_{i}d_{i}m^{2}$ so
(E.1) equals (E.2), sketching with tree embeddings also yield the optimal
asymptotic cost. ∎

When the data has a Kronecker product structure, sketching with tree tensor
network embedding is less efficient compared to Algorithm 1. As is shown in
(E.3), Algorithm 1 yields a cost of
$\Theta\left(\sum_{j=1}^{N}s_{j}m+Nm^{2.5}\right)$ to sketch the Kronecker
product data. However, for tree embeddings, the asymptotic cost (E.1) is equal
to

$\displaystyle\Theta\left(\sum_{j=1}^{N}s_{j}m+Nm^{3}\right).$ (E.3)

##  Appendix F Computational cost analysis of sketched CP-ALS

In this section, we provide detailed computational cost analysis of the
sketched CP-ALS algorithm based on Algorithm 1. We are given a tensor
${\mathcal{X}}\in\mathbb{R}^{s\times\cdots\times s}$, and aim to decompose
that into $N$ factor matrices, $A_{i}\in\mathbb{R}^{s\times R}$ for $i\in[N]$.
Let
$L_{i}={A}_{1}\odot\cdots\odot{A}_{i-1}\odot{A}_{i+1}\odot\cdots\odot{A}_{N}$
and $R_{i}={X}_{(i)}^{T}$. In each iteration, we aim to update $A_{i}$ via
solving a sketched linear least squares problem,
${A}_{i}=\underset{{A}}{\arg\\!\min}\left\|S_{i}L_{i}A^{T}-S_{i}R_{i}\right\|_{F}^{2},$
where $S_{i}$ is an embedding constructed based on Algorithm 1.

Below we first discuss the sketch size of $S_{i}$ sufficient to make each
sketched least squares problem accurate. We then discuss the contraction trees
of $L_{i}$, on top of which embedding structures are determined. We select
contraction trees such that contraction intermediates can be reused across
subproblems. Finally, we present the detailed computational cost analysis of
the sketched CP-ALS algorithm.

###  F.1 Sketch size sufficient for accurate least squares subproblem

Since the tensor network of $L_{i}$ contains $N$ output dimensions and $L_{i}$
contains $R$ columns, we show below that a sketch size of
$\Theta(NR\log(1/\delta)/\epsilon^{2})=\tilde{\Theta}(NR/\epsilon^{2})$ is
sufficient for the least squares problem to be $(\epsilon,\delta)$-accurate.

######  Theorem F.1.

Consider the sketched linear least squares problem
$\min_{{A}}\left\|S_{i}L_{i}A^{T}-S_{i}R_{i}\right\|_{F}^{2}$. Let ${S}_{i}$
be an embedding constructed based on Algorithm 1, with the sketch size
$m=\Theta(NR\log(1/\delta)/\epsilon^{2})$, solving the sketched least squares
problem gives us an $(1+\epsilon)$-accurate solution with probability at least
$1-\delta$.

###### Proof.

Algorithm 1 outputs an embedding with $\Theta(N)$ vertices. Based on Theorem
3.1, a sketched size of $\Theta(NR\log(1/\delta)/\epsilon^{2})$ will make the
embedding $(\epsilon,\frac{\delta}{e^{R}})$-accurate. Based on the
$\epsilon$-net argument [47], ${S}$ is the $(\epsilon,\delta)$-accurate
subspace embedding for a subspace with dimension $R$. Therefore, we can get an
$(1+\epsilon)$-accurate solution with probability at least $1-\delta$ for the
least squares problem. ∎

###  F.2 Data contraction trees and efficient embedding structures

The structures of embeddings $S_{1},\ldots,S_{N}$ also depend on the data
contraction trees for $L_{1},\ldots,L_{N}$. We denote the contraction tree of
$L_{i}$ as $T_{i}$. We construct $T_{i}$ for $i\in[N]$ such that resulting
embeddings $S_{1},\ldots,S_{N}$ have common parts, which yields more efficient
sketching computational cost via reusing contraction intermediates.

Let the vertex $v_{i}$ represent the matrix $A_{i}$. We also let
$V_{L}^{(i)}=\\{v_{1},\ldots,v_{i}\\}$ denote the set of all first $i$
vertices, and let $V_{R}^{(i)}=\\{v_{i},\ldots,v_{N}\\}$ denote the set of
vertices from $v_{i}$ to $v_{N}$. In addition, we let $\mathcal{C}_{L}^{(i)}$
denote a contraction tree to fully contract $V_{L}^{(i)}$, from $v_{1}$ to
$v_{i}$. Let $\mathcal{C}_{L}^{(1)}=\emptyset$, we have for all $i\geq 1$,
$\mathcal{C}_{L}^{(i+1)}=\mathcal{C}_{L}^{(i)}\cup\left\\{(V_{L}^{(i)},v_{i+1})\right\\}$.
Similarly, we let $\mathcal{C}_{R}^{(i)}$ denote a contraction tree to fully
contract $V_{R}^{(i)}$, from $v_{N}$ to $v_{i}$. Let
$\mathcal{C}_{R}^{(N)}=\emptyset$, we have for all $i\leq N$,
$\mathcal{C}_{R}^{(i-1)}=\mathcal{C}_{R}^{(i)}\cup\left\\{(V_{R}^{(i)},v_{i-1})\right\\}$.

(a)  (b)  (c)  (d)  (e)  (f)  (g)  (h)  (i)  (j)

Figure 12: (a)-(e): Representations of $L_{1},\ldots,L_{5}$ for the CP
decomposition of an order 5 tensor. (f)-(j): Data dimension trees
$T_{1},\ldots,T_{5}$.

Note that the vertex set of the tensor network of $L_{i}$ is
$V_{L}^{(i-1)}\cup V_{R}^{(i+1)}$. Each $T_{i}$ is constructed so that
$V_{L}^{(i-1)},V_{R}^{(i+1)}$ are first contracted via the contraction trees
$\mathcal{C}_{L}^{(i-1)}$, $\mathcal{C}_{R}^{(i+1)}$, respectively, then a
contraction of $(V_{L}^{(i-1)},V_{R}^{(i+1)})$ is used to contract them into a
single tensor. We illustrate $T_{i}$ for the CP decomposition of an order 5
tensor in Fig. 12.

These tree structures allow us to reuse contraction intermediates during
sketching. On top of $T_{1}$, sketching $L_{1}$ using Algorithm 1 yields a
cost of $\Theta(N(smR+m^{2.5}R))$, where the term $\Theta(NsmR)$ comes from
sketching with the Kronecker product embedding, and the term
$\Theta(Nm^{2.5}R)$ comes from sketching each data contraction in
$\mathcal{C}_{R}^{(2)}$. Since
$\mathcal{C}_{R}^{(2)}=\mathcal{C}_{R}^{(3)}\cup\left\\{(V_{R}^{(3)},v_{2})\right\\}$,
all contractions in $\mathcal{C}_{R}^{(3)}$ are sketched, and we obtain the
sketching output of $V_{R}^{(3)}$, which is denoted as $\hat{V}_{R}^{(3)}$
below.

We use $\hat{V}_{R}^{(3)}$ formed during sketching $L_{1}$ to sketch $L_{2}$.
Since $T_{2}$ contains contractions

$\displaystyle T_{2}$
$\displaystyle=\mathcal{C}_{R}^{(3)}\cup\mathcal{C}_{L}^{(1)}\cup\left\\{(V_{L}^{(1)},V_{R}^{(3)})\right\\}=\mathcal{C}_{R}^{(3)}\cup\left\\{(v_{1},V_{R}^{(3)})\right\\},$

through reusing $\hat{V}_{R}^{(3)}$, we only need to sketch
$(v_{1},\hat{V}_{R}^{(3)})$ to compute $S_{2}L_{2}$, which only costs
$\Theta(smR+m^{2.5}R)$. Similarly, sketching each $L_{i}$ for $i\geq 2$ only
costs $\Theta(smR+m^{2.5}R)$, thus making the overall cost of sketching
$L_{1},\ldots,L_{N}$ being $\Theta(N(smR+m^{2.5}R))$.

###  F.3 Detailed algorithm and the overall computational cost

Algorithm 2 Sketched-ALS: Sketched ALS for CP decomposition

1: Input: Input tensor ${\mathcal{X}}$, initializations
${A}_{1},\ldots,{A}_{N}$, maximum number of iterations $I_{\text{max}}$

2: $G_{D}(L_{i})\leftarrow$ structure of the data
$L_{i}={A}_{1}\odot\cdots\odot{A}_{i-1}\odot{A}_{i+1}\odot\cdots\odot{A}_{N}$
for $i\in[N]$

3: $T_{i}\leftarrow$ contraction tree of $G_{D}(L_{i})$ for $i\in[N]$
constructed based on Section F.2

4: Build tensor network embeddings $S_{i}$ on $G_{D}(L_{i})$ and $T_{i}$ based
on Algorithm 1 for $i\in[N]$

5: Compute $\hat{R}_{i}\leftarrow S_{i}{X}_{(i)}^{T}$ for $i\in[N]$

6: for $t\in[I_{\text{max}}]$ do

7: for $i\in[N]$ do

8: Compute $\hat{L}_{i}\leftarrow S_{i}L_{i}$

9:
${A}_{i}\leftarrow\underset{{X}}{\arg\\!\min}\left\|\hat{L}_{i}X-\hat{R}_{i}\right\|_{F}^{2}$

10: end for

11: end for

12: return ${A}_{1},\ldots,{A}_{N}$

We present the detailed sketched CP-ALS algorithm in Algorithm 2. Here we
analyze the overall computational cost of the algorithm.

Line 5 yields a preparation cost of the algorithm. Note that we construct
$S_{i}$ based on Section F.2, where they share common tensors. Contracting
$S_{1}X_{(1)}^{T}$ yields a cost of $\Theta(s^{N}m)$. On top of that,
contracting $S_{i}X_{(i)}^{T}$ for $i\geq 2$ also only yields a cost of
$\Theta(s^{N}m)$, making the overall preparation cost $\Theta(s^{N}m)$.

Within each ALS iteration (Lines 7-10), based on Section F.2, computing
$S_{i}L_{i}$ for $i\in[N]$ costs $\Theta(N(smR+m^{2.5}R))$. For each
$i\in[N]$, line 9 costs $\Theta(mR^{2})$, making the cost of per-iteration
least squares solves $\Theta(NmR^{2})$. Based on Section F.1, a sketch size of
$m=\tilde{\Theta}(NR/\epsilon^{2})$ is sufficient for the least squares