Рахуба Максим Владимирович

Towards Practical Control of Singular Values of Convolutional Layers

2022 · CHAPTER · en

Robust alternating direction implicit solver in quantized tensor formats for a three-dimensional elliptic PDE

2021 · ARTICLE · en

The aim of this paper is to propose a robust numerical solver, which is capable of efficiently solving a three-dimensional elliptic problem in a data-sparse quantized tensor format. In particular, we use the combined Tucker and quantized tensor train format (TQTT), which allows us to use astronomically large grid sizes. However, due to the ill-conditioning of discretized differential operators, so fine grids lead to numerical instabilities. To obtain a robust solver, we utilize the well-known alternating direction implicit method and modify it to avoid multiplication by differential operators. So as to make the method efficient, we derive an explicit TQTT representation of the iteration matrix and quantized tensor train (QTT) representations of the inverses of symmetric tridiagonal Toeplitz matrices as an auxiliary result. As an application, we consider accurate solution of elliptic problems with singular potentials arising in electronic Schroedinger’s equation.

Spectral Tensor Train Parameterization of Deep Learning Layers

2021 · CHAPTER · en

Cherry-Picking Gradients: Learning Low-Rank Embeddings of Visual Data via Differentiable Cross-Approximation

2021 · CHAPTER · en

We propose an end-to-end trainable framework that processes large-scale visual data tensors by looking at a fraction of their entries only. Our method combines a neural network encoder with a tensor train decomposition to learn a low-rank latent encoding, coupled with cross-approximation (CA) to learn the representation through a subset of the original samples. CA is an adaptive sampling algorithm that is native to tensor decompositions and avoids working with the full high-resolution data explicitly. Instead, it actively selects local representative samples that we fetch out-of-core and on demand. The required number of samples grows only logarithmically with the size of the input. Our implicit representation of the tensor in the network enables processing large grids that could not be otherwise tractable in their uncompressed form. The proposed approach is particularly useful for large-scale multidimensional grid data (e.g., 3D tomography), and for tasks that require context over a large receptive field (e.g., predicting the medical condition of entire organs). The code is available at https://github.com/aelphy/c-pic.

T-Basis: a Compact Representation for Neural Networks

2020 · CHAPTER · en

Low rank tensor approximation of singularly perturbed partial differential equations in one dimension

2020 · PREPRINT · en

We derive rank bounds on the quantized tensor train (QTT) compressed approximation of singularly perturbed reaction diffusion partial differential equations (PDEs) in one dimension. Specifically, we show that, independently of the scale of the singular perturbation parameter, a numerical solution with accuracy 0<ϵ<1 can be represented in QTT format with a number of parameters that depends only polylogarithmically on ϵ. In other words, QTT compressed solutions converge exponentially to the exact solution, with respect to a root of the number of parameters. We also verify the rank bound estimates numerically, and overcome known stability issues of the QTT based solution of PDEs by adapting a preconditioning strategy to obtain stable schemes at all scales. We find, therefore, that the QTT based strategy is a rapidly converging algorithm for the solution of singularly perturbed PDEs, which does not require prior knowledge on the scale of the singular perturbation and on the shape of the boundary layers.

Quantized tensor FEM for multiscale problems: diffusion problems in two and three dimensions

2020 · PREPRINT · en

Homogenization in terms of multiscale limits transforms a multiscale problem with n+1 asymptotically separated microscales posed on a physical domain D⊂ℝd into a one-scale problem posed on a product domain of dimension (n+1)d by introducing n so-called "fast variables". This procedure allows to convert n+1 scales in d physical dimensions into a single-scale structure in (n+1)d dimensions. We prove here that both the original, physical multiscale problem and the corresponding high-dimensional, one-scale limiting problem can be efficiently treated numerically with the recently developed quantized tensor-train finite-element method (QTT-FEM). The method is based on restricting computation to sequences of nested subspaces of low dimensions (which are called tensor ranks) within a vast but generic "virtual" (background) discretization space. In the course of computation, these subspaces are computed iteratively and data-adaptively at runtime, bypassing any "offline precomputation". For the purpose of theoretical analysis, such low-dimensional subspaces are constructed analytically to bound the tensor ranks vs. error τ>0. We consider a model linear elliptic multiscale problem in several physical dimensions and show, theoretically and experimentally, that both (i) the solution of the associated high-dimensional one-scale problem and (ii) the corresponding approximation to the solution of the multiscale problem admit efficient approximation by the QTT-FEM. These problems can therefore be numerically solved in a scale-robust fashion by standard (low-order) PDE discretizations combined with state-of-the-art general-purpose solvers for tensor-structured linear systems. We prove scale-robust exponential convergence, i.e., that QTT-FEM achieves accuracy τ with the number of effective degrees of freedom scaling polynomially in logτ.

Tensor Rank bounds for Point Singularities in ℝ^3

2020 · PREPRINT · en

We analyze rates of approximation by quantized, tensor-structured representations of functions with isolated point singularities in ℝ3. We consider functions in countably normed Sobolev spaces with radial weights and analytic- or Gevrey-type control of weighted semi-norms. Several classes of boundary value and eigenvalue problems from science and engineering are discussed whose solutions belong to the countably normed spaces. It is shown that quantized, tensor-structured approximations of functions in these classes exhibit tensor ranks bounded polylogarithmically with respect to the accuracy ϵ∈(0,1) in the Sobolev space H1. We prove exponential convergence rates of three specific types of quantized tensor decompositions: quantized tensor train (QTT), transposed QTT and Tucker-QTT. In addition, the bounds for the patchwise decompositions are uniform with respect to the position of the point singularity. An auxiliary result of independent interest is the proof of exponential convergence of hp-finite element approximations for Gevrey-regular functions with point singularities in the unit cube Q=(0,1)3. Numerical examples of function approximations and of Schrödinger-type eigenvalue problems illustrate the theoretical results.

Low-rank Riemannian eigensolver for high-dimensional Hamiltonians

2019 · ARTICLE · en

Such problems as computation of spectra of spin chains and vibrational spectra of molecules can be written as high-dimensional eigenvalue problems, i.e., when the eigenvector can be naturally represented as a multidimensional tensor. Tensor methods have proven to be an efficient tool for the approximation of solutions of high-dimensional eigenvalue problems, however, their performance deteriorates quickly when the number of eigenstates to be computed increases. We address this issue by designing a new algorithm motivated by the ideas of Riemannian optimization (optimization on smooth manifolds) for the approximation of multiple eigenstates in the tensor-train format, which is also known as matrix product state representation. The proposed algorithm is implemented in TensorFlow, which allows for both CPU and GPU parallelization.

Robust solver in a quantized tensor format for three-dimensional elliptic problems

2019 · PREPRINT · en

The aim of this paper is to propose a robust numerical solver, which is capable of efficiently solving a three-dimensional elliptic problem in a data-sparse quantized tensor format. In particular, we use the combined Tucker and quantized tensor train format (TQTT), which allows us to use astronomically large grid sizes. However, due to ill-conditioning of discretized differential operators, such fine grids lead to numerical instabilities. The idea to obtain a robust solver is to utilize the well-known alternating direction implicit method and modify it to avoid multiplication by differential operators. So as to make the method efficient, we derive an explicit TQTT representation of the iteration matrix and QTT representations of the inverses of symmetric tridiagonal Toeplitz matrices as an auxiliary result. As an application, we consider accurate solution of elliptic problems with singular potentials arising in electronic Schroedinger’s equation.