TT-cross approximation for multidimensional arrays
Multilinear algebra, tensor calculus (15A69) Vector and tensor algebra, theory of invariants (15A72) Approximate quadratures (41A55) Multidimensional problems (41A63) Numerical interpolation (65D05) Numerical quadrature and cubature formulas (65D32) Iterative numerical methods for linear systems (65F10) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Numerical computation of matrix norms, conditioning, scaling (65F35)
It is well known that a rank-\(r\) matrix can be recovered from a cross of \(r\) linearly independent columns and rows, and an arbitrary matrix can be interpolated on the cross entries. Other entries by this cross or ``pseudo-skeleton approximation are given with errors depending on the closeness of the matrix to a rank-\(r\) matrix and as well on the choice of the cross. In the present paper the authors are extending this construction to \(d\)-dimensional arrays (tensors) and suggest a new interpolation formula in which a \(d\)-dimensional array is interpolated on the entries of some TT-cross (Tensor-Train-cross). The total number of entries and the complexity of the proposed interpolation algorithm depend on \(d\)-linearly, so the approach does not suffer from the curse of dimensionality. The main contribution of the paper is the new interpolation formula in \(d\) dimensions. It generalizes the skeleton (dyadic) decomposition to \(d\) dimensions via the TT format, and it turns out that if all compression ranks are bounded then it is sufficient to compute only part of the elements of a tensor in certain prescribed positions and use them to completely recover this tensor. Thus, from a virtual (black-box) tensor on input it become possible to get a tensor-train representation of this tensor on output. A simple variant of the TT cross algorithm is presented and convincing numerical experiments are given. Then the TT cross algorithm is applied to approximate some black-box tensors arising in the numerical computation of \(d\)-dimensional integrals. Throughout the paper several notations from linear algebra are used that are now becoming standard. For the purpose of not distracting the reader with notations, the authors are not giving them in detail, and are referring to previous works. Standard MATLAB notations are also used for handling tensor and matrix operations, especially to describe algorithms. It is important to note that the TT-cross formula represents a tensor exactly if its auxiliary unfolding matrices are of low rank. The latter is always the case when a tensor has a low canonical rank. In other cases this formula can represent a tensor approximately. For general TT approximations, in this regard it is proved that with the best possible accuracies for approximations of predetermined ranks to the unfolding matrices, there exists a TT approxima-tion with error bounded from above. It immediately follows that if there is the best possible accuracy for TT approximations with fixed compression rank bounds, then the constructions provide a quasi-optimal TT approximation with the error bounded from above. A simple variant of the TT-cross approximation method is proposed in the case when a tensor is given as a black box by a procedure for computation of any required element. This method allows obtaining TT approximations to some functional tensors in really many dimensions in a moderate time (up to a few minutes) on a notebook. Then, as soon as the tensors are available in the TT format, it becomes possible to perform many basic operations with these tensors in a very efficient way. A TT-cross method for computation of \(d\)-dimensional integrals is also proposed. It is applied to some examples with dimensionality in the range from \(d = 100\) up to \(d = 4000\) and the relative accuracy of order \(-10\). All in all, the presented interpolation method for high-dimensional tensors is given with a complete proof in the exact case, and numerical experiments confirm that it is a very efficient approximation tool for black-box tensors.
- A Multilinear Singular Value Decomposition
- A new tensor decomposition
- A theory of pseudoskeleton approximations
- Algorithms for Numerical Analysis in High Dimensions
- Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
- Approximation of 1/x by exponential sums in [1, ∞)
- Approximation of boundary element matrices
- Approximation of matrices with logarithmic number of parameters
- Breaking the Curse of Dimensionality, Or How to Use SVD in Many Dimensions
- Combining Kronecker Product Approximation with Discrete Wavelet Transforms to Solve Dense, Function-Related Linear Systems
- Efficient MATLAB Computations with Sparse and Factored Tensors
- Existence and computation of low Kronecker-rank approximations for large linear systems of tensor product structure
- Fast Multilinear Singular Value Decomposition for Structured Tensors
- Hierarchical Kronecker tensor-product approximations
- How to find a good submatrix
- scientific article; zbMATH DE number 3138903 (Why is no real title available?)
- scientific article; zbMATH DE number 1061412 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Incomplete cross approximation in the mosaic-skeleton method
- Numerical integration using sparse grids
- Numerical operator calculus in higher dimensions
- On cross approximation of multi-index arrays
- On tensor approximation of Green iterations for Kohn-Sham equations
- On the Best Rank-1 and Rank-(R1 ,R2 ,. . .,RN) Approximation of Higher-Order Tensors
- On the efficient computation of high-dimensional integrals and the approximation by exponential sums
- Recursive decomposition of multidimensional tensors
- Tensor approximations of matrices generated by asymptotically smooth functions
- Tensor Decompositions and Applications
- The maximal-volume concept in approximation by low-rank matrices
- Tucker Dimensionality Reduction of Three-Dimensional Arrays in Linear Time
- ttTensor
- Tensor network subspace identification of polynomial state space models
- Matrix output extension of the tensor network Kalman filter with an application in MIMO Volterra system identification
- Pseudo-skeleton approximations with better accuracy estimates
- Rectangular maximum-volume submatrices and their applications
- A tensor network Kalman filter with an application in recursive MIMO Volterra system identification
- Tensor network alternating linear scheme for MIMO Volterra system identification
- A tensor-train accelerated solver for integral equations in complex geometries
- Multilevel tensor approximation of PDEs with random data
- Nearest-neighbor interaction systems in the tensor-train format
- Approximation of integral operators using product-convolution expansions
- On the Dirac-Frenkel variational principle on tensor Banach spaces
- Higher-order principal component analysis for the approximation of tensors in tree-based low-rank formats
- Superfast Fourier transform using QTT approximation
- On minimal subspaces in tensor representations
- Black box approximation of tensors in hierarchical Tucker format
- A tensor decomposition approach to data compression and approximation of ND systems
- Constructive representation of functions in low-rank tensor formats
- A parametric and non-intrusive reduced order model of car crash simulation
- A continuous analogue of the tensor-train decomposition
- Greedy low-rank approximation in Tucker format of solutions of tensor linear systems
- New applications of matrix methods
- TT ranks of approximate tensorizations of some smooth functions
- TT-QI: faster value iteration in tensor train format for stochastic optimal control
- Prospects of tensor-based numerical modeling of the collective electrostatics in many-particle systems
- Tensor-train numerical integration of multivariate functions with singularities
- Truncation of tensors in the hierarchical format
- Low-rank tensor approximation of singularly perturbed boundary value problems in one dimension
- Faster tensor train decomposition for sparse data
- Tensor approximation of cooperative games and their semivalues
- Tensor-based computation of metastable and coherent sets
- Interval approach to solving parametric identification problems for dynamical systems
- Tensor train based isogeometric analysis for PDE approximation on parameter dependent geometries
- Deep composition of tensor-trains using squared inverse Rosenblatt transports
- Some algorithms for maximum volume and cross approximation of symmetric semidefinite matrices
- Low-rank tensor reconstruction of concentrated densities with application to Bayesian inversion
- Nonnegative tensor-train low-rank approximations of the Smoluchowski coagulation equation
- Tensor rank bounds for point singularities in \(\mathbb{R}^3\)
- A low rank tensor representation of linear transport and nonlinear Vlasov solutions and their associated flow maps
- Interpolatory tensorial reduced order models for parametric dynamical systems
- Tensor-train decomposition for image recognition
- High-order tensor estimation via trains of coupled third-order CP and Tucker decompositions
- FFT-based homogenisation accelerated by low-rank tensor approximations
- Tensor train-Karhunen-Loève expansion: new theoretical and algorithmic frameworks for representing general non-Gaussian random fields
- Global optimization based on TT-decomposition
- Characterization of sampling patterns for low-tt-rank tensor retrieval
- Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
- Nonlinear system identification with regularized tensor network B-splines
- Computing the density of states for optical spectra of molecules by low-rank and QTT tensor approximation
- Adaptive interpolation algorithm using TT-decomposition for modeling dynamical systems with interval parameters
- Quasioptimality of maximum-volume cross interpolation of tensors
- Approximation and sampling of multivariate probability distributions in the tensor train decomposition
- Nonnegative tensor train factorization with DMRG technique
- Analysis of parametric models. Linear methods and approximations
- Gradient-based optimization for regression in the functional tensor-train format
- Tensor trains approximation estimates in the Chebyshev norm
- Non-intrusive tensor reconstruction for high-dimensional random PDEs
- Approximate solution of linear systems with Laplace-like operators via cross approximation in the frequency domain
- Tensor representation of non-linear models using cross approximations
- Stable als approximation in the TT-format for rank-adaptive tensor completion
- Adaptive stochastic Galerkin FEM with hierarchical tensor representations
- A low-rank approach to the computation of path integrals
- Tensor train versus Monte Carlo for the multicomponent Smoluchowski coagulation equation
- Approximation rates for the hierarchical tensor format in periodic Sobolev spaces
- An equi-directional generalization of adaptive cross approximation for higher-order tensors
- Randomized algorithms for the approximations of Tucker and the tensor train decompositions
- Global and local optimization in identification of parabolic systems
- MERACLE: constructive layer-wise conversion of a tensor train into a MERA
- Fast nonnegative tensor factorizations with tensor train model
- A Lanczos-type procedure for tensors
- Computation and learning in high dimensions. Abstracts from the workshop held August 1--7, 2021 (hybrid meeting)
- Parallel cross interpolation for high-precision calculation of high-dimensional integrals
- Towards an efficient use of the BLAS library for multilinear tensor contractions
- Evaluation of the docking algorithm based on tensor train global optimization
- Spectral tensor-train decomposition
- HOID: higher order interpolatory decomposition for tensors based on Tucker representation
- Riemannian optimization for high-dimensional tensor completion
- A literature survey of low-rank tensor approximation techniques
- Low-Rank Tensor Approximation for High-Order Correlation Functions of Gaussian Random Fields
- Multilevel preconditioning and low-rank tensor iteration for space-time simultaneous discretizations of parabolic PDEs
- Constrained optimization with low-rank tensors and applications to parametric problems with PDEs
- Using the Tensor-Train Approach to Solve the Ground-State Eigenproblem for Hydrogen Molecules
- Structured matrix problems from tensors
- Computational Methods for Linear Matrix Equations
- Error Analysis of TT-Format Tensor Algorithms
- Tensors in Modelling Multi-particle Interactions
- Global Optimization Algorithms Using Tensor Trains
- Application of the Global Optimization Methods for Solving the Parameter Estimation Problem in Mathematical Immunology
- Geometric Methods on Low-Rank Matrix and Tensor Manifolds
- 6 The Loewner framework for system identification and reduction
- Variants of alternating least squares tensor completion in the tensor train format
- Hierarchical tensor approximation of output quantities of parameter-dependent PDEs
- Polynomial Chaos Expansion of Random Coefficients and the Solution of Stochastic Partial Differential Equations in the Tensor Train Format
- Non-uniform FFT for the finite element computation of the micromagnetic scalar potential
- Gradient-type methods: a unified perspective in computer science and numerical analysis
- Generalized cross approximation for 3D-tensors
- Fast evaluation of singular BEM integrals based on tensor approximations
- Constructing nested bases approximations from the entries of non-local operators
- Computing low-rank approximations of large-scale matrices with the tensor network randomized SVD
- Literature survey on low rank approximation of matrices
This page was built for publication: TT-cross approximation for multidimensional arrays
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q126160)
