Given a dense tensor, how can we efficiently find latent patterns and relations? Tucker decomposition is widely used for analyzing multidimensional data in the form of tensors. However, existing Tucker decomposition methods have limitations of time and space since they directly handle large dense tensors to obtain the result of Tucker decomposition. Although few methods have tried to reduce their computational time by sampling tensors, sketching tensors, and efficient matrix operations, their speed is limited and the scalability issues still remain.
In this paper, we propose D-Tucker, a fast and memory-efficient method for Tucker decomposition on large dense tensors. D-Tucker consists of the approximation, the initialization, and the iteration phases. In the approximation phase, D-Tucker computes randomized singular value decomposition of matrices sliced from a tensor. In the initialization phase, D-Tucker provides initial factor matrices to reduce the number of iterations in the iteration phase. In the iteration phase, D-Tucker iteratively updates orthogonal factor matrices and a core tensor by using SVD results of sliced matrices. Through experiments, we show that D-Tucker is up to 38.4x faster, and requires up to 17.2x less space than existing methods with little sacrifice in accuracy. Furthermore, D-Tucker provides the best scalability with regard to dimensionality, rank, order, and number of iterations.
D-Tucker is described in the following paper:
The paper is accepted to ICDE2020 as a short paper[Paper]
|Brainq||3||(360,21764,9)||fMRI dataset. consist of (word,voxel, person; measurement)||Brainq||Download|
|Boats||3||(320,240,7000)||gray scale videos. consist of (height,width,frame; value)||Boats||Download|
|Air Quality||3||(30648, 376, 6)||air pollutants information in Korea. consists of (timestamp in hour, location, atmospheric pollutants; measurement)||Korean Air Quality||Download|
|HSI||4||(1021,1340,33,8)||hyperspectral images of natural scenes. consist of (number of images, spatial dimension (x), spatial dimension (y), spectral dimension; value)||HSI||Download|