Near-Optimal Compressed Sensing of a Class of Sparse Low-Rank Matrices Via Sparse Power Factorization

摘要

Compressed sensing of simultaneously sparse and low-rank matrices enablesrecovery of sparse signals from a few linear measurements of their bilinearform. One important question is how many measurements are needed for a stablereconstruction in the presence of measurement noise. Unlike conventionalcompressed sensing for sparse vectors, where convex relaxation via the$ell_1$-norm achieves near optimal performance, for compressed sensing ofsparse low-rank matrices, it has been shown recently Oymak et al. that convexprogrammings using the nuclear norm and the mixed norm are highly suboptimaleven in the noise-free scenario. We propose an alternating minimization algorithm called sparse powerfactorization (SPF) for compressed sensing of sparse rank-one matrices. For aclass of signals whose sparse representation coefficients are fast-decaying,SPF achieves stable recovery of the rank-1 matrix formed by their outer productand requires number of measurements within a logarithmic factor of theinformation-theoretic fundamental limit. For the recovery of general sparselow-rank matrices, we propose subspace-concatenated SPF (SCSPF), which hasanalogous near optimal performance guarantees to SPF in the rank-1 case.Numerical results show that SPF and SCSPF empirically outperform convexprogrammings using the best known combinations of mixed norm and nuclear norm.