A Note on Generalized Tensor CUR Approximation for Tensor Pairs and Tensor Triplets Based on the Tubal Product

Abstract

In this note, we briefly present a generalized tensor CUR (GTCUR) approximation for tensor pairs

(\underline{\mathbf{X}},\underline{\mathbf{Y}})

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(\underline{\textbf{X}},\underline{\textbf{Y}})$$\end{document}

and tensor triplets

(\underline{\mathbf{X}},\underline{\mathbf{Y}},\underline{\mathbf{Z}})

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(\underline{\textbf{X}},\underline{\textbf{Y}},\underline{\textbf{Z}})$$\end{document}

based on the tubal product (t-product). We use the tensor Discrete Empirical Interpolation Method (TDEIM) to do these extensions. We demonstrate how the TDEIM can be applied to extend the traditional tensor CUR (TCUR) approximation, which operates on a single tensor, to simultaneously compute the TCUR approximations for two or three tensors. This method allows for the sampling of relevant lateral or horizontal slices from one data tensor in relation to one or two other data tensors. In certain special cases, the generalized TCUR (GTCUR) method simplifies to the classical TCUR approximations for both tensor pairs and tensor triplets, akin to the process shown for matrices.

Keywords

CUR approximation / Generalized tensor singular value decomposition (GTSVD) / Tubal product (t-product) / 15A69 / 46N40 / 15A23

References

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

[2] Ahmadi-Asl S, Caiafa CF, Cichocki A, Phan AH, Tanaka T, Oseledets I, Wang J. Cross tensor approximation methods for compression and dimensionality reduction. IEEE Access, 2021, 9: 150809-150838

[3] Ahmadi-Asl, S., Phan, A.-H., Caiafa, C.F., Cichocki, A.: Robust low tubal rank tensor recovery using discrete empirical interpolation method with optimized slice/feature selection. Adv. Comput.Math. 50(2), 23 (2024)

[4] Ahmadi-Asl S, Phan A-H, Cichocki A. A randomized algorithm for tensor singular value decomposition using an arbitrary number of passes. J. Sci. Comput., 2024, 98(1): 23

[5] Ahmadi-Asl S, Rezaeian N, Ugwu UO. Randomized algorithms for computing the generalized tensor SVD based on the tensor product. Commun. Appl. Math. Comput., 2025

