Discontinuous information in the worst case and randomized settings

被引：8

作者：

Hinrichs, Aicke ^{[1
]}

Novak, Erich ^{[1
]}

Wozniakowski, Henryk ^{[2
,3
]}

机构：

[1] Univ Jena, Math Inst, D-07737 Jena, Germany

[2] Columbia Univ, Dept Comp Sci, New York, NY 10027 USA

[3] Univ Warsaw, Inst Appl Math, PL-02097 Warsaw, Poland

来源：

MATHEMATISCHE NACHRICHTEN | 2013年 / 286卷 / 07期

基金：

美国国家科学基金会;

关键词：

Discontinuous information; randomized algorithms; information-based complexity; FUNCTION-SPACES; NUMBERS;

D O I：

10.1002/mana.201100128

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We believe that discontinuous linear information is never more powerful than continuous linear information for approximating continuous operators. We prove such a result in the worst case setting. In the randomized setting we consider compact linear operators defined between Hilbert spaces. In this case, the use of discontinuous linear information in the randomized setting cannot be much more powerful than continuous linear information in the worst case setting. These results can be applied when function evaluations are used even if function values are defined only almost everywhere. (C) 2012 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim

引用

页码：679 / 690

页数：12

共 20 条

[1] [Anonymous], 2010, Standard Information for Functionals
[2] [Anonymous], 2010, Bases in Function Spaces, Sampling, Discrepancy, Numerical Integration
[3] BOLLOBAS BELA., 1990, LINEAR ANAL
[4] Carlan B., 1990, ENTROPY COMPACTNESS
[5] ON THE RELATION BETWEEN LINEAR N-WIDTHS AND APPROXIMATION NUMBERS
HEINRICH, S
[J]. JOURNAL OF APPROXIMATION THEORY, 1989, 58 (03) : 315 - 333
[6] Heinrich S., 2010, MONTE CARLO QUASIMON
[7] Heinrich S., UNTRASTABILITY UNPUB
[8] Heinrich S., 1992, J COMPLEXITY, V8, P277
[9] Randomized approximation of Sobolev embeddings
Heinrich, Stefan
[J]. MONTE CARLO AND QUASI-MONTE CARLO METHODS 2006, 2008, : 445 - 459
[10] Randomized approximation of Sobolev embeddings, III
Heinrich, Stefan
[J]. JOURNAL OF COMPLEXITY, 2009, 25 (05) : 473 - 507

← 1 2 →