.png){kind=icon}
.png){kind=icon}
Return
MULTILEVEL TOEPLITZ MATRICES GENERATED BY TENSOR-STRUCTURED VECTORS AND CONVOLUTION WITH LOGARITHMIC COMPLEXITY
.png){kind=icon}
PRE
AI
DOI：10.1137/110844830.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We study the tensor structure of two operations: the transformation of a given multidimensional vector into a multilevel Toeplitz matrix and the convolution of two given multidimensional vectors. We show that the low-rank tensor structure of the input is preserved in the output and propose efficient algorithms for these operations in the newly introduced quantized tensor train (QTT) format. Consider a d-dimensional 2n x ... x 2n-vector x. If it is represented elementwise, the number of parameters is (2n)(d). However, if we assume that x is given in a QTT representation with ranks bounded by p, the number of parameters is reduced to O(dp(2) log n). Under this assumption we show how the multilevel Toeplitz matrix generated by x can be obtained in the QTT format with ranks bounded by 2p in O(dp(2) log n) operations. We also describe how the convolution x star y of x and a d-dimensional n x ... x n-vector y can be computed in the QTT format with ranks bounded by 2t in O(dt(2) log n) operations, provided that the matrix xy' is given in the same format with ranks bounded by t. We exploit an algorithm for the inexact matrix-vector multiplication in the QTT format to accelerate the convolution algorithm dramatically. The performance of our approach to convolution is demonstrated with numerical examples, including the computation of the Newton potential of a strong cusp on fine grids with up to 2(20) x 2(20) x 2(20) points in three dimensions.
Keywords:
Toeplitz matrices
circulant matrices
convolution
virtual levels
tensor decompositions
tensor rank
low-rank representation
Newton potential
tensor train
TT
quantized tensor train
QTT
Journal
IF:
2.6
Papers:
5.1K
Citations:
1.8W
Organization
View more organizations