Skip to main content
Added citation for linked paper, added "splines" tag
Source Link
gmvh
  • 3.1k
  • 6
  • 27
  • 46

Let $f \in \mathrm{Lip}^{L,\alpha}[a,b]$, and let $f_{h} \in C^{L}$ be a spline which interpolates $f$ at $a + ih$. Then standard theorems (standard theoremsDaubechies & Lagarias, SIAM J. Math. Anal. 22 (1991) 1388-1410) show that \begin{align*} \left\| f - f_{h} \right\|_{\infty} \le Ch^{(\alpha+L)} \end{align*} I'm interested in if there are any theorems which bound the error from below, i.e., does there exist $C_1 > 0$ such that \begin{align*} \left\| f - f_{h} \right\|_{\infty} \ge C_1h^{(\alpha+L)}? \end{align*} Obviously, if $f$ is a polynomial of degree $L$, no such constant exists, so we first must assume $f \in \mathrm{Lip}^{L,\alpha}[a,b]$, but not in $f \in \mathrm{Lip}^{L,\alpha + \epsilon}[a,b]$. Second, the set of points at which $f$ is not infinitely differentiable must be infinite, or else we can just divide $[a,b]$ into subintervals where everything converges faster.

Essentially, I want to know if the Hölder regularity of $f$ somehow fundamentally limits how fast we can compute approximations to $f$. (For example, the same sort of convergence rates hold for trigonometric polynomial approximations as well; this is Jackson's theorem.)

Let $f \in \mathrm{Lip}^{L,\alpha}[a,b]$, and let $f_{h} \in C^{L}$ be a spline which interpolates $f$ at $a + ih$. Then standard theorems show that \begin{align*} \left\| f - f_{h} \right\|_{\infty} \le Ch^{(\alpha+L)} \end{align*} I'm interested in if there are any theorems which bound the error from below, i.e., does there exist $C_1 > 0$ such that \begin{align*} \left\| f - f_{h} \right\|_{\infty} \ge C_1h^{(\alpha+L)}? \end{align*} Obviously, if $f$ is a polynomial of degree $L$, no such constant exists, so we first must assume $f \in \mathrm{Lip}^{L,\alpha}[a,b]$, but not in $f \in \mathrm{Lip}^{L,\alpha + \epsilon}[a,b]$. Second, the set of points at which $f$ is not infinitely differentiable must be infinite, or else we can just divide $[a,b]$ into subintervals where everything converges faster.

Essentially, I want to know if the Hölder regularity of $f$ somehow fundamentally limits how fast we can compute approximations to $f$. (For example, the same sort of convergence rates hold for trigonometric polynomial approximations as well; this is Jackson's theorem.)

Let $f \in \mathrm{Lip}^{L,\alpha}[a,b]$, and let $f_{h} \in C^{L}$ be a spline which interpolates $f$ at $a + ih$. Then standard theorems (Daubechies & Lagarias, SIAM J. Math. Anal. 22 (1991) 1388-1410) show that \begin{align*} \left\| f - f_{h} \right\|_{\infty} \le Ch^{(\alpha+L)} \end{align*} I'm interested in if there are any theorems which bound the error from below, i.e., does there exist $C_1 > 0$ such that \begin{align*} \left\| f - f_{h} \right\|_{\infty} \ge C_1h^{(\alpha+L)}? \end{align*} Obviously, if $f$ is a polynomial of degree $L$, no such constant exists, so we first must assume $f \in \mathrm{Lip}^{L,\alpha}[a,b]$, but not in $f \in \mathrm{Lip}^{L,\alpha + \epsilon}[a,b]$. Second, the set of points at which $f$ is not infinitely differentiable must be infinite, or else we can just divide $[a,b]$ into subintervals where everything converges faster.

Essentially, I want to know if the Hölder regularity of $f$ somehow fundamentally limits how fast we can compute approximations to $f$. (For example, the same sort of convergence rates hold for trigonometric polynomial approximations as well; this is Jackson's theorem.)

Notice removed Authoritative reference needed by CommunityBot
Bounty Ended with no winning answer by CommunityBot
Notice added Authoritative reference needed by user14717
Bounty Started worth 50 reputation by user14717

Hardness results for approximating HolderHölder continuous functions

Let $f \in \mathrm{Lip}^{L,\alpha}[a,b]$, and let $f_{h} \in C^{L}$ be a spline which interpolates $f$ at $a + ih$. Then standard theorems show that \begin{align*} \left\| f - f_{h} \right\|_{\infty} \le Ch^{(\alpha+L)} \end{align*} I'm interested in if there are any theorems which bound the error from below, i.e., does there exist $C_1 > 0$ such that \begin{align*} \left\| f - f_{h} \right\|_{\infty} \ge C_1h^{(\alpha+L)}? \end{align*} Obviously, if $f$ is a polynomial of degree $L$, no such constant exists, so we first must assume $f \in \mathrm{Lip}^{L,\alpha}[a,b]$, but not in $f \in \mathrm{Lip}^{L,\alpha + \epsilon}[a,b]$. Second, the set of points at which $f$ is not infinitely differentiable must be infinite, or else we can just divide $[a,b]$ into subintervals where everything converges faster.

Essentially, I want to know if the HolderHölder regularity of $f$ somehow fundamentally limits how fast we can compute approximations to $f$. (For example, the same sort of convergence rates hold for trigonometric polynomial approximations as well; this is Jackson's theorem.)

Hardness results for approximating Holder continuous functions

Let $f \in \mathrm{Lip}^{L,\alpha}[a,b]$, and let $f_{h} \in C^{L}$ be a spline which interpolates $f$ at $a + ih$. Then standard theorems show that \begin{align*} \left\| f - f_{h} \right\|_{\infty} \le Ch^{(\alpha+L)} \end{align*} I'm interested in if there are any theorems which bound the error from below, i.e., does there exist $C_1 > 0$ such that \begin{align*} \left\| f - f_{h} \right\|_{\infty} \ge C_1h^{(\alpha+L)}? \end{align*} Obviously, if $f$ is a polynomial of degree $L$, no such constant exists, so we first must assume $f \in \mathrm{Lip}^{L,\alpha}[a,b]$, but not in $f \in \mathrm{Lip}^{L,\alpha + \epsilon}[a,b]$. Second, the set of points at which $f$ is not infinitely differentiable must be infinite, or else we can just divide $[a,b]$ into subintervals where everything converges faster.

Essentially, I want to know if the Holder regularity of $f$ somehow fundamentally limits how fast we can compute approximations to $f$. (For example, the same sort of convergence rates hold for trigonometric polynomial approximations as well; this is Jackson's theorem.)

Hardness results for approximating Hölder continuous functions

Let $f \in \mathrm{Lip}^{L,\alpha}[a,b]$, and let $f_{h} \in C^{L}$ be a spline which interpolates $f$ at $a + ih$. Then standard theorems show that \begin{align*} \left\| f - f_{h} \right\|_{\infty} \le Ch^{(\alpha+L)} \end{align*} I'm interested in if there are any theorems which bound the error from below, i.e., does there exist $C_1 > 0$ such that \begin{align*} \left\| f - f_{h} \right\|_{\infty} \ge C_1h^{(\alpha+L)}? \end{align*} Obviously, if $f$ is a polynomial of degree $L$, no such constant exists, so we first must assume $f \in \mathrm{Lip}^{L,\alpha}[a,b]$, but not in $f \in \mathrm{Lip}^{L,\alpha + \epsilon}[a,b]$. Second, the set of points at which $f$ is not infinitely differentiable must be infinite, or else we can just divide $[a,b]$ into subintervals where everything converges faster.

Essentially, I want to know if the Hölder regularity of $f$ somehow fundamentally limits how fast we can compute approximations to $f$. (For example, the same sort of convergence rates hold for trigonometric polynomial approximations as well; this is Jackson's theorem.)

Source Link
user14717
  • 221
  • 2
  • 6

Hardness results for approximating Holder continuous functions

Let $f \in \mathrm{Lip}^{L,\alpha}[a,b]$, and let $f_{h} \in C^{L}$ be a spline which interpolates $f$ at $a + ih$. Then standard theorems show that \begin{align*} \left\| f - f_{h} \right\|_{\infty} \le Ch^{(\alpha+L)} \end{align*} I'm interested in if there are any theorems which bound the error from below, i.e., does there exist $C_1 > 0$ such that \begin{align*} \left\| f - f_{h} \right\|_{\infty} \ge C_1h^{(\alpha+L)}? \end{align*} Obviously, if $f$ is a polynomial of degree $L$, no such constant exists, so we first must assume $f \in \mathrm{Lip}^{L,\alpha}[a,b]$, but not in $f \in \mathrm{Lip}^{L,\alpha + \epsilon}[a,b]$. Second, the set of points at which $f$ is not infinitely differentiable must be infinite, or else we can just divide $[a,b]$ into subintervals where everything converges faster.

Essentially, I want to know if the Holder regularity of $f$ somehow fundamentally limits how fast we can compute approximations to $f$. (For example, the same sort of convergence rates hold for trigonometric polynomial approximations as well; this is Jackson's theorem.)