Update SVD for an added diagonal

Question

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$

Answer 1

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.