0
$\begingroup$

Let $X \in \mathbb{R}^{a \times b}$ and

$$\|X\|_2 = \sigma_{\max}(X) = \sqrt{\lambda_{\max} \left( X^T X \right)}$$

How can I compute $\nabla_X \|AX\|_2$, where $A \in \mathbb{R}^{c \times a}$ is some known matrix?

$\endgroup$
  • $\begingroup$ Why do you need the gradient? $\endgroup$ – Rodrigo de Azevedo May 25 '18 at 20:27
  • $\begingroup$ I want to find X minimizing $||AX||_2$, and I would like to find the optimum by using gradient descent. The problem could be solved with semidefinite programming, however I need to consider gradient descent. $\endgroup$ – pulosky May 27 '18 at 0:17
1
$\begingroup$

Consider a matrix and its SVD $$Y = \sum_{k=1}^r\sigma_ku_kv_k$$ and let $\,\phi=\|Y\|=\sigma_1\,$ be the spectral norm $($assuming that the singular values are ordered such that $\sigma_1>\sigma_2>\sigma_3>\ldots>\sigma_r>0\,)$

The gradient of the norm is $$\frac{\partial\phi}{\partial Y} = u_1v_1^T$$

Write the differential in terms of this gradient and perform a change of variables $Y=AX$ $$\eqalign{ d\phi &= u_1v_1^T:dY \cr &= u_1v_1^T:A\,dX \cr &= A^Tu_1v_1^T:dX \cr \frac{\partial\phi}{\partial X} &= A^Tu_1v_1^T \cr }$$ to obtain the desired gradient.

A colon is used to denote the trace/Frobenius product, i.e. $A:B={\rm tr}(A^TB),\,$ in some of the steps above.

If the first few singular values are identical, $($e.g. $\sigma_1=\sigma_2=\sigma_3)$, then the result changes slightly $$\eqalign{ \frac{\partial\phi}{\partial X} &= \sum_{k=1}^3A^Tu_kv_k^T \cr }$$

$\endgroup$
  • $\begingroup$ Could you please expand on why $\frac{\partial \phi}{\partial Y}=u_1 v_1^T$? $\endgroup$ – pulosky May 27 '18 at 0:23
  • $\begingroup$ I'll refer you to this question for the details. $\endgroup$ – greg May 27 '18 at 0:48

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.