We study the problem of approximating a rank-r p×p symmetric and positive semidefinite matrix. Assume that K is structured as K = [A B; B^T C], where A is m×m, B is m×n, C is n×n, m « n and p = m+n. One technique for approximation is the Nyström method, which estimates the matrix C using the full blocks A and B. We focus on the setting where only a few entries are sampled in the B block. By introducing a novel sampling model, we show that this problem can be equivalently formulated as a low-rank matrix recovery problem with respect to a specific basis. Under mild assumptions, we show that B can be exactly recovered from very few sparse samples. The implications of this for kernel approximation are discussed.