1
$\begingroup$

Given a tall matrix $F \in \mathbb{C}^{m \times n}$, where $m > n$, and a non-symmetric matrix $A$ of size $n \times n$, consider the spectral norm

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

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?

$\endgroup$
3
  • $\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, 2019 at 14:08
  • $\begingroup$ @AleksejsFomins Is there an analytic way to do this? $\endgroup$
    – abina shr
    Jan 17, 2019 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, 2019 at 14:53

1 Answer 1

Reset to default
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Nice proof. I found this post useful in understanding one of the steps better $\endgroup$
    – Aleksejs Fomins
    Jan 18, 2019 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, 2019 at 22:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .