3
$\begingroup$

I have a positive definite matrix $K$ which has an SVD of $UDU^T$. Is there a way of finding the SVD of $K+\operatorname{diag}(\sigma_1,\sigma_2,\dots,\sigma_n)$ efficiently by the knowledge of the SVD of $K$ alone?

Would it be helpful to know that most $\sigma_i=0$

$\endgroup$
1
+50
$\begingroup$

I assume that your $K$ is an hermitian matrix. Your problem is equivalent to this one: knowing the eigenvalues of $2$ hermitian matrices $A,B$, what can be said about the eigenvalues of $A+B$ ? It is the Alfred Horn's conjecture. Cf

http://math.ucr.edu/~jdolan/schubert2.pdf

This conjecture has recently been solved by Klyachko, Knutson and the inevitable Tao. Give them your bounty !

EDIT: a priori, the previous result concerns only the eigenvalues. If you know the spectra of $A,B$, then the eigenvalues of $A+B$ satisfy a set of inequalities. Conversely, if you choose $\tau$, a set of $n$ real numbers satisfying the previous inequalities, then there are unitary matrices $U,V$ s.t. $UDU^*+diag(\sigma_i)=Vdiag(\tau_i)V^*$. I do not think that the couple $(U,V)$ is unique (even up to a permutation of the eigenvalues and even if the eigenvalues are in general position). Finally the link between the eigenvalues and the choice of $U,V$ is not clear. Unfortunately, I think that you must read the entire proof ! Moreover, if you obtain such a link, then you could perhaps to be a candidate to a Fields medal.

EDIT 2: Remark: in fact, the matrices $U,V$ above are unitary (edited). I do not think that the problem can be restricted to the orthogonal matrices.

About your comment: you are right. For instance, when $n=2$, let $d_1\geq d_2, \sigma_1\geq \sigma_2,\tau_1\geq \tau_2$. The set of inequalities is $\tau_1\leq d_1+\sigma_1,\tau_2\leq d_1+\sigma_2,\tau_2\leq d_2+\sigma_1$ and do not forget the equality about the traces: $d_1+d_2+\sigma_1+\sigma_2=\tau_1+\tau_2$. When $n=3, resp\; 7$, there are $12,resp\;2062$ linear inequalities plus the trace equality.

$\endgroup$
2
  • $\begingroup$ I've only read first 5 pages, but does this address the issue of figurint out the matrix $U$ in itself? Or is it just the eigen values? Forgive me if this was a stupid question (eg. if its trivial to figure out $U$ once eigen values are known) $\endgroup$ – sachinruk Mar 4 '14 at 6:09
  • $\begingroup$ ah, so if I understand correctly I will only obtain limits on each $\tau_i$ and not the exact value? $\endgroup$ – sachinruk Mar 5 '14 at 5:56

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.