How does additive noise change the SVD

Question

For matrix $M$ with SVD $M=U\Sigma V^*$ and random matrix $A$, what is the SVD of $M+A$?

That is, how will $A$ change the singular values and vectors of $M$? Let's even say that the entries of $A$ are i.i.d from $\mathcal{N}(0,1)$

Answer 1

Given the wide variety of results available on the subject, I doubt that any sigle answer would be completely to your satisfaction. A good place to start, however, would be to read the following papers:

1. G. W. Stewart, Perturbation Theory for the Singular Value Decomposition, SVD AND SIGNAL PROCESSING, II: ALGORITHMS, ANALYSIS AND APPLICATIONS, p. 99-100 (1990). (Link)
2. Ilse CF Ipsen, Relative perturbation results for matrix eigenvalues and singular values, Acta Numerica 7, p. 151-201 (1998). (Especially section 3, see link)
3. REN-CANG LI, RELATIVE PERTURBATION THEORY: I. EIGENVALUE AND SINGULAR VALUE VARIATIONS, SIAM J. MATRIX ANAL. Vol. 19, No. 4, p. 956–982 (1998). (Link)

In the above papers, most of the bounds on the difference between the singular values of $M$ and $M+A$ are given in terms of $\|A\|$ or a function of $\|A\|$, where $\|\cdot\|$ is some matrix norm. Thus, you would probably also be interested in bounds and estimates for the norm of random matrices. Such results are fairly easy to find: For example, by typing "norm of random matrices" in google, one of the first 10 results is this paper.