Sketching Based Fast Tensor Computation

In recent years,the emergence of large-scale datasets has increased the burden of software and hardware for data processing,transmission,and storage.Sketching refers to a subclass of the randomization-based algorithms.It uses a structured random sketching matrix to map the input data to the low dimensional sketched subspace,while retaining some useful information of the data.Using sketching techniques,some statistics of the original data can be approximately estimated in the sketched subspace directly.Therefore,algorithm acceleration and data dimensionality reduction can be realized at the cost of accuracy loss to some extent.This paper mainly studies the sketching algorithms to improve their approximation accuracy and computation efficiency in the application of tensor computation.Robust Tensor Power Method(RTPM)is a tensor CANDECOMP/PARAFAC decomposition algorithm.It needs to calculate tensor contractions in the process of each power iteration,resulting in low computational efficiency.Tensor Sketch(TS)has been used to accelerate RTPM,but the existing TS-based RTPM(TS-RTPM)is data-oblivious and does not make use of the distribution information of input data.This paper proposes the first data-driven TS framework named TS-Fast-RTPM-Net(TS-FRTPM-Net),which improves the efficiency of TS-RTPM by unrolling the outer iteration of TS-RTPM algorithm into Fast Power Iterations(FPI)modules of a neural network.Specifically,TSFRTPM-Net uses stochastic gradient descent method to optimize TS value matrices and RTPM initial matrices,and uses two greedy algorithms to optimize TS location matrices,which improves the approximation accuracy of TS-RTPM.In addition,by computing power iterations parallelly in FPI modules,the acceleration of TS-RTPM is realized.The experimental results show that compared with TS-RTPM,TS-FRTPM-Net has advantages in accuracy,speed and memory consumption,plus transferability to some extent.The existing sketching techniques have some limitations: Count Sketch(CS)is essentially a sketch for vectors.When the input is a high-order tensor,it needs to sketch along its vectorization.Therefore,constructing the CS matrix requires a pair of hash functions with a large size,which increases the memory consumption for the hash functions.In addition,for some tensors with specific structures,such as rank-1 tensors,CS cannot use its structural characteristics to accelerate sketch computation.TS uses multiple pairs of small-sized hash functions to construct the sketching matrix,so the storage consumption is much lower than CS.And it possesses a fast algorithm for rank-1 tensor.However,the construction of the TS matrix inevitably leads to hash confliction,which results in low approximation accuracy.Combining the advantages of CS and TS,this paper proposes a new sketching technique named Fast Count Sketch(FCS).FCS constructs sketching matrix in a similar way as TS,but uses a method similar to public overflow area to avoid hash confliction.While improving the approximation accuracy of TS,FCS inherits the advantages of TS in low storage complexity and efficient computation for rank-1 tensors.Theoretical analysis and numerical experimental results show that compared with CS and TS,FCS has advantages in approximation accuracy or computational efficiency.