Near-optimal compressed sensing of a class of sparse low-rank matrices via sparse power factorization

Kiryung Lee, Yihong Wu, Yoram Bresler

Research output: Contribution to journalArticlepeer-review


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 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-one 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-one case. Numerical results show that SPF and SCSPF empirically outperform convex programmings using the best known combinations of mixed norm and nuclear norm.

Original languageEnglish (US)
Pages (from-to)1666-1698
Number of pages33
JournalIEEE Transactions on Information Theory
Issue number3
StatePublished - Mar 2018


  • Compressed sensing
  • alternating minimization
  • non-convex optimization
  • restricted isometry property
  • sample complexity
  • sparse and low-rank matrix

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Near-optimal compressed sensing of a class of sparse low-rank matrices via sparse power factorization'. Together they form a unique fingerprint.

Cite this