Premium
Quantized CP approximation and sparse tensor interpolation of function‐generated data
Author(s) -
Khoromskij Boris N.,
Kishore Kumar N.,
Schneider Jan
Publication year - 2019
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.2262
Subject(s) - mathematics , tensor (intrinsic definition) , discretization , function (biology) , interpolation (computer graphics) , approximation algorithm , rank (graph theory) , approximation error , function approximation , algorithm , mathematical analysis , combinatorics , pure mathematics , image (mathematics) , computer science , artificial neural network , evolutionary biology , artificial intelligence , machine learning , biology
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 .