| Abstract: |
By a tensor problem in general, we mean one where all data on
input and output are given exactly or approximately in tensor
formats defined by a small number of parameters compared to the
total amount of data. For such problems we propose to seek for
algorithms that work with data exclusively in tensor formats,
the price we pay is a contamination of data through some approximation
(recompression) at each operation. We show that a certain intentional
corruption of data, under pretty mild assumptions, still preserves
the convergence rate of superlinear iterations. Then, we discuss
which tensor formats are best suitable and advocate to deal with
the Tucker format for all operands. As an application, we present
new approximate matrix inversion algorithms with linear and even
sublinear complexity in the matrix size and recent suggestions
for construction of eigenvalue solvers. Also, we discuss the
gains of combination of tensor and typical Toeplitz-like structures.
In particular, doubly Toeplitz (block Toeplitz with Toeplitz
blocks) matrices of a wide class can be approximately inverted
with the complexity of order of square root of the matrix size.
|
