Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
45/2011

QTT-rank-one vectors with QTT-rank-one and full-rank Fourier images

Dmitry Savostyanov

Abstract

Quantics tensor train (QTT), a new data-sparse format for one-- and multi--dimensional vectors, is based on a bit representation of mode indices followed by a separation of variables. A radix-2 reccurence, that lays behind the famous FFT algorithm, can be efficiently applied to vectors in the QTT format. If input and all intermediate vectors of the FFT algorithm have moderate QTT ranks, the resulted QTT-FFT algorithm outperforms the FFT for large vectors. It is instructive to describe a class of such vectors explicitly. We find all vectors that have QTT ranks one on input, intermediate steps and output of the FFT algorithm. We also give an example of QTT-rank-one vector that has the Fourier image with full QTT ranks. By numerical experiments we show that for certain rank-one vectors with full-rank Fourier images, the practical $\varepsilon$--ranks remain moderate for large mode sizes.

Received:
Jul 18, 2011
Published:
Jul 19, 2011
MSC Codes:
15A23, 15A69, 65F99, 65T50
Keywords:
Multidimensional arrays, Quantics Tensor Train, Fourier transform, data-sparse formats

Related publications

inJournal
2012 Repository Open Access
Dmitry V. Savostyanov

QTT-rank-one vectors with QTT-rank-one and full-rank Fourier images

In: Linear algebra and its applications, 436 (2012) 9, pp. 3215-3224