ALBERT

Description: 〈p〉Publication date: Available online 1 November 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity〈/p〉 〈p〉Author(s): Robert J. Kunsch, Erich Novak, Daniel Rudolf〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉We compute the integral of a function or the expectation of a random variable with minimal cost and use, for our new algorithm and for upper bounds of the complexity, i.i.d. samples. Under certain assumptions it is possible to select a sample size based on a variance estimation, or – more generally – based on an estimation of a (central absolute) 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈mi〉p〈/mi〉〈/math〉-moment. That way one can guarantee a small absolute error with high probability, the problem is thus called solvable. The expected cost of the method depends on the 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈mi〉p〈/mi〉〈/math〉-moment of the random variable, which can be arbitrarily large. In order to prove the optimality of our algorithm we also provide lower bounds. These bounds apply not only to methods based on i.i.d. samples but also to general randomized algorithms. They show that – up to constants – the cost of the algorithm is optimal in terms of accuracy, confidence level, and norm of the particular input random variable. Since the considered classes of random variables or integrands are very large, the worst case cost would be infinite. Nevertheless one can define adaptive stopping rules such that for each input the expected cost is finite. We contrast these positive results with examples of integration problems that are not solvable.〈/p〉〈/div〉

Description: 〈p〉Publication date: October 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 48〈/p〉 〈p〉Author(s): Alexander E. Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, Pierre Youssef〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉Let 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈mi〉d〈/mi〉〈/math〉 be a (large) integer. Given 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si2.gif"〉〈mi〉n〈/mi〉〈mo〉≥〈/mo〉〈mn〉2〈/mn〉〈mi〉d〈/mi〉〈/math〉, let 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈msub〉〈mrow〉〈mi〉A〈/mi〉〈/mrow〉〈mrow〉〈mi〉n〈/mi〉〈/mrow〉〈/msub〉〈/math〉 be the adjacency matrix of a random directed 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈mi〉d〈/mi〉〈/math〉-regular graph on 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si5.gif"〉〈mi〉n〈/mi〉〈/math〉 vertices, with the uniform distribution. We show that the rank of 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈msub〉〈mrow〉〈mi〉A〈/mi〉〈/mrow〉〈mrow〉〈mi〉n〈/mi〉〈/mrow〉〈/msub〉〈/math〉 is at least 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si7.gif"〉〈mi〉n〈/mi〉〈mo〉−〈/mo〉〈mn〉1〈/mn〉〈/math〉 with probability going to one as 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si5.gif"〉〈mi〉n〈/mi〉〈/math〉 grows to infinity. The proof combines the well known method of simple switchings and a recent result of the authors on delocalization of eigenvectors of 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈msub〉〈mrow〉〈mi〉A〈/mi〉〈/mrow〉〈mrow〉〈mi〉n〈/mi〉〈/mrow〉〈/msub〉〈/math〉.〈/p〉〈/div〉

Description: 〈p〉Publication date: December 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 49〈/p〉 〈p〉Author(s): Hongzhi Tong, Michael Ng〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉In this paper, we study and analyze the regularized least squares for functional linear regression model. The approach is to use the reproducing kernel Hilbert space framework and the integral operators. We show with a more general and realistic assumption on the reproducing kernel and input data statistics that the rate of excess prediction risk by the regularized least squares is minimax optimal.〈/p〉〈/div〉

Description: 〈p〉Publication date: February 2019〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 50〈/p〉 〈p〉Author(s): Jia Chen, Heping Wang〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉In this paper, we investigate optimal linear approximations (〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈mi〉n〈/mi〉〈/math〉-approximation numbers) of the embeddings from the Sobolev spaces 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si2.gif"〉〈msup〉〈mrow〉〈mi〉H〈/mi〉〈/mrow〉〈mrow〉〈mi〉r〈/mi〉〈/mrow〉〈/msup〉〈mspace width="0.33em"〉〈/mspace〉〈mrow〉〈mo〉(〈/mo〉〈mi〉r〈/mi〉〈mo〉〉〈/mo〉〈mn〉0〈/mn〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 for various equivalent norms and the Gevrey type spaces 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈msup〉〈mrow〉〈mi〉G〈/mi〉〈/mrow〉〈mrow〉〈mi〉α〈/mi〉〈mo〉,〈/mo〉〈mi〉β〈/mi〉〈/mrow〉〈/msup〉〈mspace width="0.33em"〉〈/mspace〉〈mrow〉〈mo〉(〈/mo〉〈mi〉α〈/mi〉〈mo〉,〈/mo〉〈mi〉β〈/mi〉〈mo〉〉〈/mo〉〈mn〉0〈/mn〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 on the sphere 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si4.gif"〉〈msup〉〈mrow〉〈mi mathvariant="double-struck"〉S〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msup〉〈/math〉 and on the ball 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si5.gif"〉〈msup〉〈mrow〉〈mi mathvariant="double-struck"〉B〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msup〉〈/math〉, where the approximation error is measured in the 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si6.gif"〉〈msub〉〈mrow〉〈mi〉L〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/msub〉〈/math〉-norm. We obtain preasymptotics, asymptotics, and strong equivalences of the above approximation numbers as a function in 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈mi〉n〈/mi〉〈/math〉 and the dimension 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si8.gif"〉〈mi〉d〈/mi〉〈/math〉. We emphasize that all equivalence constants in the above preasymptotics and asymptotics are independent of the dimension 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si8.gif"〉〈mi〉d〈/mi〉〈/math〉 and 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈mi〉n〈/mi〉〈/math〉. As a consequence we obtain that for the absolute error criterion the approximation problems 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si11.gif"〉〈msub〉〈mrow〉〈mi〉I〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msub〉〈mo〉:〈/mo〉〈msup〉〈mrow〉〈mi〉H〈/mi〉〈/mrow〉〈mrow〉〈mi〉r〈/mi〉〈/mrow〉〈/msup〉〈mo〉→〈/mo〉〈msub〉〈mrow〉〈mi〉L〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/msub〉〈/math〉 are weakly tractable if and only if 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si12.gif"〉〈mi〉r〈/mi〉〈mo〉〉〈/mo〉〈mn〉1〈/mn〉〈/math〉, not uniformly weakly tractable, and do not suffer from the curse of dimensionality. We also prove that for any 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si13.gif"〉〈mi〉α〈/mi〉〈mo〉,〈/mo〉〈mi〉β〈/mi〉〈mo〉〉〈/mo〉〈mn〉0〈/mn〉〈/math〉, the approximation problems 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si14.gif"〉〈msub〉〈mrow〉〈mi〉I〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msub〉〈mo〉:〈/mo〉〈msup〉〈mrow〉〈mi〉G〈/mi〉〈/mrow〉〈mrow〉〈mi〉α〈/mi〉〈mo〉,〈/mo〉〈mi〉β〈/mi〉〈/mrow〉〈/msup〉〈mo〉→〈/mo〉〈msub〉〈mrow〉〈mi〉L〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/msub〉〈/math〉 are uniformly weakly tractable, not polynomially tractable, and quasi-polynomially tractable if and only if 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si15.gif"〉〈mi〉α〈/mi〉〈mo〉≥〈/mo〉〈mn〉1〈/mn〉〈/math〉.〈/p〉〈/div〉

