Quasi-polynomial tractability of linear problems in the average case setting

We study d$d$-variate approximation problems in the average case setting with respect to a zero-mean Gaussian measure. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. For the absolute error criterion, we obtain the necessary and sufficient conditions in terms of the eigenvalues of its covariance operator and obtain an estimate of the exponent t^qpol-avg$t^{\text{qpol-avg}}$ of quasi-polynomial tractability which cannot be improved in general. For the linear tensor product problems, we find that the quasi-polynomial tractability is equivalent to the strong polynomial tractability. For the normalized error criterion, we solve a problem related to the Korobov kernels, which is left open in Lifshits et al. (2012).     

On the tractability of linear tensor product problems in the worst case

It has been an open problem to derive a necessary and sufficient condition for a linear tensor product problem to be weakly tractable in the worst case. The complexity of linear tensor product problems in the worst case depends on the eigenvalues _{λi}i∈N${\left\{{\lambda }_i\right\}}_{i\in \mathbb{N}}$ of a certain operator. It is known that if _λ1=1${\lambda }_1=1$ and _λ2∈(0,1)${\lambda }_2\in (0,1)$ then _λn=o((lnn)⁻²)${\lambda }_n=o\left({(lnn)}^{-2}\right)$, as n→∞$n\to \infty$, is a necessary condition for a problem to be weakly tractable. We show that this is a sufficient condition as well.     

Exponential tractability of linear weighted tensor product problems in the worst-case setting for arbitrary linear functionals

We study the approximation of compact linear operators defined over certain weighted tensor product Hilbert spaces. The information complexity is defined as the minimal number of arbitrary linear functionals needed to obtain an $\epsilon$-approximation for the $d$-variate problem which is fully determined in terms of the weights and univariate singular values. Exponential tractability means that the information complexity is bounded by a certain function that depends polynomially on $d$ and logarithmically on ${\epsilon }^{-1}$. The corresponding unweighted problem was studied in Hickernell et al. (2020) with many negative results for exponential tractability. The product weights studied in the present paper change the situation. Depending on the form of polynomial dependence on $d$ and logarithmic dependence on ${\epsilon }^{-1}$, we study exponential strong polynomial, exponential polynomial, exponential quasi-polynomial, and exponential $(s,t)$-weak tractability with $max(s,t)\ge 1$. For all these notions of exponential tractability, we establish necessary and sufficient conditions on weights and univariate singular values for which it is indeed possible to achieve the corresponding notion of exponential tractability. The case of exponential $(s,t)$-weak tractability with $max(s,t)<1$ is left for future study. The paper uses some general results obtained in Hickernell et al. (2020) and Kritzer and Woźniakowski (2019).     

Average case tractability of non-homogeneous tensor product problems with the absolute error criterion

We study average case tractability of non-homogeneous tensor product problems with the absolute error criterion. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. For general non-homogeneous tensor product problems, we obtain the matching necessary and sufficient conditions for strong polynomial tractability in terms of the one-dimensional eigenvalues. We give some examples to show that strong polynomial tractability is not equivalent to polynomial tractability, and polynomial tractability is not equivalent to quasi-polynomial tractability. But for non-homogeneous tensor product problems with decreasing eigenvalues, we prove that strong polynomial tractability is always equivalent to polynomial tractability, and strong polynomial tractability is even equivalent to quasi-polynomial tractability when the one-dimensional largest eigenvalues are less than one. In particular, we find an example that quasi-polynomial tractability with the absolute error criterion is not equivalent to that with the normalized error criterion even if all the one-dimensional largest eigenvalues are one. Finally we consider a special class of non-homogeneous tensor product problems with improved monotonicity condition of the eigenvalues.     

Tractability of quasilinear problems II: Second-order elliptic problems

In a previous paper, we developed a general framework for establishing tractability and strong tractability for quasilinear multivariate problems in the worst case setting. One important example of such a problem is the solution of the Helmholtz equation in the -dimensional unit cube, in which depends linearly on , but nonlinearly on . Here, both and  are -variate functions from a reproducing kernel Hilbert space with finite-order weights of order . This means that, although  can be arbitrarily large, and  can be decomposed as sums of functions of at most  variables, with independent of .

