Robust recovery of low-rank matrices with non-orthogonal sparse decomposition from incomplete measurements

Massimo Fornasier, Johannes Maly and Valeriya Naumova

Applied Mathematics and Computation, 2021, vol. 392, issue C

Abstract: We consider the problem of recovering an unknown effectively (s1, s2)-sparse low-rank-R matrix X with possibly non-orthogonal rank-1 decomposition from incomplete and inaccurate linear measurements of the form y=A(X)+η, where η is an ineliminable noise11With “ineliminable” we mean that the focus of the paper is not on recovery from exact y=A(X) measurements, rather on the stable recovery under severe measurement noise.. We first derive an optimization formulation for matrix recovery under the considered model and propose a novel algorithm, called Alternating Tikhonov regularization and Lasso (A-T-LAS2,1), to solve it. The algorithm is based on a multi-penalty regularization, which is able to leverage both structures (low-rankness and sparsity) simultaneously. The algorithm is a fast first order method, and straightforward to implement. We prove global convergence for any linear measurement model to stationary points and local convergence to global minimizers. By adapting the concept of restricted isometry property from compressed sensing to our novel model class, we prove error bounds between global minimizers and ground truth, up to noise level, from a number of subgaussian measurements scaling as R(s1+s2), up to log-factors in the dimension, and relative-to-diameter distortion. Simulation results demonstrate both the accuracy and efficacy of the algorithm, as well as its superiority to the state-of-the-art algorithms in strong noise regimes and for matrices whose singular vectors do not possess exact (joint-) sparse support.

Keywords: Low-rank and sparse recovery; Bilinear compressed sensing; Multi-penalty regularization; Iterative soft-thresholding (LASSO) (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S009630032030655X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:392:y:2021:i:c:s009630032030655x

DOI: 10.1016/j.amc.2020.125702

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().