Sketching sparse low-rank matrices with near-optimal sample- and time-complexity

We consider the problem of recovering an n×n 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 dimension n. Our sketching operator, based on a scheme for compressed sensing by Li et al. [1] and Bakshi et al. [2], 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. The theoretical result is validated by numerical simulations.