Home work 3: Differentiation

Since it easy to google every task please please please try to undestand what's going on. The "just answer" thing will be not counted, make sure to present derivation of your solution. It is absolutely OK if you found an answer on web then just exercise in $\LaTeX$ copying it into here.

Useful links: 1 2 3 4

ex. 1

$$ y = x^Tx, \quad x \in \mathbb{R}^N $$

$$ \frac{dy}{dx} = \left[\frac{d\sum_1^N x_i^2}{dx_j} = 2x_j\right] = 2x $$

ex. 2

$$ y = tr(AB) \quad A,B \in \mathbb{R}^{N \times N} $$

$$ \frac{dy}{dA} = \left[y = \sum_1^N (AB)_{ii}\right] = \left[(AB)_{ii} = \sum_1^N a_{ik}\cdot b_{ki}\right] = \left[a_{ij}\text{входит в $y$ только 1 раз - с коэффициентом } b_{ji}\right] = B^T $$

ex. 3

$$ y = x^TAc , \quad A\in \mathbb{R}^{N \times N}, x\in \mathbb{R}^{N}, c\in \mathbb{R}^{N} $$

$$ \frac{dy}{dx} = \left[y = \sum_1^N x_i(Ac)_i = \sum_{i=1}^N \left(x_i \cdot \sum_{j=1}^N a_{ij}c_j\right)\right] = Ac $$

$$ \frac{dy}{dA} = \left[tr(x^TAc) = x^TAc, \text{т.к. это просто число}\right] = \frac{d(tr(Acx^T)}{dA} = (cx^T)^T = xc^T $$

Hint for the latter (one of the ways): use ex. 2 result and the fact $$ tr(ABC) = tr (CAB) $$

ex. 4

Classic matrix factorization example. Given matrix $X$ you need to find $A$, $S$ to approximate $X$. This can be done by simple gradient descent iteratively alternating $A$ and $S$ updates. $$ J = || X - AS ||_2^2 , \quad A\in \mathbb{R}^{N \times R} , \quad S\in \mathbb{R}^{R \times M} $$ $$ \frac{dJ}{dS} = \frac{d(tr(XX^T - ASX^T - XS^TA^T + ASS^TA^T))}{dS} = \left(-2A^TX + \frac{d(tr(SS^TA^TA))}{dS}\right) = -2A^TX + \frac{d\sum_i\sum_j\sum_k\sum_l s_{ij}s_{kj}a_{lk}a_{ki}}{dS} = \\ = 2A^T(AS - X) $$

First approach

Using ex.2 and the fact: $$ || X ||_2^2 = tr(XX^T) $$ it is easy to derive gradients (you can find it in one of the refs).

Second approach

You can use slightly different techniques if they suits you. Take a look at this derivation: (excerpt from Handbook of blind source separation, Jutten, page 517, open for better picture).

Third approach

And finally we can use chain rule! YOUR TURN to do it. let $ F = AS $

Find $$ \frac{dJ}{dF} = $$ and $$ \frac{dF}{dS} = $$ (the shape should be $ NM \times RM )$.

Now it is easy do get desired gradients: $$ \frac{dJ}{dS} = $$