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

Research output: Contribution to journalArticle

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 recursion, 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 and has asymptotically the same complexity as the superfast quantum Fourier transform. It is instructive to describe a class of such vectors explicitly. We identify 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. We show by numerical experiments that for certain rank-one vectors with full-rank Fourier images, the practical -ranks remain moderate for large mode sizes.

Original languageEnglish
Pages (from-to)3215-3224
Number of pages10
JournalLinear Algebra and its Applications
Volume436
Issue number9
DOIs
Publication statusPublished - 1 May 2012

Fingerprint

Tensor Rank
Tensors
Fast Fourier transforms
Tensor
Sparse Data
Separation of Variables
Recursion
Fourier transform
Fourier transforms
Numerical Experiment
Output

Keywords

  • Data-sparse formats
  • Fast Fourier transform
  • Quantics tensor train
  • Quantum Fourier transform

Cite this

@article{932998e6cf654e458dec0b6fc06feb6c,
title = "QTT-rank-one vectors with QTT-rank-one and full-rank Fourier images",
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 recursion, 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 and has asymptotically the same complexity as the superfast quantum Fourier transform. It is instructive to describe a class of such vectors explicitly. We identify 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. We show by numerical experiments that for certain rank-one vectors with full-rank Fourier images, the practical -ranks remain moderate for large mode sizes.",
keywords = "Data-sparse formats, Fast Fourier transform, Quantics tensor train, Quantum Fourier transform",
author = "Dmitry Savostyanov",
year = "2012",
month = "5",
day = "1",
doi = "10.1016/j.laa.2011.11.008",
language = "English",
volume = "436",
pages = "3215--3224",
journal = "Linear Algebra and its Applications",
issn = "0024-3795",
number = "9",

}

QTT-rank-one vectors with QTT-rank-one and full-rank Fourier images. / Savostyanov, Dmitry.

In: Linear Algebra and its Applications, Vol. 436, No. 9, 01.05.2012, p. 3215-3224.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Savostyanov, Dmitry

PY - 2012/5/1

Y1 - 2012/5/1

N2 - 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 recursion, 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 and has asymptotically the same complexity as the superfast quantum Fourier transform. It is instructive to describe a class of such vectors explicitly. We identify 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. We show by numerical experiments that for certain rank-one vectors with full-rank Fourier images, the practical -ranks remain moderate for large mode sizes.

AB - 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 recursion, 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 and has asymptotically the same complexity as the superfast quantum Fourier transform. It is instructive to describe a class of such vectors explicitly. We identify 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. We show by numerical experiments that for certain rank-one vectors with full-rank Fourier images, the practical -ranks remain moderate for large mode sizes.

KW - Data-sparse formats

KW - Fast Fourier transform

KW - Quantics tensor train

KW - Quantum Fourier transform

UR - http://www.scopus.com/inward/record.url?scp=84857993457&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2011.11.008

DO - 10.1016/j.laa.2011.11.008

M3 - Article

AN - SCOPUS:84857993457

VL - 436

SP - 3215

EP - 3224

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

SN - 0024-3795

IS - 9

ER -