80
$\begingroup$

It's stated that the gradient of:

$$\frac{1}{2}x^TAx - b^Tx +c$$

is

$$\frac{1}{2}A^Tx + \frac{1}{2}Ax - b$$

How do you grind out this equation? Or specifically, how do you get from $x^TAx$ to $A^Tx + Ax$?

$\endgroup$
1
  • 4
    $\begingroup$ did you understand the answer? $\endgroup$ Dec 4, 2017 at 1:54

6 Answers 6

62
$\begingroup$

The only thing you need to remember/know is that $$\dfrac{\partial (x^Ty)}{\partial x} = y$$ and the chain rule, which goes as $$\dfrac{d(f(x,y))}{d x} = \dfrac{\partial (f(x,y))}{\partial x} + \dfrac{d( y^T(x))}{d x} \dfrac{\partial (f(x,y))}{\partial y}$$ Hence, $$\dfrac{d(b^Tx)}{d x} = \dfrac{d (x^Tb)}{d x} = b$$

$$\dfrac{d (x^TAx)}{d x} = \dfrac{\partial (x^Ty)}{\partial x} + \dfrac{d (y(x)^T)}{d x} \dfrac{\partial (x^Ty)}{\partial y}$$ where $y = Ax$. And then, that is,

$$\dfrac{d (x^TAx)}{d x} = \dfrac{\partial (x^Ty)}{\partial x} + \dfrac{d( y(x)^T)}{d x} \dfrac{\partial (x^Ty)}{\partial y} = y + \dfrac{d (x^TA^T)}{d x} x = y + A^Tx = (A+A^T)x$$

$\endgroup$
10
  • 38
    $\begingroup$ To help future generations: the full specification of the chain rule used here is $$ \frac{df(g,h)}{dx} = \frac{d(g(x)^T)}{dx} \frac{\partial f(g,h)}{\partial g} + \frac{d(h(x)^T)}{dx} \frac{\partial f(g,h)}{\partial h} $$ The order of multiplication is very important since we're dealing with vectors! $\endgroup$
    – Neil Traft
    Sep 23, 2014 at 9:58
  • 3
    $\begingroup$ the first statement seems wrong to me. Isn't the right statement $ \nabla_x(x^Ty) = y$? @NeilTraft $\endgroup$ Oct 21, 2017 at 23:22
  • 2
    $\begingroup$ Like for example how does the answerer know where $\dfrac{\partial y^T}{\partial x}$ goes on the left or on the right or if there is a transpose or not? Or maybe I just unfamiliar with the chain rule using gradients and I only know it using partial derivatives. $\endgroup$ Oct 21, 2017 at 23:37
  • 2
    $\begingroup$ Where can someone learn about these differentiation rules? In my standard analysis and calculus courses, we didn't see the differentiation of matrices or vectors, only of multivariate functions $\endgroup$ Oct 15, 2018 at 9:44
  • 3
    $\begingroup$ @Euler_Salter just write it as a multivariate function of the components of the vector $x$ and take the gradient. You will get the same result. $\endgroup$ Jan 20, 2019 at 21:49
25
$\begingroup$

Let $f : \mathbb R^n \to \mathbb R$ be defined by

$$f (\mathrm x) := \rm x^\top A \, x$$

Hence,

$$f (\mathrm x + h \mathrm v) = (\mathrm x + h \mathrm v)^\top \mathrm A \, (\mathrm x + h \mathrm v) = f (\mathrm x) + h \, \mathrm v^\top \mathrm A \,\mathrm x + h \, \mathrm x^\top \mathrm A \,\mathrm v + h^2 \, \mathrm v^\top \mathrm A \,\mathrm v$$

Thus, the directional derivative of $f$ in the direction of $\rm v$ at $\rm x$ is

$$\lim_{h \to 0} \frac{f (\mathrm x + h \mathrm v) - f (\mathrm x)}{h} = \mathrm v^\top \mathrm A \,\mathrm x + \mathrm x^\top \mathrm A \,\mathrm v = \langle \mathrm v , \mathrm A \,\mathrm x \rangle + \langle \mathrm A^\top \mathrm x , \mathrm v \rangle = \left\langle \mathrm v , \color{blue}{\left(\mathrm A + \mathrm A^\top\right) \,\mathrm x} \right\rangle$$

Lastly, the gradient of $f$ with respect to $\rm x$ is

$$\nabla_{\mathrm x} \, f (\mathrm x) = \color{blue}{\left(\mathrm A + \mathrm A^\top\right) \,\mathrm x}$$


$\endgroup$
7
  • 3
    $\begingroup$ +1. What are that tags in your answer? $\endgroup$
    – C.F.G
    Sep 30, 2020 at 14:31
  • 1
    $\begingroup$ @C.F.G The tags are there to ensure I can find my answer even if the question is vandalized, tags are merged or renamed, etc. Insurance against others' misbehavior. $\endgroup$ Sep 30, 2020 at 14:34
  • $\begingroup$ how were you able to swap the x^TA to A^Tx in the line with the inner products to arrive at <v, (A + A^T) x> $\endgroup$ Oct 17, 2020 at 20:53
  • 3
    $\begingroup$ @Learningstatsbyexample Note that $\rm x^\top A v$ is a scalar, and a scalar is equal to its transpose. Hence, $$\rm x^\top A v = \left( \rm x^\top A v \right)^\top = \rm v^\top A^\top x$$ Does this clarify the matter? $\endgroup$ Oct 17, 2020 at 21:00
  • 1
    $\begingroup$ < 7 minute response time; that is service :) Yes that helps, thanks! $\endgroup$ Oct 17, 2020 at 21:06
14
$\begingroup$

I am just writing this answer for future reference and for clarity because the accepted answer is not completely correct and may case confusion.

I will use a simple proof to better understand the multiplication rule in the calculation of $\nabla\mathbf{x^TAx}$.

For $\mathbf{x}\in \mathbb{R}^n$ and $\mathbf{A}\in \mathbb{R}^{n\times n}$ let: $$f(g(\mathbf{x}),h(\mathbf{x}))=\langle g(\mathbf{x}),h(\mathbf{x})\rangle=g^T(\mathbf{x})h(\mathbf{x})$$

Where: \begin{equation} \begin{split} &g(\mathbf{x})=\mathbf{x}\\ &h(\mathbf{x})=\mathbf{Ax} \end{split} \end{equation}

From the definition of $f$, it is obvious that $f(g(\mathbf{x}),h(\mathbf{x}))=\mathbf{x^TAx}$.

In order to calculate the derivative, we will use the following fundamental properties, where $\mathbf{I}$ is the identity matrix:

\begin{equation} \begin{split} &\dfrac{\partial \mathbf{A^Tx}}{\partial\mathbf{x}}=\dfrac{\partial \mathbf{x^TA}}{\partial\mathbf{x}}=\mathbf{A^T}\\ &\dfrac{\partial \mathbf{x}}{\partial\mathbf{x}}=\mathbf{I} \end{split} \end{equation}

Hence, from the multiplication rule (you can see the rule at wikipedia), we got: \begin{equation} \begin{split} \dfrac{df(g(\mathbf{x}),h(\mathbf{x}))}{d\mathbf{x}}&=g^T(\mathbf{x})\dfrac{\partial h(\mathbf{x})}{\partial\mathbf{x}}+h^T(\mathbf{x})\dfrac{\partial g(\mathbf{x})}{\partial\mathbf{x}}=\\ &=\mathbf{x^T}\dfrac{\partial \mathbf{Ax}}{\partial\mathbf{x}}+(\mathbf{Ax})^T\dfrac{\partial \mathbf{x}}{\partial\mathbf{x}}=\\ &=\mathbf{x^TA}+\mathbf{x^TA^TI}=\\ &=\mathbf{x^TA}+\mathbf{x^TA^T}=\\ &=\mathbf{x^T}(\mathbf{A+A^T}) \end{split} \end{equation}

As a result, from the definition of gradient, we got: $$ \nabla f=\Bigg(\dfrac{df}{d\mathbf{x}}\Bigg)^T=(\mathbf{x^T}(\mathbf{A+A^T}))^T=(\mathbf{A^T+A})\mathbf{x} $$

Note: The reason I did the proof this way is to be more generalizable. So you can can plug arbitrary functions $g$ and $h$ and use the above multiplication rule to derive the result.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you. Till date this is the simplest of all answers. However, reading this first might be helpful. $\endgroup$
    – Ombrophile
    Aug 3, 2020 at 7:56
  • $\begingroup$ Hi, @G.Margaritis, excuse me, coulde you help me this equation, i.e., $f(x) = \frac{1}{2} \dot q^T A(q(x)) \dot q$ when matrix A is function of vector variable q and q is vector function of vector variable x and $ \dot x = J \dot q$ $\endgroup$
    – eason
    Jan 10 at 10:33
10
$\begingroup$

There is another way to calculate the most complex one, $\frac{\partial}{\partial \theta_k} \mathbf{x}^T A \mathbf{x}$. It only requires nothing but partial derivative of a variable instead of a vector.

This answer is for those who are not very familiar with partial derivative and chain rule for vectors, for example, me. Therefore, although it seems long, it is actually because I write down all the details. :)

