基于随机素描的单通高阶张量分解算法

doi:10.12677/airr.2026.155117

期刊菜单

基于随机素描的单通高阶张量分解算法
Single-Pass High-Order Tensor Decomposition Algorithms Based on Randomized Sketching Techniques

DOI: 10.12677/airr.2026.155117, PDF,
作者: 李翼, 覃文金^*：西南大学数学与统计学院，重庆
关键词: 高阶张量分解；单通随机算法；高斯投影；误差上界理论；High-Order Tensor Decomposition； Single-Pass Randomized Algorithm； Gaussian Projection； Error Upper Bound Theory

摘要: 基于随机素描技术与张量–张量乘积框架，本文研究了若干针对高阶张量LU分解的单通随机算法。这类算法仅需对原始张量进行一次访问遍历，因此非常适用于存储在核心内存之外、或以流方式生成的大规模高阶张量。文中已严谨推导了这些算法的误差上界理论与计算复杂度。数值实验表明，相比于当前前沿的随机张量分解算法，所提出的高效单通算法在精度与CPU运行时间上均具有优势性。

Abstract: In this paper, by leveraging tensor-tensor product framework, we develop some single-pass randomized algorithms for high-order tensor LU decomposition based on sketching techniques. These algorithms need only one pass over the original tensor and hence are very suitable for extremely large and high-dimensional tensor stored outside of core memory or generated in a streaming fashion. Rigorous error upper bound theory and complexity analysis of these algorithms have been derived. Numerical experiments show that the proposed efficient single-pass algorithms have the similar accuracy and CPU runtime compared with the state-of-the-art randomized algorithms for high-order tensor decomposition.

文章引用：李翼, 覃文金. 基于随机素描的单通高阶张量分解算法[J]. 人工智能与机器人研究, 2026, 15(5): 1276-1292. https://doi.org/10.12677/airr.2026.155117

参考文献

