On Tensor Train Rank Minimization : Statistical Efficiency and Scalable Algorithm
Masaaki Imaizumi, Takanori Maehara, Kohei Hayashi
Abstract
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 a randomized optimization method, 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.
BibTeX
@inproceedings{NIPS2017_1b5230e3,
author = {Imaizumi, Masaaki and Maehara, Takanori and Hayashi, Kohei},
booktitle = {Advances in Neural Information Processing Systems},
editor = {I. Guyon and U. Von Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {On Tensor Train Rank Minimization : Statistical Efficiency and Scalable Algorithm},
url = {https://proceedings.neurips.cc/paper_files/paper/2017/file/1b5230e3ea6d7123847ad55a1e06fffd-Paper.pdf},
volume = {30},
year = {2017}
}