In a new paper, we expose connections between tensor networks and recent recursive representations of high-dimensional tensors described by binary tensor trees and based on a sequence of skeleton (dyadic) decompositions for special unfolding matrices for a given tensor.    As the main result, we prove that a tensor decomposition by any binary tensor tree with certain restrictions on the distribution of spatial and auxiliary indices reduces to one and same for a particular case of tree. Since the latter tree is of simple predetermined shape, it becomes not needed at all in the construction of numerical algorithms. The tree input is replaced with a permutation of spatial indices (modes). The corresponding decomposition is given by the so-called tensor trains and known as TT decomposition.
In our new paper, “TT cross approximation for multidimensional arrays” a new formula is presented for the recovery of a high-dimensional array from a part of its entries, provided that the array possesses some low-rank structure, namely it has small compression ranks (for example, a tensor of low canonical rank satisfies this). The only previous work known to us is the work by Grasedyck, Espig and Hackbusch, which uses interpolation on “fiber crosses”. It is based on canonical decomposition, requires minimization methods and there is no guarantee that the method will work even in the exact. Our new representation solves this problem completely, and it is shown, in particular, that if the rank of the tensor is r, then it can be exactly recovered from O(dnr^2) of its entries. This is a natural generalization of the skeleton decomposition of matrices and it becomes possible due to the replacement of the canonical format by the TT format, which is related to a series of matrix decompositions. Â It is also proven that the TT approximation obtained by a sequence of SVD decompositions can be worser only up to a factor of \sqrt(d-1)Â then the optimal TT approximation in the Frobenious norm.
The simple alternating maxvol algorithm is presented for the computation of the TT-cross decomposition of a black box tensors, which has complexity linear in the dimensions, and its effectiveness is illustratred on several examples in multidimensional integrations, with dimensions of order hundreds and even thousands. The algorithm is implemented as part of TT Toolbox and the code will be presented shortly after.
A first version of TT toolbox for MATLAB is released. It seems to works also under Octave — through not fully tested. Any comments, suggestions and bug reports are welcome at ivan.oseledets(dog)gmail.com
All basic algorithms are implemented as a set of short MATLAB functions. You can try to design your own fast algorithm with these routines or test if there is indeed a hidden TT structure in your vector/matrix/tensor. Really high-dimensional black box TT approximation is underway and will be realized soon in the future versions of TT toolbox.
The efficient Fortran (or C) versions of the TT toolbox are under development right now.
The idea of Edelman et al. (published in 2005 in SIAM News) for fast evaluation of excluded sums and their relation with the non-recursive multipole method was largely unnoticed. The authors promised to give a new implementation of the multipole method based on their (quite elegant) approach however up to now nothing is known. From my point of view the problem is that they didn’t succeed with the efficient implementation of functional approximations. In our new paper this idea is fully investigated in the one-dimensional case. It appears that it can be done in a simple manner by using successive low-rank skeleton approximation of a matrices in the lower triangular part and in the upper triangular part of the matrix and it can be shown that the obtained method works for an arbitrary quasiseparable matrix (i.e., matrix where every submatrix strictly below or over the diagonal has low rank), and moreover, a new representation for the class of quasiseparable matrices is obtained. This is a first step in the project “Matrix methods for the N-body problems”.
The future research will go in two directions. The first one concerns quasiseparable matrices and effective solvers and eigensolvers using the new representation and the second is the generalization to two or three dimensions.
The recently intoduced TT-format finds a surprising application for the compression of ordinary “two” or “three” dimensional matrices, related to the discretization of operators on tensor grids. For some examples the complexity is shown to be logarithmic in the matrix order. The new format (named TTM format) can be used to implement all basic operations efficiently. The Matlab codes will be posted here soon. The paper itself is here
A new paper, A compact matrix form of the d-dimensional tensor decomposition is added. A new version of the TT (name is now not coming from “Tree Tucker”, but from “Three dimensional Tensors” which are the defining parameters of the format) format is presented, which is much simpler than the recursive TT format and the subspace format by Hackbusch and Kuhn (they do not present any numerical experiments). It presents a nice and clear way to implement basic operations, like matrix-by-vector product, multidimensional convolution, norms, and what is the most important, the recompression procedure is based entirely on the SVD and QR decompositions. Its implementation takes about 150 lines of Matlab code compared to thousand of lines for the recursive TT-format, and the results for the computation of the smallest eigenvalue of a 19-dimensional operator are presented.
In our new publication, “Breaking the curse of dimensionality, or how to use SVD in many dimensions” we present a simple recursive decomposition for multidimensional functions, operators, vectors and matrices. We prove that in the case when the canonical decomposition exists our new Tree-Tucker decomposition also exists with the same (and often fewer) number of parameters. However, unlike the canonical decomposition, the Tree-Tucker format is stable and robustly computable by exploiting the SVD decomposition (or any rank-revealing decomposition). We show how to perform a simple operation (multidimensional convolution) in such format and provide numerical experiments for the dimensions up to d=200 on a notebook in several minutes.
Check out our new paper, “How to find a good submatrix” . It contains the description of an algorithm to find the well-conditioned submatrix in a given matrix. This algorithm plays a crucial role in our low-rank approximation methods, both for matrices and tensors. Matlab code is here.
A new publication on tensor-structured matrices, with a tentative title “Linear algebra for tensor problems” is added. It is submitted to the special issue of Computing.
This paper is about structured iterations with matrices of low tensor rank in three dimensions. We show that in three dimensions we can use Tucker decomposition instead of the canonical decomposition without any substantial increase in the computational cost. To achieve this goal we have to compute quite complex six-fold sum, but it is shown that they can be computed with calls to BLAS/LAPACK. Therefore Tucker format is highly recommended for 3-dimensional problems. With a current MATLAB code (will be posted here soon) it is possible to handle dense matrices (i.e., approximate inversion) on a grid of size 256^3. In a future research by using additional approximation techniques we will be able to increase this number to at least 1024^3.
Added a paper “Improved n-term Karatsuba formulae in GF(2)” that contains improved (and without proof — optimal!) formulae for multiplication of binary polynomials in GF(2). As noted in the end of this paper, the goal is not purely theoretic, but also practical — these optimal formulae will be used for the superfast implementation of the Coppersmith algorithm (as in the work by Thome), where the key step is the multiplication of binary polynomials.