Low-Rank Tucker Approximation of a Tensor From Streaming Data
This provides an efficient solution for tensor decomposition in streaming or distributed settings, which is incremental but offers practical gains for data analysis applications.
The paper tackles the problem of computing low-Tucker-rank approximations of tensors from streaming data, introducing a randomized sketching algorithm that uses storage proportional to the output's degrees of freedom and achieves rigorous error guarantees, with experiments showing improvements over state-of-the-art methods.
This paper describes a new algorithm for computing a low-Tucker-rank approximation of a tensor. The method applies a randomized linear map to the tensor to obtain a sketch that captures the important directions within each mode, as well as the interactions among the modes. The sketch can be extracted from streaming or distributed data or with a single pass over the tensor, and it uses storage proportional to the degrees of freedom in the output Tucker approximation. The algorithm does not require a second pass over the tensor, although it can exploit another view to compute a superior approximation. The paper provides a rigorous theoretical guarantee on the approximation error. Extensive numerical experiments show that that the algorithm produces useful results that improve on the state of the art for streaming Tucker decomposition.