Tensor-sparsity of solutions to highdimensional elliptic partial differential equations

Abstract. A recurring theme in attempts to break the curse of dimensionality in the numerical approximations of solutions to high-dimensional partial differential equations (PDEs) is to em-ploy some form of sparse tensor approximation. Unfortunately, there are only a few results that quantify the possible advantages of such an approach. This paper introduces a class Σn of func-tions, which can be written as a sum of rank-one tensors using a total of at most n parameters and then uses this notion of sparsity to prove a regularity theorem for certain high-dimensional elliptic PDEs. It is shown, among other results, that whenever the right-hand side f of the elliptic PDE can be approximated with a certain rate O(n−r) in the norm of H−1 by elements of Σn, then the solution u can be approximated in H1 from Σn to accuracy O(n−r ′ ) for any r ′ ∈ (0, r). Since these results require knowledge of the eigenbasis of the elliptic operator consid-ered, we propose a second “basis-free ” model of tensor sparsity and prove a regularity theorem for this second sparsity model as well. We then proceed to address the important question of the extent such regularity theorems translate into results on computational complexity. It is shown how this second model can be used to derive computational algorithms with performance that breaks the curse of dimensionality on certain model high-dimensional elliptic PDEs with tensor-sparse data