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

DOI10.1109/TIT.2017.2784479zbMATH Open1390.94261arXiv1312.0525MaRDI QIDQ4566735FDOQ4566735

Author name not available (Why is that?)

Publication date: 27 June 2018

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: 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 $el{l}_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.

Full work available at URL: https://arxiv.org/abs/1312.0525

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (14)

• Low-Rank PSD Approximation in Input-Sparsity Time
• Sparse power factorization: balancing peakiness and sample complexity
• A novel blind restoration and reconstruction approach for CT images based on sparse representation and hierarchical Bayesian-MAP
• Self-calibration and biconvex compressive sensing
• A geometric analysis of phase retrieval
• Sparse Model Uncertainties in Compressed Sensing with Application to Convolutions and Sporadic Communication
• Blind Deconvolution by a Steepest Descent Algorithm on a Quotient Manifold
• Optimal Injectivity Conditions for Bilinear Inverse Problems with Applications to Identifiability of Deconvolution Problems
• Riemannian thresholding methods for row-sparse and low-rank matrix recovery
• Jointly low-rank and bisparse recovery: Questions and partial answers
• Parametrized quasi-soft thresholding operator for compressed sensing and matrix completion
• Robust sensing of low-rank matrices with non-orthogonal sparse decomposition
• Sparse blind deconvolution and demixing through \(\ell_{1,2}\)-minimization
• Robust recovery of low-rank matrices with non-orthogonal sparse decomposition from incomplete measurements

This page was built for publication: Near-Optimal Compressed Sensing of a Class of Sparse Low-Rank Matrices Via Sparse Power Factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4566735)