How eigenvalue perturbation affects back to the original matrix?

Question

Both "eigenvalue perturbation" and "matrix perturbation" seems to study this scenario that given a matrix $A$, if we add something to it like $\tilde{A} = A+E$, how will the eigenvalues of $\tilde{A}$ distribute differently from the eigenvalues of $A$.

I want to ask a reverse question here: given $A=USV^T$, and we change $\tilde{S} = SD$, then how will $\tilde{A}=U\tilde{S}V^T$ distribute differently from $A$?. What are some relevant studies that I can look into?

I guess this is very likely to be a hard problem in general, but I'm currently only hoping to find some solution to a more practical problem.

To reiterate the problem here briefly: truncated SVD (TSVD) is well known as an effective method for denoising data, which basically means that: for $\tilde{A} = A + E$, we take the SVD of $ \tilde{A} = U\tilde{S}V^T$, and then reconstruct with first $k$ dominant singular values $\hat{A} = \sum_i^kU_i\tilde{S}_iV_i^T$, then empirically $\hat{A}$ is a better approximation of $A$ than $\tilde{A}$. I wonder how to show this conclusion officially, given whatever properties we need to assume about $A$, $E$, and $k$.

I tried to make some progress in a more specific setting, say $A$ is symmetric, p.s.d, block diagonal structure, with all elements to be positive, and the expectation of these values (denoted as $a$) is greater than the expectation of values in $E$ (with a gap denoted as $c$). $E$ is a dense matrix with all elements to be positive. Now I can work with $\hat{A}_{ij} = \tilde{A}_{ij} - \delta_{ij}$, then I got stuck and need some help:

• With large enough $k$, can I just assume $\delta$ are uniformly distributed across the entire matrix?
• If not, is there any relation between the $\delta$ within block-diagonal and the $\delta$ off-diagonal that can be represented by $A, E, a,c,k$?

Since this is a relatively long post and I asked a hierarchy of questions, I put my questions in bold, any insights of any of these questions will be helpful!

Answer 1

If you just ask about the relation between $A = USV^T$ and $\tilde A = U\tilde SV^T$ it is just that (for the spectral or the Frobenius norm) it holds that $$ \|A-\tilde A\| = \|USV^T - U\tilde SV^T\| = \|S-\tilde S\|, $$ so the error in $A$ is just the error in the perturbation in the eigenvalues. It is a little more intricate to see what happens with the solutions of $\tilde Ax =b$ for vanishing perturbation especially in the underdetermined case, but this is well studied also for bounded operators in Hilbert spaces (see, e.g. "Regularization of Inverse Problems" by Engl, Hanke and Neubauer).

If you are more interested in the case where $A$ is interpreted as an image and you aim to denoise $A$ by truncating its SVD I would say:

• This is a terrible idea for denoising - other methods are much better (and simpler…).
• It does not work in general, but it works (quite bad, but it does) in practice and this is due to the fact that, empirically, singular vectors corresponding to small singular values are oscillating more than the ones for large singular values, hence, removing the oscillatory components in $USV^T$ reduces overall oscillations.
• The last point is really empirical. You can easily construct examples of $A$ where $\tilde A$ obtained by TSVD is more noisy (just assign the oscillatory singular vectors to the large singular values…).

On your paragraph

Truncated SVD (TSVD) is well known as an effective method for denoising data, which basically means that we take the SVD of $ \tilde{A} = USV^T$, and then reconstruct with first $k$ dominant singular values $\hat{A} = \sum_i^kU_iS_iV_i^T$, then empirically $\hat{A}$ is a better approximation of $A$ than $\tilde{A}$.

There seems to be a misunderstanding. In what you write $\tilde A = A$, so $\hat A$ is not a better approximation of $A$, because $\tilde A$ is exact. What you refer to may be the fact that for $A$ with large condition number (i.e. large ratio of largest and smallest singular value) and some $x^\dagger$ and $b = Ax^\dagger$ and a perturbation $b^\delta$ with small $\| b-b^\delta\|$ it is true that the solution $\tilde A^+ b^\delta$ is a better approximation to $x^\dagger$ than $A^+ b^\delta$ (where $A^+$ denotes the Moore-Penrose pseudo inverse), but only for suitably chosen truncation…