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

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.

References

[1] Ahmadi-Asl S. An efficient randomized fixed-precision algorithm for tensor singular value decomposition Commun. Appl. Math. Comput., 2023, 5(4): 1564-1583.

[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 PO, Botstein D. Generalized singular value decomposition for comparative analysis of genome-scale expression data sets of two different organisms Proc. Natl. Acad. Sci., 2003, 100(6): 3351-3356.

[7] Bai, Z.: Numerical treatment of restricted Gauss-Markov model. Commun. Stat.-Simul. Comput. 17(2), 569–579 (1988)

[8] Barlow JL. Error analysis and implementation aspects of deferred correction for equality constrained least squares problems SIAM J. Numer. Anal., 1988, 25(6): 1340-1358.

[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., 2022, 29(6): e2444.

[11] Che M, Wei Y. Randomized algorithms for the approximations of Tucker and the tensor train decompositions Adv. Comput. Math., 2019, 45(1): 395-428.

[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., 2023, 197(1): 358-382.

[14] Golub GH, Van Loan CF Matrix Computations, 2013 Baltimore JHU Press.

[15] Halko N, Martinsson P-G, Tropp JA. Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions SIAM Rev., 2011, 53(2): 217-288.

[16] Hansen PC Rank-deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion, 1998 Philadelphia SIAM.

[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 ( a - λ b \documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\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 ME, Martin CD. Factorization strategies for third-order tensors Linear Algebra Appl., 2011, 435(3): 641-658.

[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., 2019, 42(4): 925-938.

[22] Martin CD, Shafer R, LaRue B. An order-p tensor factorization with applications in imaging SIAM J. Sci. Comput., 2013, 35(1): A474-A490.

[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 CC. The general linear model and the generalized singular value decomposition Linear Algebra Appl., 1985, 70: 269-284.

[25] Paige CC, Saunders MA. Towards a generalized singular value decomposition SIAM J. Numer. Anal., 1981, 18(3): 398-405.

[26] Ponnapalli SP, Saunders MA, Van Loan CF, Alter O. A higher-order generalized singular value decomposition for comparison of global mRNA expression from multiple organisms PLoS ONE, 2011, 6(12): e28072.

[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 A X ≈ B \documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$AX\approx B$$\end{document} when some or all columns in A \documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$A$$\end{document} are subject to error SIAM J. Matrix Anal. Appl., 1989, 10(3): 294.

[34] Van Loan C. On the method of weighting for equality-constrained least-squares problems SIAM J. Numer. Anal., 1985, 22(5): 851-864.

[35] Van Loan CF. Generalizing the singular value decomposition SIAM J. Numer. Anal., 1976, 13(1): 76-83.

[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., 2021, 3(1): 137-156.

[38] Wei Y, Xie P, Zhang L. Tikhonov regularization and randomized GSVD SIAM J. Matrix Anal. Appl., 2016, 37(2): 649-675.

[39] Yu W, Gu Y, Li Y. Efficient randomized algorithms for the fixed-precision low-rank matrix approximation SIAM J. Matrix Anal. Appl., 2018, 39(3): 1339-1359.

[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)

RIGHTS & PERMISSIONS

Shanghai University