In this paper, we apply our previous general results to the Helmholtz equation, subject to either Dirichlet or Neumann homogeneous boundary conditions. We study both the absolute and normalized error criteria. For all four possible combinations of boundary conditions and error criteria, we show that the problem is tractable. That is, the number of evaluations of and  needed to obtain an -approximation is polynomial in  and , with the degree of the polynomial depending linearly on . In addition, we want to know when the problem is strongly tractable, meaning that the dependence is polynomial only in  , independently of . We show that if the sum of the weights defining the weighted reproducing kernel Hilbert space is uniformly bounded in  and the integral of the univariate kernel is positive, then the Helmholtz equation is strongly tractable for three of the four possible combinations of boundary conditions and error criteria, the only exception being the Dirichlet boundary condition under the normalized error criterion.

     

Complexity of multilinear problems in the worst case setting

This is the first of two papers on multilinear problems, and it is devoted to the worst case setting. A second paper will analyze the average case setting. We show how to reduce the analysis of multilinear problems to linear subproblems. In particular, it is proven that adaption can help by a factor of at most k and k-linear problems. The error of multilinear algorithms is analyzed and optimality properties of spline algorithms for the Hilbert case are established. We illustrate our analysis with an example of a multilinear problem from signal processing.     

Tractability of linear problems defined over Hilbert spaces

We study d$d$-variate approximation problems in the worst and average case settings. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. In the worst case setting, we obtain necessary and sufficient conditions for quasi-polynomial tractability and uniform weak tractability. Furthermore, we give an estimate of the exponent of quasi-polynomial tractability which cannot be improved in general. In the average case setting, we obtain necessary and sufficient conditions for uniform weak tractability. As applications we discuss some examples.     

Tractability of quasilinear problems I: General results

The tractability of multivariate problems has usually been studied only for the approximation of linear operators. In this paper we study the tractability of quasilinear multivariate problems. That is, we wish to approximate nonlinear operators S_d(·,·) that depend linearly on the first argument and satisfy a Lipschitz condition with respect to both arguments. Here, both arguments are functions of d variables. Many computational problems of practical importance have this form. Examples include the solution of specific Dirichlet, Neumann, and Schrödinger problems. We show, under appropriate assumptions, that quasilinear problems, whose domain spaces are equipped with product or finite-order weights, are tractable or strongly tractable in the worst case setting.This paper is the first part in a series of papers. Here, we present tractability results for quasilinear problems under general assumptions on quasilinear operators and weights. In future papers, we shall verify these assumptions for quasilinear problems such as the solution of specific Dirichlet, Neumann, and Schrödinger problems.     

Tractability of convex vector optimization problems in the sense of polyhedral approximations

There are different solution concepts for convex vector optimization problems (CVOPs) and a recent one, which is motivated from a set optimization point of view, consists of finitely many efficient solutions that generate polyhedral inner and outer approximations to the Pareto frontier. A CVOP with compact feasible region is known to be bounded and there exists a solution of this sense to it. However, it is not known if it is possible to generate polyhedral inner and outer approximations to the Pareto frontier of a CVOP if the feasible region is not compact. This study shows that not all CVOPs are tractable in that sense and gives a characterization of tractable problems in terms of the well known weighted sum scalarization problems.     

A survey of average case complexity for linear multivariate problems

We survey recent results on the average case complexity for linear multivariate problems. Our emphasis is on problems defined on spaces of functions of d variables with large d. We present the sharp order of the average case complexity for a number of linear multivariate problems as well as necessary and sufficient conditions for the average case complexity not to be exponential in d. Dedicated to the 50th anniversary of the journal. The text was submitted by the authors in English.     

Well-posedness of convex maximization problems on Stiefel manifolds and orthogonal tensor product approximations

Problems of best tensor product approximation of low orthogonal rank can be formulated as maximization problems on Stiefel manifolds. The functionals that appear are convex and weakly sequentially continuous. It is shown that such problems are always well-posed, even in the case of non-compact Stiefel manifolds. As a consequence, problems of finding a best orthogonal, strong orthogonal or complete orthogonal low-rank tensor product approximation and problems of best Tucker format approximation to any given tensor are always well-posed, even in spaces of infinite dimension. (The best rank-one approximation is a special case of all of them.) In addition, the well-posedness of a canonical low-rank approximation with bounded coefficients can be shown. The proofs are non-constructive and the problem of computation is not addressed here.