6
$\begingroup$

I want to calculate the derivative of the spectral norm of a symmetric square matrix $W$:

$$ \frac{\partial}{\partial w_{ij}} \|W\|_2 $$

How should I go about this?

$\endgroup$
  • 2
    $\begingroup$ The norm is convex, hence Lipschitz and so differentiable ae., but not differentiable everywhere. You either need extra conditions (such as $W^* W$ having a unique maximum eigenvalue) or deal with subdifferentials (or subgradients). $\endgroup$ – copper.hat Sep 13 '14 at 7:44
  • $\begingroup$ @copper.hat we can assume $W$ has a unique maximum eigenvalue. $\endgroup$ – akxlr Sep 13 '14 at 7:47
  • $\begingroup$ I do believe it is differentiable under that very specific circumstance. $\endgroup$ – Michael Grant Sep 13 '14 at 23:46
  • $\begingroup$ You need the maximum absolute value eigenvalue to be unique. $\endgroup$ – copper.hat Sep 13 '14 at 23:47
6
$\begingroup$

Here is an approach based on the implicit function theorem, similar to loup blanc's approach, with a connection to my other answer.

Let $W=U \Sigma V^T$ be a SVD of $W$, where $\Sigma = \operatorname{diag}(\sigma_1,...,\sigma_n)$, with $\sigma_k \ge \sigma_{k+1}$. Then $\|W\|_2 = \sigma_1$, where $\sigma_1 = \sqrt{\lambda_\max(W^TW)}$.

Let $\eta(x,A) = \det(x I -A^TA)$, then $\eta(x,A)=0$ iff $\sqrt{x}$ is a singular value of $A$. Note that $\eta$ is a polynomial in $x$ and the entries of $A$, hence so are the various derivatives.

Note that ${\partial \det(A) \over \partial A} (\Delta) = \operatorname{tr} ((\operatorname{adj} A) \Delta)$, and if $A$ is invertible, we have ${\partial \det(A) \over \partial A} (\Delta) = \det A \operatorname{tr} (A^{-1} \Delta ) $. The latter form is more convenient to work with.

If $\sqrt{x}$ is not a singular value of $W$, we have ${ \partial \eta(x, W) \over \partial x} = \det(x I -W^T W) \operatorname{tr} ((x I -W^TW)^{-1} )$. Using the SVD expansion (and continuity), we have ${ \partial \eta(x, W) \over \partial x} = \sum_k \prod_{i\neq k} (x-\sigma_i^2)$ for all $x$.

