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 δ$), 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 $Ω(\frac{n\max\{ε^{-4},k^2\}μ_0^2\|A\|_F^2\log n}{σ_{k+1}(A)^2})$ elements of $A$ where $σ_{k+1}\left(A\right)$ is the $\left(k+1\right)$-th singular value of $A$ and $μ_0$ is the incoherence, the truncated SVD on a zero-filled matrix satisfies $\|\widehat{A}_k-A\|_F \leq (1+O(ε))\|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 $ν^2/n$ variance on each entry. Then the truncated SVD of $\widehat{A}$ satisfies $\|\widehat{A}_k-A\|_F \leq (1+O(\sqrt{ν/σ_{k+1}(A)}))\|A-A_k\|_F + O(\sqrt{k}ν)$. (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 = Ω\left(n\max\{ε^{-4},k^2\}γ_k(A)^2\log N\right)$ for $γ_k(A)=σ_1(A)/σ_{k+1}(A)$, then $\|\widehat{A}_k-A\|_F \leq (1+O(ε))\|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.