A random sampling algorithm for fully-connected tensor network decomposition with applications

Fully-connected tensor network (FCTN) decomposition is a generalization of the popular tensor train and tensor ring decompositions and has been applied to various fields with great success. The standard method for computing this decomposition is the well-known alternating least squares (ALS). However, it is very expensive, especially for large-scale tensors. To reduce the cost, we propose an ALS-based randomized algorithm. Specifically, by defining a new tensor product called subnetwork product and adjusting the sizes of FCTN factors suitably, the structure of the coefficient matrices of the ALS subproblems from FCTN decomposition is first figured out. Then, with the structure and the properties of subnetwork product, we devise the randomized algorithm based on leverage sampling. This algorithm enables sampling on FCTN factors and hence avoids the formation of full coefficient matrices of ALS subproblems. The computational complexity and numerical performance of our algorithm are presented. Experimental results show that it requires much less computation time to achieve similar accuracy compared with the deterministic ALS method. Further, we apply our algorithm to four famous problems, i.e., tensor-on-vector regression, multi-view subspace clustering, nonnegative tensor approximation and tensor completion, and the performances are quite decent.