Relation of SVDs between two particular matrices

Question

Let $A = B - C$ be a very large matrix, where $C$ is a matrix with constant value $C$. Note that in my case $A$ represents an undirected graph adjacency matrix. I need to find the max singular value of $A$, however because of implementation details related to the scientific library I am currently using, I can just perform the SVD on the matrix $B$. Is there a relation that links the singular values computed for $B$ and those computed for $A$? Since I need the associated singular vectors too, is there a similar relation for them?

Answer 1

Your perturbation can be expressed as $$C = \gamma ee^T,$$ where $e = (1,1,\dots,1)^T$ is the vector of ones. In particular, your matrix $A = B - C$ is a rank $1$ perturbation of the known matrix $B$. You have very little information to utilize and it seems to me that you can do no better than apply the interlacing theorem for singular values, see Theorem 1 of this freely available paper:

http://www.sciencedirect.com/science/article/pii/0024379576900446

In the case of the largest singular value, the only information obtained from the interlacing theorem, is that the largest singular value of $A$ is larger than the second largest singular value of $B$.

I believe that your best bet is to apply the subspace iteration to compute the dominant eigenspaces of $A^T A$ and $AA^T$. Here you can capitalize on sparsity of $B$ and the simplicity of $C$ when performing the necessary matrix vector multiplications.