Two-Level QTT-Tucker Format for Optimized Tensor Calculus
Authors:
- Sergey DolgovSDSergey Dolgov
- Boris KhoromskijBKBoris Khoromskij
- 1 January 2013
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 34 (2) , 593-623
Abstract
We propose a combined tensor format, which encapsulates the benefits of Tucker, tensor train (TT), and quantized TT (QTT) formats. The structure is composed of subtensors in TT representations, so the approximation problem is proven to be stable. We describe all important algebraic and optimization operations, which are recast to the TT routines. Several examples on explicit function and operator representations are provided. The asymptotic storage complexity is at most cubic in the rank parameter, that is larger than for the global QTT approximation, but the numerical examples manifest that the ranks in the two-level format usually increase more slowly with the approximation accuracy than the QTT ones. In particular, we observe that high rank peaks, which usually occur in the TT/QTT representations, are significantly relaxed. Thus the reduced costs can be achieved.Keywords
This publication has 52 references indexed in Scilit:
- Greedy Approximation of High-Dimensional Ornstein–Uhlenbeck OperatorsFoundations of Computational Mathematics, 2012
- Fast and accurate tensor approximation of a multivariate convolution with linear scaling in dimensionJournal of Computational and Applied Mathematics, 2010
- Low rank Tucker-type tensor approximation to classical potentialsCentral European Journal of Mathematics, 2007
- A new family of solvers for some classes of multidimensional partial differential equations encountered in kinetic theory modeling of complex fluidsJournal of Non-Newtonian Fluid Mechanics, 2006
- Estimating Mean Dimensionality of Analysis of Variance DecompositionsJournal of the American Statistical Association, 2006
- Low-rank Kronecker-product Approximation to Multi-dimensional Nonlocal Operators. Part I. Separable Approximation of Multi-variate FunctionsComputing, 2005
- Sparse gridsActa Numerica, 2004
- Numerical solution of parabolic equations in high dimensionsESAIM: Mathematical Modelling and Numerical Analysis, 2004
- Thermodynamic Limit of Density Matrix RenormalizationPhysical Review Letters, 1995
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965