Low-Rank Tucker Approximation of a Tensor From Streaming Data
Low-Rank Tucker Approximation of a Tensor From Streaming Data
复制标题
DOI：
10.1137/19m1257718
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Yiming Sun;Yang Guo;Charlene Luo;J. Tropp;Madeleine Udell
中科院分区：
文献类型：
--
作者：
Yiming Sun;Yang Guo;Charlene Luo;J. Tropp;Madeleine Udell
本文描述了一种计算张量低Tucker秩近似的新算法。该方法将随机线性映射应用于张量以获得捕获每个模式内的重要方向以及模式之间的相互作用的草图。草图可以从流或分布式数据中提取，也可以通过张量进行单次传递，并且它使用与输出Tucker近似中的自由度成比例的存储。该算法不需要第二次通过张量，尽管它可以利用另一个视图来计算上级近似。本文对逼近误差提供了严格的理论保证。大量的数值实验表明，该算法产生有用的结果，提高了最先进的流塔克分解。
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.