Randomized Algorithms for Computing the Generalized Tensor SVD Based on the Tensor Product

doi:10.1007/s42967-024-00461-3

Abstract

Abstract: This work deals with developing two fast randomized algorithms for computing the generalized tensor singular value decomposition (GTSVD) based on the tensor product (T-product). The random projection method is utilized to compute the important actions of the underlying data tensors and use them to get small sketches of the original data tensors, which are easier to handle. Due to the small size of the tensor sketches, deterministic approaches are applied to them to compute their GTSVD. Then, from the GTSVD of the small tensor sketches, the GTSVD of the original large-scale data tensors is recovered. Some experiments are conducted to show the effectiveness of the proposed approach.

Key words: Randomized algorithms, Generalized tensor singular value decomposition (GTSVD), Tensor product (T-product)

CLC Number:

Salman Ahmadi-Asl, Naeim Rezaeian, Ugochukwu O. Ugwu. Randomized Algorithms for Computing the Generalized Tensor SVD Based on the Tensor Product[J]. Communications on Applied Mathematics and Computation, 2026, 8(2): 605-621.

TrendMD

References

[1] Ahmadi-Asl, S.: An efficient randomized fixed-precision algorithm for tensor singular value decomposition. Commun. Appl. Math. Comput. 5(4), 1564–1583 (2023)
[2] Ahmadi-Asl, S.: A note on generalized tensor CUR approximation for tensor pairs and tensor triplets based on the tubal product. arXiv:2305.00754 (2023)
[3] Ahmadi-Asl, S., Abukhovich, S., Asante-Mensah, M.G., Cichocki, A., Huy Phan, A., Tanaka, T., Oseledets, I.: Randomized algorithms for computation of Tucker decomposition and higher order SVD (HOSVD). IEEE Access 9, 28684–28706 (2021)
[4] Ahmadi-Asl, S., Cichocki, A., Huy Phan, A., Asante-Mensah, M.G., Musavian Ghazani, M., Tanaka, T., Oseledets, I.: Randomized algorithms for fast computation of low rank tensor ring model. Mach. Learn. Sci. Technol. 2(1), 011001 (2020)
[5] Ahmadi-Asl, S., Huy Phan, A., Cichocki, A.: A randomized algorithm for tensor singular value decomposition using an arbitrary number of passes. J. Sci. Comput. 98(1), 23 (2024)
[6] Alter, O., Brown, P.O., Botstein, D.: Generalized singular value decomposition for comparative analysis of genome-scale expression data sets of two different organisms. Proc. Natl. Acad. Sci. 100(6), 3351–3356 (2003)
[7] Bai, Z.: Numerical treatment of restricted Gauss-Markov model. Commun. Stat.-Simul. Comput. 17(2), 569–579 (1988)
[8] Barlow, J.L.: Error analysis and implementation aspects of deferred correction for equality constrained least squares problems. SIAM J. Numer. Anal. 25(6), 1340–1358 (1988)
[9] Cao, Z., Xie, P.: Perturbation analysis for t-product-based tensor inverse, Moore-Penrose inverse and tensor system. Commun. Appl. Math. Comput. 4(4), 1441–1456 (2022)
[10] Che, M., Wang, X., Wei, Y., Zhao, X.: Fast randomized tensor singular value thresholding for low-rank tensor optimization. Numer. Linear Algebra Appl. 29(6), e2444 (2022)
[11] Che, M., Wei, Y.: Randomized algorithms for the approximations of Tucker and the tensor train decompositions. Adv. Comput. Math. 45(1), 395–428 (2019)
[12] Cichocki, A., Lee, N., Oseledets, I., Huy Phan, A., Zhao, Q., Mandic, D.P.: Tensor networks for dimensionality reduction and large-scale optimization: part 1 low-rank tensor decompositions. Found. Trends Mach. Learn. 9(4/5), 249–429 (2016)
[13] Ding, M., Wei, Y., Xie, P.: A randomized singular value decomposition for third-order oriented tensors. J. Optim. Theory Appl. 197(1), 358–382 (2023)
[14] Golub, G.H., Van Loan, C.F.: Matrix Computations. JHU Press, Baltimore (2013)
[15] Halko, N., Martinsson, P.-G., Tropp, J.A.: Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2), 217–288 (2011)
[16] Hansen, P.C.: Rank-deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion. SIAM, Philadelphia (1998)
[17] Hitchcock, F.L.: The expression of a tensor or a polyadic as a sum of products. J. Math. Phys. 6(1/2/3/4), 164–189 (1927)
[18] Kågström, B.: The generalized singular value decomposition and the general (

\begin{document}$ a-\lambda b $\end{document}

)-problem. BIT Numer. Math. 24, 568–583 (1984)
[19] Kilmer, M.E., Braman, K., Hao, N., Hoover, R.C.: Third-order tensors as operators on matrices: a theoretical and computational framework with applications in imaging. SIAM J. Matrix Anal. Appl. 34(1), 148–172 (2013)
[20] Kilmer, M.E., Martin, C.D.: Factorization strategies for third-order tensors. Linear Algebra Appl. 435(3), 641–658 (2011)
[21] Lu, C., Feng, J., Chen, Y., Liu, W., Lin, Z., Yan, S.: Tensor robust principal component analysis with a new tensor nuclear norm. IEEE Trans. Pattern Anal. Mach. Intell. 42(4), 925–938 (2019)
[22] Martin, C.D., Shafer, R., LaRue, B.: An order-p tensor factorization with applications in imaging. SIAM J. Sci. Comput. 35(1), A474–A490 (2013)
[23] Miao, Y., Qi, L., Wei, Y.: Generalized tensor function via the tensor singular value decomposition based on the T-product. Linear Algebra Appl. 590, 258–303 (2020)
[24] Paige, C.C.: The general linear model and the generalized singular value decomposition. Linear Algebra Appl. 70, 269–284 (1985)
[25] Paige, C.C., Saunders, M.A.: Towards a generalized singular value decomposition. SIAM J. Numer. Anal. 18(3), 398–405 (1981)
[26] Ponnapalli, S.P., Saunders, M.A., Van Loan, C.F., Alter, O.: A higher-order generalized singular value decomposition for comparison of global mRNA expression from multiple organisms. PLoS ONE 6(12), e28072 (2011)
[27] Reichel, L., Ugwu, U.O.: Tensor Arnoldi-Tikhonov and GMRES-type methods for ill-posed problems with a t-product structure. J. Sci. Comput. 90, 1–39 (2022)
[28] Saibaba, A.K., Hart, J., van Bloemen Waanders, B.: Randomized algorithms for generalized singular value decomposition with application to sensitivity analysis. Numer. Linear Algebra Appl. 28(4), e2364 (2021)
[29] Speiser , J.M., Van Loan, C.: Signal processing computations using the generalized singular value decomposition. In: Real-Time Signal Processing VII, vol. 495, pp. 47–57. SPIE (1984)
[30] Tucker, L.R.: The extension of factor analysis to three-dimensional matrices. Contrib. Math. Psychol. 110119, 110–182 (1964)
[31] Ugwu, U.O: Viterative Tensor Factorization Based on Krylov Subspace-Type Methods with Applications to Image Processing, PhD Thesis. Kent: Kent State University (2021)
[32] Ugwu, U.O., Reichel, L.: Tensor Regularization by Truncated Iteration: a Comparison of Some Solution Methods for Large-Scale Linear Discrete Ill-Posed Problem with a t-Product. arXiv:2110.02485 (2021)
[33] Van Huffel, S., Vandewalle, J.: Analysis and properties of the generalized total least squares problem

\begin{document}$ AX\approx B $\end{document}

when some or all columns in

\begin{document}$ A $\end{document}

are subject to error. SIAM J. Matrix Anal. Appl. 10(3), 294 (1989)
[34] Van Loan, C.: On the method of weighting for equality-constrained least-squares problems. SIAM J. Numer. Anal. 22(5), 851–864 (1985)
[35] Van Loan, C.F.: Generalizing the singular value decomposition. SIAM J. Numer. Anal. 13(1), 76–83 (1976)
[36] Wang, X., Che, M., Wei, Y.: Tensor neural network models for tensor singular value decompositions. Comput. Optim. Appl. 75, 753–777 (2020)
[37] Wei, W., Zhang, H., Yang, X., Chen, X.: Randomized generalized singular value decomposition. Commun. Appl. Math. Comput. 3(1), 137–156 (2021)
[38] Wei, Y., Xie, P., Zhang, L.: Tikhonov regularization and randomized GSVD. SIAM J. Matrix Anal. Appl. 37(2), 649–675 (2016)
[39] Yu, W., Gu, Y., Li, Y.: Efficient randomized algorithms for the fixed-precision low-rank matrix approximation. SIAM J. Matrix Anal. Appl. 39(3), 1339–1359 (2018)
[40] Zhang, J., Saibaba, A.K., Kilmer, M.E., Aeron, S.: A randomized tensor singular value decomposition based on the t-product. Numer. Linear Algebra Appl. 25(5), e2179 (2018)
[41] Zhang, Y., Guo, X., Xie, P., Cao, Z.: CS decomposition and GSVD for tensors based on the t-product. arXiv:2106.16073 (2021)