12
$\begingroup$

I am trying to find the minimum of $(Ax-b)^T(Ax-b)$ but I am not sure whether I am taking the derivative of this expression properly.

What I did is the following: \begin{align*} \frac{\delta}{\delta x_i}\left(\sum_i \sum_j (A_{ij}x_i-b_i)(A_{ij}x_j-b_j)\right)&= \sum_j A_{ij}(A_{ij}x_j-b_j) + \sum_i A_{ij}(A_{ij}x_j-b_i) \end{align*}

but I'm not quite sure if this is correct and what the derivate would then be. Any help is appreciated.

$\endgroup$
  • $\begingroup$ Minimum over what? $\endgroup$ – Igor Rivin Dec 14 '13 at 15:57
  • $\begingroup$ @IgorRivin over $x$ $\endgroup$ – dreamer Dec 14 '13 at 16:00
  • $\begingroup$ Do you actually mean $\|Ax-b\|^2$? I don't know what $(Ax-b)(Ax-b)$ is supposed to mean otherwise. And it is not a correct notation. $\endgroup$ – Julien Dec 14 '13 at 16:03
  • $\begingroup$ @julien I am sorry, I see that I am missing some transposes now. I will correct it immediately. $\endgroup$ – dreamer Dec 14 '13 at 16:04
  • $\begingroup$ Ok, so what you are looking for is $d^2$, where $d=d(b,\mathrm{im } A)$ is the Euclidean distance between the point $b$ and the range of $A$. $\endgroup$ – Julien Dec 14 '13 at 16:05
12
$\begingroup$

Perhaps some help to compute the partial derivatives would be appreciated. It is always best to be explicit when one is a bit confused with heavy notation. Write $A = (a_{ij})$, $x = (x_1,\dots,x_n)^{\top}$ and $b = (b_1,\dots, b_m)^{\top}$, assuming $A$ is an $m \times n$ matrix. Then the $i^{\text{th}}$ component of $Ax-b$ is $$ (Ax-b)_i = \left( \sum_{j=1}^n a_{ij} x_j \right) - b_i $$ so that $$ (Ax-b)^{\top} (Ax-b) = \sum_{i=1}^m (Ax-b)_i^2 = \sum_{i=1}^m \left( \left( \sum_{j=1}^n a_{ij} x_j \right) - b_i \right)^2. $$ Suppose you want to compute the derivative with respect to $x_k$, $1 \le k \le n$ (I choose $k$ because choosing $i$ or $j$ would be confusing with the preceding subscripts used). Then $$ \frac{\partial}{\partial x_k} (Ax-b)^{\top} (Ax-b) = \sum_{i=1}^m \frac{\partial}{\partial x_k} \left( \left( \sum_{j=1}^n a_{ij} x_j \right) - b_i \right)^2 = \sum_{i=1}^m 2 \left( \left( \sum_{j=1}^n a_{ij}x_j \right) - b_i \right) (a_{ik}). $$ In particular, we can let $A_k = (a_{1k},a_{2k},\dots,a_{mk})$ so that $$ \frac{\partial}{\partial x_k} (Ax-b)^{\top} (Ax-b) = 2 \langle A_k, Ax-b \rangle $$ where $\langle - , - \rangle$ denotes inner product. You can use convexity arguments to show that any critical point is a minimizer in this case ; although you can see that the minimizer will not always be unique, even when $m=n$ ; it suffices for $A$ to be singular for this to happen.

Hope that helps,

$\endgroup$
  • 1
    $\begingroup$ Thank you so much, I really, really appreciate your help :)! This clarifies everything, many thanks :)! $\endgroup$ – dreamer Dec 17 '13 at 17:11
  • 1
    $\begingroup$ @901301 : Don't worry about it. :) $\endgroup$ – Patrick Da Silva Dec 18 '13 at 1:50
5
$\begingroup$

