  We consider the problem of recovering an $n_1 \times n_2$ low-rank matrix
with $k$-sparse singular vectors from a small number of linear measurements
(sketch). We propose a sketching scheme and an algorithm that can recover the
singular vectors with high probability, with a sample complexity and running
time that both depend only on $k$ and not on the ambient dimensions $n_1$ and
$n_2$. Our sketching operator, based on a scheme for compressed sensing by Li
et al. and Bakshi et al., uses a combination of a sparse parity check matrix
and a partial DFT matrix. Our main contribution is the design and analysis of a
two-stage iterative algorithm which recovers the singular vectors by exploiting
the simultaneously sparse and low-rank structure of the matrix. We derive a
nonasymptotic bound on the probability of exact recovery, which holds for any
$n_1\times n_2 $ sparse, low-rank matrix. We also show how the scheme can be
adapted to tackle matrices that are approximately sparse and low-rank. The
theoretical results are validated by numerical simulations and comparisons with
existing schemes that use convex programming for recovery.
