Error Analysis of Tensor-Train Cross Approximation
Error Analysis of Tensor-Train Cross Approximation
复制标题
DOI：
10.48550/arxiv.2207.04327
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Zhen Qin;Alexander Lidiak;Zhexuan Gong;Gongguo Tang;M. Wakin;Zhihui Zhu
中科院分区：
文献类型：
--
作者：
Zhen Qin;Alexander Lidiak;Zhexuan Gong;Gongguo Tang;M. Wakin;Zhihui Zhu
张量列分解由于其对高维张量的简洁表示，克服了维数的困扰，在机器学习和量子物理中得到了广泛的应用。交叉近似——最初用于从一组选定的行和列中表示矩阵——是一种有效的方法，用于从张量的几个条目构建张量的张量序列分解。虽然张量列交叉逼近在实际应用中取得了显著的成绩，但其理论分析，特别是关于逼近误差的理论分析，迄今还缺乏。据我们所知，现有的结果只提供了元素逼近精度保证，这导致扩展到整个张量时的边界非常松散。在本文中，我们通过为精确和噪声测量提供整个张量的精度保证来弥补这一差距。我们的结果说明了所选子张量的选择如何影响交叉近似的质量，以及由模型误差和/或测量误差引起的近似误差可能不会随着张量的阶数呈指数增长。这些结果通过数值实验得到了验证，并且可能对高阶张量交叉近似的有用性具有重要意义，例如在描述量子多体态时遇到的那些。
Tensor train decomposition is widely used in machine learning and quantum physics due to its concise representation of high-dimensional tensors, overcoming the curse of dimensionality. Cross approximation-originally developed for representing a matrix from a set of selected rows and columns-is an efficient method for constructing a tensor train decomposition of a tensor from few of its entries. While tensor train cross approximation has achieved remarkable performance in practical applications, its theoretical analysis, in particular regarding the error of the approximation, is so far lacking. To our knowledge, existing results only provide element-wise approximation accuracy guarantees, which lead to a very loose bound when extended to the entire tensor. In this paper, we bridge this gap by providing accuracy guarantees in terms of the entire tensor for both exact and noisy measurements. Our results illustrate how the choice of selected subtensors affects the quality of the cross approximation and that the approximation error caused by model error and/or measurement error may not grow exponentially with the order of the tensor. These results are verified by numerical experiments, and may have important implications for the usefulness of cross approximations for high-order tensors, such as those encountered in the description of quantum many-body states.