5
$\begingroup$

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

$\endgroup$
3

2 Answers 2

1
$\begingroup$

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

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


See also how-much-regularization-to-add-to-make-svd-stable on scicomp.stack:

If two symmetric matrices are approximately the same, then should we expect their canonical eigendecompositions to also be approximately the same?
The answer is a surprising no ... there is no way to make the SVD "stable" in the sense of the singular vectors.

$\endgroup$
0
$\begingroup$

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 C􏰝F􏰝 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .