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<n$ 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$.

  • $\begingroup$ 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$. $\endgroup$ – Ian Aug 2 at 3:11
  • $\begingroup$ 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? $\endgroup$ – mzp Aug 2 at 13:19
  • $\begingroup$ 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. $\endgroup$ – Ian Aug 2 at 13:28
  • $\begingroup$ 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. $\endgroup$ – Ian Aug 2 at 13:32
  • $\begingroup$ I see, then $D\leq ||I_n-P(P^T P)^{-1}P^T||_p$ with equality if $p=2$. Right? $\endgroup$ – mzp Aug 2 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.