On the Power of Truncated SVD for General High-rank Matrix Estimation Problems
This provides theoretical guarantees for truncated SVD in high-rank settings, addressing problems in matrix completion, denoising, and covariance estimation for data analysis and machine learning, though it is incremental as it builds on existing SVD methods.
The paper tackles the problem of estimating high-rank positive semi-definite matrices using truncated SVD, showing that it yields multiplicative approximations in Frobenius norm under spectral norm closeness. Results include sample complexity bounds for matrix completion, denoising, and covariance estimation, with guarantees like (1+O(ε)) relative error.
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.