D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors

Overview

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.


Paper

D-Tucker is described in the following paper:


Code


Datasets

Name#Order#DimensionalityDescriptionLinkDownload
Brainq3(360,21764,9) fMRI dataset. consist of (word,voxel, person; measurement) Brainq Download
Boats3(320,240,7000) gray scale videos. consist of (height,width,frame; value) Boats Download
Air Quality3(30648, 376, 6) air pollutants information in Korea. consists of (timestamp in hour, location, atmospheric pollutants; measurement) Korean Air Quality Download
HSI4(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

Update Note

2020-10-31: README file of AirQuality dataset is updated. Meta files (time dictionary, location dictionary, and pollutants dictionary) of the AirQuality dataset are added.