  Compressed sensing of simultaneously sparse and low-rank matrices enables
recovery of sparse signals from a few linear measurements of their bilinear
form. One important question is how many measurements are needed for a stable
reconstruction in the presence of measurement noise. Unlike conventional
compressed sensing for sparse vectors, where convex relaxation via the
$\ell_1$-norm achieves near optimal performance, for compressed sensing of
sparse low-rank matrices, it has been shown recently Oymak et al. that convex
programmings using the nuclear norm and the mixed norm are highly suboptimal
even in the noise-free scenario.
  We propose an alternating minimization algorithm called sparse power
factorization (SPF) for compressed sensing of sparse rank-one matrices. For a
class of signals whose sparse representation coefficients are fast-decaying,
SPF achieves stable recovery of the rank-1 matrix formed by their outer product
and requires number of measurements within a logarithmic factor of the
information-theoretic fundamental limit. For the recovery of general sparse
low-rank matrices, we propose subspace-concatenated SPF (SCSPF), which has
analogous near optimal performance guarantees to SPF in the rank-1 case.
Numerical results show that SPF and SCSPF empirically outperform convex
programmings using the best known combinations of mixed norm and nuclear norm.
