Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation
  Recently, Musco and Woodruff (FOCS, 2017) showed that given an $n \times n$
positive semidefinite (PSD) matrix $A$, it is possible to compute a
$(1+\epsilon)$-approximate relative-error low-rank approximation to $A$ by
querying $O(nk/\epsilon^{2.5})$ entries of $A$ in time $O(nk/\epsilon^{2.5} +n
k^{\omega-1}/\epsilon^{2(\omega-1)})$. They also showed that any relative-error
low-rank approximation algorithm must query $\Omega(nk/\epsilon)$ 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/\epsilon)$
entries of $A$ and outputs a relative-error low-rank approximation in
$O(n(k/\epsilon)^{\omega-1})$ time. Note, our running time improves that of
Musco and Woodruff, and matches the information-theoretic lower bound if the
matrix-multiplication exponent $\omega$ 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/\epsilon^{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/\epsilon)$ query algorithm, which is optimal. Our algorithm
applies to all distance matrices that arise from metrics satisfying
negative-type inequalities, including $\ell_1, \ell_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.
