# Singular Value Decomposition of Noisy Matrices

I am an engineer who makes measurements of a variable over a grid of, say, $m\times n$. Since these are actual measurements, the true values are always corrupted by noise, and what I measure is a noisy version of the true set of values. Let $\mathbf{U}$ be the true (unknown) matrix of values and $\widetilde{\mathbf{U}}=\mathbf{U}+\mathbf{E}$ be the (measured) noisy version, where $\mathbf{E}$ is a matrix of error values. It is commonly assumed that elements of $\mathbf{E}$ are obtained from a zero-mean Gaussian distribution with some variance $\sigma^{2}$.

Let $\lambda_{i}$ be the singular values of $\mathbf{U}$ arranged in descending order and $\mathbf{l}_{i}$ and $\mathbf{r}_{i}$ the corresponding left and right eigenvectors respectively, i.e. $\mathbf{U}_{(m\times n)}=\mathbf{L}_{(m\times m)}\mathbf{S}_{(m\times n)}\mathbf{R}_{(n\times n)}^{T}$, where $\mathbf{l}_{i}$ and $\mathbf{r}_{i}$ are the columns respectively of $\mathbf{L}$ and $\mathbf{R}$. Let $\widetilde{\lambda_{i}}$, $\widetilde{\mathbf{l}_{i}}$ and $\widetilde{\mathbf{r}_{i}}$ be the correpsonding quantities for $\widetilde{\mathbf{U}}$.

I would like to estimate the singular values and eigenvectors of $\mathbf{U}$ knowing only the corresponding quantities of $\widetilde{\mathbf{U}}$ and the variance $\sigma^{2}$ of the error. Therefore, I would like to know the answer to the following two questions:

1. what is the relationship between $\widetilde{\lambda_{i}}$ and $\lambda_{i}$?
2. what is the relationship between the eigenvectors of $\widetilde{\mathbf{U}}$ and those of $\mathbf{U}$?
-
I think the $\mathbf{l}_i$ and $\mathbf{r}_i$ should be singular vectors. $\:$ – Ricky Demer Nov 8 '12 at 16:40
Perhaps this is a question of terminology, but what i mean is that the $\mathbf{l}_i$ and the $\mathbf{r}_i$ are eigenvectors of $\mathbf{UU}^T$ and $\mathbf{U}^T\mathbf{U}$ respectively. – Sankara Subramanian Nov 8 '12 at 17:19

You might look at Wikipedia: http://en.wikipedia.org/wiki/Eigenvalue_perturbation#Summary

This is for eigenvalues, not singular values, but singular values are eigenvalues of M*M', so one may deduce one from another. Also it discusses generalized eigenvalue problem so you should put M=id, $\delta M=0$ Also it is for non-random perturbation - but using 3-sigma rule you can reduce you random task to this non-random.

Let me briefly comment. Consider not pertubation $\tilde K = K + \Delta$, for simplicity assume that K is diagonal (so $\lambda_i = K_{ii}$), then the first formula says that first order perturbation of i-th eigenvalue $K_{ii}$ is given by $\Delta_{ii}$ i.e. by the diagonal element of perturbation matrix.

Since any matrix can be diagonalized (well, generic matrix) so without diagonality assumption you will have that perturbation to $\lambda_i$ is given by matrix element of $\Delta$ equal $v_i' * \Delta *v_i$ where $v_i$ is i-th eigenvector of $K$.

Now it is interesting to discuss what happens with eigenvector. It is important to understand the following idea the magnitude of perturbation of eigenvector depends not only on the magnitude of $\Delta$, but on the difference $\lambda_i - \lambda_{j(i)}$ where $\lambda_{j(i)}$ is eigenvalue nearest to $\lambda_i$.

You can see this difference in the denominator of the second formula - so if you have two close eigenvalues - you have problem - meaning that even small perturbation of the matrix may cause large perturbation of the corresponding vectors.

This should be written in any numerical linear algebra text book, sorry I cannot suggest any, since I learnt it from quantum mechanics textbook - this is also discussed in any quantum mechanics textbook.

-
Thanks. Thanks also to Prof. Van Vu, who pointed me to his recent work 'Singular vectors under random perturbation' (on arXiv), which addresses precisely my question, especially when matrix U is of low rank. – Sankara Subramanian Nov 11 '12 at 3:46

It seems to be a classical question (handled by methods) of "factor analysis". There the problem is attacked using the covariance-, or correlation matrix, in this case possibly simply $\small \widetilde C = \widetilde U \cdot \widetilde U^{\Tiny T} /n$ (without or with centering) and then some "pca","paf" or "maximum likelihood" factor extraction appended, based on your assumtion of characteristics of $E$ resp. $\small E \cdot E^{\Tiny T}$, i.e. estimates about the variances of the error.
But there is less "classical" method, possibly even better suited for your case, called ICA - unfortunately I do not exactly know how this is computed and how it is approached at all. (The wikipedia links may give a first impression, there is much more available even in internet sources)

-
Yes, certainly the covariance or correlation matrix may be used to identify the singular values and eigenvectors of $\widetilde{\mathbf{C}}$, but what I am trying to do is to relate the singular values of $\widetilde{\mathbf{U}}$ to those of $\mathbf{U}$. I came across Weyl's inequality for the singular values of the sum of any two matrices $\mathbf{A}$ and $\mathbf{B}$: $\lambda_{i+j-1}(\mathbf{A}+\mathbf{B}) \le \lambda_{i}(\mathbf{A}) + \lambda_j(\mathbf{B})$ – Sankara Subramanian Nov 9 '12 at 11:24
(continued) If we identify $\mathbf{A}$ and $\mathbf{B}$ with my $\mathbf{U}$ and $\mathbf{E}$ respectively and set $j=1$, then I get the following bound on the singular values of $\widetilde{\mathbf{U}}$ in terms of those of $\mathbf{U}$: $\lambda_{i}(\widetilde{\mathbf{U}}) \le \lambda_{i}(\mathbf{U}) + \lambda_1(\mathbf{E})$. However, a few numerical experiments that I have done indicate that these bounds are are too wide. – Sankara Subramanian Nov 9 '12 at 11:24
(continued) In any case, I have some bounds on the singular values. But, I have no idea how to proceed with the eigenvectors of $\widetilde{\mathbf{U}}$. The numerical experiments again indicate that the eigenvectors corresponding to the largest singular values are least affected by the addition of noise. As we increase $i$, the index of the eigenvector, the effect of noise is increasingly felt. But, how do we quantify the noise in these eigenvectors as a function of the variance $\sigma^2$ and the eigenvector index $i$ and possibly the singular values $\lambda_i$` themselves? – Sankara Subramanian Nov 9 '12 at 11:32
@Sankara: Sorry, I had no time for this yesterday. Well, I on't have information about the amount of distortion by the error, which goes to the principal axes, after data is rotated into such a position. Only it is somehow obvious to me, that the relative amount of coordinate-distortion is smaller in the direction of the principal axis, where the squared values of coordinates by U are maximized. (But this is surely not that what your after, sorry) – Gottfried Helms Nov 11 '12 at 14:11