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 function of the form $$ E(\mathbf{x})=E_1(\mathbf{x})+E_2(\mathbf{x}) =\sum_i\|\ldots\|^2+\sum_j\|\ldots\|^2 $$ and want to solve the optimization problem $$ \text{argmin}_{\mathbf{x}} E(\mathbf{x}) $$ using linear least-squares. So, in order to build the linear equation system $A\mathbf{x}=\mathbf{b}$ one could choose between two strategies

  1. $\frac{\partial E(\mathbf{x})}{\partial x_m}=0$ and add one equation to $A$
  2. $\frac{\partial E_1(\mathbf{x})}{\partial x_m}=0$ and $\frac{\partial E_2(\mathbf{x})}{\partial x_m}=0$ and add two equations to $A$

and do this for all partial derivatives $m$.

My question: When confronted with a situation like this, is it better/more efficient/simpler/$\lt$your adjective here$\gt$ doing it like in 1.? Or does it make sense to break a function down like in 2. and add more but simpler constraints when building $A\mathbf{x}=\mathbf{b}$?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

The second alternative makes no sense. A smooth function $E(\mathbf x) = E_1(\mathbf x) + E_2(\mathbf x)$ is minimized when $\partial E(\mathbf x)/\partial x_m = 0$ for all $m$, or equivalently when $\partial E_1(\mathbf x)/\partial x_m + \partial E_2(\mathbf x)/\partial x_m = 0$. But of course the fact that $\partial E_1(\mathbf x)/\partial x_m$ and $\partial E_2(\mathbf x)/\partial x_m$ add up to zero does not mean that they are both zero!

For example, consider $E_1(x) = x^2$ and $E_2(x) = 2x$. The function $E(x) = E_1(x) + E_2(x) = x^2 + 2x$ is minimized at $x = -1$, even though $dE_2(x)/dx = 2$ is zero nowhere.

share|improve this answer
    
Just one remark: both, $E_1(x)$ and $E_2(x)$, are square. Would that mean, that the solution in a least-squares sense would be the same regardless of choosing 1. or 2. For example, $E_1(x)=x^2$ and $E_2(x)=(x+1)^2$, then the minimum of E is $x=-1/2$, the one of $E_1$ is at $x_1=-1$ and the one of $E_2$ is at $x_2=0$. But the least square solution with 2. should still be $x=-0.5$. –  Nils Feb 18 '12 at 11:32
    
What do you mean by a function being square? Do you mean it is a quadratic function, i.e. that $E_1(\mathbf x) = \mathbf x^T \mathbf A \mathbf x + \mathbf b^T \mathbf x + c$ for some $\mathbf A$, $\mathbf b$ and $c$? –  Rahul Feb 18 '12 at 12:01
    
Anyway, consider $E_1 = x^2$ and $E_2 = 2(x+1)^2$. The minimum of $E_1 + E_2$ is at $x = -2/3$, while the least-squares solution of $dE_1/dx = 0$ and $dE_2/dx = 0$ is at $x = -4/5$. –  Rahul Feb 18 '12 at 12:10
    
Alright, I guess that is enough to show that it cannot work the way I thought it would. Thanks for your help to clarify this! –  Nils Feb 18 '12 at 12:23

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.