Randomized Algorithms for Tensor Decompositions in the Tucker Format

Abstract:
With the scale of data continually increasing, it has become infeasible to store and access all of a dataset at once. Randomized methods can ease the burden of working with such large amounts of data by closely approximating the data in smaller dimensions. Data today also frequently has inherent multidimensional structure, but standard techniques treat the data as two-dimensional. Handling this type of data as tensors allows us to exploit the multidimensional structure for cost- and memory-saving benefits. In this talk, I will demonstrate the effectiveness of randomized methods in approximating both matrices and tensors. Specifically, I will consider randomized SVD algorithms, and discuss how to incorporate this kind of randomization into a popular algorithm for tensor decompositions in the Tucker form. I will also improve upon the base tensor approximation algorithm in several ways. One way is by employing new sketching techniques that exploit structure of the random matrices involved to accelerate key computations. Another is by using subset selection methods in combination with randomized techniques to create an algorithm that preserves structure of the original data, thus allowing computations with large, sparse, datasets that were previously infeasible. To accompany the algorithms, I will show probabilistic error bounds as well as numerical results demonstrating the performance on synthetic and real-world data.