Tensor Rank bounds for Point Singularities in R 3 .

Carlo Marcati, Maxim Rakhuba, C. Schwab

TL;DR

This paper develops theoretical bounds for approximating functions with point singularities in 3D using tensor-structured methods. It shows that these approximations can achieve exponential convergence rates with tensor ranks that grow only polylogarithmically with accuracy, a significant improvement for handling complex functions arising in scientific computing.

What Problem Does This Paper Address?

Many problems in science and engineering, such as those involving quantum mechanics, fluid dynamics, or material science, lead to partial differential equations (PDEs) whose solutions exhibit singularities. These singularities, often occurring at specific points, edges, or corners of a domain, pose a significant challenge for traditional numerical methods. Approximating these functions efficiently is crucial. Tensor-structured methods, like Tensor Train (TT) and its quantized variants (QTT), offer a promising avenue for representing high-dimensional data and functions with low-rank structures. However, understanding the theoretical limits of these methods, particularly for functions with challenging singularities, is essential for their reliable application. This paper addresses this gap by providing rigorous bounds on the tensor ranks required for approximating functions with isolated point singularities in 3D, specifically within weighted Sobolev spaces.

Methods

The paper introduces and analyzes three tensor-structured approximation formats:

  • Classic Quantized Tensor Train (QTT): This method reshapes a multi-dimensional tensor into a high-dimensional one and then applies the TT decomposition.
  • Transposed Order QTT (QT3): This format rearranges the tensor's indices before applying the TT decomposition.
  • Tucker-QTT (TQTT): This approach combines Tucker decomposition with QTT, offering a hybrid representation.

A key methodological contribution is the use of auxiliary hp-finite element (FE) spaces. These spaces, with geometrically refined meshes and adaptive polynomial degrees, provide an exponential convergence rate for approximating the singular functions. The authors then use these hp-approximations as a bridge to establish the tensor rank bounds for the QTT-based methods. They prove that the required tensor ranks grow polylogarithmically with respect to the desired accuracy, a crucial result for practical applications. The analysis also extends to domains with internal singularities by employing a patchwise approach.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and numerical experiments with model functions and problems, rather than training on specific datasets.

Key Insights and Ideas

  • Polylogarithmic Rank Growth: The most significant insight is that for functions with isolated point singularities, tensor-structured approximations (QTT, QT3, TQTT) can achieve exponential convergence with tensor ranks that grow only polylogarithmically with respect to the approximation accuracy. This is a substantial improvement over methods where ranks might grow much faster.
  • hp-FEM as a Bridge: The paper cleverly uses the known exponential convergence of hp-FEM for singular functions as a stepping stone to prove the low-rank properties of tensor representations. This connection highlights the underlying low-rank structure of these singular functions.
  • Uniformity of Bounds: The derived rank bounds are uniform with respect to the position of the point singularity, which is a valuable property for practical implementations where singularity locations might vary.
  • TQTT Efficiency: Numerical experiments suggest that the TQTT format often requires the fewest degrees of freedom to achieve a given accuracy compared to QTT and QT3, making it a potentially more efficient choice in practice.

Key Results

  • Theoretical Rank Bounds: The paper provides explicit theoretical bounds on the tensor ranks for QTT, QT3, and TQTT representations of functions with isolated point singularities in weighted Gevrey and analytic classes. These ranks grow polylogarithmically with the approximation accuracy $\epsilon$.
  • Exponential Convergence: The analysis demonstrates that these tensor-structured approximations achieve exponential convergence rates in the $H^1(Q)$ norm.
  • Numerical Validation: Numerical experiments confirm the theoretical findings, showing that the observed convergence rates are often better than the derived bounds. The experiments also illustrate the practical performance of the different tensor formats, with TQTT showing promising efficiency.
  • Extension to Internal Singularities: The framework is extended to handle singularities located in the interior of a domain using a patchwise approach, maintaining similar rank bound properties.

Limitations and Future Work

  • Focus on Isolated Singularities: The current analysis primarily focuses on isolated point singularities. The authors mention that extending these results to line and face singularities, or to multiple well-separated singularities, would be a valuable next step.
  • Constant Factors: While the polylogarithmic growth of ranks is established, the constants in these bounds can depend on various parameters, which might affect practical performance.
  • Numerical Implementation: The paper relies on existing libraries (like TT-Toolbox) for numerical experiments. Further research could explore optimized implementations tailored to these specific singularity structures.
  • PDE Solvers: The authors suggest that these theoretical results pave the way for developing more efficient tensor-structured solvers for PDEs with singular solutions, particularly in areas like electronic structure calculations. This remains an active area for future research.

Summary updated

BibTeX
@article{marcati2022tensor,
  author = {Carlo Marcati and Maxim Rakhuba and C. Schwab},
  title = {{Tensor Rank bounds for Point Singularities in R 3 .}},
  journal = {Adv. Comput. Math.},
  year = {2022},
  doi = {10.1007/s10444-022-09925-7},
}
Figure