Efficient Tensor Contraction via Fast Count Sketch
Sketching uses randomized Hash functions for dimensionality reduction and acceleration. The existing sketching methods, such as count sketch (CS), tensor sketch (TS), and higher-order count sketch (HCS), either suffer from low accuracy or slow speed in some tensor based applications. In this paper, the proposed fast count sketch (FCS) applies multiple shorter Hash functions based CS to the vector form of the input tensor, which is more accurate than TS since the spatial information of the input tensor can be preserved more sufficiently. When the input tensor admits CANDECOMP/PARAFAC decomposition (CPD), FCS can accelerate CS and HCS by using fast Fourier transform, which exhibits a computational complexity asymptotically identical to TS for low-order tensors. The effectiveness of FCS is validated by CPD, tensor regression network compression, and Kronecker product compression. Experimental results show its superior performance in terms of approximation accuracy and computational efficiency.
Code (0)
등록된 구현이 없습니다.
Tasks
Computational EfficiencyDimensionality ReductionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Fast and Guaranteed Tensor Decomposition via Sketching
Tensor CANDECOMP/PARAFAC (CP) decomposition has wide applications in statistical learning of latent variable models and in data mining. In this paper, we propose fast and randomized tensor CP decomposition algorithms bas…
Tensor DecompositionHigher-order Count Sketch: Dimensionality Reduction That Retains Efficient Tensor Operations
Sketching is a randomized dimensionality-reduction method that aims to preserve relevant information in large-scale datasets. Count sketch is a simple popular sketch which uses a randomized hash function to achieve compr…
Dimensionality Reductionimage-classificationImage ClassificationCost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputs
This work discusses tensor network embeddings, which are random matrices ($S$) with tensor network structure. These embeddings have been used to perform dimensionality reduction of tensor network structured inputs $x$ an…
Dimensionality ReductionTensor DecompositionEfficient Contraction of Large Tensor Networks for Weighted Model Counting through Graph Decompositions
Constrained counting is a fundamental problem in artificial intelligence. A promising new algebraic approach to constrained counting makes use of tensor networks, following a reduction from constrained counting to the pr…
Tensor NetworksFast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions
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 f…