[1]	Shu, H., Wang, H., Peng, J. and Meng, D. (2024) Low-Rank Tensor Completion with 3-D Spatiotemporal Transform for Traffic Data Imputation. IEEE Transactions on Intelligent Transportation Systems, 25, 18673-18687. https://doi.org/10.1109/tits.2024.3422214
[2]	李德仁, 张良培, 夏桂松. 遥感大数据自动分析与数据挖掘[J]. 测绘学报, 2014, 43(12): 1211-1216.
[3]	Liu, C., Li, S., Hu, D., Wang, J., Qin, W., Liu, C., et al. (2024) Nonlocal Tensor Decomposition with Joint Low Rankness and Smoothness for Spectral CT Image Reconstruction. IEEE Transactions on Computational Imaging, 10, 613-627. https://doi.org/10.1109/tci.2024.3384812
[4]	Wang, Y., Hou, H., Yi, X., Wang, W. and Jin, S. (2025) Toward Unified AI Models for MU-MIMO Communications: A Tensor Equivariance Framework. IEEE Transactions on Wireless Communications, 24, 10517-10533. https://doi.org/10.1109/twc.2025.3580321
[5]	Kolda, T.G. and Bader, B.W. (2009) Tensor Decompositions and Applications. SIAM Review, 51, 455-500. https://doi.org/10.1137/07070111x
[6]	Tucker, L.R. (1966) Some Mathematical Notes on Three-Mode Factor Analysis. Psychometrika, 31, 279-311. https://doi.org/10.1007/bf02289464
[7]	Oseledets, I.V. (2011) Tensor-Train Decomposition. SIAM Journal on Scientific Computing, 33, 2295-2317. https://doi.org/10.1137/090752286
[8]	Zhao, Q., Zhou, G., Xie, S., Zhang, L. and Cichocki, A. (2016) Tensor Ring Decomposition. arXiv: 1606.05535.
[9]	Kilmer, M.E., Horesh, L., Avron, H. and Newman, E. (2021) Tensor-Tensor Algebra for Optimal Representation and Compression of Multiway Data. Proceedings of the National Academy of Sciences, 118, e2015851118. https://doi.org/10.1073/pnas.2015851118
[10]	Zheng, Y.-B., Huang, T.-Z., Zhao, X.-L., Zhao, Q. and Jiang, T.-X. (2021) Fully-Connected Tensor Network Decomposition and Its Application to Higher-Order Tensor Completion. Proceedings of the AAAI Conference on Artificial Intelligence, 35, 11071-11078. https://doi.org/10.1609/aaai.v35i12.17321
[11]	Woodruff, D.P. (2014) Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends® in Theoretical Computer Science, 10, 1-157. https://doi.org/10.1561/0400000060
[12]	Martinsson, P. and Tropp, J.A. (2020) Randomized Numerical Linear Algebra: Foundations and Algorithms. Acta Numerica, 29, 403-572. https://doi.org/10.1017/s0962492920000021
[13]	Murray, R., Demmel, J., Mahoney, M.W., et al. (2023) Randomized Numerical Linear Algebra: A Perspective on the Field with an Eye to Software. arXiv: 2302.11474.
[14]	Minster, R., Saibaba, A.K. and Kilmer, M.E. (2020) Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format. SIAM Journal on Mathematics of Data Science, 2, 189-215. https://doi.org/10.1137/19m1261043
[15]	Che, M., Wei, Y. and Yan, H. (2020) The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection. SIAM Journal on Matrix Analysis and Applications, 41, 605-636. https://doi.org/10.1137/19m1237016
[16]	Che, M., Wei, Y. and Yan, H. (2025) Efficient Randomized Algorithms for Fixed Precision Problem of Approximate Tucker Decomposition. SIAM Journal on Matrix Analysis and Applications, 46, 256-297. https://doi.org/10.1137/23m1594066
[17]	Ahmadi-Asl, S., Cichocki, A., Huy Phan, A., Asante-Mensah, M.G., Musavian Ghazani, M., Tanaka, T., et al. (2020) Randomized Algorithms for Fast Computation of Low Rank Tensor Ring Model. Machine Learning: Science and Technology, 2, Article 011001. https://doi.org/10.1088/2632-2153/abad87
[18]	Shi, T., Ruth, M. and Townsend, A. (2023) Parallel Algorithms for Computing the Tensor-Train Decomposition. SIAM Journal on Scientific Computing, 45, C101-C130. https://doi.org/10.1137/21m146079x
[19]	Al Daas, H., Ballard, G., Cazeaux, P., Hallman, E., Międlar, A., Pasha, M., et al. (2023) Randomized Algorithms for Rounding in the Tensor-Train Format. SIAM Journal on Scientific Computing, 45, A74-A95. https://doi.org/10.1137/21m1451191
[20]	Zhang, J., Saibaba, A.K., Kilmer, M.E. and Aeron, S. (2018) A Randomized Tensor Singular Value Decomposition Based on the T‐Product. Numerical Linear Algebra with Applications, 25, e2179. https://doi.org/10.1002/nla.2179
[21]	Tarzanagh, D.A. and Michailidis, G. (2018) Fast Randomized Algorithms for T-Product Based Tensor Operations and Decompositions with Applications to Imaging Data. SIAM Journal on Imaging Sciences, 11, 2629-2664. https://doi.org/10.1137/17m1159932
[22]	Qin, W., Wang, H., Zhang, F., Ma, W., Wang, J. and Huang, T. (2024) Nonconvex Robust High-Order Tensor Completion Using Randomized Low-Rank Approximation. IEEE Transactions on Image Processing, 33, 2835-2850. https://doi.org/10.1109/tip.2024.3385284
[23]	Halko, N., Martinsson, P.G. and Tropp, J.A. (2011) Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions. SIAM Review, 53, 217-288. https://doi.org/10.1137/090771806
[24]	Tropp, J.A., Yurtsever, A., Udell, M. and Cevher, V. (2017) Practical Sketching Algorithms for Low-Rank Matrix Approximation. SIAM Journal on Matrix Analysis and Applications, 38, 1454-1485. https://doi.org/10.1137/17m1111590
[25]	Bjarkason, E.K. (2019) Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views. SIAM Journal on Scientific Computing, 41, A2355-A2383. https://doi.org/10.1137/18m118966x
[26]	Kaloorazi, M.F. and de Lamare, R.C. (2018) Subspace-Orbit Randomized Decomposition for Low-Rank Matrix Approximations. IEEE Transactions on Signal Processing, 66, 4409-4424. https://doi.org/10.1109/tsp.2018.2853137
[27]	Li, H. and Yin, S. (2020) Single-Pass Randomized Algorithms for LU Decomposition. Linear Algebra and Its Applications, 595, 101-122. https://doi.org/10.1016/j.laa.2020.03.001
[28]	孙峻聪. 基于DCT变换的分块单通张量素描算法及其应用[D]: [硕士学位论文]. 杭州: 杭州电子科技大学, 2024.
[29]	程志光. 基于变换域下的素描算法在张量低秩近似中的应用[D]: [硕士学位论文]. 杭州: 杭州电子科技大学, 2023.
[30]	Qin, W., Wang, H., Zhang, F., Wang, J., Luo, X. and Huang, T. (2022) Low-Rank High-Order Tensor Completion with Applications in Visual Data. IEEE Transactions on Image Processing, 31, 2433-2448. https://doi.org/10.1109/tip.2022.3155949
[31]	Litvak, A.E., Pajor, A., Rudelson, M. and Tomczak-Jaegermann, N. (2005) Smallest Singular Value of Random Matrices and Geometry of Random Polytopes. Advances in Mathematics, 195, 491-523. https://doi.org/10.1016/j.aim.2004.08.004

为你推荐

友情链接