Tensor-Train Ranks for Matrices and Their Inverses

Ivan V. Oseledets, Eugene E. Tyrtyshnikov, Nickolai L. Zamarashkin

Abstract

This paper formalizes the application of the Tensor-Train (TT) decomposition to large-scale matrices and investigates the preservation of low-rank structures under matrix inversion. By leveraging recursive Kronecker products and the Quantized Tensor-Train (QTT) format, the authors demonstrate that massive matrices—often of size $2^d \times 2^d$—can be stored and manipulated with logarithmic complexity relative to their dimensions. The primary theoretical contribution is the proof that the inverse of a banded Toeplitz matrix has a QTT-rank bounded by a constant, $1 + (l+u)^2$, where $l$ and $u$ are the lower and upper bandwidths. This result suggests that the inverses of large, sparse structured systems are inherently low-complexity objects, enabling the development of "superfast" numerical solvers.

Introduction

In modern numerical analysis and high-dimensional physics, researchers frequently encounter matrices of gargantuan proportions, such as those with dimensions $2^d \times 2^d$. Direct storage of these matrices is precluded by the "curse of dimensionality," as the number of entries grows exponentially with the dimension $d$. While standard low-rank approximations like the Singular Value Decomposition (SVD) are effective for certain data-driven applications, they fail to compress many fundamental operators—such as the identity or shift matrices—because their standard algebraic rank is full.

To address this, the authors explore the Tensor-Train (TT) format, a decomposition that sits between the simplicity of a single Kronecker product and the computational complexity of the Canonical Polyadic (CP) decomposition. This paper specifically focuses on the Tensor-Train Matrix (TTM) format and its "quantized" variant (QTT), providing a framework for maintaining algebraic closure during matrix operations, most notably inversion.

The TTM and QTT Formats

The Tensor-Train decomposition for matrices (TTM) represents a matrix as a sequence of interconnected cores. This structure emerges naturally from recursive Kronecker products. For a matrix of size $2^d \times 2^d$, the authors utilize "quantization" (QTT), which treats the matrix indices as a $d$-dimensional tensor. This allows the decomposition to exploit structural redundancies across multiple scales that are invisible in a standard 2D representation.

Unlike the CP decomposition, which is often numerically unstable and difficult to compute for high-order tensors, the TT format is computationally robust. It allows for the use of standard linear algebra tools, such as the SVD, to truncate ranks and maintain efficiency. The QTT format is particularly powerful because it reduces the $n^2$ storage requirement of a matrix to $O(\log n)$ parameters, provided the TT-rank remains small.

Theoretical Analysis of Matrix Inverses

A critical challenge in numerical linear algebra is determining whether the inverse of a structured matrix retains a compressible form. The authors analyze how the TT-rank behaves under inversion using Sherman-Morrison-Woodbury-type identities and the properties of shift matrices.

They first establish a baseline for rank-1 matrices: if a nonsingular matrix has a QTT-rank of 1 (meaning it is a pure Kronecker product of smaller matrices), its inverse also maintains a QTT-rank of 1. This property of algebraic closure is vital for iterative solvers and matrix functions, where repeated operations could otherwise lead to an exponential explosion in rank.

The Case of Banded Toeplitz Matrices

The most significant result of the paper concerns banded Toeplitz matrices. These matrices are ubiquitous in the discretization of differential equations and signal processing. The authors prove that for a nonsingular banded Toeplitz matrix $A$ with lower bandwidth $l$ and upper bandwidth $u$, the QTT-rank of its inverse is bounded by:

$$\text{qttr}(A^{-1}) \le 1 + (l + u)^2$$

This bound is independent of the size of the matrix. This implies that as the matrix size $n$ grows toward infinity, the complexity of representing its inverse remains constant in terms of rank, and logarithmic in terms of total parameters. This theoretical guarantee justifies the use of QTT-based "superfast" solvers that can bypass the traditional $O(n^3)$ or $O(n \log n)$ limits of standard algorithms.

Discussion and Future Work

While the proof for banded Toeplitz matrices is a landmark result, the authors acknowledge several areas for further exploration. The current estimates for other structured classes, such as general Hankel matrices or multilevel Toeplitz matrices, remain subjects of ongoing research. Furthermore, the paper focuses on the existence of these low-rank representations. In practice, the growth of TT-ranks during iterative computations is often managed via $\epsilon$-approximations, and the trade-off between approximation error and computational speed requires further empirical study.

Ultimately, this work provides a rigorous foundation for the QTT format in numerical linear algebra, proving that the structural complexity of matrix inverses is often far lower than their dimensions would suggest. This opens the door for black-box software capable of performing high-dimensional matrix inversions with unprecedented efficiency.

Summary updated

Abstract

We show that the recent tensor-train (TT) decompositions of matrices come up from its recursive Kronecker-product representations with a systematic use of common bases. The names TTM and QTT used in this case stress the relation with multilevel matrices or quantization that increases artificially the number of levels. Then we investigate how the tensor-train ranks of a matrix can be related to those of its inverse. In the case of a banded Toeplitz matrix, we prove that the tensor-train ranks of its inverse are bounded above by 1+(l+u)^2, where l and u are the bandwidths in the lower and upper parts of the matrix without the main diagonal.
BibTeX
@article{oseledets2011tensor,
  author = {Ivan V. Oseledets and Eugene E. Tyrtyshnikov and Nickolai L. Zamarashkin},
  title = {{Tensor-Train Ranks for Matrices and Their Inverses}},
  journal = {Comput. Methods Appl. Math.},
  year = {2011},
  doi = {10.2478/cmam-2011-0022},
}
Figure