Cost-efficient Gaussian tensor network embeddings for tensor-structured inputs
Authors: Linjian Ma
Edgar Solomonik
Venue: NeurIPS 2022 Accept (2022)
Keywords: tensor networks
randomized numerical linear algebra
non-convex optimization
tensor decomposition
tensor train

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 the optimality of an existing algorithm for tensor train rounding.


Cost-efficient Gaussian tensor network embeddings for tensor-structured inputs
Linjian Ma, Edgar Solomonik
Department of Computer Science, University of Illinois at Ürbana-Champars {1ma16, colomon2]@illinoii
Abstract
This work discusses tensor network embeddings, which are random matrices (S) with tensor network structure. These embeddings have been used to perform di- mensionality reduction of tensor network structured inputs x and accelerate appli- cations such as tensor decomposition and kernel regression. Existing works have designed embeddings for inputs æ with specific structures, such as the Kronecker product Khatri-Ras product, such that the computational cost for calculating Sa is efficient. We provide a systematic way to design tensor network embeddings general
consisting of Gaussian random tensors, such that for inputs with 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 sequence of sketching matrices. We provide sufficient condition to quantify the accuracy of such embeddings and derive sketching asymptotic cost lower bounds using em- beddings that satisfy this condition and have 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 linear dependence on the number of sketching dimensions the input. Assum- ing tensor contractions are performed with classical dense matrix multiplication algorithms, this algorithm achieves asymptotic cost within a factor O ((ym) 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 opti- mal sketching asymptotic cost. We apply our sketching analysis to inexact tensor decomposition optimization algorithms. We provide sketching algorithm for CP decomposition that is asymptotically faster than existing work in multiple regimes, and show the optimality of an existing algorithm for tensor train rounding.
Introduction
Sketching techniques, which randomly project high-dimensional data onto lower dimensional spaces while still preserving relevant information in the data [43], have been widely used in numerical linear algebra, including for regression, low-rank approximation, and matrix multiplication [50]. One key step of sketching algorithms is to design an embedding matrix S E Rmxx with m < n, such that for any input (also called data throughout the paper) R. the projected vector norm is (1 e)-close to the input vector, || |z = (1 + e) |)]|2// with probability at least 1 - (defined as (c, acccurree embedding throughout the paper), and the multiplication Sz can be computationally efficient. S is commonly chosen as random matrix with each element being an i.i.d. Gaussian variable when dense, random sparse matrix when is sparse, etc.
In this work, we focus on the case where x has a tensor network structure. tensor network [35] uses set of (small) tensors, where some all of their dimensions are contracted according some
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

