Finding an Inner Product for Approximating Polynomials on a Set of Real Numbers

[Treadstone 71]

Let S be a finite set of real numbers. What is a natural inner product to define on the space of all functions f:S->R? I want to approximate an arbitrary function with a polynomial of a fixed degree (both of which are defined only on S), and I want to use projections to do it, but I have no inner product.

 

[matt grime]

Since S is a finite set, any function on it (to R) is (equivalent to) a polynomial (indeed infinitely many distinct such), you don't need to approximate it.

 

[Treadstone 71]

Let me just post the question completely, in case I said something wrong:

"Let $$S={x_1,...,x_N}$$ be a collection of real numbers, and let $$(y_1,...,y_N)$$ be a sequence of real numbers. Fix an integer $$k<N$$. In general, there need not be a polynomial $$p$$ of degree $$\leq k$$ such that $$p(x_j)=y_j$$ for $$j=1,...,N$$. The next best thing one might ask for is a polynomial $$p$$ of degree less than $$k$$ for which the quantity

$$(p(x_1)-y_1)^2+...+(p(x_N)-y_N)^2$$

is minimized. Describe an approach that would produce such a $$p$$."

I'm not sure how any function is equivalent to a polynomial.

 

[Treadstone 71]

I could proceed as follows:

Let $$P$$ be the space of polynomials of degree $$\leq k$$. Let $$p\in P$$. Define $$T:P\rightarrow \mathbb{R}^N$$ by $$T(p)=(p(x_1),...,p(x_N))$$ and then proceed to use the dot product on $$\mathbb{R}^N$$ and somehow minimize it?

 

[Hurkyl]

I'm not sure how any function is equivalent to a polynomial.

Not even f(x) := x² + 2x + 1?

and somehow minimize it?

You know techniques for minimizing functions in several variables. (what are the variables?) Why are you defining an inner product? It might be useful, but I get the feeling you simply want to use an inner product on this problem!

 

[Treadstone 71]

Not even f(x) := x² + 2x + 1?

What about f(x)=ln(x)?

You know techniques for minimizing functions in several variables. (what are the variables?) Why are you defining an inner product? It might be useful, but I get the feeling you simply want to use an inner product on this problem!

I must use an inner product to solve this problem. I want to use the fact that the orthogonal projection of a vector in the space of polynomials of degree less than k to the space of finitely-supported real-valued functions is the best approximation. But I don't know the inner product to use.

 

[matt grime]

Firstly, you did not limit the degree of the approximation required.

It is trivial that given a finite set of points and a function on them to R, that it might be realized by *some* polynomial, and equally trivial that it cannot in general be done by polys less than some fixed degree (less than the number of points). But none of that you bothered to state in the question.

Given points (x_1,..x_n) I can trivially produce some polynomial f such that f(x_i)=log(x_i) as long as deg(f) is allowed to be arbitrary. If you don't see that you can get a line passing through any two points in the plane (quadratic through any 3 etc), then you missed out on something somewhere.Of course, less than n and it is impossible (generically), but you did not state that at the start.

You're simply doing some minimization problem in your case, albeit probably a hard one.

 

[Hurkyl]

It's a quadratic minimization problem -- they're fairly straightforward to solve through a number of techniques. I would have suggested to just take the gradient of the darned thing and set it equal to zero, or maybe to try and set it up as a least-squares problem so he could use the general technique for that.

But he says he must use an inner product. Hrm. The expression he wants to minimize looks like it's the dot product of something with itself, but that doesn't seem to be a useful observation, although it might help a little with bookkeeping.

 

[Treadstone 71]

It's a mess, involves lots of transformations and solving a system of n equations, but I did it. Although my solution is probably not optimal.

Can someone tell me if the rough sketch of it looks ok:

P={polynomials of degree k or less}
T:P->R^N defined by T(p)=(P(x_1),...,p(x_n))
X={T(p): p in P}

X is a k+1 dimensional subspace of R^N, so (T(1),...,T(t^k)) is a basis of X. Use Gram-Schmidt procedures to construct an orthonormal basis and use it to project y=(y_1,..,y_n), and find (b_1,...,b_N)=Y. Solve a1T(1)+...+anT(t^k)=Y and find the coefficients for the polynomial.