Tensor rank bounds for point singularities in ℝ3

Carlo Marcati, Maksim Rakhuba, Christoph Schwab

Abstract This paper provides the first rigorous proof that functions with point singularities in 3D—common in quantum chemistry and electromagnetics—can be approximated with exponential efficiency using quantized tensor formats. The authors demonstrate that the "tensor rank," a measure of computational complexity, grows only polylogarithmically with the desired accuracy. This result effectively breaks the curse of dimensionality for a wide class of singular physical problems, offering a robust alternative to traditional adaptive mesh methods.

1. Introduction

In scientific computing, functions with point singularities—where values or derivatives blow up at specific locations—are ubiquitous. A classic example is the $1/|x|$ potential of an electron near a nucleus. Standard numerical methods, such as the Finite Element Method (FEM), struggle with these features; achieving high accuracy typically requires an impractically large number of grid points clustered near the singularity.

While specialized techniques like $hp$-FEM (which utilize variable mesh sizes and polynomial degrees) can achieve exponential convergence, they are notoriously difficult to implement in three dimensions. This paper explores Quantized Tensor Decompositions as a solution. These methods reshape a standard 3D grid into a high-dimensional "virtual" space of bits. This study investigates whether the complexity (tensor rank) of these representations remains manageable as accuracy requirements increase for singular functions.

2. Methodology

The authors analyze three specific quantized tensor formats:

  1. Quantized Tensor Train (QTT): The standard approach where the 3D grid is reshaped into a long chain of bit-level dimensions.
  2. Transposed QTT (QT3): A variation that interleaves the bits of the $x, y,$ and $z$ coordinates to better capture local spatial correlations.
  3. Tucker QTT (TQTT): A hybrid approach using Tucker decomposition to compress physical dimensions, combined with QTT for the resulting factors.

The "Bridge" Proof

To establish rank bounds, the authors utilize a novel intermediate step. They first prove that $hp$-FEM approximations converge exponentially for "Gevrey-regular" functions—a class including analytic functions but allowing for more general derivative growth. They then demonstrate that these $hp$-FEM functions can be exactly represented as low-rank tensors. By linking these two domains, they prove that the tensor approximation of the original singular function must also possess low ranks.

3. Experimental Setup

As a theoretical numerical analysis, the study utilizes mathematical model problems for validation:

  • Synthetic Singular Functions: Functions defined as $u(x) = |x|^\alpha m(x)$, where $\alpha$ determines the singularity strength at the origin.
  • The Hydrogen Atom: A benchmark eigenvalue problem for the Schrödinger equation featuring a singular Coulomb potential ($V = -1/|x|$).
  • Implementation: Numerical experiments were conducted using the ttpy Python library.

4. Key Insights and Results

Polylogarithmic Rank Growth

The primary theoretical contribution is the proof that the tensor rank $r$ required to achieve accuracy $\epsilon$ satisfies $r \le C |\log \epsilon|^\kappa$. This polylogarithmic scaling is the hallmark of exponential convergence. In 3D experiments, such as the hydrogen atom model, observed ranks were even lower than the theoretical upper bounds.

Format Efficiency and Adaptation

  • Automatic Adaptation: Unlike $hp$-FEM, which requires manual geometric mesh design, quantized tensor algorithms (like SVD-based rounding) automatically discover the low-rank structure of the singularity.
  • Interleaving Benefits: The QT3 format provides superior theoretical scaling for certain singularities by grouping bits from different spatial dimensions.
  • TQTT Performance: The Tucker-QTT hybrid was found to be the most efficient format, requiring the fewest parameters to reach prescribed accuracy levels.

5. Conclusion and Future Work

While this work rigorously addresses point singularities, several avenues for future research remain. The current proof does not yet formally cover line or face singularities (e.g., the edges of a cube), which are common in engineering applications. Additionally, while the paper provides upper bounds on ranks, it is not yet known if these bounds are tight.

Future work will focus on applying these bounds to more complex many-body interaction problems in quantum chemistry and addressing the ill-conditioning that arises in extremely refined grids through specialized derivative-free tensor algorithms.

Summary updated

Abstract

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.
BibTeX
@article{marcati2022tensor,
  author = {Carlo Marcati and Maksim Rakhuba and Christoph Schwab},
  title = {{Tensor rank bounds for point singularities in ℝ3}},
  journal = {Adv. Comput. Math.},
  year = {2022},
  doi = {10.1007/s10444-022-09925-7},
}
Figure