pattern, to implicitly represent tensor. Tensor network structured data is commonly seen in multiple applications, including kernel based statistical learning [38. 51, 31]. machine learning and data mining via tensor decomposition methods [3, 46, 22, 46], and simulation of quantum systems [49, 27, 44, 15, 16]. Commonly used embedding matrices are sub-optimal for sketching many such data. For example, consider the case where I E R= is a chain of Kronecker products, I = 2: @ 8.... ...,, where E R for i E a computational cost of 9 ((ms"), ), and the exponential dependence on the tensor order N makes the calculation impractical when N or is large.
NJ. If S E Rmxx" is Gaussian matrix, the multiplication Sar has
The computational cost of the multiplication Sr can be reduced when S has a structure that can be easily multiplied with the target data. One example is when S has Kronecker product structure,
= S @ ... & SN and each S; E IRm xx, When x = Ø1 @ ..... @ N. Sx can then be calculated efficiently via ( ... @ (SNIN), ), reducing the cost to ON + m). Another example is when S has Khatri-Rao product structure, S (S1 o.. .SS) )" and each S; R Sr can then be calculated efficiently via (ST x1) *................... (N where * denotes the Hadamard product, which wwwooo-wtwwwooseeeeooeeeee
reduces the cost to mmNss.. However, 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- product embeddings to be (c, -a-ccure 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.
embedding matrices that can be
Existing works discuss tensor network embeddings with more efficient sketch size than Kronecker and Khatri-Rao product structure, such tensor train [41] and balanced binary tree [1]. In par- ticular, Ahle et al. [1] designed a balanced binary tree structured embedding and showed that the sketch size sufficient for (e, -aacuureee embedding can have only linear dependence on N. Using this embedding to sketch Kronecker product structured data yields 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 In this work, we design algorithms to efficiently sketch more general data tensor networks such that each dimension 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. In particular, we look at the following question.
Embedding
Data
For arbitrary data with a lensor network structure of interest, can we au- tomatically 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?
Figure 1: Illustration of target data and em- bedding. Blue edges have larger weights than the red edge.
Different from existing works [1, 17, 26, 29] that construct the embedding based on fast sketching techniques, including Countsketch [8]. Tensors- ketch [37], and fast Johnson-Lindenstral (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, 40J. This choice also enables us use simple computational model to analyze the sketching cost, where tensor contractions are performed with classical dense matrix multiplication algorithms. Note that a related work [29] builds tree tensor network embeddings based on Countsketch for getting low-rank tensor network approximation of an input tensor.
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 stud- ied [1, 10, 4]. Each one of these embeddings consisting of NE tensors be reduced to sequence of N₂ sketches (random sketching matrices). In Section 3, we show that if each of these sketches is (e/ Le/, -accuurae,, then the embedding is at least (e, o-accurate.
In Section 4, we provide an algorithm to sketch input data with an embedding that not only satisfies the (e, 8) accurate sufficient condition, but is computationally efficient and has low sketch size.

---

Given a data tensor network and one data contraction tree To, this algorithm outputs a sketching contraction tree that is constrained on Tp- This setting 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 [39, 25, 28]. 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 (c, 6) -accurate sufficient condition and only have one output sketch dimension, this algorithm achieves asymptotic cost within a factor of ((mm) of the lower bound, where m is the sketch size. When the input data tensor network structure is graph, the factor improves to (m35.375. In addition, when each tensor 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 To 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, CANDECOMPPPARAFAAE (CP) tensor decomposition [14, 13] and tensor train rounding [36]. We present a new sketching- al- ternating 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 (the length/number of elements in each dimension) of the input tensor. We also provide analysis on the recently intro- duced 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
We introduce some tensor network notation here, and pro- vide additional definitions and background in Appendix A. The structure of a tensor network can be described by an undi- rected hypergraph G (V, E, w). also called tensor diagram. Each hyperedge E E may be adjacent to either one or at least two vertices, and we refer to hyperedges with dangling end (one end not adjacent to any vertex) as uncontracted hy- peredges, and those without dangling end as contracted hyper- edges. We refer to the cardinality of a hyperedge as its number of ends. An example is shown in Fig. 2. We use w denote w(e) = log(s) is the natural logarithm of the dimension sizes represented by hyperedge e. For a hyperedge set E, we use wn( E) Eeer w=() to denote the weighted sum of the hyperedge set.
Σg Ainu
B
Figure 2: An example of tensor di- agram notation.
function such that for each e E E,
tensor network embedding is the matricization of tensor described by a tensor network, and each embedding can be described by S = =GGE, E), where G = (VE, EE. w) shows the embedding graph structure and E _ Eg is the edge set connecting data and the embedding. In this work we only discuss the case where Gg is graph, such that each uncontracted edge in Eg is adjacent to one vertex and contracted edge in Eg is adjacent to two vertices. Let Ej C. Eg be the subset of uncontracted edges, S is a matricization such that uncontracted dimensions in E are grouped into the column of the matrix, and dimensions in Ej are grouped into the row. We use N = E to denote the order of the embedding, and use GD = (Vp, Ep. w) to represent the data tensor network structure, and use G = (Gp, Gx) to denote the overall tensor network structure.
cxp(w((,)) denotes the output sketch size. We
Within the tensor network G (V, F, w²) the contraction between two tensors represented by U1 Ug E V is denoted by (v, U.). The contraction between two tensors that are the contraction
3

---

outputs of W; C V. W C V, respectively, is denoted by (W,, W) A contraction tree on the tensor network G = (V. w) is a rooted binary tree Tn (VB. EB) showing how the tensor network is fully contracted. Fach vertex in VB can be represented by subset of the vertices, W S V, and denotes the contraction output of W. The two children of W, denoted as W1 and W2, must satisfy W1 U 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.
Sufficient condition for accurate embedding
We consider the scenario where the data tensor networks have a general hypergraph structure, while the em- beddings have graph structure, thus some embeddings, such as those with a Khatri-Raa product structure [41, 91. not considered in this work. Such embeddings can be linearized to sequence of sketches. Let Næ
A
Figure 3: Illustration of embedding linearization. Each gray vertex denotes tensor of the embedding, each white vertex denotes an identity matrix, and each white box denotes a permutation matrix.
VEl denote the number of vertices in the embedding, in each linearization, each vertex is given an unique index i E [Ng]' and denoted Vg. The ith tensor is denoted by A, and A, denotes its matricization where we combine all uncontracted dimensions and contracted dimensions connected to A, with j > i into the row, and other di- mensions into the column. The embedding can then be represented as a chain of multiplications, MNg PNg ... P1, where M, the Kronecker product of identity matrices with A, for i E [Ne], and P; is a permutation matrix. We illustrate the linearization in Fig. 3 using fully con- nected tensor network embedding. We show in Theorem 3.1 a sufficient condition for embeddings to be (e. 8) -accuraae.
Theorem 3.1 ((e, ac-uurae sufficient condition), Consider a Gaussian tensor network embedding where there exists a linearization such that each A, for i [Ng] has row size (NNN (og(1))1/)/)) ()g(1/)/e)) (2). Then the tensor network embedding is (c, aaccurate
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,P, satisfy the strong LVVN 8)-L -JL moment property so S satisfies the strong (c, -)- moment property. This implies the embedding is (c, acccurate
Theorem 3.1 is a sufficient (but not necessary) condition for constructing (c, -accurate embedding. It also implies that specific tree embeddings are (c, 5) -accurate, as we show below.
Corollary 3.2. Consider Gaussian embedding containing a tree tensor network structure, where there is only one output sketch dimension with size m = O NE log(1 log(1/8)/2)) and each dimension within the embedding has size m. Then the embedding (e. -)accuratee.
Proof. Consider the linearization such that vertices are labelled based on the reversed ordering of breath-first search from the vertex adjacent to the edge associated with the output sketch dimension. Each A₁ has row size m (NN log(1/8)fe²) thus the embedding satisfies Theorem 3.1. O
One special case of Corollary 3.2 is the tensor train [36] (also called matrix product states (MPS) [45]) embedding, where the embedding tensor network has a ID 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, 42], quantum physics [44], high-dimensional data analysis [20, 21] and machine learning [6. 47, 33]. Since the tensor train embedding contains N vertices, Corollary 3.2 directly implies that sketch size of m = O N log(1/8)/e² is sufficient for the MPS embedding to be (c, acccuraee This embedding has already been used in applications including tensor train rounding [10] and low rank approximation of matrix product operators [4].
'hrouuhoou the paper we [N] denote {L, .L...,AA N).

---

Note that the tensor train embedding introduced in this work and [10] adds an output sketch dimen- sion to the standard tensor train, and restricts the tensor train rank be the sketch size m. This is different from the recent work by Rakhshan and Rabusseau [41], where they construct an embed- ding consisting of m independent tensor trains, each one with a tensor train rank of R. A sketch size upper bound of m @ (1/22 (1 2/ R) log" (1/8)) is derived for that embedding to be (e, 0)- -cccurate. However, this bound has an exponential dependence N.
4 A sketching algorithm with efficient computational cost and sketch size
We find Gaussian tensor network embeddings Ge that both have efficient sketch size and yield effi cient computational cost. We are given a specific data tensor network GD that implicitly represents matrix M E |R*1...... xt, and want to sketch the row dimension of the matrix. We assume that size of each dimension to be sketched, s; for i E [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 Gaussian embedding Ge satisfying the following properties.
GE E Gle.e), where ((+.6) contains all embeddings not only satisfying the (e, 8)-acuraeee sufficient condition in Theorem 3.1, but also only have one output sketch dimension (|Eil = 1) with size m @ [ log(1/6)/22) This guarantees that the embedding is accurate and the output sketch size is linear w.r.t. the number of vertices in Gg- Note that although the data can be hypergraph, the embeddings considered in G((,5) are defined on graphs
To fully contract the tensor network system (GD, Gg). this embedding yields contraction tree with the optimal asymptotic contraction cost under a fixed data contraction tree. The data contrac- tion 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,
s.t. GE E g((,,), TG(GD) TB(GD, GE), min min Ca(Ta(GD,GG)) Ge TB
(4.1)
where TB (G Gg) denotes a contraction tree of the tensor network (G GE), C. denotes the asymptotic computational cost, and D) C TD GE) means the contraction tree TB is constrained on To (the detailed definition and simple example are shown in Definition 1 and Appendix B.I, respectively).
Definition (Constrained contraction tree). Given G = (Gg: Gp) and a contraction tree To of Go. the contraction tree TB for constrained on To if for each contraction (A, B) E To, there must exist one contraction (A, B) E TB, such that Á n Vp= = A and VD = =B
Algorithm We propose an algorithm to sketch tensor network data with an embedding containing two parts, a Kronecker prod- uct embedding and an embedding containing a binary tree of small tensor networks. The embedding is illustrated in Fig. 4. The Kro- necker product embedding consists of N Gaussian random matrices and is used to reduce the weight of each edge in E, the set of edges 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 F. The em- bedding with a binary tree structure may not be a binary tree tensor network, since each tree vertex is not restricted to represent one ten- sor. The binary tree is chosen to be consistent with the dimension tree of the data contraction tree Ty. which is a directed binary tree showing the way edges in E are merged onto the same tensor in Tp. The detailed definition of dimension tree is in Appendix B.I.
Go
Figure 4: Illustration of the embedding. The black box includes the Kronecker prod- uct embedding and the orange box includes the embedding containing a binary tree of small tensor networks.
We first introduce some notation before presenting the algorithm. Consider given input data tensor network GD = (VD, En, w) and its given data contraction tree, To. Below we let F. = (e1, e,....,,..,... ) } to denote the edges to be sketched. Let ND = |VDl. Based on the definition we have N < ND and To contains ND contractions. Let one contraction path
5

---

of To, which is a topological sort of the contractions in Tú. be expressed as
{(U1, Vi),... (UNg-1, VND-1)),
(4.2)
where (U,, Vi)) represents the contraction of two intermediate tensors represented by two sub- set of vertices Ug, Vi C VD. The No 1 contractions can be categorized into N sets, S, I, as follows, and these sets are illustrated with an example in Appendix C.
Consider contractions (U,, Vi) such that both U, and V; are adjacent to edges in E. S contains all contractions with this property.
Consider contractions (U,, Vi) such that the only edge in that is adjacent to the contraction output is ej, E(U U V.) {e,). We let D(e,) contains contractions with this property. When D(e,) is not empty, we let (e,) C V represent the sub network contracted by D(e,). When D(e;) is empty, we let ((e)) Ui, where by is the vertex in the data graph adjacent to Ej- The remaining contractions in the contraction tree include (U,, Vi) such that both U, and Vi are not adjacent to F, and contractions where U; or Vi is adjacent to at least two edges in F, and the other one is not adjacent to any edge in E.. We let I contain these contractions.
The sketching algorithm is shown in Algo-
rithm 1, and the details are as follows,
Algorithm 1 Sketching algorithm
1: Input: Input data tensor network Go data
One matrix in the Kronecker product embedding is used to sketch the sub data network X(ez). which guarantees
contraction tree To expressed in (4.2)
2: for each e; E E do
that two sketch dimensions to be merged onto one tensor will both have size ON log(1/))/E=) D(e,) 0, we directly sketch X(e,) = 2 using an embedding matrix. For the case where Dee,) * V. we select k(e,) e Dee,) and apply the sketching matrix during the contraction (Un(es), Ve(ez))- The value of k(ey)) is selected via an exhaustive search over all (D(e;)l contractions, so that sketch- ing (ee) has the lowest asymptotic cost.
3: // Sketch with Kronecker product embedding
4: W < contract and sketch X(e,)
5: Replace the contraction output of ((e)) by
For the case where
W in To
6: end for
7: for each contraction (U., Vi) in S U I do
8: if i E S then
9:
// Sketch with binary tree embedding
10:
W; + contract and sketch (U,, Vi) (de-
tailed in Appendix C.1)
11:
else
12:
W; + contract(UU, Vi)
One small tensor network (denoted as Z,) represented by binary tree vertex in the binary tree structured embedding is used to sketch the contraction (U,, V.) when i S, which means that both U; and Vú are adja- cent to E. Let Ü., V2 denote the sketched U, and Vi formed in previous contractions in the sketching contraction tree TB, such that U,VVD= = U4 and Vn = Vi, the structure of Z, determined so that the asymptotic cost sketch (Ū., V.) is minimized under the constraint that Z; is in glt/vN.5), so that it satisfies the (e/vN, a)aacureeee sufficient condition and only has one output dimension. In Appendix C. we provide an algorithm to construct Z, containing 2 tensors, so that the output sketch size of Z, is O(N ()g()/))/²²)
13:
end if
14: Replace the contraction output of (U,, Vi)
by W, in To
15:
end for
16: return WND-1
The total computational cost of Algorithm I consists of three components: the cost of determining the embedding structure, the cost of determining the sketching contraction tree, and the cost of sketching. The first two components are O(N) and are therefore negligible in comparison to the cost of sketching.
Analysis of the algorithm The embedding constructed during Algorithm 1 contains (NN ver- tices, and the output sketch size is m O (1))))))22). Therefore, the sketching result both has low sketch size and is (c, -aacuuuree Below we discuss the optimality of Algorithm 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 E.
Theorem 4.1. For data tensor networks where each vertex is adjacent to an edge in F,, the asymp- totic cost of Algorithm I is optimal w.r.t. the optimization problem in (4.

---

We show the detailed proof of the theorem above in Appendix D.I. 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- ALS algorithm for CP tensor decomposition.
Note that the embedding in Algorithm may not be tree embedding. As we will show in Section 6, for cases including sketching a Kronecker product data, Algorithm I 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 E, Algorithm 1 may not yield the optimal sketching asymptotic cost, but is within factor of at most O( ((ym) from the cost lower bound. Below we show the theorem, and the detailed proof is in Appendix D.2.
Theorem 4.2. For any data tensor network GD. the asymptotic cost of Algorithm (denoted as c) satisfy Olym Copt), where Cops is the optimal asymptotic computational cost for the optimiza- tion problem (4.1) and (og))/// When GD is a graph, (m Capt).
Efficiency of tree tensor network embedding We discuss cases where tree tensor network em- beddings 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 [41, 10, 4J. 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,, Vi) with S, such that both U3 and V; are adjacent to edges in 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 GD with each veriex adjacent an edge to be sketched and its given contraction tree To. If each contraction in To 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 is more efficient. For example, when the data is vector with Kronecker product structure, sketching with Algorithm yields a cost of ( sym + Nm255) and sketching with a tree embedding yields cost of N
N
8ym + Nm!). We present the detailed analysis in Appendix C.2 and Appendix E. O j== O
5 Applications
Alternating least squares for CP decomposition On top of Algorithm 1, we propose a new sketching-baset ALS algorithm for CP tensor decomposition.
Throughout analysis we as- sume the input tensor is dense, and has order N and size x ... 8, and the CP rank is R. The goal of CP decomposition is to minimize the objective function, f(AI...., Ax)
|x - A(sr)) AN r) || F' where A, E R for i [N] are called factor ma- trices, and X' denotes the input tensor. In each iteration of ALS, N subproblems are solved quentially, and the ith subproblem can be formulated as A, = arg ain - R& where T, = A₁ S....... ........... A, ② A @-... ... .Q A consists of a chain of Khatri-Rao products, and R. ( is the transpose of ith matricization of X.
Multiple sketching based based randomized algorithms are proposed to accelerate each subproblem in CP- ALS [5, 24, 30]. The sketched problem can be formulated as A; = argmin S.L.AT - R, 1|
A
where S; is an embedding. The goal to design S, such that the sketched subproblem can be solved efficiently and accurately. In Table 1, we summarize two state-of oftte-of-the-art sketching methods for CP-ALS. Larsen and Kolda [24] propose a method that sketches the subproblem based on (approx- imate) leverage score sampling (LSS), but both the per-iteration computational cost and the sketch size sufficient for (e, -)accure solution has an exponential dependence on N, which inefficient for decomposing high order tensors. Malik [30] proposes method called recursive leverage score
7

---

sampling for CP-ALS, where the embedding contains two parts, S; St,. and S4.2 is an em- bedding with a binary tree structure proposed in [1] with sketch size @ /6), and St performs approximate leverage score sampling on S1,2 with sketch size @(NR/e)) This sketching method has a better dependence on R in terms of per-iteration cost, For both algorithms, the preparation cost shown in Table denotes the cost to go over all elements in the tensor and initialize factor matrices using randomized range finder. As is shown in [24, 26], randomized range finder based initialization is critical for achieving accurate CP decomposition with sampling-bas -bsed sketched ALS.
CP-ALS algorithm
Per-iteration cost
Sketch size (m²)
Prep cost
Standard ALS
0(s R)
LSS [24]
((N(H* + 1/2)
6(R
((s*)
Recursive LSS [30]
((N + NsH /c)00)
((N /0) and ((R/(c8))
((s*)
Algorithm 1
(NN /e" + ))))
((NR/E))
(s m)
Table 1: Comparison of asymptotic algorithmic complexity between standard CP-ALS, CP-ALS with leverage score sampling (LSSS), CP-AL-S with recursive leverage score sampling (recursive LSS), and sketching CP-ALS with Algorithm 1. 'hee third column shows the sketch size sufficient for the sketched linear least squares to be (1 + -)accuraate with probability at least - 8. By using é, we neglect logarithmic factors, including log R) and log(1/6).
We propose a new sketching algorithm for CP-ALS based on Algorithm 1. Each St is generated on top of the data tensor network L; and its given data contraction tree T., with the sketch size being ē(N R/ The contraction trees T. for i [N] are chosen in fixed alternating order, such that the resulting embeddings S; for i E [N] have common parts and allow reusing contraction intermediates. We leave the detailed analysis in Appendix F.2.
m (N llg((/))
é(N ( 1.5 g3.5 + We present the detailed sketching algorithm and its cost analysis in Appendix F.3. When performing low-rank CP decomposition with s >> RI.5 and is not too small so that dominated by the term @ & /e/e"), which is (e/ = ((N R) times better than the per- iteration cost of the recursive LSS algorithm. For another case of a high-rank CP decomposition with R >> s. which happens when one wants a high-accurace CP decomposition of high order tensors, the per-iteration cost of our sketched CP-ALS algorithm is dominated by the term ( 123.5 fe), and the cost ratio between this algorithm and the recursive LSS algorithm is ((N1-58/ 1//1-58/(e" (/(e R)..)) For this case, our algorithm is only preferable when N 5//e is not too large compared to RO.5
The ALS per-iteration cost is ( ((N(m2 R++ sm)R)
O()? the per-iteration cost
Although our proposed sketching algorithm yields better per-iteration asymptotic cost in multiple regimes compared to existing leverage score based sketching algorithms, some preparation compu- tations are needed sketch right-hand-sides R, for i E [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 com- parison 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 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. The standard tensor train rounding algorithm [36] 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 (NNRR²). Recently, [10] has introduced a randomized rounding algorithm called " "Randomize-then-O0 Orrtooooeeee-- 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 quence of truncated SVDs on top of SX. The sketch size m of S is r plus some constant, and is assumed be smaller than R. The bottleneck to compute SX,, which costs O m))
2 As is shown in [26]. in practice, setting to be 0.1-0.2 will result in accurate sketched least squares with relative residual norm error less than 0.05.
8

---

We can recast the problem finding an embedding satisfying the linearization sufficient condi- tion with sketch size m, such that the asymptotic cost of computing SXX 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 (R thus the sketching algorithm in [10] attains the asymptotic cost lower bound and is efficient. Note that sketching with Algorithm yields the same asymptotic cost, despite using a different embedding.
Experiments
We conduct multiple experiments to demonstrate the efficacy of our proposed embeddings. Below we first justify the theoretical analysis in Theorem 4.1 and Theorem 4.3 via testing the sketching performance on tensor train inputs and Kronecker product inputs. We then perform experiments to demonstrate that the accuracy our proposed sketching algorithms is comparable to that of state-of- ahe sketching techniques for CP decomposition and tensor train rounding. Our experiments are carried out on Intel Core 17 2.9 GHz Quad-Core machine using NumPy [34] routines in Python.
Sketching tensor train and Kronecker product inputs We compare the performance of gen- eral tensor network embedding used in Algorithm 1 (called TN embedding), tree embedding dis- cussed in Theorem 4.3, and the baseline, tensor train embedding [10], in sketching tensor train input data Fig. 5. The input tensor train data has order 6, and the dimension size is 500. We test the sketching per- formance under different tensor train ranks. For a given rank, we randomly generate 25 different in- puts, with each element in each tensor being an ii.d. variable uniformly distributed within [0, 1]. Additional experiments with Gaussian-distriuuted input tensor train data are presented in Appendix H. For each input æ and a spe- cific 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
TN embedding
120
1o-10
+
Tansar train
Tree ambadding
Sketch size
100 80
60
1c+7
te+8
20
255
125
Rank
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.
1o+5.
1e+8
1e+4
Sketch 0++
TN embedcing
16+7
Tree ambestiing
Tonsor train
1c+5
Khatri-Rao
1et2
Tensor order
Tensor order
Figure 6: Results for sketching Kronecker product inputs.
are within 0.2, ||Salle < 0.2. We also calculate the number of floating point operations (FI.OPs) T|=||
for computing Sz 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 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.
We also compare the performance of TN, tree, and two baselines proposed in [41], tensor train and Khatri-Re -ho product embeddings, in sketching Kronecker product inputs in Fig. 6. Each dimension size of the Kronecker product input fixed to be 1000, and we test the sketching performance under different tensor orders. For each input z and specific embedding structure, we record the smallest sketch size such that its relative sketching error is within 0. 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.
CP decomposition and tensor train rounding We perform experiments to demonstrate that the accuracy of our proposed sketching methods for CP-ALS and tensor train rounding is comparable to that of state-of-the-art sketching techniques. For both applications, we evaluate accuracy based on the final fitness f for each algorithm, defined f= - where T is the input tensor I|
and T is the reconstructed low-rank tensor.
For CP-ALS, we conduct experiments on Time-Lapse hyperspectral radiance im- age [32], which is a 3-D tensor with di- mensions of 1024 x 1344 x 33. This in- put data is used to demonstrate the applica- bility of our method in real-world scenar- ios. Standard CP-ALS, sketched CP-ALS using Algorithm 1,, and sketched CP-ALS with approximate leverage score sampling (LSS) [24] are compared. The output CP decomposition fitness under varying CP ranks and sketch sizes is shown in Ta- ble 2. As can be seen, sketching with Al- gorithm yields comparable fitness with the algorithm that sketches with approxi- mate leverage score sampling- Note that
CP rank
2
5
10
Sketch size
25
64
100
CP-ALS
0.737
0.804
0.838
LSS [24]
0.739
0.773
0.789
Algorithm
0.737
0.770
0.801
Table 2: Comparison of the final fitness of different CP decomposition algorithms under different CP ranks and sketch sizes. 10 ALS iterations are performed for all algorithms before the final fitness are calculated.
TT rounding rank
4
11
20
Sketch size
9
16
25
TT-SVD [36]
0.734
0.862
0.944
0.981
the computational cost of Algorithm 1 is lower that LSS especially when the CP rank is low and the tensor dimension is large, as stated in Table 1.
TT embedding [10]
0,573
0.757
0.882
0.951
Algorithm
0.527
0.761
0.866
0.948
Table 3: Comparison of the final fitness of different tensor train rounding algorithms under different tensor train rounding ranks and sketch sizes.
We use 9 images from the Time-Lapse hy- perspectral radiance image dataset for ten- sor train rounding, and reshape the input data to an order 6 tensor with size 9 x 32 x 32 x 28 x 48 x 33. We use the Tensorlyy [23] library to truncate the input tensor to a tensor train with a rank of 30. On top of this tensor train, we evaluate the accuracy of various approaches, including tensor train SVD [36], randomized algorithm using tensor train embedding [10], and randomized algorithm us- ing Algorithm 1. The fitness of the truncated tensor trains are displayed in Table 3 for variety of rounding rank thresholds and sketch sizes. As can be seen, sketching with Algorithm has com- parable accuracy with the baseline algorithm (sketching with tensor train embedding). In addition, both sketching algorithms also have similar complexity as is analyzed in Section 5.
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 efficiently sketch such data using Gaussian embeddings that can be linearized into sequence of sketching matrices and have low sketch size. Our sketching method is then used to design state-of-the-ar 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. 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 eircuits. We also leave the high perfforeffre implementation of the algorithm for general tensor networks as future work.
Acknowledgments
This work is supported by the US NSF OAC via award No. 1942995.
10

---

References
[1] D. Ahle, M. Kapralov, J. B. Knudsen, R. Pagh, A. Velingker, D. P. Woodruff, and A. Zandich. 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 Chazelle. Approximate nearest neighbors and the fast Johnson Sechnson-Lindeenn Lindenstrauss transform. In Proceedings of the thirty-eighth annual ACM symposium on Theory of comput- ing. 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-122221144, 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 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, 3105):140-1187, 2009.
[7] 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 Inter- national 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, 1703)11703 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 drXiv:2110.043933 2021.
[11] C. Damm, M. Holzer, and P. McKenzie. The complexity of tensor calculus. computational complexity (1--)):54889 2002.
[12] S. Dolgov, B. N. Khoromskij, and 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, 3416)43016--3033, 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 Moller-Plesset perturbation theory. The Journal of chemical physics, 37444)044103, 2012.
[16] Hummel, T. Tsatsoulis, and A. Grüneis. Low rank factorization of the Coulomb integrals for periodic coupled cluster theory. The Jourmal of chemical physics, 146(12):124100 2017.
[17] R. Jin, G. Kolda, and Ward. Faster products. arXiv preprint arXiv: 1909.0409. 2019.
transforms via Kronecker

---

[18] D. Kane, R. Meka, and J. Nelson. Almost optimal explicit Approximation. Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages
families, In
Springer, 2011.
[19] D. M. Kane and J. Nelson. Sparser Johnson-Lindeestraass transforms. Journal of the ACM (JACM), 61(1):1-23, 2014.
[20] S. Klus, P. GelB, S. Peitz, and Schütte. Tensor-based dynamic mode decomposition. Non- linearity, 31(79)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:/5/2.059977 2015.
[22] T. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM review, 5 51(3):455-500 2009.
[23] J. Kossaifi, Y. Panagakis, A. Anandkumar, and M. Pantic. Tensorly: Tensor learning in python. arXiv preprint
2016.
[24] B. W. Larsen and T. G. Kolda. Practical leverage-based sampling for low-rank tensor decom- position, arXiv preprint arXiv:2006. 16438, 2020.
[25] L. Ma and E. Solomonik. Efficient parallel CP decomposition with pairwise perturbation and multi-sweep dimension tree. In 202/ IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 412 421. IEEE, 2021.
[26] L. Ma and E. Solomonik. Fast and accurate randomized algorithms for low-rank tensor de- compositions. In Advances in Neural Information Processing Systems, 2021.
[27] L. Ma and C. Yang. Low rank approximation in simulations of quantum algorithms. Journal of Computational Science, page 101561, 2022.
(28) L. 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.
[29] A. V. Mahankali, D. P. Woodruff, and Z. Zhang. Low rank approximation for general tensor networks. arXiv preprint arXiv:2207.074177 2022.
[30] O. A. Malik. More efficient sampling for tensor decomposition. arXiv preprint arXiv:2110.07611, 2021.
[31] M. Meister, T. Sarlos, and D. P. Woodruff. Tight dimensionality reduction for sketching low degree polynomial kernels. In NeurIPS, pages 9470-9481, 2019.
[32] S. M. Nascimento, K. Amano, and H. Foster. Spatial distributions of local illumination color in natural scenes. Vision research, 120:39 44, 2016.
[33] A. Obukhov, M. Rakhuba, A. Liniger, Z. Huang, S. Georgoulis, D. Dai, and L. Van Gool. Spectral tensor train parameterization of deep learning layers. International Conference on Artificial Intelligence and Statistics, pages 3547-3555. PMLR, 2021.
[34] T. Oliphant. A guide to NumPy, volume 1. Trelgol Publishing USA, 2006.
[35] R. Orús. A practical introduction to tensor networks: Matrix product states and projected entangled pair states. Annals of Physics, 349:117-158, 2014.
[36] I. V. Oseledets. Tensor-train decomposition.
SIAM Journal Scientific Computing,
33(5):2295-23) 2017,2317,22222 2011.
[37] R. Pagh. Compressed matrix multiplication. ACM Transactions on Computation Theory (TOCT), 5(3):1-17,2011
[38] N. Pham and R. Pagh. Fast and scalable polynomial kemnlss via explicit feature maps. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 239-247, 2013.
12

---

[39] A.-H. Phan, P. Tichavský, and A. Cichocki. Fast alternating LS algorithms for high order CANDECOMPIPARAFAC tensor factorizations. IEEE Transactions on Signal Processing, 61(19):4834-488 4846, 2013.
[40] M. Pilanci and M. Wainwright. Randomized sketches of convex programs with sharp guar- antees. IEEE Transactions on Information Theory, 61(9):5096-5) 5115,,115111101 2015.
[41] B. Rakhshan and G. Rabusseau. Tensorized random projections. International Conference on Artificial Intelligence and Statistics, pages 3306-3316. PMLR, 2020.
[42] 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.
[43] 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.
[44] U. Schollwöck. The density-matrix renormalization group. Reviews of modern physics, 77(1):259, 2005.
[45] U. Schollwöck. The density density-matrix renormalization group in the age of matrix product states. Annals of physics, 326(1):96-19)) 192, 2011.
[46] N. D. Sidiropoulos, L. De Lathauwer, X. Fu, K. Huang, E. E. Papalexakis, and C. Falout- sos. Tensor decomposition for signal processing and machine learning. IEEE Transactions on Signal Processing, 65(13):355133582 2017.
[47] E. Stoudenmire and D. J. Schwab. Supervised learning with tensor networks. Advances in Neural Information Processing Systems, 29, 2016.
[48] L. G. Valiant. The complexity of computing the permanent. Theoretical computer science, 8(2):189-201, 1979.
[49] G. Vidal. Efficient classical simulation of slightly entangled quantum computations. Physical review letters, 11714),44790, 2003.
[50] D. P. Woodruff. Sketching as tool for numerical linear algebra. Theoretical Computer Sci- ence, 1011-2)11157, 2014.
[51] D. Woodruff and A. Zandieh. Leverage score sampling for tensor product matrices in input sparsity time. arXiv preprint arXiv.2202.04515. 2022.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The limitations (assumptions in our theoretical analysis) are summarized multiple places throughout the paper, includ- ing Section and Section
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] Our work focuses on fast sketching techniques for numerical linear algebra and there is no direct potential negative societal impacts. 2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] These are stated throughout the paper, including Section 1, Section and sections presenting the detailed theory (Section and Section 4).
13

