Error Analysis of Tensor-Train Cross Approximation
Authors: Zhen Qin
Alexander Lidiak
Zhexuan Gong
Gongguo Tang
Michael Wakin
Zhihui Zhu
Venue: NeurIPS 2022 Accept (2022)

Abstract: Tensor train decomposition is widely used in machine learning and quantum physics due to its concise representation of high-dimensional tensors, overcoming the curse of dimensionality. Cross approximation---originally developed for representing a matrix from a set of selected rows and columns---is an efficient method for constructing a tensor train decomposition of a tensor from few of its entries. While tensor train cross approximation has achieved remarkable performance in practical applications, its theoretical analysis, in particular regarding the error of the approximation, is so far lacking. To our knowledge, existing results only provide element-wise approximation accuracy guarantees, which lead to a very loose bound when extended to the entire tensor. In this paper, we bridge this gap by providing accuracy guarantees in terms of the entire tensor for both exact and noisy measurements. Our results illustrate how the choice of selected subtensors affects the quality of the cross approximation and that the approximation error caused by model error and/or measurement error may not grow exponentially with the order of the tensor. These results are verified by numerical experiments, and may have important implications for the usefulness of cross approximations for high-order tensors, such as those encountered in the description of quantum many-body states.

Error Analysis of Tensor-Trail Cross Approximation
Zhen Qin Ohio State University qin. wew.666.osu.eee edu
Alexander Lidiak
Zhexuan Gong
Colorado School of Mines alidiakemines.ee edu
Colorado School of Mines gong@mines edu
Gongguo Tang University of Colorado gongguo. wang@coloraaeeeoo edu
Michael B. Wakin
Zhihui Zhu" Ohio State University zhu 34408osu. edu
Colorado School of Mines mwakin@mines, edu
Abstract
Tensor train decomposition is widely used in machine learning and quantum physics due to its concise representation of high-dimensional tensors, overcoming the curse of dimensionality. Cross approximation -oriiiiaiioooiiiillllllyl developed for representing a matrix from set of selected rows and columns-ai is an efficient method for constructing tensor train decomposition of tensor from few of its entries. While tensor train cross approximation has achieved remarkable performance in practical applications, its theoretical analysis, particular regarding the error of the approximation, is so far lacking. To our knowledge, existing results only provide element-wise approximation accuracy guarantees, which lead very loose bound when extended to the entire tensor. In this paper, we bridge this gap by providing accuracy guarantees terms the entire tensor for both exact and noisy measurements. Our results illustrate how the choice of selected subtensors affects the quality of the cross approximation and that the approximation error caused by model error and/or measurement error may not grow exponentially with the order the tensor. These results are verified by numerical experiments and may have important implications for the usefulness of eross approximations for high-order tensors, such as those encountered the description quantum many-body states.
Introduction
As modern big datasets typically represented in the form of huge tensors, tensor decomposition has become ubiquitous across science and engineering applications, including signal processing and [3], chemometrics [4, 5], genetic engineering [6], and on.
machine learning [1, 2], communication
The most widely used tensor decompositions include the canonical polyadic (CP) [7], Tucker [8] and tensor train (TT) [9] decompositions. In general. the CP decomposition provides compact representation but comes with computational difficulties finding the optimal decomposition for high-order tensors [10, 11]. The Tucker decomposition can be approximately computed via the higher order singular value decomposition (SVD) [12), but is inapplicable for high-order tensors since its number of parameters scales exponentially with the tensor order. The TT decomposition sits in the middle between CP and Tucker decompositions and combines the best of the two worlds: the number of parameters does not grow exponentially with the tensor order, and it can be approximately computed by the SVD-based algorithms with a guaranteed accuracy [9]. (See the monograph [13] for detailed description.) As such, TT decomposition has attracted tremendous interest over the past decade [1 [14-26]. Notably, the TT decomposition is equivalent to the matrix product state (MPS) or matrix product operator (MPO) introduced in the quantum physics community efficiently represent
"Correspondigg author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

one-dimensional quantum states, where the number of particles in quantum system determines the order of the tensor [27-29]. The use of TT decomposition may thus allow one to classically simulate a one-dimension quantum many-body system with resources polynomial in the number of particles [29]. or to perform scalable quantum state tomography [30].
While an SVD-based algorithm [9] can be used to compute a TT decomposition, this requires infor- mation about the entire tensor. However, in many practical applications such as low-rank embeddings of visual data [31], density estimation [32], surrogate visualization modeling [33], quantum state tomography [30], multidimensional harmonic retrieval [34], parametric partial differential equations [35], interpolation [36], and CMOS ring oscillators [37], one can or it is desirable to only evaluate a small number of elements of tensor in practice, since a high-order tensor has exponentially many elements. To address this issue, the work [38] develops a cross approximation technique for efficiently computing a TT decomposition from selected subtensors. Originally developed for matrices, cross approximation represents a matrix from a selected set of its rows and columns, preserving structure such as sparsity and non-negativity within the data. Thus, it has been widely used for data analysis [39, 40]. subspace clustering [41], active learning [42], approximate SVDs [43, 44), data compression and sampling [45-47], and it has been extended for tensor decompositions [38, 48-52]. See Section for detailed description of cross approximation for matrices and Section 3 for its extension to TT decomposition.
Although the theoretical analysis and applications of matrix cross approximation [53-64] have been developed for last two decades, to the best of our knowledge, the theoretical analysis of TT cross approximation, especially regarding its error bounds, has not been well studied [65, 66]. Although cross approximation gives an accurate TT decomposition when the tensor exactly the TT format [38], the question remains largely unsolved as to how good the approximation is when the tensor is only approximately in the TT format, which is often the case for practical data. In particular, an important question is whether the approximation error grows exponentially with the order due to the cascaded multiplications between the factors; this exponential error growth is proved to occur with the Tucker decomposition [48, 49]. Fortunately, for TT cross approximation, the works [65, 66] establish element- wise error bounds that do not grow exponentially with the order. Unfortunately, when one extends these element- wise results to the entire tensor, the Frobenius norm enror bound grows exponentially with the order of the tensor, indicating that the cross approximation could essentially fail for high-order tensors. However, in practice cross approximation is often found to work well even for high-order tensors, leading us to seek for tighter error bounds on the entire tensor. Specifically, we ask the following main question:
Question: Does cross approximation provide a stable tensor train (TT) decomposition of a high-order tensor with accuracy guaranteed in terms of the Frobenius norm?
In this paper, we answer this question affirmatively by developing accuracy guarantees for tensors that are not exactly in the TT format. Our results illustrate how the choice of subtensors affects the quality of the approximation and that the approximation error need not grow exponentially with the order. We also extend the approximation guarantee to noisy measurements.
The rest of this paper is organized as follows. In Section 2, we review and summarize existing error bounds for matrix cross approximation. Section 3 introduces our new error bounds for TT cross approximation. Section 4 includes numerical simulation results that supports our new error bounds and Section 5 concludes the paper.
Notation:
We use calligraphic letters (e.g., A) to denote tensors, bold capital letters (e.g., A) to denote matrices, bold lowercase letters (e.g., a) to denote vectors, and italic letters (e.g., a) to denote scalar quantities. A and At represent the inverse and the Mlore-PPnnrose pseudoinverse matrices of A, respectively. Elements of matrices and tensors are denoted parentheses, as in Matlab notation. For example, A(i,, 22, ig) denotes the element in position (i i2, ia) of the order-3 tensor A, : denotes the -th row of A, and A J) denotes the submatrix of A obtained by taking the columns indexed by J. ||||| and || respectively represent the spectral norm and Frobenius norm of A.

