Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.

For the more mathematically minded,

we have $x \in \mathbb{R}^2$ and the function $h(x)$ defined as:

$h(x)=\alpha_1x_1^2+\alpha_2x_2^2+\alpha_3x_1+\alpha_4x_2+\alpha_5x_1x_2+\alpha_6$

and the vector of alpha's is known and further guaranteed to be such that $h(x)$ is a general elliptic paraboloid (i.e. a convex function).

Now, define $g(x)=(h(x))^+$ where $(z)^+$ is the positive part of $z\in\mathbb{R}$.

The questions follows:

  1. Is there a way to globally approximate $g(x)$ by a polynomial ? If so what it is?
  2. Can this approach (the answer to the previous sub-question) be extended to $x\in\mathbb{R}^p$ with $p$ moderatly large ?
  3. Would the problem be any easier if we were to assume $\alpha_5=0$ ?

Following Whuber's comment: is it possible to find a polynomial approximation to $g(x)$ that would be better than $h(x)$? in the event that many approximations solution for this problem exist, what are they ?

I can obviously solve $argmin.\int_{\mathbb{R}^2}(g(x)-\hat{g}(x))^2 dx$. I'm wondering if there are explicit, known solutions to this problem (i.e. polynomial series for example of which i know close to nothing).

share|improve this question
It would help immensely to clarify what you mean by "globally" and "approximate"! For example, h itself is a fine approximation to g according to many measures. If you require that g and its approximator be relatively close pointwise for all of R^2, then you're not going to get any better than that. – whuber Sep 9 '10 at 12:54
I may be missing something but I agree with @whuber. I do not see why you need an approximation g(x) when you have h(x)^+ and in what sense will any other function g(x) be better than h(x)^+? – user28 Sep 9 '10 at 16:36
In light of your clarification, are you asking for a polynomial approximation to the entire function g or to the data (x_i, g(x_i))? (The solutions to those questions are somewhat different...) – whuber Sep 9 '10 at 17:42
@ Sri. Indeed i do have h(x) (the alpha are known) and therefore h(x)^+. But h(x)^+ is not a polynome. For reason pertaining to computational issues and ease of derivation of some properties, i need to approximate this function by a polynomial. Since h(x) [and therefore h(x)^+] are convex functions, i though, maybe, there should be a way to approximate them by some polynome, over the entire domain (R^2). – user603 Sep 9 '10 at 18:43
@ Whuber: Im really looking for an approximation to the entire function g(x_i). The criterion is such that we have somethin practical to work with (i.e. the criterion is essentially L2 distance between g and \hat{g}). See also my response to Sri's comment above. – user603 Sep 9 '10 at 18:45

2 Answers

up vote 5 down vote accepted

The $L^2$ distance between $g$ and a polynomial approximation will be finite if and only if the polynomial approximation behaves asymptotically like $g$, which means it behaves asymptotically like $h$, which implies it must equal $h$. Therefore $h$ is the unique $L^2$ approximator.

Thus:

(1) Yes; the global approximator to $g$ is $h$.

(2) Yes; the same reasoning holds for all finite $p$.

(3) No; the value of $\alpha_5$ makes no difference.

Follow-up question (i): No, you cannot do better than $h$.

Follow-up question (ii) [how many approximations]: Not applicable due to the answer to (i).

You can get a considerably better set of answers if you're willing to limit the domain of $g$ to a compact [measurable] subset.

share|improve this answer
1  
Fantastic. Although your contribution answers my problem, i would like to use it to ask the following question: assuming now that we only consider a compact $B\in\mathbb{R}^2$. What is not the non-trivial answer? – user603 Sep 9 '10 at 19:31
2  
@kwak: Least squares! The standard example of a compact subset is a finite set of points and the L^2 norm sums the squares of residuals. With measurable compact subsets you need to integrate the squares of residuals. There's also a classical L-infinity (sup norm) theory of approximating functions by polynomials (Weierstrass' Theorem) or even with sets of arbitrary real powers (Muntz-Szazs Theorem). Rudin's textbook on real and complex analysis has an accessible account (I'm looking at a 1974 printing). I believe these extend from R^1 to higher dimensions. – whuber Sep 9 '10 at 19:49
@kwak (continued): The L^2 theory constructs orthonormal sets of polynomial functions (such as Legendre Polynomials and Chebyshev Polynomials). You obtain the coefficients of good approximations simply by taking the inner product with the basis elements, exactly as in finite-dimensional linear algebra. Different bases have different approximation properties. Arbitrary (measurable) subsets B likely require variants of these systems adapted to their specific geometry. – whuber Sep 9 '10 at 19:51
Ok, thanks very much. In some odd way this solves my problem (limits what i can do). – user603 Sep 9 '10 at 19:53

Note that $h(x)$ itself is a polynomial in $x_1$ and $x_2$ and $g(x)$ is what I would call a truncated polynomial.

The region where $h(x)$ is negative, $g(x)$ will be zero. You can approximate this region where $h(x)$ is flat by a non-constant polynomial (non-constant because you also need to approximate the region where $h(x) > 0$) but this will always be a 'wiggly' approximation (at least for a finite number of terms in the approximating polynomial).

It's not clear to me what you want to achieve, $g(x)$ actually has a quite simple analytical form and maybe for your problem you just have to consider the two regions $h(x) < 0$ and $h(x) \ge 0$ separately.

share|improve this answer
This will get the ball rolling. $g(x)$ has indeed as simple analytical form, but not a polynomial one. It will make my problem simpler if i could re-express $g(x)$ as a (or even several) polynome(s), even very complicated one(s). Wiggly is okay, so long as i can make it more precise by adding more terms. – user603 Sep 9 '10 at 19:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.