4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Related: mathoverflow.net/questions/312536/… (but the question there is asked in a confusing way), stats.stackexchange.com/questions/371233/… $\endgroup$ – Holden Lee Oct 8 '20 at 17:27
  • 3
    $\begingroup$ 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. $\endgroup$ – Sandeep Silwal Oct 8 '20 at 17:45
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.