On Tensor Train Rank Minimization: Statistical Efficiency and Scalable Algorithm
This work addresses limitations in tensor train decomposition for machine learning applications, offering theoretical guarantees and scalable solutions, though it is incremental in nature.
The paper tackled the lack of statistical theory and scalable algorithms for tensor train decomposition in machine learning by introducing a convex relaxation with error bounds for tensor completion and developing an efficient alternating optimization method, achieving time complexity as efficient as space complexity and confirming results numerically.
Tensor train (TT) decomposition provides a space-efficient representation for higher-order tensors. Despite its advantage, we face two crucial limitations when we apply the TT decomposition to machine learning problems: the lack of statistical theory and of scalable algorithms. In this paper, we address the limitations. First, we introduce a convex relaxation of the TT decomposition problem and derive its error bound for the tensor completion task. Next, we develop an alternating optimization method with a randomization technique, in which the time complexity is as efficient as the space complexity is. In experiments, we numerically confirm the derived bounds and empirically demonstrate the performance of our method with a real higher-order tensor.