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 a good 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.

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.