An Efficient Randomized Fixed-Precision Algorithm for Tensor Singular Value Decomposition

doi:10.1007/s42967-022-00218-w

摘要/Abstract

摘要： The existing randomized algorithms need an initial estimation of the tubal rank to compute a tensor singular value decomposition. This paper proposes a new randomized fixed-precision algorithm which for a given third-order tensor and a prescribed approximation error bound, it automatically finds the tubal rank and corresponding low tubal rank approximation. The algorithm is based on the random projection technique and equipped with the power iteration method for achieving better accuracy. We conduct simulations on synthetic and real-world datasets to show the efficiency and performance of the proposed algorithm.

关键词: Tubal tensor decomposition, Randomization, Fixed-precision algorithm

Abstract: The existing randomized algorithms need an initial estimation of the tubal rank to compute a tensor singular value decomposition. This paper proposes a new randomized fixed-precision algorithm which for a given third-order tensor and a prescribed approximation error bound, it automatically finds the tubal rank and corresponding low tubal rank approximation. The algorithm is based on the random projection technique and equipped with the power iteration method for achieving better accuracy. We conduct simulations on synthetic and real-world datasets to show the efficiency and performance of the proposed algorithm.

Key words: Tubal tensor decomposition, Randomization, Fixed-precision algorithm

中图分类号:

Salman Ahmadi-Asl. An Efficient Randomized Fixed-Precision Algorithm for Tensor Singular Value Decomposition[J]. Communications on Applied Mathematics and Computation, 2023, 5(4): 1564-1583.

参考文献

1. Ahmadi-Asl, S., Caiafa, C.F., Cichocki, A., Phan, A.H., Tanaka, T., Oseledets, I., Wang, J.: Cross tensor approximation methods for compression and dimensionality reduction. IEEE Access 9, 150809- 150838 (2021)
2. Braman, K.: Third-order tensors as linear operators on a space of matrices. Linear Algebra Appl. 433(7), 1241-1253 (2010)
3. Che, M., Wang, X., Wei, Y., Zhao, X.: Fast randomized tensor singular value thresholding for low-rank tensor optimization. Numer. Linear Algebra Appl. 29, e2444 (2022)
4. Cichocki, A., Lee, N., Oseledets, I., Phan, A.-H., 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)
5. Cichocki, A., Mandic, D., De Lathauwer, L., Zhou, G., Zhao, Q., Caiafa, C., Phan, H.A.: Tensor decompositions for signal processing applications: from two-way to multiway component analysis. IEEE Signal Process. Mag. 32(2), 145-163 (2015)
6. Cichocki, A., Phan, A.-H., Zhao, Q., Lee, N., Oseledets, I., Sugiyama, M., Mandic, D.P.: Tensor networks for dimensionality reduction and large-scale optimization: part 2 applications and future perspectives. Found. Trends Mach. Learn. 9(6), 431-673 (2017)
7. Comon, P., Jutten, C.: Handbook of Blind Source Separation: Independent Component Analysis and Applications. Academic Press, Cambridge (2010)
8. De Lathauwer, L.: Decompositions of a higher-order tensor in block terms—part I: lemmas for partitioned matrices. SIAM J. Matrix Anal. Appl. 30(3), 1022-1032 (2008)
9. De Lathauwer, L.: Decompositions of a higher-order tensor in block terms—part II: definitions and uniqueness. SIAM J. Matrix Anal. Appl. 30(3), 1033-1066 (2008)
10. De Lathauwer, L., De Moor, B., Vandewalle, J.: A multilinear singular value decomposition. SIAM J. Matrix Anal. Appl. 21(4), 1253-1278 (2000)
11. De Lathauwer, L., Nion, D.: Decompositions of a higher-order tensor in block terms—part III: alternating least squares algorithms. SIAM J. Matrix Anal. Appl. 30(3), 1067-1083 (2008)
12. Ding, M., Xie, P.: A randomized singular value decomposition for third-order oriented tensors. arXiv:2203. 02761 (2022)
13. Espig, M., Naraparaju, K.K., Schneider, J.: A note on tensor chain approximation. Comput. Vis. Sci. 15(6), 331-344 (2012)
14. Gleich, D.F., Greif, C., Varah, J.M.: The power and Arnoldi methods in an algebra of circulants. Numer. Linear Algebra Appl. 20(5), 809-831 (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. 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)
17. 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)
18. Jiang, T.-X., Ng, M.K., Zhao, X.-L., Huang, T.-Z.: Framelet representation of tensor nuclear norm for third-order tensor completion. IEEE Trans. Image Process. 29, 7233-7244 (2020)
19. Kernfeld, E., Kilmer, M., Aeron, S.: Tensor-tensor products with invertible linear transforms. Linear Algebra Appl. 485, 545-570 (2015)
20. 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)
21. Kilmer, M.E., Martin, C.D.: Factorization strategies for third-order tensors. Linear Algebra Appl. 435(3), 641-658 (2011)
22. Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51(3), 455-500 (2009)
23. Leardi, R.: Multi-way Analysis with Applications in the Chemical Sciences, Age Smilde, Rasmus Bro and Paul Geladi, Wiley, Chichester, 2004, ISBN 0-471-98691-7, 381 pp. J. Chemomet. 19(2), 119-120 (2005)
24. 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)
25. Lund, K.: A new block Krylov subspace framework with applications to functions of matrices acting on multiple vectors, PhD Thesis, Temple University, Philadelphia, PA (2018)
26. Lund, K.: The tensor t-function: a definition for functions of third-order tensors. Numer. Linear Algebra Appl. 27(3), 1-17 (2020)
27. 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)
28. Martinsson, P.-G., Voronin, S.: A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices. SIAM J. Sci. Comput. 38(5), S485-S507 (2016)
29. 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)
30. Miao, Y., Qi, L., Wei, Y.: T-Jordan canonical form and T-drazin inverse based on the T-product. Commun. Appl. Math. Comput. 3, 201-220 (2021)
31. Nene, S.A., Nayar, S.K., Murase, H.: Columbia object image library (COIL-100), Report CUCS-006- 96 (1996). https://www.cs.columbia.edu/CAVE/software/softlib/coil-100.php
32. Newman, E.: A step in the right dimension: tensor algebra and applications, PhD Thesis, Tufts University, Medford (2019)
33. Newman, E., Horesh, L., Avron, H., Kilmer, M.: Stable tensor neural networks for rapid deep learning. arXiv: 1811. 06569 (2018)
34. Oseledets, I.V.: Tensor-train decomposition. SIAM J. Sci. Comput. 33(5), 2295-2317 (2011)
35. Phan, A.H., Cichocki, A.: Tensor decompositions for feature extraction and classification of high dimensional datasets. Nonlinear Theory and Its Applications, IEICE 1(1), 37-68 (2010)
36. Qi, L., Yu, G.: T-singular values and t-sketching for third order tensors. arXiv: 2103. 00976 (2021)
37. Sidiropoulos, N.D., De Lathauwer, L., Fu, X., Huang, K., Papalexakis, E.E., Faloutsos, C.: Tensor decomposition for signal processing and machine learning. IEEE Trans. Signal Process. 65(13), 3551- 3582 (2017)
38. Soltani, S., Kilmer, M.E., Hansen, P.C.: A tensor-based dictionary learning approach to tomographic image reconstruction. BIT Numer. Math. 56(4), 1425-1454 (2016)
39. Song, G., Ng, M.K., Zhang, X.: Robust tensor completion using transformed tensor singular value decomposition. Numer. Linear Algebra Appl. 27(3), e2299 (2020)
40. Tarzanagh, D.A., 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)
41. Tropp, J.A., Yurtsever, A., Udell, M., Cevher, V.: Practical sketching algorithms for low-rank matrix approximation. SIAM J. Matrix Anal. Appl. 38(4), 1454-1485 (2017)
42. Tucker, L.R.: Implications of factor analysis of three-way matrices for measurement of change. Probl. Meas. Change 15, 122-137 (1963)
43. Tucker, L.R.: Some mathematical notes on three-mode factor analysis. Psychometrika 31(3), 279-311 (1966)
44. Tucker, L.R.: The extension of factor analysis to three-dimensional matrices. In: Frederiksen, N., Gulliksen, H. (eds) Contributions to Mathematical Psychology, pp. 109-127. Holt, Rinehart and Winston, New York (1964)
45. Ugwu, U. O.: Viterative tensor factorization based on Krylov subspace-type methods with applications to image processing, PhD Thesis, Kent State University, Kent (2021)
46. 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)
47. 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)
48. 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)
49. Zhang, Z., Aeron, S.: Exact tensor completion using t-SVD. IEEE Trans. Signal Process. 65(6), 1511- 1526 (2017)
50. Zhang, Z., Ely, G., Aeron, S., Hao, N., Kilmer, M.: Novel methods for multilinear data completion and de-noising based on tensor-SVD. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3842-3849. IEEE (2014)
51. Zhao, Q., Zhou, G., Xie, S., Zhang, L., Cichocki, A.: Tensor ring decomposition. arXiv: 1606. 05535 (2016)