---

2 Cross Approximation for Matrices
As a tensor can be viewed as a generalization of a matrix, it is instructive to introduce the principles behind cross approximation for matrices. Cross approximation, also known as skeleton decomposition or CUR decomposition, approximates a low-rank matrix using small number of its rows and columns. Formally, following the conventional notation for the CUR decomposition, we construct a cross approximation for any matrix A E Rmxx as
A R CU'R,
where f denotes the pseudoinverse (not to be confused with the Hermitian conjugate widely used in quantum physics literature), C A(;, J), U A(I, and R AI,:) with I E [m]] and J E [n]] denoting the indices of the selected rows and columns, respectively. See Figure for an illustration of matrix cross approximation. While the number of selected rows and columns (i.e., [7] and [JD can be different, they are often the same since the rank of CU R is limited by the smaller number if they are different. When U is square and non- -ingula,,,,,, the cross approximation (1) takes the standard form A CU- R. Without loss of generality, rows and columns in the sequel. We note that one may replace Ut in (1) by C AR' to improve the approximation, resulting in the CUR approximation CC AR R. where CC and R R are orthogonal projections onto the subspaces spanned by the given columns and rows, respectively [67, 61]. However, such CUR approximation depends knowledge of the entire matrix A. As we mainly focus on scenarios where such knowledge is prohibitive, in the sequel we only consider the cross approximation (1) with U J).
assume equal number of selected
While in general the singu- lar value decomposition (SVD) gives the best low-rank approx- imation to matrix in terms of Frobenius norm or spectral norm, the cross approximation shown in Figure has several notable advantages: (i) it is more inter- pretable since it is constructed
T
|J]
YI
X /
U
R
A
Figure 1: Cross approximation for matrix.
with the rows and columns of the matrix, and hence could preserve structure such as sparsity, non- negativity, etc., and (ii) it only requires selected rows and columns while other factorizations often require the entire matrix. As such, cross approximation has been widely used for data analysis [39, 40), subspace clustering [41], active learning [42], approximate SVDs [43, 44], data compression and sampling [45-47], and on; see [61, 62] for detailed history of the use of cross approximation.
The following result shows that the cross approximation is exact (i.e., (1) becomes equality) as long the submatrix U has the same rank as A.
Theorem For any A E pmxn, suppose select rows and columns C= =((;,)).U U J), R A(1:) from A such that rank(U) = rank(A). Then
A CU'R.
Proof As R is a submatrix of A and U is a submatrix of R, rank(U) < &rank( R) S rank(A) always holds. Now if rank(U) rank(A), we have rank(U)- = rank R) and thus any columns in R can be linearly represented by the columns in U. Using this observation and noting that U U we can obtain that R UU R. Likewise, since rank = rank (A), any rows in A can be linearly represented by the rows in R. Thus, we can conclude that A = CURR.
In words, Theorem 1 implies that for an exactly low-rank matrix A with rank r, we can sample r (or more) rows and columns to ensure exact cross approximation. In practice, however, A is generally not exactly low-rank but only approximately low-rank. In this case, the performance of cross approximation depends crucially on the selected rows and columns. Column subset selection a classical problem in numerical linear algebra, and many methods have been proposed based on the maximal volume principle [68, 69] or related ideas [70-72]; see [72] for more references representing this research direction.
3

---

