Quantized CP approximation and sparse tensor interpolation of function-generated data.

DOI10.1002/NLA.2262zbMATH Open1474.65127arXiv1707.04525OpenAlexW2963789529WikidataQ127495244 ScholiaQ127495244MaRDI QIDQ5206497FDOQ5206497

Authors: Boris N. Khoromskij, N. Kishore Kumar, Jan Schneider 

Publication date: 18 December 2019

Published in: Numerical Linear Algebra with Applications (Search for Journal in Brave)

Abstract: In this article we consider the iterative schemes to compute the canonical (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 QTT method [16] 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 tenor including $2r^{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 $2rLll{2}^L$ parameters for storage. In the earlier papers [17] such a representation was called Q${}_{Can}$ format, while in this paper we abbreviate it as the QCP 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 the functional samples, calculated only at $O(2rL)$ grid points, is presented. The special version of 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 $2rL$ 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$.

Full work available at URL: https://arxiv.org/abs/1707.04525

Recommendations

• \(O(d \log N)\)-quantics approximation of \(N\)-\(d\) tensors in high-dimensional numerical modeling
• SOTT: greedy approximation of a tensor as a sum of tensor trains
• A Practical Randomized CP Tensor Decomposition
• A continuous analogue of the tensor-train decomposition
• Higher-order principal component analysis for the approximation of tensors in tree-based low-rank formats

zbMATH Keywords

uniform gridQTT tensor approximationCP rank\(L\)th-order tensorsalternating least squares iterationcanonical tensor approximationdiscretized functionQCP data format

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Numerical linear algebra (65F99) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Uses Software

• Matlab

This page was built for publication: Quantized CP approximation and sparse tensor interpolation of function-generated data.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5206497)