2
$\begingroup$

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}'$

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

3 Answers 3

3
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ 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)$? $\endgroup$ Aug 7, 2021 at 7:10
  • 1
    $\begingroup$ I get $-2 X^T (Y-XC)$. $\endgroup$
    – copper.hat
    Aug 7, 2021 at 7:44
  • $\begingroup$ 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! :-( $\endgroup$ Aug 7, 2021 at 9:36
  • $\begingroup$ @AshkanRanjbar Not really :-(. Just practice, grind & checking. Plus a few tricks with the trace operator. $\endgroup$
    – copper.hat
    Aug 7, 2021 at 17:33
1
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ @copper.hat yep! Thanks for that $\endgroup$ Feb 24, 2020 at 18:36
  • $\begingroup$ 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?? $\endgroup$
    – Rich
    Feb 24, 2020 at 20:21
  • 1
    $\begingroup$ @Rich that's basically right. You might find it useful to vary the parameter as you go, though. $\endgroup$ Feb 24, 2020 at 21:25
  • $\begingroup$ @Omnomnomnom Thanks! $\endgroup$
    – Rich
    Feb 25, 2020 at 0:58
  • $\begingroup$ @copper.hat missed your comment the first time, fixed $\endgroup$ Feb 25, 2020 at 7:20
1
$\begingroup$

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^+) \\ }$$

$\endgroup$

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.