On the Power of Truncated SVD for General High-rank Matrix Estimation
  Problems
  We show that given an estimate $\widehat{A}$ that is close to a general
high-rank positive semi-definite (PSD) matrix $A$ in spectral norm (i.e.,
$\|\widehat{A}-A\|_2 \leq \delta$), the simple truncated SVD of $\widehat{A}$
produces a multiplicative approximation of $A$ in Frobenius norm. This
observation leads to many interesting results on general high-rank matrix
estimation problems, which we briefly summarize below ($A$ is an $n\times n$
high-rank PSD matrix and $A_k$ is the best rank-$k$ approximation of $A$):
  (1) High-rank matrix completion: By observing
$\Omega(\frac{n\max\{\epsilon^{-4},k^2\}\mu_0^2\|A\|_F^2\log
n}{\sigma_{k+1}(A)^2})$ elements of $A$ where $\sigma_{k+1}\left(A\right)$ is
the $\left(k+1\right)$-th singular value of $A$ and $\mu_0$ is the incoherence,
the truncated SVD on a zero-filled matrix satisfies $\|\widehat{A}_k-A\|_F \leq
(1+O(\epsilon))\|A-A_k\|_F$ with high probability.
  (2)High-rank matrix de-noising: Let $\widehat{A}=A+E$ where $E$ is a Gaussian
random noise matrix with zero mean and $\nu^2/n$ variance on each entry. Then
the truncated SVD of $\widehat{A}$ satisfies $\|\widehat{A}_k-A\|_F \leq
(1+O(\sqrt{\nu/\sigma_{k+1}(A)}))\|A-A_k\|_F + O(\sqrt{k}\nu)$.
  (3) Low-rank Estimation of high-dimensional covariance: Given $N$
i.i.d.~samples $X_1,\cdots,X_N\sim\mathcal N_n(0,A)$, can we estimate $A$ with
a relative-error Frobenius norm bound? We show that if $N =
\Omega\left(n\max\{\epsilon^{-4},k^2\}\gamma_k(A)^2\log N\right)$ for
$\gamma_k(A)=\sigma_1(A)/\sigma_{k+1}(A)$, then $\|\widehat{A}_k-A\|_F \leq
(1+O(\epsilon))\|A-A_k\|_F$ with high probability, where
$\widehat{A}=\frac{1}{N}\sum_{i=1}^N{X_iX_i^\top}$ is the sample covariance.
