Quantized CP approximation and sparse tensor interpolation of function‐generated data. Issue 5 (15th July 2019)

• Record Type: Journal Article
• Authors: Khoromskij, Boris N.; Kishore Kumar, N.; Schneider, Jan
• Is Part Of: Numerical linear algebra with applications. Volume 26:Issue 5(2019)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2019-07-15
• Subjects: alternating least squares iteration -- canonical tensor approximation -- CP rank -- discretized function -- Lth‐order tensors -- QCP data format -- QTT tensor approximation -- uniform grid; Algebras, Linear -- Periodicals; 512.5
• DOI: 10.1002/nla.2262
• Languages: English
• ISSNs: 1070-5325

Abstract

Summary: In this article, we consider the iterative schemes to compute the canonical polyadic (CP) approximation of quantized data generated by a function discretized on a large uniform grid in an interval on the real line. This paper continues the research on the quantics‐tensor train (QTT) method (" O ( d log N )‐quantics approximation of N ‐ d tensors in high‐dimensional numerical modeling" in Constructive Approximation, 2011) developed for the tensor train (TT) approximation of the quantized images of function related data. In the QTT approach, the target vector of length 2 L is reshaped to a L th‐order tensor with two entries in each mode (quantized representation) and then approximated by the QTT tensor including 2 r 2 L parameters, where r is the maximal TT rank. In what follows, we consider the alternating least squares (ALS) iterative scheme to compute the rank‐ r CP approximation of the quantized vectors, which requires only 2 r L ≪2 L parameters for storage. In the earlier papers ("Tensors‐structured numerical methods in scientific computing: survey on recent advances" in Chemom Intell Lab Syst, 2012), such a representation was called Q C a n format, whereas in this paper, we abbreviate it as the QCP (quantized canonical polyadic) representation. We test the ALS algorithm to calculate the QCP approximation on various functions, and in all cases, we observed the exponential error decay in the QCP rank. The main idea for recovering a discretized function in the rank‐ r QCP format using the reduced number of the functional samples, calculated only at O (2 r L ) grid points, is presented. The special version of the ALS scheme for solving the arising minimization problem is described. This approach can be viewed as the sparse QCP‐interpolation method that allows to recover all 2 r L representation parameters of the rank‐ r QCP tensor. Numerical examples show the efficiency of the QCP‐ALS‐type iteration and indicate the exponential convergence rate in r .