Approximation of 2d˟2d Matrices Using Tensor Decomposition

By Ivan V. Oseledets. 2010

244 citations recorded by the source corpus.

A new method for structured representation of matrices and vectors is presented. The method is based on the representation of a matrix as a $d$-dimensional tensor and applying the TT-decomposition proposed recently. It turned out that for many important cases the number of parameters to represent an $n\times n$ matrix falls down to $\mathcal{O}(\log^{\alpha}n)$, giving a logarithmic storage. It is shown that this format can be used not only for storage reduction, but also for linear algebra operations. Possible applications include differential and integral equations, and data and image compression.

Subfields: Computational Mathematics, Computational Theory and Mathematics, Mathematical Optimization, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Computational Theory and Mathematics

In Mathematical Optimization

In Signal Processing

Citations in the corpus

Multilevel Toeplitz Matrices Generated by Tensor-Structured Vectors and Convolution with Logarithmic Complexity (2013, methodology): “In order to make it sublinear, one may adopt the QTT format [6, 7, 8], which is the particular case of the TT format with the smallest possible mode sizes, applied to tensors reshaped correspondingly.”
Low-Rank Explicit QTT Representation of the Laplace Operator and Its Inverse (2012, methodology): “Also, one may adopt the quantized tensor train (QTT) format [30, 19, 31], which is the TT format applied to a vector after virtual dimensions are introduced by reshaping it to smaller mode sizes (for example, nk = 2).”
QTT Representation of the Hartree and Exchange Operators in Electronic Structure Calculations (2011, methodology): “Recently introduced quantics-TT (QTT) tensor format [26] [35] [31] provides O(log n)-complexity of the 3D tensor operations, where n is the univariate grid size (see §2 for more detail).”
Tensor Ring Decomposition (2016, methodology): “the quantized tensor train (QTT) [42], [43] and the QTT-Tucker [44], which have been also applied to large-scale optimization problems [41], [45], [46].”
Model Compression and Hardware Acceleration for Neural Networks: A Comprehensive Survey (2020, background): “By tensoriz-ing the weight matrices ﬁrst, the TT format with small core tensors can be easily achieved, which is known as quantized TT (QTT) [135] with lower ranks and higher compression ratios. g) TT variant: Tensor chain (TC): The TC format [136] (also called tensor ring [118]) is a variant of TT,”
Two-level Tucker-TT-QTT format for optimized tensor calculus (2012, methodology): “To use all the benefits from tensor decompositions for low-dimensional data, we use the QTT format [26] [27] [28] [29] [44] [30] [45] [40].”
Towards an ADI iteration for Tensor Structured Equations (2014, background): “Recently tensor-trains [24, 26] have been introduced by Oseledets and Tyrtshnikov.”
Møller-Plesset (MP2) energy correction using tensor factorization of the grid-based two-electron integrals (2014, methodology): “The QTT approximation method allows us to represent a class of matrices in low QTT rank format [44,45] and to implement the multidimensional FFT and convolution transforms with logarithmic complexity scaling, O(log n) [46,47].”
QTT approximation of elliptic solution operators in higher dimensions (2011, methodology): “Finally, the conversion of a full n× n matrix into the QTT format takes O(n(2)) time, using the algorithm of [33].”