---

(b) Did you include complete proofs of all theoretical results? [Yes] Detailed proofs are presented in the appendix.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] Error bars are reported in Fig. and Fig. 6.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] The computational resources used shown in the first paragraph of Section 6.
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We use the NumPy library for experiments and is cited in the paper.
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [Yes] Our code is included in the supplemental materials.
(d) Did you discuss whether and how consent was obtained from people whose data you'l re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "kl_qUJOM6Kd", "reviewer": "Reviewer_bo7e", "summary": "This paper investigated an efficient sketching method for embedding the tensor with tensor network (TN) structures into lower-dimensional spaces. Compared with the existing works, the main contribution of this paper includes the points as follows:\n\n- The authors established a systematic framework regarding how to sketch a TN with a lower-dimensional representation.\n- The authors carefully discussed the computational cost of the proposed method with necessary proofs for demonstrating the efficiency.\n- Two potential applications are introduced: a) ALS-CP algorithm; and b) tensor train rounding algorithm.", "questions": "1. As shown in Figure 4, the embedding network is a  binary tree-structured, of which the vertices are repeatedly represented by a small TN. How do you determine the structure (e.g., bond dimension, network topology) for these small TNs? What happens if another topology is applied as an alternative?\n2. Could you give more interpretation, such as an understandable example, for Definition 1, the constrained contraction tree?\n3. It would be appreciated if the authors can give more interpretation about the Defs for $D(e_1)$, $\\mathcal{S,I}$ given in lines 241-250.\n4. Regrading the computational cost, suppose the data TN itself is contractible, meaning that the contraction cost is polynomial to the tensor dimension, I am wondering if the whole sketching of the proposed method is contractible as well? In other words, is the contractibility preserved under sketching?\n5. What is the difference between #P-complete and #P-hard? Are they equivalent? \n6. In line 398, why are the entries of the tensor drawn from the uniform distribution, rather than Gaussian?\n7. If possible, could you evaluate the sketching dimension (or compression ratio) numerically with varying the parameter $\\epsilon$ in a smaller range? Although the authors mentioned that the setting of $\\epsilon$ to be 0.1-0.2 might be good, I think it depends on the specific task.", "limitations": "The main limitation of this work is that the proposed method seems only to work superiorly when the data TN is very low-rank. It might not be suitable for most tasks in practice.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n- (originality) This work reveals the potential advantage regarding of how the inherent TN structure can be leveraged to improve the sketching performance.\n- (originality) The joint discussion of the effective sketching with computational cost (modeled by the contraction tree) is very interesting.\n- (quality) The theoretical discussion of the paper on complexity analysis is remarkable.\n\n**Weaknesses:**\n\n- (clarity) The paper is relatively well written, but the introduction of the algorithm details (sec. 4) is very hard to follow, even though I carefully go through the appendix. For example, the meaning of the letter U in Eq. (4.2) is not clear. I finally found its definition in the appendix but it should be well defined in the manuscript.\n- (significance) A fundamental assumption of the work — the TN ranks should be smaller than the mode dimensions — seems not reasonable in practice. It might be true for some tensor decomposition models such as CP and Tucker for lower-order tensors. In the sense of TN, one typically has to be faced in practice with lower mode dimension (only 2 or 3) but higher ranks (e.g., 100). In this case (also acknowledged by the authors in the paper), the improvement by the proposed method becomes not so significant. The numerical results in the paper also verify this point.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "F1h__Iu71M5", "reviewer": "Reviewer_QwJS", "summary": "This paper discussed the tensor network embedding. Specially, they focus on the problem to derive a sequence of sketching matrices. They generalized the embedding accuracy in Theorem 3.1, w.r.t the sketch size of the matrix. They later proposed an efficient sketching algorithm which enjoyed batter per-iteration cost than previous methods.  ", "questions": "Though most questions are in weakness. I do curious that, Is there a good way to assume the hypergraph structure of the tensor network embedding?\n\n", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The theoretical analysis is strong. Especially theorem 3.1 which discussed the accuracy of the tensor network embedding.\n2. The proposed sketching method has less computational cost per iteration.\n3. This framework showed broad application on different tensor decompositions like CP decomposition and tensor train embedding.\n\nWeaknesses:\n1. The theoretical part of this paper discussed a very general tensor network embedding rooted in the hypergraph presentation. But in the later part, they barely discussed it. As for me, such arrangement is quite confusing and disconnected. \n2. This paper is more focused on the sketching size. Following the hypergraph setting, the graph structure is very important to the embedding. Currently the author assumes the graph structure is given, but most of times, the structure is unknown. The paper did not further discuss that.\n3. The computational cost is efficient on per-iteration level. It still relies on exhaustive search. The overall computational cost can not be effectively measured.\n4. Experimental part is locking. The author only conducted general comparison in algorithm 1, but did not show experimental results with baseline methods.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-sqntrDjLOo", "reviewer": "Reviewer_eUJi", "summary": "This paper discusses a sketching method for tensor network (TN) structured input data. Unlike previous methods mainly focusing on specific TN structures of the input data, this paper considers more general structures. To alleviate the exponentially large sketching size, the authors impose TN structure on the coefficients. Theoretical guarantees are provided. Finally, the authors also present two applications of the proposed model, including CP-ALS and TT-rounding.\n\nFor empirical results, they conducted several synthetic data analyses to justify the theoretical results.\n", "questions": "See above.", "limitations": "The authors addressed some limitations. I think one limitation is that they should show some real applications to show the usefulness of the proposed model.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. While previous related works focusing on specific input structure, this work studies a sketching algorithm for general TN structures. This may be useful for more applications. It also improves studies in such fields.\n\n2. The authors also present some theoretical results, which may be beneficial to future work.\n\n3. Based on the proposed algorithms, the authors improve the CP-ALS and TT-rounding algorithms, which are two popular tensor decomposition algorithms used in many applications. So the proposed model may have impacts on potential applications.\n\n\nWeaknesses\n\n1. The authors conducted several synthetic analyses to justify the theoretical results. However, I think it’s better to also include some real data experiments to show the usefulness of the proposed model.\n\n2. The authors presented two applications of the proposed algorithm, i.e., CP-ALS and TT-rounding. However, they did not conduct experiments on these two applications. I think it is very interesting to show how these algorithms perform in experiments.\n\n3. In this work, the authors aim to study sketching for input data of general TN structure. However, in the experiments, they only used TT and Kronecker structures, both of which are very simple TN structures. Did the authors conduct experiments on more general TNs?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept