1
$\begingroup$

The problem is formulated as follows:

Let $U\in\mathbb{R}^{d\times R}$ denote the variable matrix. $A_i\in\mathbb{R}^{d\times d}$ and $y_i$ is a scalar $$ f(U) = \frac{1}{2m}\sum^m_{i=1}(\langle{A_i, UU^T}\rangle-y_i)^2 $$

Compute the gradient of $f(U)$ over $U$.

I have never dealt with inner products much before and am confused how to take the gradient for this function. I know that

$$ \frac{d}{dt} \langle f, g \rangle = \langle f(t), g^{\prime}(t) \rangle + \langle f^{\prime}(t), g(t) \rangle $$

But if you do this then the matrix dimensions do not work. Also not sure if this is even correct as you are dealing with a variable matrix. Any help would be great as I am pretty lost on how to begin.

$\endgroup$
  • 1
    $\begingroup$ I'm confused by the quantity $\Big(\langle A_i,UU^T\rangle-y_i\Big)$ -- the first term is a scalar but $y_i$ is a matrix. Either there's a missing identity matrix multiplying the first term, or $y_i$ is actually a scalar. Is $f(U)$ itself a scalar or a matrix? $\endgroup$ – greg Oct 17 at 17:42
  • $\begingroup$ Your right, it is a scalar, editing it. I was trying to write it concisely and got mixed up. $f(U)$ is a scalar $\endgroup$ – mkohler Oct 17 at 19:17
  • $\begingroup$ Which is the inner product? I guess it is $<A,B>=\sum_{ij} A_i B_i$ ? $\endgroup$ – Miguel Oct 17 at 19:26
  • $\begingroup$ @Miguel You are correct $\endgroup$ – mkohler Oct 17 at 19:58
2
$\begingroup$

For ease of typing, I'll use a colon to denote the inner product, i.e. $$A:B = \langle A,B\rangle$$ Define a vector $v$, whose $i^{th}$ component is given by $$v_i = A_i:(UU^T) - y_i$$ and a matrix $M$ equal to the mean of the $A_i$ matrices (weighted by the components of $v$) $$M = \frac 1m\sum_{i=1}^m v_iA_i$$ Then the function can be written as $$f = \frac 1{2m}\;\sum_{i=1}^m v_i\,v_i$$ Calculate the gradient of this function as follows $$\eqalign{ df &= \frac 1m\;\sum_{i=1}^m v_i\,dv_i \\ &= \frac 1m\;\sum_{i=1}^m v_i\,A_i:d(UU^T) \\ &= M:d(UU^T) \\ &= M:(dU\,U^T+U\,dU^T) \\ &= (M+M^T):(dU\,U^T) \\ &= \left(M+M^T\right)U:dU \\ \frac{\partial f}{\partial U} &= \left(M+M^T\right)U \\ }$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for this answer. This makes sense but I am unclear how you go from step 4 to step 5 in the gradient calculation. Could you elaborate what you are doing to get this? $\endgroup$ – mkohler Oct 18 at 16:20
  • $\begingroup$ An alternative expression for the inner product is $A:B={\rm Tr}(A^TB)\;$ and the step that you're asking about follows from well-known properties of the trace. $\endgroup$ – greg Oct 18 at 17:38
  • $\begingroup$ Thanks. I will do more research $\endgroup$ – mkohler Oct 18 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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