5
$\begingroup$

The spectral norm of a symmetric matrix is the absolute value of the top eigenvalue. The gradient of this norm is $uu^T$ where $u$ is the eigenvector associated with that top eigenvalue.

Assume that $A$ has an isolated top eigenvalue. Then it is twice differentiable. What is its Hessian?

Any comments about how one generally computes Hessians of matrix norms are also appreciated!

$\endgroup$
3
$\begingroup$

Let us arrange all eigenvalues (and corresponding eigenvectors) in ascending order: $|\lambda_1| \leq \cdots |\lambda_{n-1}| < |\lambda_n|$. Then the elements of the desired Hessian are: $$\frac{\partial^2 \|A\|_2}{\partial A_{kl}\partial A_{ij}} = \frac{\partial^2 \lambda_{n}}{\partial A_{kl}\partial A_{ij}} = [\frac{\partial u^T_{n}}{\partial A_{kl}}]_i [u_{n}]_j + [u^T_{n}]_i [\frac{\partial u_{n}}{\partial A_{kl}}]_j$$

Here we use the fact that $A$ is diagonalizable, i.e., the set of eigenvectors $u_i, \ i=1,\cdots, n$ form a orthogonal basis. The basis is used to decompose $\frac{\partial u_n}{\partial A_{kl}} = \sum_{m=1}^n c_m u_m$. To find the coefficients $c_m \in \mathbb{R}$ one could follow the perturbation analysis (https://en.wikipedia.org/wiki/Eigenvalue_perturbation).

We just give the results: $$\frac{\partial u_{n}}{\partial A_{kl}} = \sum_{m=1}^{n-1} \frac{[u_m]_k[u_n]_l}{\lambda_n - \lambda_m} u_m$$ $$\frac{\partial u^T_{n}}{\partial A_{kl}} = \sum_{m=1}^{n-1} \frac{[u_m]_l[u_n]_k}{\lambda_n - \lambda_m} u_m$$ And the Hessian elements are: $$\frac{\partial^2 \|A\|_2}{\partial A_{kl}\partial A_{ij}} = \sum_{m=1}^{n-1} \frac{[u_n]_k[u_n]_j[u_m]_l[u_m]_i + [u_n]_l[u_n]_i[u_m]_k[u_m]_j}{ \lambda_n - \lambda_m} $$

$\endgroup$
  • $\begingroup$ Thanks for this answer! It took me a bit of time to go through the wikipedia derivation, but it does check out, and lends a nice mechanism for matrix norms in general. Great solution! $\endgroup$ – Y. S. Feb 9 at 20:53
0
$\begingroup$

@Andrey's solution is very nice, but I found the wikipedia part a bit hard to read, so for completeness, I am adding a simplified proof here to determine $\frac{\partial [u_i]_l}{\partial A_{st}}$ where $u_i$ is the $i$th eigenvector of $A$.

Consider the $i$th eigenvalue/eigenvector pair of $A$, where $Au_i = \lambda_i u_i$.

We use the perturbation analysis by taking the derivative of $Au_i=\lambda_iu_i$ via product rule $$ \partial A u_i + A\partial u_i = \partial \lambda_i u_i + \lambda_i \partial u_i. $$ Now $\partial u_i$ is a vector in $\mathbb R^n$, and we assume the eigenvectors $u_1,...,u_n$ are normalized, and thus form an orthonormal basis for $\mathbb R^n$. Therefore there exists $c_{ik}$ for $k = 1,...,n$ such that $$ \partial u_i = \sum_{k=1}^n c_{ik} u_k. $$ We substitute, left-multiply by $u_j^T$, and simplify with $Au_k = \lambda_ku_k$ to get $$ u_j^T\partial A u_i + c_{ij}\lambda_j = \partial \lambda_i u_j^Tu_i + \lambda_i c_{ij}. $$ When $i = j$, this reduces to $$ u_i^T\partial A u_i = \partial \lambda_i $$ which you can then use to find the gradient of the spectral norm. When $i\neq j$, this reduces to $$ \frac{ u_j^T\partial A u_i }{\lambda_i-\lambda_j }= c_{ij}. $$ Expanding out gives $$ \partial u_i = c_{ii}u_i + \sum_{k\neq i} \frac{ u_i^T\partial A u_k }{\lambda_i-\lambda_k } u_k = c_{ii}u_i + \sum_{k\neq i} \sum_{s,t=1}^n \frac{ \partial A_{s,t}[u_i]_s[u_k]_t }{\lambda_i-\lambda_k } u_k $$ Thus, we get $$ \frac{\partial [u_i]_l}{\partial A_{s,t}} =\sum_{k\neq i} \frac{ [u_i]_s[u_k]_t[u_k]_l}{\lambda_i-\lambda_k } $$

The rest follows from @Andrey's answer.

$\endgroup$
  • 1
    $\begingroup$ Here you won't have second-order perturbations; you need to take the derivative of $A u_i = \lambda_i u_i$ that is $\partial A u_i + A \partial u_i = \partial \lambda_i u_i + \lambda_i \partial u_i$. $\endgroup$ – Andrey Gorbunov Feb 11 at 2:46
  • $\begingroup$ That makes sense; just using product rule on the derivative. Thanks! $\endgroup$ – Y. S. Feb 12 at 16:22

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.