Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation

Recently, Musco and Woodruff (FOCS, 2017) showed that given an n × n positive semidefinite (PSD) matrix A, it is possible to compute a (1+ε)-approximate relative-error low-rank approximation to A by querying O(nk/ε2.5) entries of A in time O(nk/ε2.5 +n kω-1/ε2(ω-1)). They also showed that any relative-error low-rank approximation algorithm must query Omega(nk/ε) entries of A, this gap has since remained open. Our main result is to resolve this question by obtaining an optimal algorithm that queries O(nk/ε) entries of A and outputs a relative-error low-rank approximation in O(n(k/ε)ω-1) time. Note, our running time improves that of Musco and Woodruff, and matches the information-theoretic lower bound if the matrix-multiplication exponent ω is 2. We then extend our techniques to negative-type distance matrices. Bakshi and Woodruff (NeurIPS, 2018) showed a bi-criteria, relative-error low-rank approximation which queries O(nk/ε2.5) entries and outputs a rank-(k+4) matrix. We show that the bi-criteria guarantee is not necessary and obtain an O(nk/ε) query algorithm, which is optimal. Our algorithm applies to all distance matrices that arise from metrics satisfying negative-type inequalities, including ℓ1, ℓ2, spherical metrics and hypermetrics. Next, we introduce a new robust low-rank approximation model which captures PSD matrices that have been corrupted with noise. While a sample complexity lower bound precludes sublinear algorithms for arbitrary PSD matrices, we provide the first sublinear time and query algorithms when the corruption on the diagonal entries is bounded. As a special case, we show sample-optimal sublinear time algorithms for low-rank approximation of correlation matrices corrupted by noise.