Singular Value Decomposition of Noisy Matrices

Question

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}$?

Answer 1

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.

Answer 2

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)