I assume you are trying to minimize $\langle A x -b, A x - b\rangle.$ This is always nonnegative, so if $A$ is nonsingular, then the minimum is $0.$ Otherwise, the $i$-th component of the gradient is

$$\langle A_i, Ax +b\rangle + \langle A x + b, A_i\rangle$$

Where $A_i$ is the $i$-th column of $A.$ What does this tell you?

$\endgroup$
  • $\begingroup$ Thanks for your help. Is the expression you are minimizing the same as $||Ax-b||^2=(Ax-b)^T(Ax-b)$ (if so, I'm slightly confused by your notation)? And I'm not quite sure what this tells me. $\endgroup$ – dreamer Dec 14 '13 at 16:15
  • $\begingroup$ It's not clear that $A$ is a square matrix, much less non-singular. This is a common minimization problem when $A$ is non-square... $\endgroup$ – Thomas Andrews Dec 14 '13 at 16:42
  • $\begingroup$ @ThomasAndrews Indeed, but the approach I am describing (with no claims to any sort of originality) works for any $A.$ $\endgroup$ – Igor Rivin Dec 14 '13 at 16:50
5
$\begingroup$

The derivation becomes a lot simpler if we take the derivative with respect to the entire $x$ in one go:

$$\frac{\delta}{\delta x}(Ax-b)^T(Ax-b) \ \ = \ \ 2(Ax-b)^T\frac{\delta}{\delta x}(Ax-b) \ \ = \ \ 2(Ax-b)^TA$$

This follows from the chain rule:

$$\frac{\delta}{\delta x}uv \ \ = \ \ \frac{\delta u}{\delta x}v+u\frac{\delta v}{\delta x}$$

And that we can swap the order of the dot product:

$$\frac{\delta}{\delta x}u^Tu \ \ = \ \ \frac{\delta u^T}{\delta x}u+u^T\frac{\delta u}{\delta x} \ \ = \ \ (\frac{\delta u}{\delta x})^Tu+u^T\frac{\delta u}{\delta x} \ \ = \ \ 2u^T\frac{\delta u}{x}$$

I just learned matrix calculus from the Matrix Cookbook yesterday, and I love it :)

$\endgroup$
  • $\begingroup$ Nice one! Thanks for sharing your newfound knowledge :)! $\endgroup$ – dreamer Mar 12 '14 at 12:02
  • $\begingroup$ @Thomas, you love Matrix Cookbook ; Petersen and Pedersen will be happy. But have you understand it ? Firstly an expression of type $\frac{\partial f}{\partial x}$ is not a derivative (as you wrote) but a gradient. Secondly, if you look at the formula (73) of your new bible, then you see that the gradient is a vector ; unfortunately your result $2(Ax-b)^TA$ is a row. Do you know how to correct your result? $\endgroup$ – loup blanc Mar 13 '14 at 1:34
  • $\begingroup$ @loupblanc: You got me ;-) I still have much to learn about this topic. Specifically I'd really really like a hint on this problem: math.stackexchange.com/questions/708696/… because it's driving me nuts and I think I need an element-wise multiplication. $\endgroup$ – Thomas Ahle Mar 13 '14 at 7:35
1
$\begingroup$

Using the identities: $\frac{\partial x^{T} Bx}{\partial x} = (B+B^{T} )x $

$\frac{\partial x ^{T} a}{\partial x} = \frac{\partial x a ^{T}}{\partial x} = a$

$\frac{\partial a ^{T} x b}{\partial x} = a b ^{T}$

$\frac{\partial a ^{T} x ^{T} b}{\partial x} = ba ^{T}$

We have

$f(x) = (Ax-b)^{T}(Ax-b) $

$= x^{T} A^{T} Ax - x^{T} A^{T} b -b ^{T} Ax -b^{T} b$

Using above identities, we have

${f}'(x) = (A^{T} A+(A^{T} A)^{T})x - A^{T} b -(b^{T} A)^{T} $

$ = 2A^{T} Ax - 2A^{T} b$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.