Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Thank you all for the help, I got some informations on the web. convex optimization stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf Nuclear norm approximation abel.ee.ucla.edu/cvxopt/applications/nucnrm INTERIOR-POINT METHOD FOR NUCLEAR NORM APPROXIMATION WITH APPLICATION TO SYSTEM IDENTIFICATION ee.ucla.edu/~vandenbe/publications/nucnrm.pdf –  Zhi Ming Chen Jun 10 '10 at 16:53

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer
    
Mr. Stein, Thank you very much. I've received many important messages from your post. Thanks again. Z.M. –  Zhi Ming Chen Jun 9 '10 at 6:57

Interesting question. Nuclear norm minimization is getting much attention right now as it relates directly to compressed sensing.

Some software for minimization with this constraint that I've used: http://perception.csl.illinois.edu/matrix-rank/sample_code.html

A fun related problem: http://www-stat.stanford.edu/~candes/papers/MatrixCompletion.pdf

share|improve this answer
    
Thank you so much. –  Zhi Ming Chen Sep 17 '10 at 23:03

If it helps, here is code using Matlab and Yalmip:

n = 5;

%Random symmetric matrix
A = 10*rand(n,n);
A=A'*A;

%Zero on the diagonal
A(sub2ind([n n],1:n,1:n)) = 0;

X = sdpvar(n,n,'symmetric');

%Equal to A off the diagonal
C=[];
for i=1:n
    for j=i+1:n
        C = [C; set(X(i,j) == A(i,j))];
    end
end

%We can add this if we want
%C = [C; set(trace(X)==0)];

solvesdp( C, sumabsk(X,n));
X=double(X);

X
sum(abs(eig(X)))
A
sum(abs(eig(A)))

It performs the optimization you are asking for by recognizing it as an SDP and solving it.

share|improve this answer
    
I do not know why the colors are wrong. –  Ben Jun 8 '10 at 22:15
    
There's an single quote on the fourth line. –  Qiaochu Yuan Jun 8 '10 at 23:51
    
Ben, Thank you for your nice code. I wish I could vote more than one....... ZM –  Zhi Ming Chen Jun 9 '10 at 6:40
    
Hello Ben, Since I want to speed up the execution while n is large, I was informed a method below. On page 25 of the paper "Interior Point Semidefinite Programming" rutcor.rutgers.edu/~alizadeh/MYPAPERS/sdp.ps.gz the maximizatin problem (primal) Max Tr(A*Y)-Tr(A*W) s.t. Tr(Y+W)=n, 0<=Y<=I, 0<=W<=I and the minimization problem (dual) Min nz+Tr(V)+Tr(U) s.t. zI+V-A>=0, zI+U+A>=0, U>=0, V>=0 Is it possible to implement by using basic operations of Matlab only? (then I could try to write it in C.) –  Zhi Ming Chen Dec 28 '10 at 21:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.