Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions

Abstract

Low-rank Tucker and CP tensor decompositions are powerful tools in data analytics. The widely used alternating least squares (ALS) method, which solves a sequence of over-determined least squares subproblems, is costly for large and sparse tensors. We propose a fast and accurate sketched ALS algorithm for Tucker decomposition, which solves a sequence of sketched rank-constrained linear least squares subproblems. Theoretical sketch size upper bounds are provided to achieve $O(\epsilon )$ relative error for each subproblem with two sketching techniques, TensorSketch and leverage score sampling. Experimental results show that this new ALS algorithm, combined with a new initialization scheme based on randomized range finder, yields up to $22.0\%$ relative decomposition residual improvement compared to the state-of-the-art sketched randomized algorithm for Tucker decomposition of various synthetic and real datasets. This Tucker-ALS algorithm is further used to accelerate CP decomposition, by using randomized Tucker compression followed by CP decomposition of the Tucker core tensor. Experimental results show that this algorithm not only converges faster, but also yields more accurate CP decompositions.

References in corpus (7)

• Low rank factorization of the Coulomb integrals for periodic coupled cluster theory
• Approximate tensor-product preconditioners for very high order discontinuous Galerkin methods
• Decomposition of Big Tensors With Low Multilinear Rank
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• A Practical Guide to Randomized Matrix Computations with MATLAB Implementations
• Tensor Random Projection for Low Memory Dimension Reduction
• Efficient parallel CP decomposition with pairwise perturbation and multi-sweep dimension tree

Cited by in corpus (4)

• TUCKET: A Tensor Time Series Data Structure for Efficient and Accurate Factor Analysis over Time Ranges
• Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm
• Parallel algorithms for computing the tensor-train decomposition
• A rank-adaptive higher-order orthogonal iteration algorithm for truncated Tucker decomposition