Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices
  We show how to compute a relative-error low-rank approximation to any
positive semidefinite (PSD) matrix in sublinear time, i.e., for any $n \times
n$ PSD matrix $A$, in $\tilde O(n \cdot poly(k/\epsilon))$ time we output a
rank-$k$ matrix $B$, in factored form, for which $\|A-B\|_F^2 \leq
(1+\epsilon)\|A-A_k\|_F^2$, where $A_k$ is the best rank-$k$ approximation to
$A$. When $k$ and $1/\epsilon$ are not too large compared to the sparsity of
$A$, our algorithm does not need to read all entries of the matrix. Hence, we
significantly improve upon previous $nnz(A)$ time algorithms based on oblivious
subspace embeddings, and bypass an $nnz(A)$ time lower bound for general
matrices (where $nnz(A)$ denotes the number of non-zero entries in the matrix).
We prove time lower bounds for low-rank approximation of PSD matrices, showing
that our algorithm is close to optimal. Finally, we extend our techniques to
give sublinear time algorithms for low-rank approximation of $A$ in the (often
stronger) spectral norm metric $\|A-B\|_2^2$ and for ridge regression on PSD
matrices.
