Given a matrix $F \in \mathbb{C}^{m \times n}$ such that a $m>n$ and other matrix $A$ (non-symmetric matrix) of size $n \times n$ and spectral norm as:

$$\|A-F^*\operatorname{diag}(b)F\|_2 = \sigma_{\max}(A-F^*\operatorname{diag}(b)F) = \sqrt{\lambda_{\max} \left( (A-F^*\operatorname{diag}(b)F)^* (A-F^*\operatorname{diag}(b)F \right)),}$$

How do I compute analytically $\nabla_b \|A-F^*\operatorname{diag}(b)F\|_2$, where $b \in \mathbb{C}^{m \times 1}$ is some vector and {$*$} is a sign for conjugate transpose?

I need gradient because I want to find $b$ by minimizing $\|A-F^*\operatorname{diag}(b)F\|_2$ as I would like to find the optimum by using gradient descent. Is it possible?

  • $\begingroup$ If you only care about result and your problem is not too large, use a monte-carlo based method. They don't converge as fast, but they don't require you to know the gradient. See, for example the metropolis-hastings algorithm. The logic is to compute the value at a random point not too far from the current point, and move to it with a certain probability, that is larger if your result is better than the one before $\endgroup$ – Aleksejs Fomins Jan 17 at 14:08
  • $\begingroup$ @AleksejsFomins Is there an analytic way to do this? $\endgroup$ – abina shr Jan 17 at 14:13
  • $\begingroup$ To do what? Metropolis-Hastings - no, it is a numerical technique: you plug in a metric you want to minimize, you get back a vector that minimizes it. Gradient Descent that you have expressed the intent of using also is not analytical - it is a numeric technique for finding minimum or maximum. It is a little faster than MH, but it only works if your problem has only 1 maximum/minimum. Perhaps you are asking if it is possible to find the gradient you seek analytically - I don't know. What I try to say is that maybe you don't even need it $\endgroup$ – Aleksejs Fomins Jan 17 at 14:53

Let's use $\big\{F^T,\,F^C,\,F^H=(F^C)^T\big\}\,$ to denote the $\big\{$Transpose, Complex, Hermitian$\big\}$ conjugates of $F$, respectively.

Let's also use the Frobenius product (:) notation instead of the Trace function, i.e. $$A:B = {\rm Tr}(A^TB)$$ [NB:  The use of $A^T$ (rather than $A^H$) on the RHS is deliberate.]

Define the variables $$\eqalign{ B &= {\rm Diag}(b) \cr X &= F^HBF-A \cr }$$ Given the SVD of $X$ $$\eqalign{ X &= USV^H \cr U &= \big[\,u_1\,u_2 \ldots u_n\,\big],\,&u_k&\in{\mathbb C}^{m\times 1} \cr S &= {\rm Diag}(\sigma_k),&S&\in{\mathbb R}^{n\times n} \cr V &= \big[\,v_1\,v_2 \ldots v_n\,\big],&v_k&\in{\mathbb C}^{n\times 1} \cr }$$ where the $\sigma_k$ are ordered such that $\,\,\sigma_1>\sigma_2\ge\ldots\ge\sigma_n\ge 0$

The gradient of the spectral norm $\phi = \|X\|_2$ can be written as $$G = \frac{\partial\phi}{\partial X} = (u_1v_1^H)^C = u_1^Cv_1^T$$ To find the gradient wrt the vector $b$, write the differential and perform a change of variables. $$\eqalign{ d\phi &= G:dX \cr &= G:F^H\,dB\,F \cr &= F^C GF^T:dB \cr &= F^C GF^T:{\rm Diag}(db) \cr &= {\rm diag}\big(F^CGF^T\big):db \cr \frac{\partial\phi}{\partial b} &= {\rm diag}\big(F^CGF^T\big) \cr &= {\rm diag}\big((Fu_1)^C(Fv_1)^T\big) \cr }$$

  • $\begingroup$ Nice proof. I found this post useful in understanding one of the steps better $\endgroup$ – Aleksejs Fomins Jan 18 at 17:12
  • 1
    $\begingroup$ @AleksejsFomins Looking at that post (especially python_enthusiast's answer) made me realize that I had mistakenly calculated the complex conjugate of $G$, which I have now corrected. Thanks. $\endgroup$ – greg Jan 18 at 22:26

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.