Description: 〈p〉Publication date: December 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 49〈/p〉 〈p〉Author(s): Domingo Gómez-Pérez, Min Sha, Andrew Tirkel〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉In this paper, we define the linear complexity for multidimensional sequences over finite fields, generalizing the one-dimensional case. We give some lower and upper bounds, valid with large probability, for the linear complexity and 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈mi〉k〈/mi〉〈/math〉-error linear complexity of multidimensional periodic sequences.〈/p〉〈/div〉

Description: 〈p〉Publication date: October 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 48〈/p〉 〈p〉Author(s): Robert J. Kunsch〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉We study the 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si2.gif"〉〈msub〉〈mrow〉〈mi〉L〈/mi〉〈/mrow〉〈mrow〉〈mi〉∞〈/mi〉〈/mrow〉〈/msub〉〈/math〉-approximation of 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈mi〉d〈/mi〉〈/math〉-variate functions from Hilbert spaces via linear functionals as information. It is a common phenomenon in tractability studies that unweighted problems (with each dimension being equally important) suffer from the curse of dimensionality in the deterministic setting, that is, the number 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si4.gif"〉〈mi〉n〈/mi〉〈mrow〉〈mo〉(〈/mo〉〈mi〉ϵ〈/mi〉〈mo〉,〈/mo〉〈mi〉d〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 of information needed in order to solve a problem within a given accuracy 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si5.gif"〉〈mi〉ϵ〈/mi〉〈mo〉〉〈/mo〉〈mn〉0〈/mn〉〈/math〉 grows exponentially in 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈mi〉d〈/mi〉〈/math〉. We show that for certain approximation problems in periodic tensor product spaces, in particular Korobov spaces with smoothness  〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si7.gif"〉〈mi〉r〈/mi〉〈mo〉〉〈/mo〉〈mn〉1〈/mn〉〈mo〉∕〈/mo〉〈mn〉2〈/mn〉〈/math〉, switching to the randomized setting can break the curse of dimensionality, now having polynomial tractability, namely 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si8.gif"〉〈mi〉n〈/mi〉〈mrow〉〈mo〉(〈/mo〉〈mi〉ϵ〈/mi〉〈mo〉,〈/mo〉〈mi〉d〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈mo〉⪯〈/mo〉〈msup〉〈mrow〉〈mi〉ϵ〈/mi〉〈/mrow〉〈mrow〉〈mo〉−〈/mo〉〈mn〉2〈/mn〉〈/mrow〉〈/msup〉〈mspace width="0.16667em"〉〈/mspace〉〈mi〉d〈/mi〉〈mspace width="0.16667em"〉〈/mspace〉〈mrow〉〈mo〉(〈/mo〉〈mn〉1〈/mn〉〈mo〉+〈/mo〉〈mo〉log〈/mo〉〈mi〉d〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉. Similar benefits from Monte Carlo methods in terms of tractability have only been known for integration problems so far.〈/p〉〈/div〉

Description: 〈p〉Publication date: October 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 48〈/p〉 〈p〉Author(s): Kateryna Tatarko〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉Let 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈mi〉A〈/mi〉〈mo〉=〈/mo〉〈mrow〉〈mo〉(〈/mo〉〈msub〉〈mrow〉〈mi〉a〈/mi〉〈/mrow〉〈mrow〉〈mi〉i〈/mi〉〈mi〉j〈/mi〉〈/mrow〉〈/msub〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 be a square 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si2.gif"〉〈mi〉n〈/mi〉〈mo〉×〈/mo〉〈mi〉n〈/mi〉〈/math〉 matrix with i.i.d. zero mean and unit variance entries. It was shown by Rudelson and Vershynin in 2008 that the upper bound for the smallest singular value 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈msub〉〈mrow〉〈mi〉s〈/mi〉〈/mrow〉〈mrow〉〈mi〉n〈/mi〉〈/mrow〉〈/msub〉〈mrow〉〈mo〉(〈/mo〉〈mi〉A〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 is of order 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si4.gif"〉〈msup〉〈mrow〉〈mi〉n〈/mi〉〈/mrow〉〈mrow〉〈mo〉−〈/mo〉〈mfrac〉〈mrow〉〈mn〉1〈/mn〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/mfrac〉〈/mrow〉〈/msup〉〈/math〉 with probability close to one under the additional assumption that the entries of 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si5.gif"〉〈mi〉A〈/mi〉〈/math〉 satisfy 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si6.gif"〉〈mi mathvariant="double-struck"〉E〈/mi〉〈msubsup〉〈mrow〉〈mi〉a〈/mi〉〈/mrow〉〈mrow〉〈mn〉11〈/mn〉〈/mrow〉〈mrow〉〈mn〉4〈/mn〉〈/mrow〉〈/msubsup〉〈mo〉〈〈/mo〉〈mi〉∞〈/mi〉〈/math〉. We remove the assumption on the fourth moment and show the upper bound assuming only 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si7.gif"〉〈mi mathvariant="double-struck"〉E〈/mi〉〈msubsup〉〈mrow〉〈mi〉a〈/mi〉〈/mrow〉〈mrow〉〈mn〉11〈/mn〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/msubsup〉〈mo〉=〈/mo〉〈mn〉1〈/mn〉〈mo〉.〈/mo〉〈/math〉〈/p〉〈/div〉

Description: 〈p〉Publication date: February 2019〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 50〈/p〉 〈p〉Author(s): Yoshihito Kazashi, Quoc T. Le Gia〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉We investigate a discretization of a class of stochastic heat equations on the unit sphere with multiplicative noise. A spectral method is used for the spatial discretization and the truncation of the Wiener process, while an implicit Euler scheme with non-uniform steps is used for the temporal discretization. Some numerical experiments inspired by Earth’s surface temperature data analysis GISTEMP provided by NASA are given.〈/p〉〈/div〉

Description: 〈p〉Publication date: February 2019〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 50〈/p〉 〈p〉Author(s): Shao-Bo Lin〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉Needlets have been recognized as state-of-the-art tools to tackle spherical data, due to their excellent localization properties in both spacial and frequency domains. This paper considers developing kernel methods associated with the needlet kernel for nonparametric regression problems whose predictor variables are defined on a sphere. Due to the localization property in the frequency domain, we prove that the regularization parameter of the kernel ridge regression associated with the needlet kernel can decrease arbitrarily fast. A natural consequence is that the regularization term for the kernel ridge regression is not necessary in the sense of rate optimality. Based on the excellent localization property in the spacial domain further, we prove that all 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈msup〉〈mrow〉〈mi〉l〈/mi〉〈/mrow〉〈mrow〉〈mi〉q〈/mi〉〈/mrow〉〈/msup〉〈/math〉〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si2.gif"〉〈mrow〉〈mo〉(〈/mo〉〈mn〉0〈/mn〉〈mo〉〈〈/mo〉〈mi〉q〈/mi〉〈mo〉≤〈/mo〉〈mn〉2〈/mn〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 kernel regularization estimates associated with the needlet kernel, including the kernel lasso estimate and kernel bridge estimate, possess almost same generalization capability for a large range of regularization parameters in the sense of rate optimality. This finding tentatively reveals that, if the needlet kernel is utilized, then the choice of 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈mi〉q〈/mi〉〈/math〉 might not have a strong impact on the generalization capability in some modeling contexts. The above two properties reveal the theoretical advantages of the needlet kernel in kernel methods for spherical nonparametric regression problems.〈/p〉〈/div〉

Description: 〈p〉Publication date: December 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 49〈/p〉 〈p〉Author(s): Janak Raj Sharma, Deepak Kumar〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉An iterative method with fifth order of convergence for solving systems of nonlinear equations is presented. The scheme is composed of three steps, of which the first two steps are that of double Newton’s method with frozen derivative and third step is second derivative-free modification of Chebyshev’s method. The semilocal convergence of the method in Banach spaces is established by using a system of recurrence relations. Then an existence and uniqueness theorem is given to show the 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si98.gif"〉〈mi〉R〈/mi〉〈/math〉-order of the method to be five and a priori error bounds. Computational complexity is discussed and compared with existing methods. Numerical results are included to confirm theoretical results. A comparison with the existing methods shows that the new method is more efficient than existing ones and hence use the minimum computing time in multiprecision arithmetic.〈/p〉〈/div〉

Description: 〈p〉Publication date: Available online 12 November 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity〈/p〉 〈p〉Author(s): C. Cartis, N.I.M. Gould, Ph.L. Toint〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉Necessary conditions for high-order optimality in smooth nonlinear constrained optimization are explored and their inherent intricacy discussed. A two-phase minimization algorithm is proposed which can achieve approximate first-, second- and third-order criticality and its evaluation complexity is analyzed as a function of the choice (among existing methods) of an inner algorithm for solving subproblems in each of the two phases. The relation between high-order criticality and penalization techniques is finally considered, showing that standard algorithmic approaches will fail if approximate constrained high-order critical points are sought.〈/p〉〈/div〉

Description: 〈p〉Publication date: October 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 48〈/p〉 〈p〉Author(s): Sjoerd Dirksen, Tino Ullrich〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉We consider the problem of determining the asymptotic order of the Gelfand numbers of mixed-(quasi-)norm embeddings 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈msubsup〉〈mrow〉〈mi〉ℓ〈/mi〉〈/mrow〉〈mrow〉〈mi〉p〈/mi〉〈/mrow〉〈mrow〉〈mi〉b〈/mi〉〈/mrow〉〈/msubsup〉〈mrow〉〈mo〉(〈/mo〉〈msubsup〉〈mrow〉〈mi〉ℓ〈/mi〉〈/mrow〉〈mrow〉〈mi〉q〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msubsup〉〈mo〉)〈/mo〉〈/mrow〉〈mo〉↪〈/mo〉〈msubsup〉〈mrow〉〈mi〉ℓ〈/mi〉〈/mrow〉〈mrow〉〈mi〉r〈/mi〉〈/mrow〉〈mrow〉〈mi〉b〈/mi〉〈/mrow〉〈/msubsup〉〈mrow〉〈mo〉(〈/mo〉〈msubsup〉〈mrow〉〈mi〉ℓ〈/mi〉〈/mrow〉〈mrow〉〈mi〉u〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msubsup〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 given that 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si2.gif"〉〈mi〉p〈/mi〉〈mo〉≤〈/mo〉〈mi〉r〈/mi〉〈/math〉 and 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈mi〉q〈/mi〉〈mo〉≤〈/mo〉〈mi〉u〈/mi〉〈/math〉, with emphasis on cases with 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si4.gif"〉〈mi〉p〈/mi〉〈mo〉≤〈/mo〉〈mn〉1〈/mn〉〈/math〉 and/or 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si5.gif"〉〈mi〉q〈/mi〉〈mo〉≤〈/mo〉〈mn〉1〈/mn〉〈/math〉. These cases turn out to be related to structured sparsity. We obtain sharp bounds in a number of interesting parameter constellations. Our new matching bounds for the Gelfand numbers of the embeddings of 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si6.gif"〉〈msubsup〉〈mrow〉〈mi〉ℓ〈/mi〉〈/mrow〉〈mrow〉〈mn〉1〈/mn〉〈/mrow〉〈mrow〉〈mi〉b〈/mi〉〈/mrow〉〈/msubsup〉〈mrow〉〈mo〉(〈/mo〉〈msubsup〉〈mrow〉〈mi〉ℓ〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msubsup〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 and 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si7.gif"〉〈msubsup〉〈mrow〉〈mi〉ℓ〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈mrow〉〈mi〉b〈/mi〉〈/mrow〉〈/msubsup〉〈mrow〉〈mo〉(〈/mo〉〈msubsup〉〈mrow〉〈mi〉ℓ〈/mi〉〈/mrow〉〈mrow〉〈mn〉1〈/mn〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msubsup〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 into 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si8.gif"〉〈msubsup〉〈mrow〉〈mi〉ℓ〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈mrow〉〈mi〉b〈/mi〉〈/mrow〉〈/msubsup〉〈mrow〉〈mo〉(〈/mo〉〈msubsup〉〈mrow〉〈mi〉ℓ〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msubsup〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 imply optimality assertions for the recovery of block-sparse and sparse-in-levels vectors, respectively. In addition, we apply our sharp estimates for 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si9.gif"〉〈msubsup〉〈mrow〉〈mi〉ℓ〈/mi〉〈/mrow〉〈mrow〉〈mi〉p〈/mi〉〈/mrow〉〈mrow〉〈mi〉b〈/mi〉〈/mrow〉〈/msubsup〉〈mrow〉〈mo〉(〈/mo〉〈msubsup〉〈mrow〉〈mi〉ℓ〈/mi〉〈/mrow〉〈mrow〉〈mi〉q〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msubsup〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉-spaces to obtain new two-sided estimates for the Gelfand numbers of multivariate Besov space embeddings in regimes of small mixed smoothness. It turns out that in some particular cases these estimates show the same asymptotic behavior as in the univariate situation. In the remaining cases they differ at most by a 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si10.gif"〉〈mo〉log〈/mo〉〈mo〉log〈/mo〉〈/math〉 factor from the univariate bound.〈/p〉〈/div〉

Description: 〈p〉Publication date: October 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 48〈/p〉 〈p〉Author(s): 〈/p〉

Description: 〈p〉Publication date: December 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 49〈/p〉 〈p〉Author(s): Stefan Heinrich〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉We study the complexity of computing the norm 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si2.gif"〉〈mo〉‖〈/mo〉〈mi〉f〈/mi〉〈msub〉〈mrow〉〈mo〉‖〈/mo〉〈/mrow〉〈mrow〉〈msub〉〈mrow〉〈mi〉L〈/mi〉〈/mrow〉〈mrow〉〈mi〉q〈/mi〉〈/mrow〉〈/msub〉〈mrow〉〈mo〉(〈/mo〉〈mi〉Q〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/mrow〉〈/msub〉〈/math〉, where 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈mi〉f〈/mi〉〈/math〉 is from the unit ball of a Sobolev space 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si4.gif"〉〈msubsup〉〈mrow〉〈mi〉W〈/mi〉〈/mrow〉〈mrow〉〈mi〉p〈/mi〉〈/mrow〉〈mrow〉〈mi〉r〈/mi〉〈/mrow〉〈/msubsup〉〈mrow〉〈mo〉(〈/mo〉〈mi〉Q〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 and 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si5.gif"〉〈mi〉Q〈/mi〉〈mo〉=〈/mo〉〈msup〉〈mrow〉〈mrow〉〈mo〉[〈/mo〉〈mn〉0〈/mn〉〈mo〉,〈/mo〉〈mn〉1〈/mn〉〈mo〉]〈/mo〉〈/mrow〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msup〉〈/math〉 is the unit cube. The deterministic case is a consequence of a general result by Wasilkowski. We consider the randomized setting with standard information and determine the order of the randomized 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si6.gif"〉〈mi〉n〈/mi〉〈/math〉th minimal error. Furthermore, we discuss problems related to the arithmetic cost of the proposed algorithms and present modifications of nearly optimal arithmetic cost in the one-dimensional case.〈/p〉〈/div〉

Description: 〈p〉Publication date: Available online 30 October 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity〈/p〉 〈p〉Author(s): Feng Yang, Yong-Dao Zhou, Aijun Zhang〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉In many industrial applications, follow-up experimental designs are often used to explore the relationship between inputs (factors) and outputs (responses) step by step. Some extra factors with two or three levels may be added in the follow-up stage since they are quite important but may be neglected in the initial stage. In this paper, mixed-level column augmented uniform designs are proposed under the uniformity criterion, wrap-around 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈msub〉〈mrow〉〈mi〉L〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/msub〉〈/math〉-discrepancy (WD). The multi-stage augmented procedure is also investigated. We present the analytical expressions and the corresponding lower bounds on the WD of the column augmented designs. It is shown that the column augmented uniform designs are also the optimal designs under the non-orthogonality criterion, 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si2.gif"〉〈mi〉E〈/mi〉〈mrow〉〈mo〉(〈/mo〉〈msub〉〈mrow〉〈mi〉f〈/mi〉〈/mrow〉〈mrow〉〈mi〉N〈/mi〉〈mi〉O〈/mi〉〈mi〉D〈/mi〉〈/mrow〉〈/msub〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉. Furthermore, a construction algorithm for column augmented uniform designs is provided. Some examples show that the lower bounds are tight and the construction algorithm is effective.〈/p〉〈/div〉

Description: 〈p〉Publication date: Available online 29 October 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity〈/p〉 〈p〉Author(s): Alicja Dota, Leszek Skrzypczak〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉Let 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈msub〉〈mrow〉〈mi〉R〈/mi〉〈/mrow〉〈mrow〉〈mi〉γ〈/mi〉〈/mrow〉〈/msub〉〈msubsup〉〈mrow〉〈mi〉B〈/mi〉〈/mrow〉〈mrow〉〈mi〉p〈/mi〉〈mo〉,〈/mo〉〈mi〉q〈/mi〉〈/mrow〉〈mrow〉〈mi〉s〈/mi〉〈/mrow〉〈/msubsup〉〈mrow〉〈mo〉(〈/mo〉〈msup〉〈mrow〉〈mi mathvariant="double-struck"〉R〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msup〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 be a subspace of the Besov space 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si2.gif"〉〈msubsup〉〈mrow〉〈mi〉B〈/mi〉〈/mrow〉〈mrow〉〈mi〉p〈/mi〉〈mo〉,〈/mo〉〈mi〉q〈/mi〉〈/mrow〉〈mrow〉〈mi〉s〈/mi〉〈/mrow〉〈/msubsup〉〈mrow〉〈mo〉(〈/mo〉〈msup〉〈mrow〉〈mi mathvariant="double-struck"〉R〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msup〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 that consists of block-radial functions. We prove that the asymptotic behaviour of the entropy numbers of compact embeddings 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈mo〉id〈/mo〉〈mo〉:〈/mo〉〈mspace width="2.22198pt"〉〈/mspace〉〈msub〉〈mrow〉〈mi〉R〈/mi〉〈/mrow〉〈mrow〉〈mi〉γ〈/mi〉〈/mrow〉〈/msub〉〈msubsup〉〈mrow〉〈mi〉B〈/mi〉〈/mrow〉〈mrow〉〈msub〉〈mrow〉〈mi〉p〈/mi〉〈/mrow〉〈mrow〉〈mn〉1〈/mn〉〈/mrow〉〈/msub〉〈mo〉,〈/mo〉〈msub〉〈mrow〉〈mi〉q〈/mi〉〈/mrow〉〈mrow〉〈mn〉1〈/mn〉〈/mrow〉〈/msub〉〈/mrow〉〈mrow〉〈msub〉〈mrow〉〈mi〉s〈/mi〉〈/mrow〉〈mrow〉〈mn〉1〈/mn〉〈/mrow〉〈/msub〉〈/mrow〉〈/msubsup〉〈mrow〉〈mo〉(〈/mo〉〈msup〉〈mrow〉〈mi mathvariant="double-struck"〉R〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msup〉〈mo〉)〈/mo〉〈/mrow〉〈mo〉→〈/mo〉〈msub〉〈mrow〉〈mi〉R〈/mi〉〈/mrow〉〈mrow〉〈mi〉γ〈/mi〉〈/mrow〉〈/msub〉〈msubsup〉〈mrow〉〈mi〉B〈/mi〉〈/mrow〉〈mrow〉〈msub〉〈mrow〉〈mi〉p〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/msub〉〈mo〉,〈/mo〉〈msub〉〈mrow〉〈mi〉q〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/msub〉〈/mrow〉〈mrow〉〈msub〉〈mrow〉〈mi〉s〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/msub〉〈/mrow〉〈/msubsup〉〈mrow〉〈mo〉(〈/mo〉〈msup〉〈mrow〉〈mi mathvariant="double-struck"〉R〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msup〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 depends on the number of blocks of the lowest dimension, the parameters 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si4.gif"〉〈msub〉〈mrow〉〈mi〉p〈/mi〉〈/mrow〉〈mrow〉〈mn〉1〈/mn〉〈/mrow〉〈/msub〉〈/math〉 and 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si5.gif"〉〈msub〉〈mrow〉〈mi〉p〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/msub〉〈/math〉, but is independent of the smoothness parameters 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si6.gif"〉〈msub〉〈mrow〉〈mi〉s〈/mi〉〈/mrow〉〈mrow〉〈mn〉1〈/mn〉〈/mrow〉〈/msub〉〈/math〉, 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si7.gif"〉〈msub〉〈mrow〉〈mi〉s〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/msub〉〈/math〉. We apply the asymptotic behaviour to estimation of powers of a negative spectra of Schrödinger type operators with block-radial potentials. This part essentially relies on the Birman–Schwinger principle.〈/p〉〈/div〉

Description: 〈p〉Publication date: Available online 5 November 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity〈/p〉 〈p〉Author(s): A.G. Werschulz, H. Woźniakowski〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉We study multivariate approximation for complex-valued functions defined over the 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈mi〉d〈/mi〉〈/math〉-dimensional torus, these functions belonging to weighted standard Sobolev spaces of smoothness〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si2.gif"〉〈mi〉r〈/mi〉〈/math〉. Algorithms are allowed to use finitely many arbitrary continuous linear functionals, which may be chosen adaptively. The error of an algorithm is measured by the 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈msub〉〈mrow〉〈mi〉L〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/msub〉〈/math〉norm, in the worst case setting. No matter how we choose positive weights, we prove that multivariate approximation cannot be quasi-polynomially tractable, meaning that the minimal number of continuous linear functionals needed to find an 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si4.gif"〉〈mi〉ε〈/mi〉〈/math〉-approximation in the 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈mi〉d〈/mi〉〈/math〉-variate case grows faster than any polynomial in〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si6.gif"〉〈msup〉〈mrow〉〈mi〉ε〈/mi〉〈/mrow〉〈mrow〉〈mo〉−〈/mo〉〈mo〉ln〈/mo〉〈mspace width="0.16667em"〉〈/mspace〉〈mi〉d〈/mi〉〈/mrow〉〈/msup〉〈/math〉. We also study 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si7.gif"〉〈mrow〉〈mo〉(〈/mo〉〈mi〉s〈/mi〉〈mo〉,〈/mo〉〈mi〉t〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉-weak tractability for positive 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si8.gif"〉〈mi〉s〈/mi〉〈/math〉 and 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si9.gif"〉〈mi〉t〈/mi〉〈/math〉, meaning that the minimal number of continuous linear functionals is 〈em〉not〈/em〉 exponential in 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si10.gif"〉〈msup〉〈mrow〉〈mi〉ε〈/mi〉〈/mrow〉〈mrow〉〈mo〉−〈/mo〉〈mi〉t〈/mi〉〈/mrow〉〈/msup〉〈/math〉 and〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si11.gif"〉〈msup〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈mrow〉〈mspace width="0.16667em"〉〈/mspace〉〈mi〉s〈/mi〉〈/mrow〉〈/msup〉〈/math〉. We restrict our attention to product weights, defined as products of powers of weightlets〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si12.gif"〉〈msub〉〈mrow〉〈mi〉γ〈/mi〉〈/mrow〉〈mrow〉〈mi〉j〈/mi〉〈/mrow〉〈/msub〉〈/math〉. We obtain conditions on the weightlets that are necessary and sufficient for our problem to be 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si7.gif"〉〈mrow〉〈mo〉(〈/mo〉〈mi〉s〈/mi〉〈mo〉,〈/mo〉〈mi〉t〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉-weakly tractable. In particular, if 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si14.gif"〉〈mi〉r〈/mi〉〈mi〉s〈/mi〉〈mo〉〈〈/mo〉〈mn〉2〈/mn〉〈/math〉 and 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si15.gif"〉〈mi〉t〈/mi〉〈mo〉≤〈/mo〉〈mn〉1〈/mn〉〈/math〉, then our problem is 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si7.gif"〉〈mrow〉〈mo〉(〈/mo〉〈mi〉s〈/mi〉〈mo〉,〈/mo〉〈mi〉t〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉-weakly tractable iff 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si17.gif"〉〈msub〉〈mrow〉〈mi〉γ〈/mi〉〈/mrow〉〈mrow〉〈mi〉j〈/mi〉〈/mrow〉〈/msub〉〈mo〉=〈/mo〉〈mi〉o〈/mi〉〈mrow〉〈mo〉(〈/mo〉〈msup〉〈mrow〉〈mi〉j〈/mi〉〈/mrow〉〈mrow〉〈mo〉−〈/mo〉〈mrow〉〈mo〉(〈/mo〉〈mn〉2〈/mn〉〈mo〉−〈/mo〉〈mi〉r〈/mi〉〈mi〉s〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈mo〉∕〈/mo〉〈mrow〉〈mo〉(〈/mo〉〈mi〉r〈/mi〉〈mi〉s〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/mrow〉〈/msup〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 as 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si18.gif"〉〈mi〉j〈/mi〉〈mo〉→〈/mo〉〈mi〉∞〈/mi〉〈/math〉.〈/p〉〈/div〉

Description: 〈p〉Publication date: February 2019〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 50〈/p〉 〈p〉Author(s): 〈/p〉

Description: 〈p〉Publication date: February 2019〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 50〈/p〉 〈p〉Author(s): 〈/p〉

Description: 〈p〉Publication date: February 2019〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 50〈/p〉 〈p〉Author(s): 〈/p〉

Description: 〈p〉Publication date: Available online 28 November 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity〈/p〉 〈p〉Author(s): Frank Aurzada, Mikhail Lifshits〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉We study the amount of information that is contained in “random pictures”, by which we mean the sample sets of a Boolean model. To quantify the notion “amount of information”, two closely connected questions are investigated: on the one hand, we study the probability that a large number of balls is needed for a full reconstruction of a Boolean model sample set. On the other hand, we study the quantization error of the Boolean model w.r.t. the Hausdorff distance as a distortion measure.〈/p〉〈/div〉

Description: 〈p〉Publication date: Available online 20 November 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity〈/p〉 〈p〉Author(s): Peter J. Grabner, Tetiana A. Stepanyuk〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉In this paper we study the worst-case error of numerical integration on the unit sphere 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈msup〉〈mrow〉〈mi mathvariant="double-struck"〉S〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msup〉〈mo〉⊂〈/mo〉〈msup〉〈mrow〉〈mi mathvariant="double-struck"〉R〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈mo〉+〈/mo〉〈mn〉1〈/mn〉〈/mrow〉〈/msup〉〈/math〉, 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si2.gif"〉〈mi〉d〈/mi〉〈mo〉≥〈/mo〉〈mn〉2〈/mn〉〈/math〉, for certain spaces of continuous functions on 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈msup〉〈mrow〉〈mi mathvariant="double-struck"〉S〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msup〉〈/math〉. For the classical Sobolev spaces 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si4.gif"〉〈msup〉〈mrow〉〈mi mathvariant="double-struck"〉H〈/mi〉〈/mrow〉〈mrow〉〈mi〉s〈/mi〉〈/mrow〉〈/msup〉〈mrow〉〈mo〉(〈/mo〉〈msup〉〈mrow〉〈mi mathvariant="double-struck"〉S〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msup〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 (〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si5.gif"〉〈mi〉s〈/mi〉〈mo〉〉〈/mo〉〈mfrac〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/mfrac〉〈/math〉) upper and lower bounds for the worst case integration error have been obtained in Brauchart and Hesse (2007), Hesse (2006) and Hesse and Sloan (2005,2006). We investigate the behaviour for 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si6.gif"〉〈mi〉s〈/mi〉〈mo〉→〈/mo〉〈msup〉〈mrow〉〈mfrac〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/mfrac〉〈/mrow〉〈mrow〉〈mo〉+〈/mo〉〈/mrow〉〈/msup〉〈/math〉 by introducing spaces 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si7.gif"〉〈msup〉〈mrow〉〈mi mathvariant="double-struck"〉H〈/mi〉〈/mrow〉〈mrow〉〈mfrac〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/mfrac〉〈mo〉,〈/mo〉〈mi〉γ〈/mi〉〈/mrow〉〈/msup〉〈mrow〉〈mo〉(〈/mo〉〈msup〉〈mrow〉〈mi mathvariant="double-struck"〉S〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msup〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉, 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si8.gif"〉〈mi〉γ〈/mi〉〈mo〉〉〈/mo〉〈mfrac〉〈mrow〉〈mn〉1〈/mn〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/mfrac〉〈/math〉, with an extra logarithmic weight. For these spaces we obtain similar upper and lower bounds for the worst case integration error.〈/p〉〈/div〉

Description: 〈p〉Publication date: February 2019〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 50〈/p〉 〈p〉Author(s): Sotirios Sabanis, Ying Zhang〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉A conjecture appears in Kumar and Sabanis (2016), in the form of a remark, where it is stated that it is possible to construct, in a specified way, any high order explicit numerical schemes to approximate the solutions of SDEs with superlinear coefficients. We answer this conjecture to the positive for the case of order 1.5 approximations and show that the suggested methodology works. Moreover, we explore the case of having Hölder continuous derivatives for the diffusion coefficients.〈/p〉〈/div〉

Description: 〈p〉Publication date: December 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 49〈/p〉 〈p〉Author(s): 〈/p〉

Description: 〈p〉Publication date: Available online 3 May 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity〈/p〉 〈p〉Author(s): A.A. Khartov, M. Zani〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉We study approximation properties of centred additive random fields 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈msub〉〈mrow〉〈mi〉Y〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msub〉〈/math〉, 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si2.gif"〉〈mi〉d〈/mi〉〈mo〉∈〈/mo〉〈mi mathvariant="double-struck"〉N〈/mi〉〈/math〉. The average case approximation complexity 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈msup〉〈mrow〉〈mi〉n〈/mi〉〈/mrow〉〈mrow〉〈msub〉〈mrow〉〈mi〉Y〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msub〉〈/mrow〉〈/msup〉〈mrow〉〈mo〉(〈/mo〉〈mi〉ε〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 is defined as the minimal number of evaluations of arbitrary linear functionals needed to approximate 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈msub〉〈mrow〉〈mi〉Y〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msub〉〈/math〉, with relative 2-average error not exceeding a given threshold 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si5.gif"〉〈mi〉ε〈/mi〉〈mo〉∈〈/mo〉〈mrow〉〈mo〉(〈/mo〉〈mn〉0〈/mn〉〈mo〉,〈/mo〉〈mn〉1〈/mn〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉. We investigate the growth of 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈msup〉〈mrow〉〈mi〉n〈/mi〉〈/mrow〉〈mrow〉〈msub〉〈mrow〉〈mi〉Y〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msub〉〈/mrow〉〈/msup〉〈mrow〉〈mo〉(〈/mo〉〈mi〉ε〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 for arbitrary fixed 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si5.gif"〉〈mi〉ε〈/mi〉〈mo〉∈〈/mo〉〈mrow〉〈mo〉(〈/mo〉〈mn〉0〈/mn〉〈mo〉,〈/mo〉〈mn〉1〈/mn〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉 and 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si8.gif"〉〈mi〉d〈/mi〉〈mo〉→〈/mo〉〈mi〉∞〈/mi〉〈/math〉. Under natural assumptions we obtain general results concerning asymptotics of 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈msup〉〈mrow〉〈mi〉n〈/mi〉〈/mrow〉〈mrow〉〈msub〉〈mrow〉〈mi〉Y〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msub〉〈/mrow〉〈/msup〉〈mrow〉〈mo〉(〈/mo〉〈mi〉ε〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉. We apply our results to additive random fields with marginal random processes corresponding to the Korobov kernels.〈/p〉〈/div〉

Description: 〈p〉Publication date: February 2019〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 50〈/p〉 〈p〉Author(s): Aicke Hinrichs, Joscha Prochno, Mario Ullrich〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉We prove the curse of dimensionality in the worst case setting for multivariate numerical integration for various classes of smooth functions. We prove the results when the domains are isotropic convex bodies with small diameter satisfying a universal 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈msub〉〈mrow〉〈mi〉ψ〈/mi〉〈/mrow〉〈mrow〉〈mn〉2〈/mn〉〈/mrow〉〈/msub〉〈/math〉-estimate. In particular, we obtain the result for the important class of volume-normalized 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si2.gif"〉〈msubsup〉〈mrow〉〈mi〉ℓ〈/mi〉〈/mrow〉〈mrow〉〈mi〉p〈/mi〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈/msubsup〉〈/math〉-balls in the complete regime 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈mn〉2〈/mn〉〈mo〉≤〈/mo〉〈mi〉p〈/mi〉〈mo〉≤〈/mo〉〈mi〉∞〈/mi〉〈/math〉. This extends a result in a work of Hinrichs et al. (2014) to the whole range 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈mn〉2〈/mn〉〈mo〉≤〈/mo〉〈mi〉p〈/mi〉〈mo〉≤〈/mo〉〈mi〉∞〈/mi〉〈/math〉, and additionally provides a unified approach. The key ingredient in the proof is a deep result from the theory of Asymptotic Geometric Analysis, the thin-shell volume concentration estimate due to O. Guédon and E. Milman. The connection of Asymptotic Geometric Analysis and Information-based Complexity revealed in this work seems promising and is of independent interest.〈/p〉〈/div〉

Description: 〈p〉Publication date: February 2019〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 50〈/p〉 〈p〉Author(s): David Krieg〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉We consider functions on the 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si2.gif"〉〈mi〉d〈/mi〉〈/math〉-dimensional unit cube whose partial derivatives up to order 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈mi〉r〈/mi〉〈/math〉 are bounded by one. It is known that the minimal number of function values that is needed to approximate the integral of such functions up to the error 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si4.gif"〉〈mi〉ε〈/mi〉〈/math〉 is of order 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si5.gif"〉〈msup〉〈mrow〉〈mrow〉〈mo〉(〈/mo〉〈mi〉d〈/mi〉〈mo〉∕〈/mo〉〈mi〉ε〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈mo〉∕〈/mo〉〈mi〉r〈/mi〉〈/mrow〉〈/msup〉〈/math〉. Among other things, we show that the minimal number of function values that is needed to approximate such functions in the uniform norm is of order 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si6.gif"〉〈msup〉〈mrow〉〈mrow〉〈mo〉(〈/mo〉〈msup〉〈mrow〉〈mi〉d〈/mi〉〈/mrow〉〈mrow〉〈mi〉r〈/mi〉〈mo〉∕〈/mo〉〈mn〉2〈/mn〉〈/mrow〉〈/msup〉〈mo〉∕〈/mo〉〈mi〉ε〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/mrow〉〈mrow〉〈mi〉d〈/mi〉〈mo〉∕〈/mo〉〈mi〉r〈/mi〉〈/mrow〉〈/msup〉〈/math〉 whenever 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈mi〉r〈/mi〉〈/math〉 is even.〈/p〉〈/div〉

Description: 〈p〉Publication date: October 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 48〈/p〉 〈p〉Author(s): Joris van der Hoeven, Grégoire Lecerf〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉Modular composition is the problem to compute the composition of two univariate polynomials modulo a third one. For polynomials with coefficients in a finite field, Kedlaya and Umans proved in 2008 that the theoretical bit complexity for performing this task could be made arbitrarily close to linear. Unfortunately, beyond its major theoretical impact, this result has not led to practically faster implementations yet. In this article, we explore how polynomial factorization may help modular composition. Most of our algorithms assume that the modulus is fixed, which allows us to precompute factorizations of the modulus over suitable extension fields. This significant restriction with respect to Kedlaya and Umans’ algorithm is acceptable whenever we need to perform many compositions modulo the same modulus. For polynomials over a finite field, we show that compositions modulo a fixed modulus of composite degree are cheaper than general modular compositions. In some very favorable cases of fixed moduli of very smooth degree, we show that the complexity even becomes quasi-linear.〈/p〉〈/div〉

Description: 〈p〉Publication date: Available online 9 May 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity〈/p〉 〈p〉Author(s): Henryk Woźniakowski〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉 〈p〉This is a tutorial introducing basic concepts of Information-Based Complexity (IBC) with the emphasis on tractability of multivariate problems. IBC deals with the complexity of computing approximate solutions of continuous problems. No prior knowledge of IBC is required from the reader, however, some knowledge of basic concepts of functional analysis and measure theory will be very helpful.〈/p〉 〈p〉This text is based on tutorials delivered by the author during the workshop “IBC-Paris 2017: Information-Based Complexity, High-Dimensional Problems” in Paris, March 2017, and the mini-semester at the Erwin Schrödinger Institute “Information-Based Complexity and Tractability of Multivariate Problems” in Vienna, September–October 2017.〈/p〉 〈/div〉

Description: 〈p〉Publication date: December 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 49〈/p〉 〈p〉Author(s): Marek Karpinski, László Mérai, Igor E. Shparlinski〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉 〈p〉We consider the problem of identity testing and recovering (that is, interpolating) of a “hidden” monic polynomial 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈mi〉f〈/mi〉〈/math〉, given an oracle access to 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si2.gif"〉〈mi〉f〈/mi〉〈msup〉〈mrow〉〈mrow〉〈mo〉(〈/mo〉〈mi〉x〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/mrow〉〈mrow〉〈mi〉e〈/mi〉〈/mrow〉〈/msup〉〈/math〉 for 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si3.gif"〉〈mi〉x〈/mi〉〈mo〉∈〈/mo〉〈msub〉〈mrow〉〈mi mathvariant="double-struck"〉F〈/mi〉〈/mrow〉〈mrow〉〈mi〉q〈/mi〉〈/mrow〉〈/msub〉〈/math〉, where 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si4.gif"〉〈msub〉〈mrow〉〈mi mathvariant="double-struck"〉F〈/mi〉〈/mrow〉〈mrow〉〈mi〉q〈/mi〉〈/mrow〉〈/msub〉〈/math〉 is the finite field of 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si5.gif"〉〈mi〉q〈/mi〉〈/math〉 elements and queries with 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si6.gif"〉〈mi〉x〈/mi〉〈/math〉 from an extension field are not permitted.〈/p〉 〈p〉The naive interpolation algorithm needs 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si7.gif"〉〈mi〉d〈/mi〉〈mi〉e〈/mi〉〈mo〉+〈/mo〉〈mn〉1〈/mn〉〈/math〉 queries, where 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si8.gif"〉〈mi〉d〈/mi〉〈mo〉=〈/mo〉〈mo〉deg〈/mo〉〈mi〉f〈/mi〉〈/math〉 and thus requires 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si9.gif"〉〈mi〉d〈/mi〉〈mi〉e〈/mi〉〈mo〉〈〈/mo〉〈mi〉q〈/mi〉〈/math〉. For a prime 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si10.gif"〉〈mi〉q〈/mi〉〈mo〉=〈/mo〉〈mi〉p〈/mi〉〈/math〉, we design algorithms that are asymptotically better in certain cases, especially when 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si11.gif"〉〈mi〉d〈/mi〉〈/math〉 is large. These algorithms are based on some new results in the spirit of additive combinatorics. In particular, we give an upper bound on the number of values of a rational function of large degree, evaluated on a short sequence of consecutive integers, that belong to a small subgroup of 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si12.gif"〉〈msubsup〉〈mrow〉〈mi mathvariant="double-struck"〉F〈/mi〉〈/mrow〉〈mrow〉〈mi〉p〈/mi〉〈/mrow〉〈mrow〉〈mo〉∗〈/mo〉〈/mrow〉〈/msubsup〉〈/math〉.〈/p〉 〈/div〉

Description: 〈p〉Publication date: October 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 48〈/p〉 〈p〉Author(s): K.Yu. Osipenko〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉The paper is concerned with the recovery problem of derivatives at the origin from noisy information about functions defined on the semiaxis for the Sobolev class. The problem of S. B. Stechkin about approximation of derivatives by bounded linear functionals is also studied.〈/p〉〈/div〉

Description: 〈p〉Publication date: December 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 49〈/p〉 〈p〉Author(s): Jia Chen, Heping Wang, Jie Zhang〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉We study 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si2.gif"〉〈mi〉d〈/mi〉〈/math〉-variate problems in the average case setting with respect to a zero-mean Gaussian measure. The covariance kernel of this Gaussian measure is a product of univariate kernels and satisfies some special properties. We study 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si1.gif"〉〈mrow〉〈mo〉(〈/mo〉〈mi〉s〈/mi〉〈mo〉,〈/mo〉〈mi〉t〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉-weak tractability of this multivariate problem under the absolute or normalized error criterion, and obtain a necessary and sufficient condition for 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si4.gif"〉〈mi〉s〈/mi〉〈mo〉〉〈/mo〉〈mn〉0〈/mn〉〈/math〉 and 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="si5.gif"〉〈mi〉t〈/mi〉〈mo〉∈〈/mo〉〈mrow〉〈mo〉(〈/mo〉〈mn〉0〈/mn〉〈mo〉,〈/mo〉〈mn〉1〈/mn〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉. Our result can apply to the problems with covariance kernels corresponding to Euler and Wiener integrated processes, Korobov kernels, and analytic Korobov kernels.〈/p〉〈/div〉

Description: 〈p〉Publication date: October 2018〈/p〉 〈p〉〈b〉Source:〈/b〉 Journal of Complexity, Volume 48〈/p〉 〈p〉Author(s): Anna Breger, Martin Ehler, Manuel Gräf〈/p〉 〈h5〉Abstract〈/h5〉 〈div〉〈p〉Given a finite set of points on the Euclidean sphere, the worst case quadrature error for functions in Sobolev spaces has recently been shown to provide upper bounds on the covering radius of the point set. Moreover, sequences of Quasi-Monte Carlo (QMC) designs for Sobolev spaces on the sphere achieve asymptotically optimal covering radii. Here, we extend these results from sequences of QMC designs on the sphere to sequences of weighted QMC designs on compact smooth Riemannian manifolds. We also provide numerical experiments illustrating our findings for the Grassmannian manifold.〈/p〉〈/div〉