How to get the SVD of $2AA^T-\operatorname{diag}(AA^T)$ given $A$ and its SVD $A=USV^T$?

Question

Given a matrix $A\in R^{n\times d}$ with $n>d$, and we can have some fast ways to (approximately) calculate the SVD (Singular Value Decomposition) of $A$, saying $A=USV^T$ and $V\in R^{d\times d}$. It is straightforward to know that the SVD of $2AA^T$ is $U(2SS)V^T$, that is to say the SVD of $2AA^T$ requires $O(nd^2)$ time similar to that of $A$.

However, to get the SVD of $2AA^T-\operatorname{diag}(AA^T)\in R^{n\times n}$ where $\operatorname{diag}(AA^T)$ is a square diagonal matrix who only has the diagonal elements of $AA^T$ in its diagonal, if running SVD directly on $2AA^T-\operatorname{diag}(AA^T)$, we might need $O(n^3)$ time. My question is, do you have any method or equation to use $A$ and its SVD $USV^T$ to indirectly get the SVD of $2AA^T-\operatorname{diag}(AA^T)$? Many thanks for your help.

Answer 1

This should be a comment, but is slightly long for a comment and may also qualify as an answer.

In general, diagonal updates are hard to handle for a general matrix. It is known (and can be proved) that diagonal updates to LU is as hard as performing the LU on the updated matrix, i.e., if $A=LU$ and $D$ is a diagonal matrix, then the $LU$ factorisation of $A+D$ again costs $\mathcal{O}(n^3)$ (and in fact, you can't even gain on the constants in front of the scaling). On some googling, a short proof of this is available here. I would expect the same to be true for SVD.

Answer 2

1. Let $A,B$ be hermitian matrices. Since we consider proper elements of the matrices, we may assume that $B$ is diagonal; assume that we know $spectrum(A)=(\alpha_i),spectrum(B)=(\beta_i)\subset \mathbb{R}^n$ (in non-increasing order). What can we say about $spectrum(A+B)=(\gamma_i)\subset \mathbb{R}^n$ (in non-increasing order)?

The answer is given by the Horn's conjecture (cf. http://math.ucr.edu/~jdolan/schubert2.pdf ) whose proof is dated 1998-1999. The NS condition contains only one equality, the obvious one, $\sum_i\gamma_i=\sum_i\alpha_i+\sum_i\beta_i$ and many linear inequalities linking some $\alpha_i,\beta_i,\gamma_i$. Finally, for generic hermitian matrices $A,B$, the $(\gamma_i)$ satisfy only one equality OR the $(\gamma_i)$ goes throught a real algebraic subset of dimension $n-1$.

2. Although $A,B$ are linked by $B=r.diag(A)$, it is of little importance because the spectra of $A,B$ are linked by only one equality, the obvious one. Indeed one has

Proposition (Schur-Horn): for every $p< n, \sum_{i=1}^p \beta_i\leq\sum_{i=1}^p\alpha_i$ and $\sum_{i=1}^n \beta_i=\sum_{i=1}^n\alpha_i$ IFF there is a hermitian matrix $C$ s.t. $diag(C)=(\beta_i)$ and $spectrum(C)=(\alpha_i)$.

3. Application to your question. We consider the "thin SVD" $A=USV^T$ where $UU^T=I_n,V^TV=I_d$ and $S\in M_d$ is diagonal. Then $AA^T=US^2U^T$ (your formula is false), that is the standard orthogonal diagonalization of $AA^T$; in particular, I do not see the point to compute the SVD of $A$. The required formula is in the form $AA^T+r.diag(AA^T)=W\Sigma W^T$. We saw that there is no real link between eigenvalues of $S^2$ and $\Sigma$ and, consequently, between their eigenvectors $U,W$.

Conclusion. The answer to your question is NO and do not dream, there is no hope.