In-Place Algorithm for Data Analysis and Compression

What is it about?

The Tucker Decomposition is a common unsupervised learning technique that is used to analyze and compress high-dimensional data (tensors). We present an algorithm that is significantly more memory efficient than the existing state-of-the-art algorithm for computing this decomposition. Existing algorithms consume memory that is proportional to the size of the original dataset to hold intermediate decompositions. The proposed FIST-HOSVD algorithm removes this constraint by overwriting the original dataset with its decomposition, thereby increasing the size of the dataset that can be compressed by up to 3x. We demonstrate that this algorithm leads to over 135x reduction in memory consumption for computing combustion simulations compared to the existing state-of-the-art algorithm.

Featured Image

Photo by Milad Fakurian on Unsplash

Photo by Milad Fakurian on Unsplash

Why is it important?

In the age of big data, memory is an extremely valuable resource. Our ability to collect and generate data is often more than we are able to feasibly store. Data compression algorithms like the Tucker Decomposition are a valuable tool to help alleviate this problem. Existing algorithms require lots of additional memory to compute the Tucker Decomposition. The proposed FIST-HOSVD algorithm requires very little additional memory compared to all existing algorithms. When the dataset one wishes to compress is more than 1/3 the size of available memory existing approaches are likely to run out memory thereby making it infeasible to compress the dataset via the Tucker Decomposition, whilst the FIST-HOSVD algorithm does not have this constraint. This is very important when the dataset larger than 1/3 available memory.

Perspectives