The power of adaption for approximating functions with singularities

Abstract

Consider approximating functions based on a finite number of their samples. We show that adaptive algorithms are much more powerful than nonadaptive ones when dealing with piecewise smooth functions. More specifically, let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper F Subscript r Superscript 1"> <mml:semantics> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>r</mml:mi> <mml:mn>1</mml:mn> </mml:msubsup> <mml:annotation encoding="application/x-tex">F_r^1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be the class of scalar functions <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f colon left-bracket 0 comma upper T right-bracket right-arrow double-struck upper R"> <mml:semantics> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>:</mml:mo> <mml:mo stretchy="false">[</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mi>T</mml:mi> <mml:mo stretchy="false">]</mml:mo> <mml:mo stretchy="false"> → </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">f:[0,T]\to \mathbb {R}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> whose derivatives of order up to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r"> <mml:semantics> <mml:mi>r</mml:mi> <mml:annotation encoding="application/x-tex">r</mml:annotation> </mml:semantics> </mml:math> </inline-formula> are continuous at any point except for one unknown <italic>singular</italic> point. We provide an adaptive algorithm <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper A Subscript n Superscript ad"> <mml:semantics> <mml:msubsup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext>ad</mml:mtext> </mml:mrow> </mml:msubsup> <mml:annotation encoding="application/x-tex">\mathcal {A}_n^\textrm {ad}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> that uses at most <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> samples of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f"> <mml:semantics> <mml:mi>f</mml:mi> <mml:annotation encoding="application/x-tex">f</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and whose <italic>worst case</italic> <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L Superscript p"> <mml:semantics> <mml:msup> <mml:mi>L</mml:mi> <mml:mi>p</mml:mi> </mml:msup> <mml:annotation encoding="application/x-tex">L^p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> error ( <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1 less-than-or-equal-to p greater-than normal infinity"> <mml:semantics> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo> ≤ </mml:mo> <mml:mi>p</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mi mathvariant="normal"> ∞ </mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">1\le p&gt;\infty</mml:annotation> </mml:semantics> </mml:math> </inline-formula> ) with respect to ‘reasonable’ function classes <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper F Subscript r Superscript 1 Baseline subset-of upper F Subscript r Superscript 1"> <mml:semantics> <mml:mrow> <mml:msubsup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow> <mml:mi>r</mml:mi> <mml:mn>1</mml:mn> </mml:msubsup> <mml:mo> ⊂ </mml:mo> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>r</mml:mi> <mml:mn>1</mml:mn> </mml:msubsup> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {F}_r^1\subset F_r^1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is proportional to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n Superscript negative r"> <mml:semantics> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo> − </mml:mo> <mml:mi>r</mml:mi> </mml:mrow> </mml:msup> <mml:annotation encoding="application/x-tex">n^{-r}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . On the other hand, the worst case error of any nonadaptive algorithm that uses <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> samples is at best proportional to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n Superscript negative 1 slash p"> <mml:semantics> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn>