0
$\begingroup$

I am currently going through this paper, but am slightly stuck on understanding how the authors arrived at theorem 3. For better understanding, I am including the relevant theorems that have been stated in the paper.


Theorem 2

The Hessian $\mathbb{H}_x$ is positive semi-definite


Theorem 3

If $L$ is the largest eigenvalue of $\mathbb{H}_x$, for any value of $\lambda_2 > L/2$, the second-order interpretation objective function (5) is strongly concave.


I am fine with the given proof for theorem 2, and I am also fine with the second half of the proof of theorem 3, but I am confused by the following. The authors prove strong concavity of the loss function by subtracting the largest eigenvalue of the Hessian from all of the diagonal elements. Apparently this turns the positive semi-definite Hessian into something that is negative definite.

In the proof (page 11), it is written

Therefore if $\lambda_2 > L/2$, $\mathbb{H}_x - 2\lambda_2\mathbb{I}$ is negative definite.

How does subtracting all the diagonal elements of a positive semi-definite matrix by a value larger than the largest eigenvalue turn it into a negative definite matrix

$\endgroup$

1 Answer 1

1
$\begingroup$

Since the Hessian is positive semidefinite, we can perform a spectral decomposition and write $H = P\Lambda P^{T}$, such that $P^T = P^{-1}$ and $\Lambda$ is a diagonal matrix with eigenvalues of $H$ on its diagonal. Subtracting the diagonal elements of $H$ by $L$, we have

$$ H - LI = P\Lambda P^{T} - LPP^{-1} = P\Lambda P^{T} - L P I P^{T} = P(\Lambda - LI) P^{T}. $$

Since $L$ is the largest eigenvalue of $H$, the eigenvalues of $H - LI$ are the same as those of $\Lambda - LI$, and the largest of which is $L - L = 0$, so $H - LI$ is negative semidefinite. Thus, if we take any $\epsilon > 0$, the eigenvalues of $H - (L + \epsilon)I$ become strictly negative, so the matrix itself is negative definite since it's also symmetric (or Hermitian, depending on the underlying field).

$\endgroup$
1
  • $\begingroup$ Beautiful thanks $\endgroup$ May 27, 2021 at 11:15

You must log in to answer this question.

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