[1]	M. Pakmanesh, Hamidreza Afshin. T_M-Eigenvalues of Odd-Order Tensors[J]. Communications on Applied Mathematics and Computation, 2022, 4(4): 1258-1279.
[2]	Zhengbang Cao, Pengpeng Xie. Perturbation Analysis for t-Product-Based Tensor Inverse, Moore-Penrose Inverse and Tensor System[J]. Communications on Applied Mathematics and Computation, 2022, 4(4): 1441-1456.
[3]	Yun Miao, Liqun Qi, Yimin Wei. T-Jordan Canonical Form and T-Drazin Inverse Based on the T-Product[J]. Communications on Applied Mathematics and Computation, 2021, 3(2): 201-220.
[4]	Kim Batselier, Andrzej Cichocki, Ngai Wong. MERACLE: Constructive Layer-Wise Conversion of a Tensor Train into a MERA[J]. Communications on Applied Mathematics and Computation, 2021, 3(2): 257-279.
[5]	Mohsen Aliabadi, Shmuel Friedland. On the Complexity of Finding Tensor Ranks[J]. Communications on Applied Mathematics and Computation, 2021, 3(2): 281-289.
[6]	Guangbin Wang, Fuping Tan. Some Criteria for H-Tensors[J]. Communications on Applied Mathematics and Computation, 2020, 2(4): 641-651.
[7]	Changqing Xu, Kaijie Xu. Separable Symmetric Tensors and Separable Anti-symmetric Tensors[J]. Communications on Applied Mathematics and Computation, 2023, 5(4): 1509-1523.