On the Power of Truncated SVD for General High-rank Matrix Estimation Problems
share
We show that given an estimate A that is close to a general high-rank positive semi-definite (PSD) matrix A in spectral norm (i.e., A-A_2 ≤δ), the simple truncated SVD of 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× n high-rank PSD matrix and A_k is the best rank-k approximation of A): (1) High-rank matrix completion: By observing Ω(n{ϵ^-4,k^2}μ_0^2A_F^2 n/σ_k+1(A)^2) elements of A where σ_k+1(A) is the (k+1)-th singular value of A and μ_0 is the incoherence, the truncated SVD on a zero-filled matrix satisfies A_k-A_F ≤ (1+O(ϵ))A-A_k_F with high probability. (2)High-rank matrix de-noising: Let 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 A satisfies A_k-A_F ≤ (1+O(√(ν/σ_k+1(A))))A-A_k_F + O(√(k)ν). (3) Low-rank Estimation of high-dimensional covariance: Given N i.i.d. samples X_1,...,X_N∼ N_n(0,A), can we estimate A with a relative-error Frobenius norm bound? We show that if N = Ω(n{ϵ^-4,k^2}γ_k(A)^2 N) for γ_k(A)=σ_1(A)/σ_k+1(A), then A_k-A_F ≤ (1+O(ϵ))A-A_k_F with high probability, where A=1/N∑_i=1^NX_iX_i^ is the sample covariance.
READ FULL TEXT