We show how, given an n x n positive semidefinite (PSD) matrix A, to obtain a (1+eps)-approximate relative error low rank approximation to A by querying only O(nk/eps) entries of A, which is significantly *sublinear* in the total number of entries of A. Although for general matrices sublinear time relative error approximations are impossible, for PSD matrices one can learn a lot of information about off-diagonal entries from the diagonal entries. We also show a matching Omega(nk/eps) lower bound. We then extend our algorithm to negative-type distance matrices, giving a significantly sublinear and optimal O(nk/eps) query algorithm, improving earlier bicriteria rank algorithms. We also discuss extensions to matrices that have been corrupted with noise. Based on a recent work with Bakshi and Chepurko (FOCS, 2020) and earlier work with Musco (FOCS, 2017).