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

Question

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.

Answer 1

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

It remains an interesting question what the best constant is.