# Approximating a Discrete Function with a Polynomial

Consider a discrete function $$f : \{x_1,\dots,x_n\} \to [a,b]$$ that, for some $$\omega>0$$, satisfies

$$\max_i |f_i-f_{i-1}| \le \omega. \tag1$$

Let $$q$$ be the polynomial of order $$m that, for some $$p$$, approximates the function $$f$$ by minimizing

$$D_p\equiv||f-q||_p = \left(\sum_{i=1}^n|f(i) - q(i)|^p\right)^{\frac{1}{p}}.$$

Is there a sharp or a "relatively tight" upper bound to $$D_p$$ that does not depend on the values of $$f$$?

I thought that this would be easy to find online but all approximation results I could find (like Jackson's inequality) are for continuous functions. One would think that tighter bounds could be established for discrete functions, but I haven't been able to find one. Any suggestion in this direction would be very welcome.

Edit based on the comments by @Ian

Let $$X$$ be a matrix with elements $$X_{ij}=x_i^j$$, for $$i=\{1,\dots,n\}$$ and $$j=\{0,\dots,m\}$$, and let $$y=[f_1,\dots,f_n]^T$$. Then, for $$p=2$$ it follows from the least squares formula that $$D_2=||(I_n-X(X^T X)^{-1}X^T)y||_2.$$ It would also follow that, for all $$p$$ $$D_p\leq ||(I_n-X(X^T X)^{-1}X^T)y||_p.$$ So, one way to get a relatively tight bound (I haven't figure out how to formalize this) would be to use condition $$(1)$$ to bound $$D_2$$.

• Say the domain is $\{ x_0,x_1,...,x_{n-1} \}$ $P_{ij}=x_i^j$ for $i=0,1,...n-1,j=0,1,...,m$, then you want the operator $p$ norm of $I_n-P(P^T P)^{-1} P^T$. For $p=1$ or $p=\infty$ this can be computed directly, for $p=2$ it can be obtained from the SVD of $P$. – Ian Aug 2 at 3:11
• Thank you for this. Is the norm of this projection matrix equal to $D$ then? Does this mean that the solution to the minimization problem is independent of the $p$ norm being used? Would you mind elaborating a bit in an answer? – mzp Aug 2 at 13:19
• It still depends on $p$. My point here is that you should probably not expect $D$ to have a nice expression. Even an error bound will have some substance to it; try writing out the formula for $m=1$ to see some of this subtlety. – Ian Aug 2 at 13:28
• Also my mistake, my original statement actually only applies for $p=2$, where you can use least squares. Otherwise the minimization itself is a nonlinear problem. – Ian Aug 2 at 13:32
• I see, then $D\leq ||I_n-P(P^T P)^{-1}P^T||_p$ with equality if $p=2$. Right? – mzp Aug 2 at 13:37