[6] Asante-Mensah MG, Ahmadi-Asl S, Cichocki A. Matrix and tensor completion using tensor ring decomposition with sparse representation. Mach. Learn. Sci. Technol., 2021, 2(3 035008

[7] Asante-Mensah MG, Phan AH, Ahmadi-Asl S, Al Aghbari Z, Cichocki A. Image reconstruction using superpixel clustering and tensor completion. Signal Process., 2023, 212 109158

[8] Caiafa CF, Cichocki A. Generalizing the column-row matrix decomposition to multi-way arrays. Linear Algebra Appl., 2010, 433(3557-573

[9] De Moor BL, Golub GH. The restricted singular value decomposition: properties and applications. SIAM J. Matrix Anal. Appl., 1991, 12(3): 401-425

[10] Drineas P, Mahoney MW, Muthukrishnan S. Relative-error CUR matrix decompositions. SIAM J. Matrix Anal. Appl., 2008, 30(2): 844-881

[11] Eldén L, Ahmadi-Asl S. Solving bilinear tensor least squares problems and application to Hammerstein identification. Numer. Linear Algebra Appl., 2019, 26(2 e2226

[12] Espig M, Naraparaju KK, Schneider J. A note on tensor chain approximation. Comput. Vis. Sci., 2012, 15(6): 331-344

[13] Gidisu PY, Hochstenbach ME. A generalized cur decomposition for matrix pairs. SIAM J. Math. Data Sci., 2022, 4(1): 386-409

[14] Gidisu, P.Y., Hochstenbach, M.E.: A restricted SVD type CUR decomposition for matrix triplets. arXiv:2204.02113 (2022)

[15] Gidisu, P.Y., Hochstenbach, M.E.: A hybrid DEIM and leverage scores based method for CUR index selection. In: Progress in Industrial Mathematics at ECMI 2021, pp. 147–153. Springer, New York (2022)

[16] Goreinov, S.A., Oseledets, I.V., Savostyanov, D.V., Tyrtyshnikov, E.E., Zamarashkin, N.L.: How to find a good submatrix. In: Olshevsky, V., Tyrtyshnikov, E. (eds) Matrix Methods: Theory, Algorithms and Applications (Dedicated to the Memory of Gene Golub), pp. 247–256. World Scientific (2010)

[17] Goreinov, S.A., Tyrtyshnikov, E.E., Zamarashkin, N.L.: A theory of pseudoskeleton approximations. Linear Algebra Appl. 261(1/2/3), 1–21 (1997)

[18] Hao N, Kilmer ME, Braman K, Hoover RC. Facial recognition using tensor-tensor decompositions. SIAM J. Imaging Sci., 2013, 6(1): 437-463

[19] He Z-H, Ng MK, Zeng C. Generalized singular value decompositions for tensors and their applications. Numer. Math. Theory Methods Appl., 2021, 14(3): 692

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

[21] Hitchcock, F.L.: Multiple invariants and generalized rank of a p-way matrix or tensor. J. Math. Phys. 7(1/2/3/4), 39–79 (1928)

[22] Jiang T-X, Ng MK, Zhao X-L, Huang T-Z. Framelet representation of tensor nuclear norm for third-order tensor completion. IEEE Trans. Image Process., 2020, 29: 7233-7244

[23] Kernfeld E, Kilmer M, Aeron S. Tensor-tensor products with invertible linear transforms. Linear Algebra Appl., 2015, 485: 545-570

[24] Kilmer ME, Braman K, Hao N, Hoover RC. Third-order tensors as operators on matrices: a theoretical and computational framework with applications in imaging. SIAM J. Matrix Anal. Appl., 2013, 34(1148-172

[25] Kilmer ME, Martin CD. Factorization strategies for third-order tensors. Linear Algebra Appl., 2011, 435(3): 641-658

[26] Li B-Z, Zhao X-L, Ji T-Y, Zhang X-J, Huang T-Z. Nonlinear transform induced tensor nuclear norm for tensor completion. J. Sci. Comput., 2022, 92(3): 83

[27] 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(4925-938

[28] Mahoney, M.W., et al. Randomized algorithms for matrices and data. Found. Trends® Mach. Learn. 3(2), 123–224 (2011)

[29] Oseledets I, Tyrtyshnikov E. TT-cross approximation for multidimensional arrays. Linear Algebra Appl., 2010, 432(1): 70-88

[30] Oseledets IV, Savostianov D, Tyrtyshnikov EE. Tucker dimensionality reduction of three-dimensional arrays in linear time. SIAM J. Matrix Anal. Appl., 2008, 30(3): 939-956

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

[32] Song G, Ng MK, Zhang X. Robust tensor completion using transformed tensor singular value decomposition. Numer. Linear Algebra Appl., 2020, 27(3 e2299

[33] Sorensen DC, Embree M. A DEIM induced CUR factorization. SIAM J. Sci. Comput., 2016, 38(3): A1454-A1482

[34] Tarzanagh DA, Michailidis G. Fast randomized algorithms for t-product based tensor operations and decompositions with applications to imaging data. SIAM J. Imaging Sci., 2018, 11(4): 2629-2664

[35] Tucker, L.R.: The extension of factor analysis to three-dimensional matrices. In: Gulliksen, H., Frederiksen, N. (eds) Contributions to Mathematical Psychology, pp. 110–127. Holt, Rinehart and Winston, New York (1964)

[36] Tucker LR. Some mathematical notes on three-mode factor analysis. Psychometrika, 1966, 31(3): 279-311

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

[38] Zha H. The restricted singular value decomposition of matrix triplets. SIAM J. Matrix Anal. Appl., 1991, 12(1): 172-194

[39] Zhang J, Saibaba AK, Kilmer ME, Aeron S. A randomized tensor singular value decomposition based on the t-product. Numer. Linear Algebra Appl., 2018, 25(5 e2179

[40] 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

Just Accepted

This article has successfully passed peer review and final editorial review, and will soon enter typesetting, proofreading and other publishing processes. The currently displayed version is the accepted final manuscript. The officially published version will be updated with format, DOI and citation information upon launch. We recommend that you pay attention to subsequent journal notifications and preferentially cite the officially published version. Thank you for your support and cooperation.