Sketching Sparse Low-Rank Matrices With Near-Optimal Sample- and Time-Complexity Using Message Passing

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 extensive numerical simulations and comparisons with existing schemes that use convex optimization for recovery.