[Math] minimize the sum of absolute eigenvalues

Question

Hi,

We have a real symmetric matrix M with diagonal elements 0's, the eigenvalues and eigenvectors of M are computed.

Now we wish to change its diagonal elements arbitrarily to minimize the sum of absolute eigenvalues. Does there exist a way to find such modifications?

If we add a constraint : keep Tr(M)=0, would that become easier?

Is there some topics about these?

Thank you for your help

Zhi Ming

Answer 1

The sum of the absolute value of the eigenvalues is the same (since the matrix is real and symmetric) as the sum of the singular values. This sum is called the nuclear norm of the matrix. So what you are saying is that you have an affine space of matrices (a "matrix pencil") over which you would like to minimize the nuclear norm. This is the case whether you add the trace constraint or not.

This is a convex optimization problem. A google search for "nuclear norm" will show how this can be converted to a semidefinite program and solved that way. You'll also get results about more specialized interior point methods which are optimized for just this problem.