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.

Given that $y(x,{\bf w}) = w_0 + w_1x + w_2x^2 + \ldots + w_mx^m = \sum_{j=0}^{m} w_jx^j$ and there exists an error function defined as $E({\bf w})=\frac{1}{2} \sum_{n=1}^{N} \{y(x_n, w)-t_n\}^2$ (where $t_n$ represents the target value). I'm having trouble making sense of a passage in my textbook. (Note: ${\bf w}$ represents a vector of the polynomial's coefficients.) I've listed the passage below:

We can solve the curve fitting problem by choosing the value of ${\bf w}$ for which $E({\bf w})$ is as small as possible. Because the error function is a quadratic function of the coefficients ${\bf w}$, its derivatives with respect to the coefficients will be linear in the elements of ${\bf w}$, and so the minimization of the error function has a unique solution, denoted by ${\bf w^*}$, which can be found in closed form.

How do we know that the minimal solution exists and is unique? What guarantees this? Any help understanding this would be appreciated.

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

Let's, as the cited passage suggest, look at the derivative of $E$. First we note that $y$ is linear in $w$, as $$ y(x,w+\mu w') = \sum_i (w_i +\mu w_i')x^i = \sum_i w_ix^i +\mu \sum_i w'_ix^i= y(x,w) + \mu y(x,w') $$ Now we have for $w, h \in \mathbb R^{m+1}$ that \begin{align*} E(w+ h) &= \frac 12\sum_{n=1}^N \bigl(y(x_n, w) + y(x_n, h) - t_n\bigr)^2\\ &= E(w) + \sum_{n=1}^N \bigl(y(x_n, w) - t_n)y(x_n, h) + \sum_{n=1}^N y(x_n, h)^2\\ &= E(w) + \sum_{n=1}^N \bigl(y(x_n, w) - t_n)\bigr)y(x_n, h) + o(h) \end{align*} so $E'(w)h = \sum_{n=1}^N \bigl(y(x_n, w) - t_n)\bigr)y(x_n, h)$. The second derivative is $$ E''(w)[h,k] = \sum_{n=1}^N y(x_n, k)y(x_n, h) $$ Now for $h \in \mathbb R^{m} -\{0\}$ $$ E''(w)[h, h] = \sum_{n=1}^N y(x_n, h)^2 $$ and this is positive if $N \ge m+1$ and all $x_i$ are different (as a polynomial of degree $m$ cannot have $N \ge m+1$ zeros). So $E''(w)$ is positive definite for every $w$, as $E''$ is constant, hence every zeros of $E'$ is a minimum for $w$. Now lets look at $E'$, we have $E'(w) = 0$, if $E'(w)e_i = 0$ for each $i$ ($e_i$ denoting the $i$th standard basis vector), it holds $$ E'(w)e_i = \sum_{n=1}^N \bigl(y(x_n, w) - t_n\bigr) x_n^i $$ That is we want $w$ to be such that $y(x,w)- t$ is orthogonal to $(x_1^i, \ldots, x_N^i)$ for all $i$. Projection of $t$ onto the subspace generated by this vectors, gives us an unique point, as $w \mapsto y(x,w)$ is injective, $w$ is unique.

share|improve this answer
    
What was the overall approach taken when going through this proof. That is, what theorems where you using. I'm just trying to figure out what sort of background knowledge I would have needed to have in order to prove this myself, so then I can go learn more about these topics. –  Amateur Math Guy Oct 16 '13 at 11:58
    
Calculus of several real variables ... the thing used, is that a function $f \colon \mathbb R^d \to \mathbb R$ has in minimum in $x_0 \in \mathbb R^d$ if $f'(x_0) = 0$, $f''(x_0) > 0$ (that is $f''(x_0)$ is positive defnite) –  martini Oct 16 '13 at 13:10
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.