Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sorry about this somewhat lengthy introduction to my question. I thought it might be useful to know what I'm trying to do.

I decided that I would like to have sequence of polynomials in $\mathbb{P}_n (x)$ defined in domain $x\in[0,1]$ which gradually learn a function. So, given an initial polynomial $P_{\alpha_0}(x)=\sum_{i=1}^n a_i x^{i-1}$ where $\alpha_0 = (a_1,\ldots,a_n) \in \mathbb{R}^n$, I would introduce a new point $(x_0,y_0) \in [0,1]\times\mathbb{R}$ and try to find all $\beta \in\mathbb{R}^n$ such that $$ P_{\alpha_0 + \beta}(x_0)=y_0 $$ If the solution space to that is $S$, then the next step would be to find optimal solution which somehow minimises the non-local difference. Define a norm which penalizes non-local difference: $$ {\lVert P_{\alpha} \rVert}_{(x_0)} = \int_0^1 {(x-x_0)}^2{(P_{\alpha}(x))^2} dx $$ The objective would be to find such $\beta \in S$ that it minimises $$ {\lVert P_{\alpha_0} -P_{\alpha_0+\beta}\rVert}_{(x_0)} $$ and then have for the next round $\alpha_1 = \alpha_0 + \beta$.

Looking at solutions for the standard basis $\beta_i=(0,\ldots,0,b_{i,i},0,\ldots,0)$ (i.e. all but the $i$:th element are zero) one finds easily that $$ P_{\alpha_0+\beta_i}(x_0)=y_0 $$ when $$ b_{i,i} = \frac{y_0 - P_{\alpha_0}(x_0)}{x_0^{i-1}} $$ Let's use $b_i = b_{i,i}$ for short.

The solution space $S$ is linear combination $\sum t_i \beta_i$ with the requirement that $\sum t_i = 1$.

Now, do you have any elegant ways to find the minimum for $$ {\lVert P_{\alpha_0} -P_{\alpha_0+\beta}\rVert}_{(x_0)} = \sum_{i,j}^n t_i t_j b_i b_j g_{x_0}(i,j) $$ where $$ g_{x_0}(i,j) = (\frac{1}{i+j+1} -\frac{2 x_0}{i+j} + \frac{x_0^2}{i+j-1}) $$ from the solution hyperplane $\sum t_i = 1$?

It's rather easy to find the equation for the null space of the partial differentials $$ \frac{d{\lVert P_{\alpha_0} -P_{\alpha_0+\beta}\rVert}_{(x_0)}}{d t_k} = \sum_i t_i b_i g_{x_0}(k,j) $$ This is a linear mapping of the form $M t = 0 $ where $M_{i,j} = b_i g_{x_0}(i,j)$. Testing numerically with some functions seems to indicate that $M$ is mostly of full rank and in those cases the solution would be $t=0$ which does not fulfill the requirement that $\sum t_i = 1$.

Adding this requirement to the mapping gives overdetermined equation $$ \left( \begin{matrix} M \\ 1 \end{matrix} \right) t = \left( \begin{matrix} 0 \\ 1 \end{matrix} \right) $$

share|improve this question
    
Hmm, does the question even make any sense or is the introduction too long? Or perhaps it is somewhat unclear. I don't need a direct answer. Any kind of indication where to look would be appreciated. –  etorri Jul 7 '11 at 12:58
add comment

1 Answer

So the problem I had was to find such $t\in S \subset \mathbb{R}^n$ that it minimises the function (1) $$ d(t,b,x_0)=\sum_{i,j=1}^n t_i t_j b_i b_j g_{ij}(x_0) $$ within the hyperplane $$ S = \{t:\sum_1^n t_i = 1\} $$ From the original integral form of the function it is easy to see that it is positive for all $t$ and from the sum form that it grows with $\lVert t \rVert$ .

I chose the rather elaborate way of substituting $t_n$ with $1-\sum_1^{n-1} t_i$ in (1) and trying to find the zero of the partial differentials of the difference. For simplicity, I also denote $g_{ij}(x_0)$ with just $g_{ij}$ and the reduced vector ${(t_i)}_{i=1}^{n-1}$ with $t^*$.

With the substitution the equation (1) can be (after several steps) written as $$ f(t^*)=\sum_{i,j=1}^{n-1} t_i^* t_j^* A_{ij} + \sum_{i=1}^{n-1} t_i^* b_n B_i + b_n^2 g_{nn} $$

where $A_{ij}=b_i b_j g_{ij} - 2 b_i b_n g_{in} + b_n^2 g_{nn}$ and $B_i = 2 b_i g_{in}-2b_n g_{nn}$.

The partial differentials (finally) have the form $$ \frac{d f}{d t_k^*} = (\sum_{i=1}^{n-1} t_i (A_{ik}+A_{ki})) + B_k $$ and from this finding the zeros of the differentials can be written in matrix form as $$ C t + B = 0 $$ where $C_{ij}=A_{ij}+A_{ji}$ is a symmetric matrix. Finding solution to this is rather easy.

Testing numerically the solution shows that $C$ is easily ill-conditioned and the whole idea perhaps rather useless. Nevertheless, watching the polynomials twist and wiggle as new points are added is very entertaining.

share|improve this answer
add comment

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.