Hence we see that if $\sigma_1 > \sigma_2$ (which also implies $\sigma_1 >0$), then ${ \partial \eta(\sigma_1^2, W) \over \partial x}\neq 0$, and the implicit function theorem gives the existence of a differentiable function $\xi$ defined in a neighbourhood of $W$ such that $\xi(W) = \sigma_1^2$ and $\eta(\xi(W'),W') = 0$ for $W'$ near $W$, hence $\sqrt{\xi(W')}$ is a singular value of $W'$, and continuity of the roots of $x \mapsto \eta(x,W')$ as a function of $W'$ shows that $\|W'\|_2 = \sqrt{\xi(W')}$.

To compute the derivative of $\xi$, we need ${ \partial \eta(\sigma_1^2, W) \over \partial A}(H)$. For $x \neq \sigma_1^2$ near $\sigma_1^2$ we have \begin{eqnarray} { \partial \eta(x, W) \over \partial A}(H) &=& -\det(x I -W^T W) \operatorname{tr} ((x I -W^T W)^{-1} (W^TH+H^TW) ) \\ &=& -2 \det(x I -W^T W) \operatorname{tr} ((x I -W^T W)^{-1} W^TH ) \end{eqnarray} and so (expanding use the SVD), \begin{eqnarray} { \partial \xi(W) \over \partial W}(H) &=& \lim_{x \to \sigma_1^2} 2 { \operatorname{tr} ((x I -W^T W)^{-1} W^TH ) \over \operatorname{tr} ((x I -W^T W)^{-1} ) } \\ &=& 2 \lim_{x \to \sigma_1^2} { \operatorname{tr} ((x I -\Sigma^2)^{-1} \Sigma U^T H V ) \over \operatorname{tr} ((x I -\Sigma^2)^{-1} ) } \\ &=& 2 \lim_{x \to \sigma_1^2} { \sum_k { \sigma_k \over x-\sigma_k^2 } [U^THV]_{kk} \over \sum_k { 1 \over x-\sigma_k^2 } } \\ &=& 2 \lim_{x \to \sigma_1^2} { \sum_k (x-\sigma_1^2) { \sigma_k \over x-\sigma_k^2 } [U^THV]_{kk} \over \sum_k (x-\sigma_1^2) { 1 \over x-\sigma_k^2 } } \\ &=& 2 \sigma_1 [U^THV]_{11} \\ &=& 2 \sigma_1 \langle u , H v \rangle \end{eqnarray} where $u = U e_1,v=V e_1$ are left and right singular vectors of $W$ corresponding to the singular value $\sigma_1$.

Finally, since $n(W') = \|W'\|_2 = \sqrt{\xi(W')}$, we have ${\partial n(W) \over \partial W} = {1 \over 2 \sqrt{ \xi(W')}} {\partial \xi(W) \over \partial W } = \langle u , H v \rangle$, as above.

The above works for any matrix $W$ as long as $\sigma_1 > \sigma_2$.

If $W$ is symmetric, then we can write the spectral decomposition $W=U \Lambda U^T$ (this also functions as a SVD), and so $W^T W = U \Lambda^2 U^T$. Hence $\|W\|_2$ is the absolute value of the eigenvalue of largest absolute value. Hence the condition $\sigma_1 > \sigma_2$ corresponds to requiring $|\lambda_1| > |\lambda_k|$ for $k >1$, and in this case ${\partial n(W) \over \partial W}(H) = \langle u , H u \rangle$, where $u$ is a unit eigenvector corresponding to $\lambda_1$.

We have, of course, ${\partial n(W) \over \partial W_{ij}} = {\partial n(W) \over \partial W}(E_{ij}) = [u]_i [u]_j$.

$\endgroup$
  • $\begingroup$ Thanks, this is great. Can you explain your notation $\frac{\partial n(W)}{\partial W} (H)$? $\endgroup$ – akxlr Sep 15 '14 at 10:20
  • $\begingroup$ It is the derivative of $n$ (where $n(A) = \|A\|_2$) evaluated in the direction $H$. $\endgroup$ – copper.hat Sep 15 '14 at 14:56
  • $\begingroup$ Because the derivative is a function $\mathbb{R}^{n \times n} \to \mathbb{R}$ and it cannot be written as a direct matrix product. $\endgroup$ – copper.hat Sep 15 '14 at 15:05
6
$\begingroup$

Let $W \in \mathbb{R}^{m\text{x}n}$. $f(W)=||W||_2 = \sigma_1(W)$, where $\sigma_1(W)$ stands for the larger singular value of (W).

The SVD decomposition of $W$ is $W=U\Sigma V^{T}$. So $||W||_2=e_1^{T}U^{T}(U\Sigma V^{T})V e_1$. Hence, $f(W)=u_1^{T}Wv_1$, where $u_1$ and $v_1$ are the first column vectors of $U$ and $V$, respectively.

Hence, the derivative can be computed as:

$Df(W)(H)= u_1^{T}Hv_1 = trace(u_1^{T}Hv_1) = trace(v_1u_1^{T}H)$.

Thus, the gradient is $\nabla f(W) = v_1u_1^{T}$.

Ps.: Notice that a sufficient condition for the existence of the derivative is that $\sigma_1 \neq \sigma_2$, otherwise the maximization problem in the induced 2-norm has more than one argmax.

$\endgroup$
  • $\begingroup$ Could you explain the last line a bit more please? Where does the trace() come from? presumably $u_1^T H v_1$ is a scalar so what does its trace mean? And what is H here? $\endgroup$ – Seyouki Jul 31 at 15:16
  • $\begingroup$ The trace of a scalar is just the scalar itself (second equality), but then we can use the trace property that you can rotate what's being multiplied inside (third equality). $\endgroup$ – python_enthusiast Jul 31 at 15:19
  • $\begingroup$ Thanks for the quick reply! So basically we can apply a trace to rearrange arguments in a cyclic fashion. That's pretty cool. I'm still a little bit confused where H comes from and how rearranging arguments help to derive the final equality? And why doesn't $\sigma _1$ appear here similar to the accepted answer? $\endgroup$ – Seyouki Jul 31 at 15:31
  • $\begingroup$ H comes from the definition of matrix derivative (we are taking the derivative of f(W), remember that derivatives are actually limits). The gradient conclusion from the derivative is coming from the definition directly. The sigma_1 question I don't understand. Sigma 1 does show up in both answers, but we took different solution paths, so it will not have exactly the same presentation. $\endgroup$ – python_enthusiast Jul 31 at 15:42
4
$\begingroup$

Another approach is to use subgradients. This approach has the added advantage of characterizing points at which the norm is differentiable in general, not just for symmetric matrices.

Let $n(W) = \|W\|_2$, and note that $n(W) = \sigma_1(W)$, the maximum singular value of $W$.

The relevant result is:

$n$ is differentiable at $W$ iff both of the subspaces of left and right singular vectors of $W$ corresponding to $\sigma_1(W)$ have dimension one.

A consequence of this assumption is that if $u,v$ are of unit norm, and $\|W\|_2 = \langle u, W v \rangle$, then $u,v$ are left and right singular vectors of $W$ corresponding to the maximum singular value of $W$, and furthermore, $u,v$ are unique modulo sign. This follows from the singular value decomposition.

If $W$ is symmetric, we can state this assumption in terms of eigenvalues: Then $n$ is differentiable at $W$ iff when we order the eigenvalues of $W$ by decreasing absolute value, then $|\lambda_1| > |\lambda_k|$, for all $k>1$ (that is, the eigenvalue of maximum absolute value is unique).

(In particular, it is not sufficient to assume that the maximum eigenvalue is unique.)

A consequence of this condition is that if $u,v$ are of unit norm, and $\|W\|_2 = \langle u, W v \rangle$, then $u,v$ are left and right eigenvectors corresponding to $\lambda_1$, and furthermore, $u=(\operatorname{sgn} \lambda_1) v$ (and $v$ is unique modulo sign).

Returning to the general case:

Note that $n(W) = \max_{u,v \in B} \phi(W, (u,v))$, where $\phi(W,(u,v)) = \langle u, W v \rangle$, and $B$ is the closed unit ball (hence compact). For each $(u,v)$, the function $W \mapsto \phi(W, (u,v))$ is convex (in fact, linear), hence $n$ is convex and since $B \times B$ is compact, it admits a subgradient $\partial n(W)$ at each $W$.

Since $n$ is convex and finite valued, $n$ is Lipschitz and regular (the directional derivatives and generalised directional derivatives coincide).

Note that ${\partial \phi(W,(u,v)) \over \partial W}(H) = \langle u, H v \rangle$.

Let $I(W) = \{(u,v) \in B \times B \, | \, \|W\|_2 = \phi(W, (u,v)) \}$. Note that $(u,v) \in I(W)$ iff $u,v$ are left and right singular vectors of $W$ corresponding to the maximum singular value of $W$ (that is, $\sigma_1(W) = \|W\|_2$).

Then Corollary 2 in Remark 2.8.3 of Clarke's "Optimization and Nonsmooth Analysis" gives $\partial n(W) = \operatorname{co}\{ {\partial \phi(W,(u,v)) \over \partial W}\}_{(u,v) \in I(W)}$. (This is true whether or not $W$ is symmetric.)

Proposition 2.2.4 shows that if $\partial n(W)$ is a singleton, then $n$ is (strictly) differentiable at $W$. Furthermore, Proposition 2.3.6 shows that if $n$ is differentiable at $W$, then $\partial n(W)$ is a singleton.

It should be clear that $\partial n(W)$ is a singleton iff $I(W)$ contains exactly two points (which are symmetric about the origin) iff both of the subspaces of left and right singular vectors of $W$ corresponding to $\sigma_1(W)$ have dimension one. When $n$ is differentiable, we have ${\partial n(W) \over \partial W}(H) = \langle u, H v \rangle$, where $u,v$ are left and right singular vectors corresponding to the maximum singular value of $W$

If $W$ is symmetric, then $\partial n(W)$ is a singleton iff the eigenvalue of maximum absolute value is unique. When $n$ is differentiable, then ${\partial n(W) \over \partial W}(H) = \langle u, H u \rangle$, where $u$ is a unit eigenvector corresponding to the (unique) maximum absolute value eigenvalue. (The corresponding gradient using the Frobenius norm inner-product on the space of matrices is $u u^T$.)

Aside: Since $n$ is locally Lipschitz, the Rademacher theorem shows that $n$ is differentiable almost everywhere (Lebesgue). In practice however, $W$ often has some restricted structure so this result is of less utility that might seem at first glance.

We have, of course, ${\partial n(W) \over \partial W_{ij}} = {\partial n(W) \over \partial W}(E_{ij}) = [u]_i [u]_j$.

$\endgroup$
2
$\begingroup$

@ akxlr , you "must" assume that there is a unique $\lambda_0\in spectrum(W)$ s.t. $||W||_2=\rho(W)=|\lambda_0|$. Assume that $\lambda_0>0$. Let $t\in\mathbb{R}\rightarrow W(t)\in S_n$ be a $C^1$ function s.t. $W(0)=W$, $p_t=\chi_{W(t)}$ be the characteristic polynomial of $W(t)$ and $\lambda(t)$ be the maximal root of $p_t$. One has $p_t(\lambda(t))=0$ and, locally, $\lambda(t)$ is a $C^1$ function such that, according to the implicit function theorem:

$\lambda'(t)=-\dfrac{\dfrac{\partial{p_t(\lambda)}}{{\partial t}}}{\dfrac{\partial{p_t(\lambda)}}{{\partial \lambda}}}_{\lambda=\lambda(t)}$. Obviously, you must know an approximation of $\lambda_0$.

Example: $W(t)=\begin{pmatrix}3+t^2&2+t\\2+t&t^3+1\end{pmatrix}$. Here $\lambda_0=4$ and $p_t(\lambda)=\lambda^2-(4+t^2+t^3)+t^5+3t^3-4t-1$, $\lambda'(t)=-\dfrac{-(2t+3t^2)\lambda(t)+5t^4+9t^2-4}{2\lambda(t)-(4+t^2+t^3)}$ and $\lambda'(0)=1/3$.

$\endgroup$
  • $\begingroup$ Note that this is the derivative of $\|\cdot\|_2 \circ W$, where $W$ is the path given above. $\endgroup$ – copper.hat Sep 13 '14 at 23:55
  • $\begingroup$ @ copper.hat , you are right, but it is equivalent to the required question. Indeed $\dfrac{\partial ||W||_2}{\partial w_{i,j}}$ is obtained for $W(t)=W+t(E_{i,j}+E_{j,i})$. $\endgroup$ – loup blanc Sep 14 '14 at 4:33
  • $\begingroup$ Well, this may be an oversight on the OP's part, but the question was to evaluate the derivative of the norm at a specific symmetric $W$ (in all directions, not just symmetric ones). So, I think you need to adapt the above analysis to look at the characteristic polynomial of $W(t)^T W(t)$. That way your result works for all directions, not just symmetric ones. $\endgroup$ – copper.hat Sep 14 '14 at 6:13

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.