Tensorisation of vectors and their efficient convolution (Q647362)

In recent papers the tensorisation of vectors has been discussed. Tensorisation is an interpretation of a usual \(\mathbb{R}^n\) vector as a tensor. For this purpose, the author introduces a tensor space \(V\) and an isomorphism \(\Phi: V\to \mathbb{R}^n\). Certain tensor representations are also introduced; they allow a simple truncation procedure. Black-box tensor approximation methods can be used to reduce the data size of the tensor representation. In particular, if the vector corresponds to a grid function, the resulting data size can become much smaller than \(n\), e.g., \(O(\log n)\ll n\). The author considers operations between vectors, a first example being the scalar product. The crucial point is that the computational work of the operations should be related to the data size of the operands. Assuming a data size \(\ll n\), the cost should also be much smaller than the operation in the standard \(\mathbb{R}^n\) vector format. The main interest of this article concerns the convolution operation \(u:= v*w\) with \(u_i= \sum_k v_k w_{i-k}\). The author discusses the convolution of two vectors which are given via a sparse tensor representation and the result is obtained again in the tensor representation. Furthermore, the cost of the convolution algorithm is related to the operands data sizes. The paper mentions that instead of \(\mathbb{R}^n\) we can also treat finite-dimensional subspaces of function spaces. While \(\mathbb{R}^n\) vectors can be considered as grid values of functions, one can apply the corresponding procedure to univariate functions. Operations like the scalar product or convolution of functions can be performed directly in the tensor format. The paper ends with some generalizations.