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.