QTT-rank-one vectors with QTT-rank-one and full-rank Fourier images
QTT-rank-one vectors with QTT-rank-one and full-rank Fourier images
复制标题
具有 QTT 秩一和全秩傅立叶图像的 QTT 秩一向量
DOI：
10.1016/j.laa.2011.11.008
复制
发表时间：
2012
影响因子：
1.1
通讯作者：
D. Savostyanov
中科院分区：
文献类型：
--
作者：
D. Savostyanov
Quantics张量序列（QTT）是一种新的一维和多维矢量数据稀疏格式，它基于模式索引的位表示和变量分离。著名的FFT算法背后的基数-2递归可以有效地应用于QTT格式的向量。如果FFT算法的输入和所有中间向量具有中等的QTT排名，则所得的QTT - FFT算法在大向量上优于FFT算法，并且具有与超快速量子傅里叶变换渐近相同的复杂性。明确地描述一类这样的向量是有指导意义的。我们确定了所有在FFT算法的输入、中间步骤和输出中QTT排名为1的向量。我们还给出了一个QTT-rank- 1向量的例子，它具有完整的QTT秩的傅里叶图像。我们通过数值实验表明，对于具有全秩傅里叶图像的某些秩一向量，对于大模态尺寸，实际秩保持中等。
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.