A fast sketching-based algorithm for rank-(L, L, 1) block term decomposition. (November 2022)

• Record Type: Journal Article
• Authors: Zhang, Hao; Huang, Ting-Zhu; Zhao, Xi-Le
• Is Part Of: Applied mathematics letters. Volume 133(2022)
• Publication Date: 2022-11
• Subjects: Block term decomposition -- Randomized algorithm -- Tensor sketching -- High-order data processing; Applied mathematics -- Periodicals; 519.05
• DOI: 10.1016/j.aml.2022.108252
• Languages: English
• ISSNs: 0893-9659

Abstract

Abstract: The rank- ( L, L, 1 ) block term decomposition (BTD) of the tensor has recently received increasing attention in diverse high-order data processing, e.g., hyperspectral image restoration and blind source separation. However, the standard alternating least squares algorithm for the rank- ( L, L, 1 ) BTD (BTD-ALS) is computationally expensive, which hinders its application on real large-scale data. In this paper, we propose a fast sketching-based algorithm for the rank- ( L, L, 1 ) BTD (FastBTD) to address the computational burden of BTD-ALS. Since the dominant cost of BTD-ALS at each iteration is the sequence of large-scale least squares subproblems, we first project these original subproblems into the low-dimensional subspace by the tensor sketching operator. Then, we can fastly obtain the approximate solutions of the original subproblems by solving these sketched small-scale subproblems at each iteration of FastBTD. The computational complexity of FastBTD ( O ( 2 J I L R + J I R ) ) is significantly lower than that of BTD-ALS ( O ( 2 I 3 L R + I 3 R ) ) for solving the least squares subproblems at each iteration, when J ≪ I 2 . Moreover, we provide the theoretical error bound for FastBTD. Extensive experiments on both synthetic and real data demonstrate that FastBTD achieves substantial speedup while maintaining accuracy compared with BTD-ALS.