Robust Recovery of Low-Rank Matrices with Non-Orthogonal Sparse Decomposition from Incomplete Measurements
Authors:
Preprint
Abstract
We consider the problem of recovering an unknown effectively $(s_1,s_2)$-sparse low-rank-$R$ matrix $X$ with possibly non-orthogonal rank-$1$ decomposition from incomplete and inaccurate linear measurements of the form $y = \mathcal A (X) + \eta$, where $\eta$ is an ineliminable 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-LA$\text{S}_{2,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(s_1+s_2)$, 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
All Related Versions
This publication has 22 references indexed in Scilit:
- Adaptive multi-penalty regularization based on a generalized Lasso pathApplied and Computational Harmonic Analysis, 2020
- Rapid, robust, and reliable blind deconvolution via nonconvex optimizationApplied and Computational Harmonic Analysis, 2019
- Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind DeconvolutionFoundations of Computational Mathematics, 2019
- Conditions on optimal support recovery in unmixing problems by means of multi-penalty regularizationInverse Problems, 2016
- Sparsity-enforcing regularisation and ISTA revisitedInverse Problems, 2016
- Minimization of multi-penalty functionals by alternating iterative thresholding and optimal parameter choicesInverse Problems, 2014
- Suprema of Chaos Processes and the Restricted Isometry PropertyCommunications on Pure and Applied Mathematics, 2014
- One‐Bit Compressed Sensing by Linear ProgrammingCommunications on Pure and Applied Mathematics, 2013
- Iterative hard thresholding for compressed sensingApplied and Computational Harmonic Analysis, 2009
- Learning the parts of objects by non-negative matrix factorizationNature, 1999