Part of Advances in Neural Information Processing Systems 30 (NIPS 2017)
Simon S. Du, Yining Wang, Aarti Singh
We show that given an estimate ^\matA that is close to a general high-rank positive semi-definite (PSD) matrix \matA in spectral norm (i.e., ‖), the simple truncated Singular Value Decomposition of \widehat{\mat A} produces a multiplicative approximation of \mat A in Frobenius norm. This observation leads to many interesting results on general high-rank matrix estimation problems: 1.High-rank matrix completion: we show that it is possible to recover a {general high-rank matrix} \mat A up to (1+\varepsilon) relative error in Frobenius norm from partial observations, with sample complexity independent of the spectral gap of \mat A. 2.High-rank matrix denoising: we design algorithms that recovers a matrix \mat A with relative error in Frobenius norm from its noise-perturbed observations, without assuming \mat A is exactly low-rank. 3.Low-dimensional estimation of high-dimensional covariance: given N i.i.d.~samples of dimension n from \mathcal N_n(\mat 0,\mat A), we show that it is possible to estimate the covariance matrix \mat A with relative error in Frobenius norm with N\approx n,improving over classical covariance estimation results which requires N\approx n^2.