Weighted sparsity and sparse tensor networks for least squares approximation
Authors
- Trunschke, Philipp
- Eigel, Martin
ORCID: 0000-0003-2687-4497 - Nouy, Anthony
2020 Mathematics Subject Classification
- 15A69 41A30 62J02 65Y20 68Q25
Keywords
- Least squares, sample efficiency, sparse tensor networks, alternating least squares
DOI
Abstract
The approximation of high-dimensional functions is a ubiquitous problem in many scientific fields that is only feasible practically if advantageous structural properties can be exploited. One prominent structure is sparsity relatively to some basis. For the analysis of these best n-term approximations a relevant tool is the Stechkin's lemma. In its standard form, however, this lemma does not allow to explain convergence rates for a wide range of relevant function classes. This work presents a new weighted version of Stechkin's lemma that improves the best n-term rates for weighted ℓp-spaces and associated function classes such as Sobolev or Besov spaces. For the class of holomorphic functions, which for example occur as solutions of common high-dimensional parameter dependent PDEs, we recover exponential rates that are not directly obtainable with Stechkin's lemma. This sparsity can be used to devise weighted sparse least squares approximation algorithms as known from compressed sensing. However, in high-dimensional settings, classical algorithms for sparse approximation suffer the curse of dimensionality. We demonstrate that sparse approximations can be encoded efficiently using tensor networks with sparse component tensors. This representation gives rise to a new alternating algorithm for best n-term approximation with a complexity scaling polynomially in n and the dimension. We also demonstrate that weighted ℓpsummability not only induces sparsity of the tensor but also low ranks. This is not exploited by the previous format. We thus propose a new low-rank tensor train format with a single weighted sparse core tensor and an ad-hoc algorithm for approximation in this format. To analyse the sample complexity for this new model class we derive a novel result of independent interest that allows to transfer the restricted isometry property from one set to another sufficiently close set. We then prove that the new model class is close enough to the set of weighted sparse vectors such that the restricted isometry property transfers. Numerical examples illustrate the theoretical results for a benchmark problem from uncertainty quantification. Although they lead up to the analysis of our final model class, our contributions on weighted Stechkin and the restricted isometry property are of independent interest and can be read independently.
Download Documents