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

Dimension-free Structured Covariance Estimation

2024 · CHAPTER · en

Given a sample of i.i.d. high-dimensional centered random vectors, we consider a problem of estimation of their covariance matrix Σ with an additional assumption that Σ can be represented as a sum of a few Kronecker products of smaller matrices. Under mild conditions, we derive the first non-asymptotic dimension-free high-probability bound on the Frobenius distance between Σ and a widely used penalized permuted least squares estimate. Because of the hidden structure, the established rate of convergence is faster than in the standard covariance estimation problem.

Group and Shuffle: Efficient Structured Orthogonal Parametrization

2024 · CHAPTER · en

Training a Tucker Model With Shared Factors: a Riemannian Optimization Approach

2024 · CHAPTER · en

Tight and Efficient Upper Bound on Spectral Norm of Convolutional Layers

2024 · CHAPTER · en

Controlling the spectral norm of the Jacobian matrix, which is related to the convolution operation, has been shown to improve generalization, training stability and robustness in CNNs. Existing methods for computing the norm either tend to overestimate it or their performance may deteriorate quickly with increasing the input and kernel sizes. In this paper, we demonstrate that the tensor version of the spectral norm of a four-dimensional convolution kernel, up to a constant factor, serves as an upper bound for the spectral norm of the Jacobian matrix associated with the convolution operation. This new upper bound is independent of the input image resolution, differentiable and can be efficiently calculated during training. Through experiments, we demonstrate how this new bound can be used to improve the performance of convolutional architectures.

Tensor rank bounds and explicit QTT representations for the inverses of circulant matrices

2023 · ARTICLE · en

In this paper, we are concerned with the inversion of circulant matrices and their quantized tensor-train (QTT) structure. In particular, we show that the inverse of a complex circulant matrix (Formula presented.), generated by the first column of the form (Formula presented.) admits a QTT representation with the QTT ranks bounded by (Formula presented.). Under certain assumptions on the entries of (Formula presented.), we also derive an explicit QTT representation of (Formula presented.). The latter can be used, for instance, to overcome stability issues arising when numerically solving differential equations with periodic boundary conditions in the QTT format. © 2022 John Wiley & Sons Ltd.

Automatic differentiation for Riemannian optimization on low-rank matrix and tensor-train manifolds

2022 · ARTICLE · en

In scientific computing and machine learning applications, matrices and more general multidimensional arrays (tensors) can often be approximated with the help of low-rank decompositions. Since matrices and tensors of fixed rank form smooth Riemannian manifolds, one of the popular tools for finding low-rank approximations is to use Riemannian optimization. Nevertheless, efficient implementation of Riemannian gradients and Hessians, required in Riemannian optimization algorithms, can be a nontrivial task in practice. Moreover, in some cases, analytic formulas are not even available. In this paper, we build upon automatic differentiation and propose a method that, given an implementation of the function to be minimized, efficiently computes Riemannian gradients and matrix-by-vector products between an approximate Riemannian Hessian and a given vector.

Low-rank tensor approximation of singularly perturbed boundary value problems in one dimension

2022 · ARTICLE · en

We derive rank bounds on the quantized tensor train (QTT) compressed approximation of singularly perturbed reaction diffusion boundary value problems in one dimension. Specifically, we show that, independently of the scale of the singular perturbation parameter, a numerical solution with accuracy 0

Tensor rank bounds for point singularities in ℝ³

2022 · ARTICLE · 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. © 2022, The Author(s).

Local convergence of alternating low-rank optimization methods with overrelaxation

2022 · ARTICLE · en

The local convergence of alternating optimization methods with overrelaxation for low-rank matrix and tensor problems is established. The analysis is based on the linearization of the method which takes the form of an SOR iteration for a positive semidefinite Hessian and can be studied in the corresponding quotient geometry of equivalent low-rank representations. In the matrix case, the optimal relaxation parameter for accelerating the local convergence can be determined from the convergence rate of the standard method. This result relies on a version of Young's SOR theorem for positive semidefinite (Formula presented.) block systems. © 2022 The Authors. Numerical Linear Algebra with Applications published by John Wiley & Sons Ltd.

Quantized Tensor FEM for Multiscale Problems: Diffusion Problems in Two and Three Dimensions

2022 · ARTICLE · en

Homogenization in terms of multiscale limits transforms a multiscale problem with 𝑛+1n+1 asymptotically separated microscales posed on a physical domain 𝐷⊂ℝ𝑑D⊂Rd into a one-scale problem posed on a product domain of dimension (𝑛+1)𝑑(n+1)d by introducing 𝑛n so-called fast variables. This procedure allows one to convert 𝑛+1n+1 scales in 𝑑d physical dimensions into a single-scale structure in (𝑛+1)𝑑(n+1)ddimensions. 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 QTT-FE approximation consists in restricting approximation and computation to sequences of nested subspaces, each of which is a tensor product of two factors of low dimension (rank), within a vast, but generic “virtual” (background) discretization space. In practice, these subspaces are determined iteratively and data-adaptively at runtime bypassing any “offline precomputation.” For theoretical analysis, low-dimensional subspaces are constructed analytically to bound the tensor ranks against the error tolerance. 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 approximation to the solution of the multiscale problem induced thereby admit efficient QTT-FE approximations. 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. Specifically, we prove the existence of QTT-FE approximations with an upper bound on the tensor ranks growing no faster than algebraically with respect to log𝜖−1log⁡ϵ−1 and independent of the scale parameters, where 𝜖ϵ is the target accuracy for the approximation of the solution and of its gradient. In numerical experiments, we verify the theoretical rank bounds and computationally investigate the dependence of the complexity of the solutions on the number 𝑛n of microscales.