Robust low tubal rank tensor recovery using discrete empirical interpolation method with optimized slice/feature selection. (English) Zbl 1537.65050
Summary: In this paper, we extend the Discrete Empirical Interpolation Method (DEIM) to the third-order tensor case based on the t-product and use it to select important/significant lateral and horizontal slices/features. The proposed Tubal DEIM (TDEIM) is investigated both theoretically and numerically. In particular, the details of the error bounds of the proposed TDEIM method are derived. The experimental results show that the TDEIM can provide more accurate approximations than the existing methods. An application of the proposed method to the supervised classification task is also presented.
MSC:
| 65F99 | Numerical linear algebra |
| 15A23 | Factorization of matrices |
| 15A69 | Multilinear algebra, tensor calculus |
References:
| [1] | Beltrami, E.: Sulle funzioni bilineari. Giornale di Matematiche ad Uso degli Studenti Delle Universita 11(2), 98-106 (1873) · JFM 05.0085.02 |
| [2] | Jordan, C., Mémoire sur les formes bilinéaires, Journal de mathématiques pures et appliquées, 19, 35-54, 1874 · JFM 06.0070.02 |
| [3] | Jordan, C., Essai sur la géométrie à \(n\) dimensions, Bulletin de la Société mathématique de France, 3, 103-174, 1875 · JFM 07.0457.01 · doi:10.24033/bsmf.90 |
| [4] | Stewart, GW, On the early history of the singular value decomposition, SIAM Rev., 35, 4, 551-566, 1993 · Zbl 0799.01016 · doi:10.1137/1035134 |
| [5] | Tyrtyshnikov, E., Incomplete cross approximation in the mosaic-skeleton method, Computing, 64, 4, 367-380, 2000 · Zbl 0964.65048 · doi:10.1007/s006070070031 |
| [6] | Goreinov, SA; Tyrtyshnikov, EE; Zamarashkin, NL, A theory of pseudoskeleton approximations, Linear Algebra Appl., 261, 1-3, 1-21, 1997 · Zbl 0877.65021 · doi:10.1016/S0024-3795(96)00301-1 |
| [7] | Mahoney, M.W., et al.: Randomized algorithms for matrices and data, Foundations and Trends® in Machine Learning 3(2), 123-224 (2011) · Zbl 1232.68173 |
| [8] | Goreinov, S. A., Oseledets, I. V., Savostyanov, D.V., Tyrtyshnikov, E.E., Zamarashkin, N.L.: How to find a good submatrix, in: Matrix Methods: Theory, Algorithms And Applications: Dedicated to the Memory of Gene Golub, World Scientific, pp. 247-256 (2010) · Zbl 1215.65078 |
| [9] | Sorensen, DC; Embree, M., A DEIM induced CUR factorization, SIAM J. Sci. Comput, 38, 3, A1454-A1482, 2016 · Zbl 1382.65121 · doi:10.1137/140978430 |
| [10] | Savostyanov, D.: Polilinear approximation of matrices and integral equations, Ph. D. dissertation, Dept. Math., INM RAS, Moscow, Russia (2006) |
| [11] | Van Loan, CF, Generalizing the singular value decomposition, SIAM J. Numer. Anal., 13, 1, 76-83, 1976 · Zbl 0338.65022 · doi:10.1137/0713009 |
| [12] | Paige, CC; Saunders, MA, Towards a generalized singular value decomposition, SIAM J. Numer. Anal., 18, 3, 398-405, 1981 · Zbl 0471.65018 · doi:10.1137/0718026 |
| [13] | Gidisu, PY; Hochstenbach, ME, A generalized CUR decomposition for matrix pairs, SIAM J. Math. Data Sci., 4, 1, 386-409, 2022 · Zbl 1492.65110 · doi:10.1137/21M1432119 |
| [14] | Gidisu, P.Y., Hochstenbach, M. E.: A restricted SVD type CUR decomposition for matrix triplets, arXiv preprint arXiv:2204.02113 (2022) |
| [15] | Oseledets, IV; Savostianov, D.; Tyrtyshnikov, EE, Tucker dimensionality reduction of three-dimensional arrays in linear time, SIAM J. Matrix Anal. Appl., 30, 3, 939-956, 2008 · Zbl 1180.15025 · doi:10.1137/060655894 |
| [16] | Oseledets, I.; Tyrtyshnikov, E., TT-cross approximation for multidimensional arrays, Linear Algebra Appl., 432, 1, 70-88, 2010 · Zbl 1183.65040 · doi:10.1016/j.laa.2009.07.024 |
| [17] | Caiafa, CF; Cichocki, A., Generalizing the column-row matrix decomposition to multi-way arrays, Linear Algebra Appl., 433, 3, 557-573, 2010 · Zbl 1194.15025 · doi:10.1016/j.laa.2010.03.020 |
| [18] | Drineas, P.; Mahoney, MW, A randomized algorithm for a tensor-based generalization of the singular value decomposition, Linear Algebra Appl., 420, 2-3, 553-571, 2007 · Zbl 1108.65032 · doi:10.1016/j.laa.2006.08.023 |
| [19] | Tarzanagh, DA; Michailidis, G., Fast randomized algorithms for t-product based tensor operations and decompositions with applications to imaging data, SIAM J. Imaging Sci., 11, 4, 2629-2664, 2018 · Zbl 07115010 · doi:10.1137/17M1159932 |
| [20] | Tucker, L.R., et al.: The extension of factor analysis to three-dimensional matrices, Contributions to mathematical psychology 110119 (1964) |
| [21] | Tucker, LR, Some mathematical notes on three-mode factor analysis, Psychometrika, 31, 3, 279-311, 1966 · doi:10.1007/BF02289464 |
| [22] | Oseledets, IV, Tensor-train decomposition, SIAM J. Sci. Comput., 33, 5, 2295-2317, 2011 · Zbl 1232.15018 · doi:10.1137/090752286 |
| [23] | 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., 34, 1, 148-172, 2013 · Zbl 1269.65044 · doi:10.1137/110837711 |
| [24] | Hitchcock, FL, The expression of a tensor or a polyadic as a sum of products, J. Math. Phys., 6, 1-4, 164-189, 1927 · JFM 53.0095.01 · doi:10.1002/sapm192761164 |
| [25] | Hitchcock, FL, Multiple invariants and generalized rank of a p-way matrix or tensor, J. Math. Phys., 7, 1-4, 39-79, 1928 · JFM 53.0097.01 · doi:10.1002/sapm19287139 |
| [26] | 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, 9, 150809-150838, 2021 · doi:10.1109/ACCESS.2021.3125069 |
| [27] | Ahmadi-Asl, S., Asante-Mensah, M.G., Cichocki, A., Phan, A.H., Oseledets, I., Wang, J.: Cross tensor approximation for image and video completion, arXiv preprint arXiv:2207.06072 (2022) |
| [28] | Saibaba, AK, Hoid: higher order interpolatory decomposition for tensors based on tucker representation, SIAM J. Matrix Anal. Appl., 37, 3, 1223-1249, 2016 · Zbl 1347.65079 · doi:10.1137/15M1048628 |
| [29] | Kilmer, ME; Martin, CD, Factorization strategies for third-order tensors, Linear Algebra Appl., 435, 3, 641-658, 2011 · Zbl 1228.15009 · doi:10.1016/j.laa.2010.09.020 |
| [30] | Kernfeld, E.; Kilmer, M.; Aeron, S., Tensor-tensor products with invertible linear transforms, Linear Algebra Appl., 485, 545-570, 2015 · Zbl 1323.15016 · doi:10.1016/j.laa.2015.07.021 |
| [31] | Jiang, TX; Ng, MK; Zhao, XL; Huang, TZ, Framelet representation of tensor nuclear norm for third-order tensor completion, IEEE Trans. Image Process., 29, 7233-7244, 2020 · Zbl 07586396 · doi:10.1109/TIP.2020.3000349 |
| [32] | Li, BZ; Zhao, XL; Ji, TY; Zhang, XJ; Huang, TZ, Nonlinear transform induced tensor nuclear norm for tensor completion, J. Sci. Comput., 92, 3, 83, 2022 · Zbl 1497.65084 · doi:10.1007/s10915-022-01937-1 |
| [33] | Song, G.; Ng, MK; Zhang, X., Robust tensor completion using transformed tensor singular value decomposition, Numer. Linear Algebra Appl., 27, 3, e2299, 2020 · Zbl 07217207 · doi:10.1002/nla.2299 |
| [34] | 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 · doi:10.1109/TPAMI.2019.2891760 |
| [35] | Zhang, J.; Saibaba, AK; Kilmer, ME; Aeron, S., A randomized tensor singular value decomposition based on the t-product, Numer. Linear Algebra Appl., 25, 5, e2179, 2018 · Zbl 1513.65104 · doi:10.1002/nla.2179 |
| [36] | Martin, CD; Shafer, R.; LaRue, B., An order-p tensor factorization with applications in imaging, SIAM J. Sci. Comput., 35, 1, A474-A490, 2013 · Zbl 1273.15032 · doi:10.1137/110841229 |
| [37] | Hao, N.; Kilmer, ME; Braman, K.; Hoover, RC, Facial recognition using tensor-tensor decompositions, SIAM J. Imaging Sci., 6, 1, 437-463, 2013 · Zbl 1305.15061 · doi:10.1137/110842570 |
| [38] | Hamm, K.; Huang, L., Perspectives on cur decompositions, Appl. Comput. Harmon. Anal., 48, 3, 1088-1099, 2020 · Zbl 1432.15014 · doi:10.1016/j.acha.2019.08.006 |
| [39] | Drineas, P.; Mahoney, MW; Muthukrishnan, S., Relative-error CUR matrix decompositions, SIAM J. Matrix Anal. Appl., 30, 2, 844-881, 2008 · Zbl 1183.68738 · doi:10.1137/07070471X |
| [40] | Barrault, M., Maday, Y., Nguyen, N.C., Patera, A.T.: An ‘empirical interpolation’method: application to efficient reduced-basis discretization of partial differential equations. Comptes Rendus Mathematique 339(9), 667-672 (2004) · Zbl 1061.65118 |
| [41] | Chaturantabut, S.; Sorensen, DC, Nonlinear model reduction via discrete empirical interpolation, SIAM J. Sci. Comput., 32, 5, 2737-2764, 2010 · Zbl 1217.65169 · doi:10.1137/090766498 |
| [42] | 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, Springer, pp. 147-153 (2022) · Zbl 07737827 |
| [43] | Ahmadi-Asl, S.: An efficient randomized fixed-precision algorithm for tensor singular value decomposition, Communications on Applied Mathematics and Computation 1-20 (2022) |
| [44] | Ahmadi-Asl, S.: A randomized algorithm for tensor singular value decomposition using an arbitrary number of passes, arXiv preprint arXiv:2207.12542 (2022) |
| [45] | Lee, TS, Image representation using 2d gabor wavelets, IEEE Trans. Pattern Anal. Mach. Intell., 18, 10, 959-971, 1996 · doi:10.1109/34.541406 |
| [46] | Hastie, T., Tibshirani, R., Friedman, J.H., Friedman, J.H.: The elements of statistical learning: data mining, inference, and prediction, Vol. 2, Springer, (2009) · Zbl 1273.62005 |
| [47] | Fisher, RA, The use of multiple measurements in taxonomic problems, Ann. Eugen., 7, 2, 179-188, 1936 · doi:10.1111/j.1469-1809.1936.tb02137.x |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
