# Gradient Descent wrt matrix

Suppose $$\mathbf{X}$$ is a p x n matrix, $$\mathbf{Y}$$ is q x n, $$\mathbf{C}$$ is an unknown q x p matrix. Can you minimize the following with gradient descent to find C? (multivariate regression)

$$|| \mathbf{Y}-\mathbf{C}\mathbf{X}||^2_F$$

Wouldn't the gradient wrt $$\mathbf{C}$$ just be

$$\nabla g = -2 (\mathbf{Y}-\mathbf{C}\mathbf{X}) \mathbf{X}'$$

• The gradient is $-2C^T(Y-CX)$. Just expand $\|Y-C(X+H)\|^2_F$ and take first order terms of $H$. Feb 24, 2020 at 17:50
• @copper.hat it's a gradient with respect to $C$, not $X$. Feb 24, 2020 at 18:09
• @Omnomnomnom: Ahh, thanks! Feb 24, 2020 at 18:17

Or explicitly, if $$g(C) = \langle Y-CX, Y-CX \rangle$$, we have $$g(C+H) -g(C) = -2 \langle Y-CX, HX \rangle+ O(\|H\|^2)$$ and since $$\langle Y-CX, HX \rangle = \operatorname{tr}((Y-CX)^T HX) = \operatorname{tr}(X(Y-CX)^T H) = \langle (Y-CX)X^T, H \rangle$$.

Hence $$\nabla g(C) = -2(Y-CX)X^T$$.

• I'm not very much of proof-goer, but can I safely assume that $\nabla_C\lVert XC - Y \rVert_F^2 = -2X^T(XC - Y)$? Aug 7, 2021 at 7:10
• I get $-2 X^T (Y-XC)$. Aug 7, 2021 at 7:44
• Man, you're really good at this. Do you know any resources or textbooks that I could teach myself these concepts? My knowledge barely goes beyond derivatives of single-valued multi-variable functions. Every time I try to lay my hands on these kinds of derivatives my brain goes on block! :-( Aug 7, 2021 at 9:36
• @AshkanRanjbar Not really :-(. Just practice, grind & checking. Plus a few tricks with the trace operator. Aug 7, 2021 at 17:33

Your function can be written in the form $$g(C) = \operatorname{tr}[(Y - CX)(Y - CX)'] = \operatorname{tr}[CXX'C] - 2\operatorname{tr}[CXY'] + [\text{const}]$$ Following this table, the gradient (either the transpose of the derivative in the left side column, or equivalently the derivative in the right-most column) will be $$\frac{\partial g}{\partial C} = [(Y - CX)(-X') + (-X)(Y - CX)']' - [2XY']' \\ = -X(Y - CX)' - (Y - CX)X' - 2YX'.$$

For a more abstract approach, note that

$$g(C+H) = \operatorname{tr}[(Y - [C+H]X)(Y - [C+H]X)']\\ = g(C) - \operatorname{tr}[HX(Y - CX)'] - \operatorname{tr}[(Y - CX)X'] + o(H)\\ = g(C) - 2\operatorname{tr}[HX(Y - CX)'] + o(H).$$ We therefore find that $$dg = -\operatorname{tr}[2X(Y - CX)' dC]$$, so that the gradient is equal to $$-[X(Y - CX)']' = -2(Y - CX)X'.$$ This matches your result.

• @copper.hat yep! Thanks for that Feb 24, 2020 at 18:36
• Great, thank you!! I missed a - sign, so I've edited the question. Now you're saying I can use gradient descent to solve for C, correct? That is start with a $\mathrm{C}$ (with values), and use a loop with a parameter alpha $\mathrm{C}^+ = \mathrm{C} - \alpha \nabla g$ until it converges??
– Rich
Feb 24, 2020 at 20:21
• @Rich that's basically right. You might find it useful to vary the parameter as you go, though. Feb 24, 2020 at 21:25
• @Omnomnomnom Thanks!
– Rich
Feb 25, 2020 at 0:58
• @copper.hat missed your comment the first time, fixed Feb 25, 2020 at 7:20

You do not need gradient descent to solve a linear equation.
Simply use the Moore-Penrose inverse $$X^+$$ \eqalign{ CX &= Y \quad\implies\quad C = YX^+ \\ } You can also include contributions from the nullspace (multiplied by an arbitrary matrix $$A$$) \eqalign{ C = YX^+ + A(I-XX^+) \\ }