Tracking tensor ring decompositions of streaming tensors

Tensor ring (TR) decomposition is an efficient approach to discover the hidden low-rank patterns in higher-order tensors, and streaming tensors are becoming highly prevalent in real-world applications. In this paper, we investigate how to track TR decompositions of streaming tensors. An efficient algorithm is first proposed. Then, based on this algorithm and randomized sketching techniques, we present a randomized streaming TR decomposition. The proposed algorithms make full use of the structure of TR decomposition, and the randomized version can allow any sketching type. Theoretical results on sketch size are provided. In addition, the complexity analyses for the obtained algorithms are also given. We compare our proposals with the existing batch methods using both real and synthetic data. Numerical results show that they have better performance in computing time with maintaining similar accuracy.

The data that support the findings of this study are available from the corresponding author upon reasonable request.

1. We use rSTR-U, rSTR-L and rSTR-K to notate rSTR with uniform sampling, leverage-based sampling and KSRFT, respectively.

2. https://cave.cs.columbia.edu/repository/COIL-20.

3. https://github.com/qbzhao/BRTF/tree/master/videos.

The authors would like to thank the editor and the anonymous reviewers for their detailed comments and helpful suggestions, which helped considerably to improve the quality of the paper.

This work was supported by the National Natural Science Foundation of China (No. 12471349) and the Natural Science Foundation Project of CQ CSTC (No. cstc2019jcyj-msxmX0267).

Authors and Affiliations

1. College of Mathematics and Statistics, Chongqing University, Chongqing, 401331, People’s Republic of China

   Yajie Yu & Hanyu Li

2. Key Laboratory of Nonlinear Analysis and its Applications (Chongqing University), Ministry of Education, Chongqing, People’s Republic of China

   Hanyu Li

Corresponding author

Correspondence to Hanyu Li.

Conflict of interest

The authors declare that they have no Conflict of interest.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Proofs

We first state some preliminaries that will be used in the proofs, where Lemma 6 is a variant of [Drineas et al. (2011), Lemma 1] for multiple right hand sides, Lemma 7 is a part of [Drineas et al. (2006), Lemma 8] and Lemma 8 is from [Drineas et al. (2011), Theorem 4].

Lemma 6

Let \({{\,\textrm{OPT}\,}}{\mathop {=}\limits ^{{\tiny \textrm{def}}}}\min _{\textbf{X}} \Vert \textbf{A} \textbf{X} - \textbf{Y}\Vert _F\) with \(\textbf{A} \in \mathbb {R}^{I \times R}\) and \(I > R\), let \(\textbf{U} \in \mathbb {R}^{I \times {{\,\textrm{rank}\,}}(\textbf{A})}\) contain the left singular vectors of \(\textbf{A}\), let \(\textbf{U}^\perp \) be an orthonormal matrix whose columns span the space perpendicular to \({{\,\textrm{range}\,}}(\textbf{U})\) and define \(\textbf{Y}^\perp {\mathop {=}\limits ^{{\tiny \textrm{def}}}}\textbf{U}^\perp (\textbf{U}^{\perp })^\intercal \textbf{Y}\). If \(\mathbf {\Psi } \in \mathbb {R}^{m \times I}\) satisfies

for some \(\varepsilon \in (0,1)\), then

where \(\tilde{\textbf{X}} {\mathop {=}\limits ^{{\tiny \textrm{def}}}}\arg \min _{\textbf{X}} \Vert \mathbf {\Psi } \textbf{A} \textbf{X} - \mathbf {\Psi } \textbf{Y} \Vert _F\).

Lemma 7

Let \(\textbf{A}\) and \(\textbf{B}\) be matrices with I rows, and let \(\varvec{q} \in \mathbb {R}^I\) be a probability distribution satisfying

If \(\mathbf {\Psi } \in \mathbb {R}^{m \times I}\) is a sampling matrix with the probability distribution \(\varvec{q}\), then

Lemma 8

Let \(\textbf{A} \in \mathbb {R}^{I \times R}\) with \(\Vert \textbf{A}\Vert _2 \le 1\), and let \(\varvec{q} \in \mathbb {R}^I\) be a probability distribution satisfying

If \(\mathbf {\Psi } \in \mathbb {R}^{m \times I}\) is a sampling matrix with the probability distribution \(\varvec{q}\), \(\varepsilon \in (0,1)\) is an accuracy parameter, \(\Vert \textbf{A}\Vert _F^2 \ge \frac{1}{24}\), and

then, with a probability of at least \(1-\delta \),

1.1 Proof of Theorem 2

We first state a theorem similar to [Malik and Becker (2021), Theorem 7] i.e., the theoretical guarantee of uniform sampling for TR-ALS.

Theorem 9

Let \(\mathbf {\Psi }_{n}\) be a uniform sampling matrix defined as in (9), and

If

with \(\varepsilon \in (0,1)\), \(\delta \in (0,1)\), and \(\gamma >1\), then the following inequality holds with a probability of at least \(1-\delta \):

Proof

Let \(\textbf{U} \in \mathbb {R}^{J_n \times {{\,\textrm{rank}\,}}(\textbf{G}_{[2]}^{\ne n})}\) contain the left singular vectors of \(\textbf{G}_{[2]}^{\ne n}\) and \({{\,\textrm{rank}\,}}(\textbf{G}_{[2]}^{\ne n}) = R_{n} R_{n+1}\). Then, there is a \(\gamma >1\) such that

Note that \(\Vert \textbf{U}\Vert _F = \sqrt{R_{n} R_{n+1}}\). Thus, setting \(\beta = \frac{1}{\gamma }\), we have

That is, the uniform probability distribution \(\varvec{q}\) on \([J_n]\) satisfies (A4). Moreover, it is easy to see that \(\Vert \textbf{U}\Vert _2 = 1\le 1\), \(\Vert \textbf{U}\Vert _F^2 = R_{n} R_{n+1}>\frac{1}{24}\), and

Thus, noting that \(\mathbf {\Psi }_{n}\) is a sampling matrix with the probability distribution \(\varvec{q}\), applying Lemma 8 implies that

On the other hand, note that for all \(i \in [R_{n} R_{n+1}]\),

Thus, choosing \(\varepsilon = 1-1/\sqrt{2}\) gives that \(\sigma ^2_{\min } (\mathbf {\Psi }_{n} \textbf{U}) \ge \frac{1}{\sqrt{2}}\), therefore (A1) is satisfied.

Next, we check (A2). Recall that \((\textbf{X}_{[n]}^\intercal )^\perp {\mathop {=}\limits ^{{\tiny \textrm{def}}}}\textbf{U}^\perp (\textbf{U}^{\perp })^\intercal \textbf{X}_{[n]}^\intercal \). Hence, \(\textbf{U}^\intercal (\textbf{X}_{[n]}^\intercal )^\perp =0\) and

Thus, noting (A3) and (A4), applying Lemma 7, we get

where \({{\,\textrm{OPT}\,}}= \min _{\textbf{G}_{n(2)}} \left\| \textbf{G}_{[2]}^{\ne n} \textbf{G}_{n(2)}^\intercal - \textbf{X}_{[n]}^\intercal \right\| _F\). Markov’s inequality now implies that with probability at least \(1-\delta _2\)

Setting \(m \ge \frac{2R_{n} R_{n+1}}{\delta _2 \beta \varepsilon }\) and using the value of \(\beta \) specified above, we have that (A2) is indeed satisfied.

Finally, using Lemma 6 concludes the proof of the theorem. \(\square \)

Proof of Theorem 2

For the temporal mode N, if

according to Theorem 9, at each time step we can obtain a corresponding upper error bound between the new coming tensor and its decomposition as follows

To obtain an upper bound on the error for all current time steps, let \({\tilde{\varepsilon }} = \min \{{\tilde{\varepsilon }}_1, {\tilde{\varepsilon }}_2, \cdots \}\), then the following holds with a probability of at least \(1-\delta \):

for

For the non-temporal mode n, if

we have

Thus, setting \(\varepsilon = \min \{{\tilde{\varepsilon }}, \varepsilon '_1, \varepsilon '_2, \cdots , \varepsilon '_{N-1}\}\), the proof can be completed. \(\square \)

Along the same line, the proofs of Theorems 4 and 5 can be completed by using [Malik and Becker (2021), Theorem 7] and [Yu and Li (2024a), Theorem 5] respectively.

Specific algorithms based on different sketching

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions