# Perturbation bound for SVD (denoising for a low-rank matrix)

Suppose that $$A$$ is a $$m\times n$$ matrix with rank $$r$$, and we observe the matrix $$\hat A = A + E$$. Let $$\hat A_r$$ be the $$r$$-SVD of $$\hat A$$. That is, if $$A=U\Sigma V^\top$$ is the singular value decomposition of $$A$$, then $$\hat A_r = U\Sigma_r V^\top$$, where $$\Sigma_r$$ keeps only the top $$r$$ entries.

What is the best possible bound for $$||A-\hat A_r||_F$$ in terms of $$||E||$$?

My guess is that there is a bound of the form $$||A-\hat A_r||_F\le C\sqrt r||E||$$ (and this is what I am hoping for for my application), as this says that doing a SVD can "denoise" a noisy observation of a low-rank matrix---compare with the error in $$\hat A$$, which is only bounded as $$||\hat A - A||_F\le \sqrt{\min\{m,n\}}||E||$$). I would also be OK with a high-probability bound when E is a random matrix satisfying some general conditions (that are less restrictive than e.g., having iid entries).

I feel this is a standard result but I am having trouble finding bounds for $$||A-\hat A_r||_F$$ in the literature. Wedin's Theorem give bounds for the perturbation to the singular values and singular vectors, but this is not what I am interested in. Naive application of Wedin's Theorem gives a factor of $$\frac{1}{\sigma_r}$$, where $$\sigma_1\ge \sigma_2\ge \cdots$$ are the singular values of A.

In the case where $$r=1$$, the desired bound does follow from Wedin's Theorem. We can split into 2 cases: (I am not being careful about constants.)

1. $$||A||\le 4||E||$$: Then $$||\hat A||\le 5||E||$$, so $$||\hat A_1||\le ||\hat A||\le 5||E||$$.
2. $$||A||> 4||E||$$: Then we can apply Wedin's Theorem to get that the angle between the top singular vectors of $$v$$ and $$\hat v$$ is $$\sin \angle (v,\hat v)\le \frac{||E||}{||A||-||E||}\le \frac 43 \frac{||E||}{||A||}$$. Combined with Weyl's bound for the perturbation to the singular value $$\sigma_1(\hat A)\in [||A||-||E||, ||A||+||E||]$$, we can obtain a bound for $$||A-\hat A_1||_F \le C||E||$$. The $$||A||$$ in the denominator of Wedin's Theorem is canceled out by multiplication by the singular value $$||A||$$.

For general rank $$r$$, however, this is not so straightforward because the singular values can be different sizes.

• Related: mathoverflow.net/questions/312536/… (but the question there is asked in a confusing way), stats.stackexchange.com/questions/371233/… – Holden Lee Oct 8 '20 at 17:27
• If you care mostly about the random case, then random perturbations are often a lot better than deterministic bounds like weyl's inequality or the davis-kahan theorem. A reference is this paper by Van vu that gives bounds on how singular vectors change from random perturbations is this: arxiv.org/pdf/1004.2000.pdf. I'm sure there are other related works that can be found by looking at the papers that cite this. – Sandeep Silwal Oct 8 '20 at 17:45

A simple argument shows that such a bound exists. We have \begin{align} ||\hat A_r - A||_F &\le \sqrt{2r} ||\hat A_r - A||_2 \\ &\le \sqrt{2r} (||\hat A_r - \hat A||_2 + ||\hat A - A||_2)\\ & \le 2\sqrt{2r}||E|| \end{align} where the first inequality follows from $$||\hat A_r - A||$$ having rank $$\le 2r$$, the second follows from triangle inequality, and the thir follows from Weyl's Theorem: $$||\hat A_r - \hat A||_2 \le \sigma_{r+1}(\hat A) \le \sigma_{r+1}(A) + ||E||=||E||$$.