Firstly, expanding the quadratic form yields: $$ \begin{align} f = \frac{\partial}{\partial \theta_k} \mathbf{x}^T A \mathbf{x} &= \frac{\partial}{\partial \theta_k} \sum_{i=1}^N \sum_{j=1}^N a_{ij}\frac{\partial}{\partial \theta_k}(\mathbf{x}_i \mathbf{x}_j) \end{align} $$ Since $$ \frac{\partial}{\partial \theta_k}(\mathbf{x}_i \mathbf{x}_j) = \begin{cases} \mathbf{x}_j, && \text{if } k = i \\ \mathbf{x}_i, && \text{if } k = j \\ 0, && \text{otherwise} \end{cases} $$ The equation is nothing but $$ f = \sum_{j=1}^N a_{kj} \mathbf{x}_j + \sum_{i=1}^N a_{ik} \mathbf{x}_i $$ Almost done! Now we only need some simplification. Recall the very simple rule that $$ \sum_{i=1}^N x_i y_i = \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix}^T \begin{bmatrix} y_1 \\ \vdots \\ y_n \end{bmatrix} = \mathbf{x}^T \mathbf{y} $$ Thus $$ \begin{align} f &= \text{(k-th row of A) } \mathbf{x} + \text{(k-th column of A)}^T \mathbf{x} \end{align} $$ Now it is time to compute the gradient from partial derivative! $$ \begin{align} \nabla_\mathbf{x} \mathbf{x}^T A \mathbf{x} & = \begin{bmatrix} \frac{\partial \mathbf{x}^T A \mathbf{x}}{\partial x_1} \\ \vdots \\ \frac{\partial \mathbf{x}^T A \mathbf{x}}{\partial x_k} \\ \vdots \\ \frac{\partial \mathbf{x}^T A \mathbf{x}}{\partial x_N} \\ \end{bmatrix} = \begin{bmatrix} \vdots \\ \text{(k-th row of A) } \mathbf{x} + \text{(k-th column of A)}^T \mathbf{x} \\ \vdots \end{bmatrix} \\ &= \left( \begin{bmatrix} \vdots \\ \text{(k-th row of A) } \\ \vdots \end{bmatrix} + \begin{bmatrix} \vdots \\ \text{(k-th column of A) }^T \\ \vdots \end{bmatrix} \right) \mathbf{x} \\ &= (A + A^T)\mathbf{x} \end{align} $$ So we are done!! The answer is: $$ \nabla_\mathbf{x} \mathbf{x}^T A \mathbf{x} = (A + A^T)\mathbf{x} $$

$\endgroup$
4
$\begingroup$

Yet another approach.

We will utilize the following the identities

  • Trace and Frobenius product relation $$\left\langle A, B \right\rangle={\rm tr}(A^TB) = A:B$$ or $$\left\langle A^T, B \right\rangle ={\rm tr}(AB) = A^T:B$$
  • Cyclic property of Trace/Frobenius product \begin{align} \left\langle A, B C \right\rangle \equiv A:BC &= AC^T:B\\ &= B^TA:C\\ &= BC : A\\ &= {\text{etc.}} \cr \end{align}

Let $f(x) := \left( \frac{1}{2} x^T A x - b^T x + c \right) $.

We obtain the differential first, and then the gradient subsequently. \begin{align} d\,f(x) &= d\left( \frac{1}{2} x^T A x - b^T x + c \right) \\ &= d\left( \frac{1}{2} \left( x: A x \right) - \left( b : x \right) + c \right) \\ &= \frac{1}{2} \left[ \left( dx: A x \right) + \left( x: A dx \right) \right] - \left( b : dx \right) \\ &= \frac{1}{2} \left[ \left( A x : dx \right) + \left( A^Tx: dx \right) \right] - \left( b : dx \right) \\ &= \frac{1}{2} \left[ \left(A + A^T \right)x: dx \right] - \left( b : dx \right) \\ &= \left( \frac{1}{2} \left[ \left(A + A^T \right)x\right] - b \right): dx \\ \end{align}

Thus the gradient is $$ \eqalign { \frac { \partial} {\partial x}f(x) &= \frac{1}{2} \left[ \left(A + A^T \right)x\right] - b \\ &= \frac{1}{2} A^T x + \frac{1}{2} A x - b . \cr } $$

$\endgroup$
0
$\begingroup$

Here's the approach I learned, with differentials. One only needs the product rule. I'll respond to the final part of the question, "Or specifically, how do you get from $x^TAx$ to $A^Tx + Ax$?"

Let $f(x) = x^T A x$. Then, to make the application of the production rule absolutely clear, let $g(x) = x^T$ and $h(x) = Ax$ so that $f(x) = g(x)h(x)$. Then by the product rule, $$df(x) = dg(x)h(x) + g(x)*dh(x)$$ We can compute $$ dg(x) = d(x^T) = (dx)^T $$ and $$ dh(x) = A dx $$ this latter one also by the product rule.

Then we have $$ df = (dx)^T Ax + x^T Adx $$ Now we want to get all the $dx$ term on the right. Since each term has dimension 1x1 (scalar), we can take the transpose of $(dx)^T Ax$ without changing its value, leaving $$ df = x^T A^T dx + x^T A dx = x^T (A^T+A) dx $$ By definition $df = (\nabla f)^T dx$. Thus we have $$ \nabla f = (A^T + A)x $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .