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.

I have a question about least squares and about what happens, if the function that we minimize, $E(P)$, is not linear in its parameters $P$.

Assume we want to minimize a function (the exact terms are not so important, these are just examples) $$ E(\mathbf{p}) = = \frac{1}{2}\| E_a(\mathbf{p}) + \alpha E_b(\mathbf{p}) \|^2$$ where $$ E_a(\mathbf{p}) = \sum_i\| x_i-p_i\|^2$$ and $$ E_b(\mathbf{p}) = \sum_i\| y_i-p_i\|^2$$ where $\mathbf{p}\in\mathbb{R}^N$, $x_i$ and $y_i$ are scalars, and $p_i$ refers to the $i$-th element of $\mathbf{p}$.

Now, on the way to setting up a (hopefully linear) equation system, computing the partial derivative of $E(\mathbf{p})$ wrt. $p_m$ gets us $$ \frac{\partial E(\mathbf{p})}{\partial p_m} = \| E_a(\mathbf{p}) + \alpha E_b(\mathbf{p}) \| \Bigl( \frac{\partial E_a(\mathbf{p})}{\partial p_m} + \alpha\frac{\partial E_b(\mathbf{p})}{\partial p_m} \Bigr) $$

My questions: Is $\frac{\partial E(\mathbf{p})}{\partial p_m}$ really linear in $\mathbf{p}$ (despite of the additional $\|\cdot\|^2$)?

share|improve this question
    
This isn't least squares, since $E_a(p)$ and $E_b(p)$ are both quadratic in $p$, hence $E(p)$ is quartic in $p$. You might call it least hypercubes... –  Chris Taylor Feb 16 '12 at 16:17
    
Alright, that's what I thought ... However, the paper, where I read about this, says that they express this exact problem as a linear system of equations but give not additional details. Do you have an idea what they might have done? Exist there any approximation tricks that I might not be aware of? –  Nils Feb 16 '12 at 16:22
    
It would help if you could link to the paper. –  Chris Taylor Feb 16 '12 at 16:31
    
Sure, the paper can be found here. The minimization problem is in eq. (8). The statement, that it is expressed as a linear equation system is on the following page at the beginning of the 3rd paragraph. –  Nils Feb 16 '12 at 16:41
    
A quick thought: since $E_a(p)$ and $E_b(p)$ are convex, their sum is a convex function as well, right? Doesn't that mean, that the minimum would remain the same, even if $\|\cdot\|^2$ in $E(p)$ were dropped? –  Nils Feb 17 '12 at 8:47

1 Answer 1

As Chris explained in his comments, this problem is not linear in the parameters $\mathbf{p}$.

However, the two functions $E_a(\mathbf{p})$ and $E_b(\mathbf{p})$ are convex. Luckily, according to Wikipedia, the sum of two convex functions is also a convex function. That means, if $\|\cdot\|^2$ is dropped from $E(\mathbf{p})$ not only does the minimum remain identical, but the resulting equation system is linear in its parameters again - my problem solved!

share|improve this answer

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.