# How does additive noise change the SVD

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)$

First the simplest case, 1d spectra:
$\qquad M = U \, S \, V$ + Gaussian noise, symmetrized, with $U = V = I$
$\qquad = O \, S_{noise} \, O^T$

How can one compare an arbitrary spectrum $S$ with its blurred / transmogrified $S_{noise}$ ? In the real world there are many many kinds of noise, and many ways of comparing even 1d functions $S()$ and $S_{noise}()$ of time (time series) or frequency: weighting large or small errors, hard or soft thresholding, different norms ...

A simple, runnable experiment: how does noise affect Low-rank approximation ? The Eckart-Young theorem says that the $k$-term series $A_k$ from SVD
$\qquad A = \sum \sigma_i \, u_i \, v_i^T$
$\qquad \ \ = A_k + Err_k$
$\qquad \ \ \ \ A_k = \sum_{i=1}^{k} \sigma_i \, u_i \, v_i^T$
is optimal, both in the spectral and Frobenius norms. Let's see how $\|Err_k\|$ falls off with $k$. Pseudocode:

Tallnoisy = noisyUSV( n, d, rank, S, noise )  # e.g. 1000 x 100, rank 10
= U S V + Gaussian( sigma=noise )
U Gaussian 1000 x 10
S = linspace( 1, 1/10, 10 )
V random orthogonal rows 10 x 100

AA = Tallnoisy.T dot Tallnoisy  # covariance 100 x 100, pos def
evals, evecs = np.linalg.eigh( AA )  # evals = sing(Tallnoisy)^2


The quite linear fall-off of $\|Err_k\|$ with $k$ surprised me; ymmv.

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.