Efforts have also been devoted to understand the robustness of cross approximation since it only yields low-rank approximation A when A is not low-rank. The work [53] provides an element- wise accuracy guarantee for the rows and columns selected via the maximal volume principle. The recent work [58] shows there exist a stable cross approximation with accuracy guaranteed in the Frobenius norm, while the work [59] establishes similar guarantee for cross approximations of random matrices using the maximum projective volume principle. A derandomized algorithm is proposed in [60] that finds cross approximation with similar performance guarantee. The work [62] establishes an approximation guarantee for cross approximation using any sets of selected rows and columns. See Appendix A for a detailed description of these results.
3 Cross Approximation for Tensor Train Decomposition
In this section, we consider cross approximation for tensor train (TT) decomposition. We begin by introducing tensor notations. For N-th order tensor T E xedxxx the k-th separa- fion or unfolding of TT denoted by ((k), is a matrix of size (d1 dx) x (dx+1. with its (i1 ... ... 1++1 ...... iN) >-th element defined by
i..i
(Kk (i) ..... 12+1 ... iN) = T(i
Here, io i....ig ig is a single multi-index that combines indices i1,..., ig. As for the matrix case, we will select rows and columns from (k) to construct a cross approximation for all k= 1, 1,....,. N To simplify the notation, we use Isk and 1> to denote the positions of the selected r rows and columns in the k-th unfolding. With abuse of notation, I and I also used the positions in the original tensor. Thus, both Tkk (IS* I²*) and T(IS* !>) represent the sampled r'K rk intersection matrix. Likewise, T(1Sk-1 dg, 12k) represents r r matrix whose (s, 1)th element given by T(ISk-1, i 12²h) for s 1, L..... and 1, 1....,
3.1 Tensor Train Decomposition
We say that T E Id xdw is in the TT format if we can express its (ii,..., 1-h element as the following matrix product form [9]
(i(;; ... X (N(;,NN;;),
(3)
where X; I 1 ,...., N with ro TN 1 and X, (()())):)) R
1. 1...., .N denotes one "slice" of X, with the second index being fixed at ij. To simplify notation, we In quantum many-body physics, (3)
often write the above TT format in short T [X i....... Xx] ]. is equivalent to a matrix product state or matrix product operator, where T(i,...... .N) denotes an element of the many-body wavefunction or density matrix, N is the number of spins/qudits, and rи N - 1) are known as the bond dimensions. Note that in general the decomposition
(k = 1,21,2 1,2. (3) is not invariant to dimensional permutation due to strictly sequential multilinear products over the latent cores. The tensor ring decomposition generalizes (3) by taking the trace of the RHS; this allows To, Nn 2 1 and is invariant to circular dimensional permutation [73].
While there may exist infinitely many ways to decompose a tensor T as in (3), we say the decomposi-
Xx 1.:)
tion is minimal if the rank of the left unfolding of each X (i.e., I(Xx)=
is r2 and
Xuli, dey:)
the rank of the right unfolding of each X₁ (i.e., R(X,) = (x 1,:) The dimensions r = (fi.....,7y -1- of such a minimal decomposition are called the TT ranks of T. According to [74], there is exactly one set of ranks r that T admits minimal TT decomposition. Moreover, F'k equals the rank of the k-thh unfolding matrix (K)), which can serve an alternative way to define the TT rank.
Xuli, de,:)) is rk-1-
Efficiency of Tensor Train Decompasition The number of elements in the N-th order tensor grows exponentially in N, a phenomenon known as the curse of dimensionality. In contrast, a TT decomposition of the form (3) can represent a tensor T with di... ... dx elements using only O(dNr²) elements, where
max(d], dx) and r = max(ri, .,, (NN-)) This makes the TT decomposition remarkably efficient in addressing the curse of dimensionality its number of

---

parameters scales only linearly in N. For this reason, the TT decomposition has been widely used for image compression [14, 15], analyzing theoretical properties of deep networks [16], network com- pression (or tensor networks) [17-22], recommendation systems [23], probabilistic model estimation (24], learning of Hidden Markov Models [25], and so on. The work [26] presents a library for TT decomposition based on TensorFlow. Notably, TT decomposition is equivalent to the matrix product state (MPS) introduced in the quantum physics community to efficiently and concisely represent quantum states; here N represents the number of qubits of the many-body system [27-29]. The concise representation by MPS is remarkably useful in quantum state tomography since it allows us to observe quantum state with both experimental and computational resources that are only polynomial rather than exponential in the number of qubits N [30].
Comparison with Other Tensor Decompositions Other commonly used tensor decompositions include the Tucker decomposition, CP decomposition, etc. The Tucker decomposition is suitable only for small-order tensors (such as N = 3) since its parameterization scales exponentially with N
[8]. Like the TT decomposition, the canonical polyadic (CP) decomposition [7] also represents tensor with linear (in N) number of parameters. However, TT has been shown to be exponentially more expressive than CP for almost any tensor [16, 75J. Moreover, computing the CP decomposition is computationally challenging; even computing the canonical rank can be NP-hard and ill-posed [10, 11]. In contrast, one can use sequential SVD-based algorithm [9] to compute a quasioptimal TT decomposition (the accuracy differs from that of the best possible approximation by at most factor of VN). We refer to [13] for detailed comparison.
3.2 Cross Approximation For Tensor Train Decomposition
While the SVD-based algorithm [9] can be used to find TT decomposition, that algorithm requires the entire tensor and is inefficient for large tensor order N. More importantly, in applications like low- rank embeddings of visual data [31], density estimation [32], surrogate visualization modeling [33], and quantum state tomography [30], it is desirable to measure a small number of tensor elements since the experimental cost proportional to the number of elements measured. In such scenarios, we can use TT cross approximation to reconstruct the full tensor using only a small number of known elements, similar the spirit of matrix cross approximation.
To illustrate the main ideas behind TT cross approximation, we first consider the case where a tensor T is in the exact TT format (3), i.e., the unfolding matrix (A) is exactly low-rank with rank ri- In this case, by Theorem I, we can represent ( with a cross approximation by choosing ri rows (with r 2 r1) indexed by r and ri columns indexed by l>| such that
(1-2,11)) (1)) (T)) 1 [ (1 (9,1"") (
x dg x...X dy
Here (:) 121) has drr entries, while (T5) is an extremely wide matrix. However, one only needs to sample the elements in (1) and can avoid sampling the entire elements of (()(()),;)) by further using cross approximation. In particular, one can re- shape ( (TS)) into an- other matrix of size r'ds x d3 dg---dy dy and then represent with cross approxima- tion by choosing r'2 rows and columns. This procedure can be applied recursively N - times, and only at the last stage does one sample both r'y_, rows and columns of an r2x-2dx11 x dx matrix. This is the procedure developed in [38] for TT cross approximation. The process TT cross approximation shown in Fig. 2.
T dg x x dN
reshape L(Xi)
A x de
L(X2)
dN
rly
Xx-2 x dx-1
L(Xx-1)
Figure 2: Cross approximation for TT format tensors with nested interpolation sets.
5

---

The procedure illustrated in Figure 2 produces nested interpolation sets as one recursively applies cross approximation on the reshaped versions of previously selected rows. However, the interpolation sets {TS*, }>*} are not required to be nested. In general, one can slightly generalize this procedure and obtain TT cross approximation T with elements given by [66]
T T iN) II T(TSk-1 ,K, 1. (T(SS (
where IS denotes the selected row indices from the multi-index {dl ... d. I> is the selection of the column indices from the multi-index (dx+1 (de+1....d. ...dy' J. and [ J>N 0. Here A denotes the T-pseudoinversion of A that sets the singular values less than 7 to zero before calculating the pseudoinversion.
Similar Theorem 1, the TT cross approximation I equals T when is the TT format (3) and the intersection matrix T(IS*, [²*) has rank rı for k = 1, ......N N [38]. Nevertheless, in practical applications, tensors may be only approximately but not exactly the TT format (3), i.e., the unfolding matrices (*) may be only approximately low-rank. Moreover, applications such as quantum tomography, one can only observe noisy samples of the tensor entries. We provide guarantees in terms of IT - F| for these cases in the following subsections.
3.3 Error Analysis of TT Cross Approximation with Exact Measurements
Assume each unfolding matrix ( is approximately low-rank with residual captured by ||T(() (k) I[, where (Kk denotes the best rank-ry: approximation of T For convenience, we define
max
Tk:
max T
T: |F,
(5)
where e captures the largest low-rank approximation error in all the unfolding matrices.
The work [65, 66] develops an element- error bound for TT cross approximation based on the maximum-volume choice of the interpolation sets. However, if we are interested in an approximation guarantee for the entire tensor (say in the Frobenius norm) instead of each entry, then directly applying the above result leads to a loose bound with scaling at least proportional vd, .dy. Our goal is to provide guarantees directly for ||'T - - r. Note that (5) implies that a fundamental lower bound
T - -
since ||T - 7 | - T 1|
|
(k)
T ||F
holds for any TT format tensor 7 with ranks r (not only those constructed by cross approximation). Fortunately, tensor models in practical applications such as image and video [14, 15] and quantum states [27-29] can be well represented in the TT format with very small e.
Our first main result proves the existence of stable TT cross approximation with exact measurements of the tensor elements:
Theorem 2 Suppose T can be approximated by TT format tensor with ranks and approximation error defined in (5). For sufficiently small e, there exists a cross approximation T of the form (4) with Ty. = 0 that satisfies
T - (3x) N1 -
(r + 1)e,
3R
where a == max, ([[T(A) (t, 12R). (TSK, 1> ( || ( 1.1. (TS(,
We use sufficiently small to simplify the presentation. This refers the value of that (t, T 12k) (ht)) (TSA, r>*)~1|| (
( (TW) -
K, which can always be guaranteed since by (7) the distance between î and T (and hence the distance between (() (:. I>a) and (M) (1, I>t)) approaches when goes to zero. The full proof is provided in Appendix B.
(1)((,))))))
On one hand, the right hand side of (7) grows only linearly with the approximation error e, with a scalar that increases only logarithmically in terms of the order N. This shows the TT cross approximation

---

can be stable for well selected interpolation sets. Recall that by (6), for any cross approximation 7 of the form (4) with ra selected rows and columns in the sets { 1=k,, ). IT - F 2 necessarily holds since (A) has rank at most rk- While may be unfair to compare the element- wiiee error bounds [65, 66], we present [65, Theorem 1] below which also involves e and similar quantity to k:
IT - 7 max S (2r + rk + 1) [log, N1 (r + 1)E, where |
max [T iN) $1
=
Loosely speaking, K. and R can be approxi- mately viewed as the condition number of the submatrix T (1 1² with respect to the spectral norm and the Chebyshev norm, respectively. Again, we note that our bound (7) is for the entire tensor, while IT - T- Imax only concerns the largest element-wise error.
and R = maxe [T maxx
IIax- (
On the other hand, Theorem 2 only shows the existence of one such stable cross approximation, but does not specify which one. As a consequence, the result may not hold for the nested sampling strategy illustrated in Figure 2 and the parameter maybe out of one's control. The following result addresses these issues by providing guarantees for any cross approximation.
Theorem 3 Suppose T can be approximated by TT format tensor with rank and approximation
errore defined (5). Let Til be the best rank Yı approximation of the k-th unfolding matrix T
and T:t) (1k) (k) V(k)* be its compact SVD. For any interpolation sets {isk, 12k] such that
rank(T, (K) (TSK, {>k))= = rk 1,.... N - denote by
max k= N-1 [IllWWas(ss)) sk 11 (1**, "00 II c=
| (1 |
max
k=
Then the cross approximation t in (4) with appropriate thresholding parameters Tk for the truncated pseudo-inverse satisfies
IT- S (a'r a² cre + a² 2) 2)0oo N1-1, (a²e + a'ce² +d)de),
(8)
where S means less than or equal up to some universal constant.
The proof of Theorem 3 is given in Appendix C. As in (7), the right hand side of (8) scales only polynomially in c and logarithmically in terms of the order N. Compared with (7), the guarantee in (8) holds for any cross approximation, but the quality of the cross approximation depends on the tensor T as well as the selected rows and columns as reflected by the parameters and c. On one hand, || [Ws
]] and [VVas(/>* (/>*;:)] ;)]]]] || can achieve their smallest possible value 1 when the singular vectors (a)) and V(R) are the canonical basis. On the other hand, one may construet examples with large ([[ (TS* ::)][] and [[[V(s) (T>R, |- Nevertheless, these terms can be upper bounded by selecting appropriate rows and columns. For example, for any orthonormal matrix W E Rmxr, if we select I such that :I,:) has maximal volume among all |/| x r submatrices of
W, then [[ S /1+ 1/1=-17) |||-+1 [62, Proposition 5.1]. In practice, without knowing W(a)
and V(K), we may instead find the interpolation sets by maximizing the volume of T (1SK />*) using algorithms such as greedy restricted cross interpolation (GRCI) [65]. We may also exploit derandomized algorithms [60] to find interpolation sets that could potentially yield small quantities a, c. We finally note that Theorem 3 uses the truncated uscudo-inverse in (4) with appropriate тk- We also observe from the experiments in Section 4 that the truncated pseudo-inverse could lead to better performance than the inverse (or pseudo-inverse) for TT cross approximation (4).
3.4 Error Analysis for TT Cross Approximation with Noisy Measurements
We now consider the case where the measurements of tensor elements are not exact, but noisy. This happens, for example, in the measurements of quantum state where each entry of the many- wavefunction or density matrix can only be measured up to some statistical error that depends on the number of repeated measurements. In this case, the measured entries T(TSk-1, ds, T2k and [= in the cross approximation (4) are noisy. Our goal is to understand how such noisy measurements will affect the quality of cross approximation.
To simplify the notation, we let & denote the measurement error though it has non-zero values only at the selected interpolation sets {I l>*). Also let 7 = T and (k) (h) + (A)) where (E))
7

---

denotes the k-th unfolding matrix of the noise. Then, the cross approximation of T E Rd with noisy measurements, denoted by T, has entries given by
NV. II T(ISI-- k=
Th iN)
_k. 12t 1 12>))
One can view T cross approximation of T with exact measurements of T. However, we cannot directly apply Theorem 3 since it would give a bound for || - F and that would also depend on the singular vectors of (k), The following result addresses this issue.
Theorem Suppose T can be approximated by TT format tensor with rank and approximation ervor e defined in (5). Let T, be the best rank Tk approximation of the k-th unfolding matrix ( and T!lk) (W))) Exk) V(k)* be its compact SVD. Let T T + E denote the noisy ten- sor where & &represents the measurement error. For any interpolation sets {TSk, I=k] such that rank(Trr (K) (1SK, 10,,) TR. ,,...,N -
N
denote by
(IllW(a) ..) |I [V ( c=
( 1>1]11|
max
max lmm I...,N N-1
fm I...,NN-
Denote by č = + ||E|| Then the noisy cross approximation i in (9) with appropriate thresholding parameters Tı for the truncated pseudo-inee inverse satisfies
-T-Tir x
(a²r a'ere 22) MI-1 (a² azcd +z)
(10)
The proof of Theorem 4 is given in Appendix D. words, Theorem 4 provides a similar guarantee to that in Theorem 3 for TT cross approximation with noisy measurements and shows that it is also stable with respect to measurement error. The parameter e Theorem 4 depends on the spectral norm of (T (TS* }² and defined this form for simplicity. It can be bounded by (T (TS*, r²*)]] and the noise and is expected to be close to (T()) (IS*, ]>*}]$ for random noise. We finally note that the measurement error & only has ONNr²) non-zero elements, and thus [[]|ee is not exponentially
large in terms of N.
4 Numerical Experiments
In this section, conduct numerical experiments to evaluate the performance of the cross approxima- tion (9) with noisy measurements. We generate an N-th order tensor T E Rd1x x-dyy approximately in the TT format T T, + ufF,, where T, is in the TT format with mode ranks (ri,...,IN-) which is generated from truncating random Gaussian tensor using a sequential SVD [9], and F is a random tensor with independent entries generated from the normal distribution. We then normalize T, and F to unit Frobenius norm. Thus 77 controls the low-rank approximation error. To simplify the selection of parameters, let dj -N-1 for the cross approximation (9).
dN 2, Ti
TN-1, and
We apply the greedy restricted cross interpolation (GRCI) algorithm in [65] for choosing the in- terpolation sets ISh and 1>b It 1,.... N. For convenience, we set = r = N 1 for
the number of selected rows and columns indexed by I= and 1>* During the procedure of cross approximation, for each of the (N 2)dr'² 2dr' 22 observed entries, we add measurement error randomly generated from the Gaussian distribution of mean 0 and variance (N-2)d-"
As in Section 3.4, for convenience, we model the measurement error as tensor such that E |[ 1. To control the signal-to-noise level, we scale the noise by factor μ. Thus, we have
7 = T + μr Tr + nf + με
(11)
where |T || E |811 1.
We measure the normalized mean square error (MSE) between T and the cross approximation 7 by
I Í12
MSE
10log
(12)
|
8

---

20
100
(r=2)
40
50
(r-4)
+=0
60
1= (r=4)
-30
80
10
-50
-100
-80
2
-100
10
14
10
10
10
10
N
(b)
(c)
-20
65
-40
l'md
-70
-60
1
-20
-80
-75
7=0, r=2
30 00, N-1 x10"'
-100
107
10
10 10a
7
5
10
15
20
25
30
35 40
45
50
N
(d)
(e)
(f)
Figure 3: Performance (in MSE (dB) defined in (12)) of tensor cross approximations with truncated
pseudo-inverse + > 0 and exact pseudo-inverse T = 0 for (a) different estimated rank r' with N 10, r 1 17- 10-5, (b) different tensor order N with
2, 1 10-5 (c) different
level 1j of deviation from TT format with N = 10, r = 2, = 10-5, (d) different noise level μ with
N 10, 17 10 (e) different rank r with N 10, μ n 10 (f) different tensor
order N with r = 2, μr 0, 10
In the first experiment, performance tensor cross approximations with different 7 and r'. From Fig. 3a, we observe that when rf is specified the exact rank (i.e., r' r). all of the TT cross approximations very accurate except when 7 is relatively large and thus useful information truncated. On the other hand, when r' т, the performance of cross approximations with the exact pseudo-inverse
N 10, d
and 1r = 10-5 and compare the
(T 0) degrades. This because the intersection matrices T(TSk, T>k) (4) or T(TEk, T>) in (9) become ill-conditioned. Fortunately, since the last r' singular values T(ISk j>*) and T(ISk [>b] only capture information about the approximation error and measurement error, this issue be addressed by using the truncated pscudo-inverse with suitable 7 > O which can make TT cross approximation stable. We notice that larger r' gives better cross approximation due to more measurements.
In the second experiment, we test the performance of tensor eross approximations with different tensor orders N. For N ranging from 6 to 22, we set all mode sizes d = 2 and
10 small, tensor still huge for 2. From Fig. 3b, we can observe that the TT
Here = corresponds to a quantum state, and while large N (e.g., N = 22). We also set all ranks cross approximation with the pseudo-inverse stable as N increases when = r (black curve) but becomes unstable when r' > (blue curve). Again, for the latter case when r' > the TT cross approximation achieves stable performance by using the truncated pscudo-inverse.
In the third experiment, we demonstrate the performance for different which controls the level of low-rank approximation error. Here, we set μ 10-7, 10-7,- 2, 10-2n, and consider the over-specified case where r' ranges from 3 to 5. Fig. 3c shows that the performance of TT cross approximation with the truncated pseudo-inverse is stable with the increase 17 and different r'.
In the fourth experiment, we demonstrate the performance for different measurement error levels Similar the third experiment, we set 10-7 2, 10-2,u, and consider the over-specified case where r' ranges from to We observe from Fig. 3d that tensor train cross approximation still provides stable performance with increasing μ and different r'.
In the fifth experiment, we test the performance for different т. We set μ 7 = 10-5 d
10 10-2n and consider the case where r' ranges from 8 to 10. Fig. 3e shows that the peformance of TT cross approximation is stable with the increase of r. with recovery error in the curves roughly increasing as O(r²) which is consistent with Theorem 4. Note that in practice is often unknown priori. For this case, the results the above figures show that we can safely use a relatively large estimate r' for tensor train cross approximation with the truncated pseudo-inverse.
In the final experiment, we test the performance with further larger tensor orders N. To achieve this goal, work on tensors in the exact TT format (i.c., 77 0) since in this we only need to store

---

the tensor factors with O(Nr²) elements rather than the entire tensor. We set rr 1= 10 10 and consider one case where N varies from 50. We observe from Fig. that the approximation emorr curve increases only logarithnically in terms of the order N, which is consistent with (10).
5 Conclusion and Outlook
While TT cross approximation has achieved excellent performance in practice, existing theoretical results only provide element-wise approximation accuracy guarantees. this paper, we provide the first error analysis in terms of the entire tensor for TT cross approximation. For a tensor in an approximate TT format, we prove that the cross approximation is stable in the sense that the approximation error for the entire tensor does not grow exponentially with the tensor order, and we extend this guarantee to the scenario noisy measurements. Experiments verify our results.
An important future direction we will pursue is to study the implications of our results for quantum tomography. In particular, we aim to find out whether our results imply that the statistical errors encountered in quantum measurements will not proliferate if we perform cross approximation of the quantum many-body state. Another future direction of our work is design optimal strategies for the selections of the tensor elements to be measured. One possible approach is to extend methods developed for matrix cross approximation [60], and another approach is to incorporate leverage score sampling [76-78]. It is also interesting to use local refinement to improve the performance of TT cross approximation. We leave these explorations future work.
Acknowledgment
We acknowledge funding support from NSF Grants No. CCF-1839232, PHY-21 122993, CCF-2106834 and CCF-2241199, as well as the W. M. Keck Foundation. We also thank the four anonymous reviewers for their constructive comments.
References
[1] A. Cichocki, D. Mandic, L. De Lathauwer, G. Zhou, Q. Zhao, C. Caiafa, and A. H. Phan. Tensor decompositions for signal processing applications: From two-way to multiway component analysis. IEEE Signal Processing Magazine, 22(2):145-163 Mar. 2015.
N. D. Sidiropoulos, I.. De Lathauwer, X. Fu, K. Huang, E. Papalexakis, and Faloutsos. Tensor decomposition for signal processing and machine learning. IEEE Transactions on Signal Processing, 65(13):355133582, Jul. 2017.
[3] N. D. Sidiropoulos, G. B. Giannakis, and R. Bro. Blind PARAFAC receivers for DS-CDMA systems. IEEE Transactions on Signal Processing, 48(3):810-823, Mar. 2000.
[4] A. Smilde, R. Bro. and P. Geladi. Multi- Malli-Way Analysis: Applications in the Chemical Sciences. Wiley, Hoboken, NJ, 2004.
[5] E. Acar and B. Yener. Unsupervised multiway data analysis: A literature survey, IEEE Trunsactions on Knowledge and Data Engineering, 21(1):6-20, Jan. 2009.
[6] V. Hore, A. Viñuela, A. Buil, J. Knight, M. I McCarthy, K. Small, and J. Marchini. Tensor decomposition for multiple-tissue gene expression experiments. Nature Genetics, 48(9):1094-11 100, Aug. 2016.
[7] R. Bro. PARAFAC. Tutorial and applications. Chemometrics and intelligent laboratory systems, 38(2):149- 171, Oct. 1997.
[8] L. Tucker. Some mathematical notes on three-mode factor analysis. Sep. 1966.
Psychometrika, 31(3):279-31
[9] I. Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33(5):2295-231) 2011.
[10] H. Johan. Tensor rank is NP-complete. Journal of Algorithms, 4(1 4(11):444655, 1990.
[11] V. De Silva and L. Lim. Tensor rank and the ill il-posednnes of the best low-rank approximation problem. SIAM Journal on Matrix Analysis and Applications, 30(3): 1088-1127,7001101111111111111111 2008.
10

---

[12] L. De Lathauwer. B. De Moor, and J. Vandewalle. A multilinear singular value decomposition. SIAM journal Matrix Analysis and Applications, 21(4):1253-1278, 2000.
2000.
[13] A. Cichocki, N. Lee. I. Oseledets, A. Phan, Q. Zhao, and D. Mandic. Tensor networks for dimensionality reduction and large-scale optimization: Part low-ran tensor decompositions. Foundations and Trends@ in Machine Learning, 9(4-5):249-42) 429, 2016.
[14] Latorre. Image compression and entanglement. arXiv preprint quant-ph/05 10031, 2005.
[15] J. Bengua, H. Phien, H. Tuan, and M. Do. Efficient tensor completion for color image and video recovery: Low-rank tensor train. IEEE Transactions on Image Processing, 26(5):2466226 2019,2017.
[16] V. Khrulkov, A. Novikov, and I. Oseledets. Expressive power of recurrent neural networks. In 6th International Conference on Learning Representations, ICLR 2018- Conferencc Track Proceedings, 2018.
[17] E. Stoudenmire and D. Schwab. Supervised learning with tensor networks. Advances in Neural Information Processing Systems, 29, 2016.
[18] A. Novikov, D. Podoprikhin, A. Osokin, and D. Vetrow. Tensorizing neural networks. Advances in neural information processing systems, 28, 2015.
[19] Y. Yang. D. Krompass, and V. Tresp. Tensor-train recurrent neural networks for video classification. In International Conference on Machine Learning, pages 3891-3900, 2017.
[20] A. Tjandra, S. Sakti, and S. Nakamura. Compressing recurrent neural network with tensor train. In 2017 International Joint Conference on Neural Networks (LCCN), pages 4451-4458, 2017.
[21] R. Yu, S. Zheng, A. Anandkumar, and Y. Yue. Long-term forecasting using tensor-train mns. Arxiv, 2017.
[22] X. Ma, P. Zhang, S. Zhang, N. Duan, Y. Hou, M. Zhou, and D. Song. A tensorized transformer for language modeling, Advances Neural Information Processing Systems, 32, 2019.
[23] E. Frolov and I. Oseledets. Tensor methods and recommender systems. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 7(3) 2017.
[24] G. Novikov, M. Panov, Intelligence, pages 1221- 2021.
Oseledets. Tensor-train density estimation. Uncertainty in Artificial
[25] M. Kuznetsov and I. Oseledets. Tensor train spectral method for leamning of hidden markov models (hmm). Computational Methods in Applied Mathematics, 19(1):93 99, 2019.
[26] A. Novikov, P. Izmailov, V. Khrulkov. M. Figurnov, and I. Oseledets. Tensor train decomposition on tensorflow (T3F). Journal of Machine Learning Research, 137 2020.
[27] F. Verstracte and J. Cirac. Matrix product states represent ground states faithfully. Physical review b. 73(9):094423, 2006.
[28] F. Verstracte, V. Murg, and J. Cirac. Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems. Advances in physics,
2008
[29] U. Schollwöck. The density-matric remormalization group in the age of matrix product states. Annals of physics, 326( 1):961992, 2011.
[30] M. Ohliger, V. Nesme, and J. Eisert. Efficient and feasible state tomography of quantum many-body systems. New Journal of Physics, 1511)20, 2013.
[31] M. Usvyatsov, A. Makarova, R. Rallester-Ripoll, M. Rakhuba, A. Krause, and K. Schindler. Cherry- picking gradients: Learning low-rank embeddings of visual data via differentiable cross-approximation In Proceedings of the IEEE International Conference on Computer Vision, pages 11466-1 1435, 2021.
[32] A. Chertkov and Oseledets. Solution of Fokker Planck equation by cross approximation method the tensor train format, Frontiers in Artificial Intelligence, 4, 2021.
[33] R. Ballester-Ripoll, E. G. Paredes, and R. Pajarola. A surrogate visualization model using the tensor train format. In Proc. SIGGRAPH ASIA 2016 Symposiun on Visualization, pages 1-8, 2016.
[34] N. Vervliet. Compressed sensing approaches to large-scale tensor decompositions. Ph.D. Thesis, May 2018.

---

[35] S. Dolgov and R. Scheichl. A hybrid alternating least -quares-TT-cross algorithm for parametric PDEs. SIAM/ASA J. Uncertain. 2. (11:260--99, Mar. 2019.
[36] D. Savostyanov and I. Oseledets. Fast adaptive interpolation of multi--imensionall arryss in tensor train format. In Proceedings of International Workshop on Multidimensional (nl) Systems, pages 1-8, 2011.
[37] Y. Kapushev, I. Oseledets, and E. Burnaev. Tensor completion via gaussian process-based initialization. SIAM Journal on Scientific Computing, +2(6))3812-38222 Dec. 2020.
[38] I. Oseledets and E. Tyrtyshnikov. TT-cross approximation for multidimensional arrays. Linear Algebru and its Applications, 432(1):70-88, Jan. 2010.
[39] Mahoney and Drineas. CUR matrix decompositions for improved data analysis. Proceedings of the National Academy of Sciences, 106(3):697-702, 2009.
[40] C. Thurau, K. Kersting, and C. Bauckhage. Deterministic CUR for improved large-scale data analysis: An empirical study. In Proceedings of the 2012 SIAM International Conference on Data Mining, pages 684 695, 2012.
[41] A. Aldroubi, K. Hamm, A. Koku, and A. Sekmen. CUR decompositions, similarity matrices, and subspace clustering. Frontiers in Applied Mathematics and Statistics, page 65, 2019.
[42] C. Li, X. Wang. W. Dong. J. Yan, Q. Liu, and H. Zha. Joint active learning with feature selection via cur matrix decomposition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 4166):1322-1396 2018.
[43] P. Drineas, R. Kannan, and M. Mahoney. Fast Monte Carlo algorithms for matrices Approximating matrix multiplication. SIAM Journal on Computing, 36(1): 3:12-155 2006.
[44] P. Drineas, R. Kannan, and M. Mahoney. Fast Monte Carlo algorithms for matrices Computing a low-rank approximation to a matrix. SIAM Journal on computing, 36(1):158-18,, 2006.
[45] P. Drineas, R. Kannan, and M. Mahoney. Fast Monte Carlo algorithms for matrices III: Computing a compressed approximate matrix decomposition. SIAM Journal on Computing, 36(1):184 206, 2006.
[46] M. Xu, R. Jin, and 7., Zhou. CUR algorithm for partially observed matrices. In International Conference on Machine Learning, pages 1412-1421, 2015.
[47] N. Mitrovic, M. Asif, U. Rasheed, J. Dauwels, and P. Jaillet. CUR dccomposition for compression and compressed sensing of large-scale traffic data. 16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013), pages 1475-1486 1480, 2013.
[48] I. Oseledets, D. Savostianov, and E. Tyrtyshnikov. Tucker dimensionality reduction of three-dimensional arrays in linear time. SIAM Journal on Matrix Analysis and Applications, 30(3):939-956, 2008
[49] S. A. Goreinov. On cross approximation of multi-inder index arrays. In Doklady Mathematics, volume 77, pages 404-406 406, 2008.
[50] M. Mahoney, M. Maggioni, and P. Drincas. Tensor-CUl decompositions for cansor-based data. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 327-336, 2006.
[51] Н. Cai, Z. Chao, L. Huang, and D. Needell. Fast robust tensor principal component analysis via fiber dccomposition. Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 189-197, 2021.
[52] H. Cai, K. Hamm, L. Huang, and Needell. Mode-wise tensor decompositions: Multi-dimensional generalizations CUR decompositions. Journal of Machine Learning Research, 22:1-36, 2021.
[53] S. A. Goreinov and E. E. Tyrtyshnikov. The maximal-volune concept in approximation by low-rank matrices. Contemporary Math., 208:47-51, 2001.
[54] P. Drineas, M. W. Mahoney, and S. Muthukrishnan. Relative-eroo CUR matrix decompositions. SIAM J. Matrix Anal, Appl., 30(2):844 881, Sep. 2008
[55] M. Mahoney and P. Drineas. CUR matrix decompositions for improved data analysis. Proceedings of the National Academy of Sciences, 106(3):977-02. 2009.
[56] S. Wang and Z. Zhang. Improving CUR matrix decomposition and the nyström approximation via adaptive sampling. Journal of Machine Learning Research, 14(1):2729 2769, Sep. 2013.
12

---

[57] C. BBousidii and D. P. Woodruff. Optimal CUR matrix decompositions. SIAM Journal on Computing. 46(2):543-589 Jan. 2017.
[58] N. I. Zamarashkin and A.I. Osinsky. On the existence of a nearly optimal skeleton approximation of matrix in the frobenius norm. Doklady Math., 97(2):164-166 166, May 2018.
[59] N. L. Zamarashkin and A.I. Osinsky. On the accuracy of cross and column low-rank maxvol approximations in average. Computational Mathematics and Mathematical Physics, 6165)788-779, Jul. 2021.
[60] A. Cortinovis and D. Kressner. Low-rank approximation in the frohenius norm by column and row subset selection. SIAM Journal Matrix Analysis and Applications, 41(4):1651-1673, Nov. 2020.
[61] K. Hamm and L. Huang. Perspectives on cur decompasitions. Applied and Computational Harmonic Analysis, 48(3):0088-1099, May 2020.
[62] K. Hamm and L. Huang. Perturbations of CUR decompositions. SIAM Journal Matrix Analysis and Applications, 42((1)3511-77) Mar. 2021.
[63] V. Y. Pan, Q Luan, J. Svadlenka, and I.. Zhao. CUR low rank approximation of a matrix at sub-linear cost. arXiv preprint arXiv: /906.049126 Jun. 2019.
[64] H. Cai, K. Hamm, L. Huang, and D. Needell. Robust CUR decomposition: Theory and imaging applications. SIAM Journal on Imaging Sciences, 1444):1472-1503, Oct. 2021.
[65] D. V. Savostyanov. Quasioptimality of maximum-volue volume cross interpolation of tensors, Linear Algebra and its Applications, 458(1):2,,,244, Oct. 2014.
[66] A. Osinsky. Tensor trains approximation estimates in the chebyshev norm. Computational Mathematics and Mathematical Physics, 59(2)20112266, May 2019.
[67] C. Boutsidis and D. Woodruff. Optimal CUR matrix decompositions. SIAM Journal Computing, 46(2):543-589, 2017.
[68] S. A. Goreinov and E. E. Tyrtyshnikov. The maximal-volume concept in approximation by low-rank matrices. Contemporary Mathematics, 280:47-52, 2001.
[69] A. Civril and M. Magdon-Ismail On selecting a maximum volume sub- matrix of matrix and related problems. Theoretical Computer Science, 410(47-49):4801 -4800, 2009.
[70] A. Deshpande, L. Rademacher, S. S. Vempala, and G. Wang. Matrix approximation and projective clustering via volume sampling. Theory of Computing, 2(1):225-247, 2006.
[71] A. Deshpande and L. Rademacher. Efficient volume sampling for row/column subset selection. In 2010 ieee 51 annual symposium on foundations of computer science, pages -38., 2010.
[72] A. Cortinovis and D. Kressner. Low-rank approximation in the Frobenius norm by column and row subset selection. SIAM Journal on Matrix Analysis and Applications, 41(4):165-1163, 2020.
[73] Q. Zhao, G. Zhou, S. Xie, L. Zhang, and A. Cichocki. Tensor ring decomposition. arXiv preprint UrXiv:1606.0553. 2016.
[74] S. Holtz, T. Rohwedder, and R. Schneider. On manifolds of tensors of fixed Ta-rank. Numerische Mathematik, 120(4):701 731, 2012.
[75] L. Grasedyck. Hierarchical singular value decomposition of tensors. SIAM Journal Matrix Analysis and Applications, 31(4):2029-205h May 2010.
[76] Y. Chen, S. Bhojanapalli, S. Sanghavi, and R. Ward. Completing any low-rank matrix, provably. The Journal of Machine Learning Research, 16(1):2999 -034,,333302000300 2015.
[77] A. Eftekhari, M. B. Wakin, and A. Ward. Mc2: A two-phase algorithm for leveraged matrix completion. Information and Inference: A Journal of the IMA, 73):581-604, 2018
[78] A. Rudi, D. Calandriello, L. Carratino, and L. Rosasco. On fast leverage score sampling and optimal learning. Advances in Neural Information Processing Systems, 31, 2018
[79] L. Grasedyck and W. Hackbusch. An introduction hierarchical (h-)rank and tt-rank of tensors with examples. Computational Methods Applied Mathematics, 1133):2113304 Jan. 2011.
13

---

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] In the abstract, introduction, main results, and conclusion, we explicitly state that our results are about the analysis of tensor train cross approximation, not about the optimal sampling strategy.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This paper focuses on the analysis tensor train cross approximation and bridges the gap between theory and implementation. So no potential negative societal impact is expected of this work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We explicitly mention the assumptions in Theorem 2, Theorem and Theorem 4.
(b) Did you include complete proofs of all theoretical results? [Yes] We include all the proof's in the Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [Yes] We detailedly describe the experimental setting in Section 4.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We detailedly describe the experimental setting Section 4.
(c) Did you report error bars (c.g., with respect to the random seed after running exper- iments multiple times)? [No] All the results are reported in terms of the accuracy of the tensor cross approximation, so error bars are not reported. But we ran these experiments many times and observed similar results.
(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)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] We cite them in Section 4.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing 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, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "fjC-prrqNs", "reviewer": "Reviewer_oKWt", "summary": "This paper provides the error analysis for the entire tensor, given clean or noisy measurements. Furthermore, it sheds light on how to sample the tensors for better approximation error. The results also show that the approximation error may not grow exponentially with the order of the tensor, implying more possible usefulness in quantum applications.", "questions": "I believe that the authors have already sufficiently answered my questions in the paper, including the error analysis in the presence of noises and the gap between an optimal cross approximation and any approximation. It would be better if the author can provide an example showing how Theorem 3 helps in selecting rows and columns to sample. While the authors have listed the optimal strategies for selections as a future direction, it would be nice if the authors can give some intuitions at a high level. It would help the readers better assess the theoretical implication and usefulness. Also, could the authors provide some intuitions of why the truncated pseudo-inverse could lead to better performance than the (pseudo-)inverse for TT cross approximation? Is it just because of the conditioning numerical stabilities?\n", "limitations": "NA.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well-supported by theoretical results as well as numerical experiments. \n\nIt provides the first error analysis for TT cross approximation that goes beyond element-wise bounds. The significance herein is that plainly applying element-wise results will yield an exponential growth in errors, and may imply a false sense of lack of accuracy. \nThe authors have done a good job walking readers through the motivation, definitions, and theoretical results. The technical contribution is self-evident.", "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": "R0pjBOmAjbb", "reviewer": "Reviewer_ViNA", "summary": "In this paper, the error of tensor train decomposition via cross approximation is analyzed. The cross approximation of tensor train decomposition is an analog of CUR decomposition for a higher-order tensor. The authors derive an error bound in terms of the Frobenius norm where the observation noise is taken into account. Numerical experiments are conducted to evaluate the actual dependency between the error and other parameters such as noise level and rank.  ", "questions": "### Question 1\nAccording to Lines 61--62 in Introduction, the main motivation to evaluate the error based on the Frobenius norm is that the prior studies only provide \"element-wise error bound\" and \"when one extends these element-wise results to the entire tensor, the Frobenius norm error bound grows exponentially with the order of the tensor\". However, the derived bound (6) contains \\epsilon, which is the Frobenius norm between observed and approximated tensors. For example, if each element of the residual tensor follows standard normal, \\epsilon becomes a square root of a xi-square variable, and its mean value increases exponentially w.r.t. the order of the tensor. In the end, the derived bounds do not resolve exponential dependence. If I misunderstood something, please correct me. \n\n### Question 2\nIn Introductions, several applications of tensor train decomposition and CUR matrix decomposition. However, as far as noticed, no specific application of \"cross approximation (CUR) of tensor train decomposition\" is provided. Could you provide a few examples for that, especially the applications in the machine learning literature?\n\n### Question 3\nI'm not convinced that the experiments of Figure 1 prove the correctness of the derived bound (6). For example, (b) doesn't exhibit the logarithmic curve w.r.t. N and (a) doesn't show the linearity in terms of r. I suspect this is because the problem size is not large enough. As a sanity check, I highly recommend conducting experiments on a larger scale so that we can clearly see the derived relationships numerically. \n\n### Question 4\nThe norm that appears in the definition of \\kappa seems undefined. ", "limitations": "See Questions above. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n1. A technically solid result is provided. \n1. Mathematical notation is consistently used and easy to follow.\n\nWeaknesses\n1. The motivation to develop the Frobenius norm-based analysis is ambiguous. See Question 1.\n2. The scope of this study (cross approximation of tensor train decomposition) seems a bit limited to the NeurIPS community. See Question 2.\n3. The derived bound is not fully examined in the numerical experiments. See Question 3.\n\n\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": {}}, {"review_id": "KBRVUXhWMRq", "reviewer": "Reviewer_iCWy", "summary": "This paper considers the problem of tensor train decomposition. It provides theoretical guarantees of cross approximation in terms of the Frobenius norm for both exact and noisy measurements. Numerical experiments are included to validate the theories.", "questions": "1. In theorem 2, it seems that the upper bound (6) will blow up if $\\kappa$ is a constant, which happens when $\\kappa$ increases with $d_1, \\dots d_N$ and $N$. In this case, the current bound may be worse than that obtained by directly multiplying the entrywise bound by $\\sqrt{d_1 \\dots d_n}$. Authors should include more discussions about $\\kappa$. In addition, as discussed in \"Weakness\", I think authors should compare the bounds with existing works, and this also applies to Theorems 3-4.\n\n2. As one can expect, the notations will be messy in tensor papers. It would make it more accessible to readers if authors can summarize the key notations in a section. ", "limitations": "N/A", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nOverall, the paper is easy to read and the literature review is comprehensive. Under certain conditions, the theoretical guarantees improve upon the prior art.\n\nWeakness:\nAs stated in the abstract and introduction, the main motivation of this work is that the existing element-wise approximation accuracy guarantees lead to loose bounds. However, the current paper only shows its own upper bounds and there is no comparison with existing results or minimax lower bounds. As a result, it is not obvious to me if it indeed leads to better theoretical guarantees. I believe it would largely improve the quality of the paper either by comparing the results with the prior works both theoretically and numerically, or by establishing the matching lower bounds to show the tightness of the upper bounds.", "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": "4WBf1nG0IU5", "reviewer": "Reviewer_HshM", "summary": "Tensor train (TT) application is a feasible approach to generalize tensor information. This paper discussed the cross approximation error for TT decomposition, where it generalize the upper bound for the decomposition error of the entire tensor and proved the cross approximation  is stable that does not grow exponentially with tensor order.", "questions": "Please see above.", "limitations": "N/A", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper orchestrated a comprehensive proof toward the tensor train decomposition with cross approximation. Both tensor train decomposition and cross approximation are well-known techniques in the field.\n2. Experimental analysis revealed that the error of the decomposition is stable with the increase of tensor order.  \n3. The author also introduce the tensor train decomposition and cross approximation in detail and illustrated their differences with related methods.\n\nWeaknesses:\n1. Full disclosure, I am not an expert in this field. On top of everything, I am not able to evaluate the significance of the proof. Somehow, I feel it is rather intuitive that error did not grow exponentially is because the decomposition scheme of the tensor train decomposition. I.e., irrespective of the actual decomposition method, i.e.cross approximation in this paper, the tensor train decomposition scheme will restrain the exponential grow of the error.\n2. I also have a hard time understand the proof. Staring with the proof of theorem 1. Does it mean, as long as rank of U and A are the same, the column space of R can be represented by U. And more confusing to me, C U R are all retrieved from A itself. I understand if two matrices have the same rank, we probably can have same set of columns or rows to represent the column and row space of these two matrices. But does it still hold, when all the decomposition matrices, C U R are all retrieved from the same matrix A? I am not very sure about this. \n3. Does the tensor train decomposition robust towards permutation? It looks like what the decomposition doing is to fold the tensor into a big matrix. During the process, it will lose track of the structure of the tensor. While permutating row, column, order of the tensor, does the decomposition result will be the same?", "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": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept