A-T-LAS$_{2,1}$: A Multi-Penalty Approach to Compressed Sensing of Low-Rank Matrices with Sparse Decompositions
Authors:
Preprint
Abstract
Compressed Sensing is about recovering an unknown vector of dimension $n$ from $m \ll n$ linear measurements. This task becomes possible, for instance, when few entries of the vector have large magnitude and, hence, the vector is essentially of low intrinsic dimension. If one wishes to recover an $n_1\times n_2$ matrix instead, low-rankness can be added as sparsity structure of low intrinsic dimensionality. For this purpose we propose a novel algorithm, which we call Alternating Tikhonov regularization and Lasso (A-T-LAS$_{2,1}$). It is based on a multi-penalty regularization for recovery of low-rank matrices with approximately sparse singular vectors, which is able to leverage both structures (low-rankness and sparsity) simultaneously and effectively reduce further the number of necessary measurements with respect to the sole use of one of the two sparsity structures. We provide nearly-optimal recovery guarantees of A-T-LAS$_{2,1}$. The analysis is surprisingly relatively simple, e.g., compared to the one of other similar approaches such as Sparse Power Factorization (SPF). It relies on an adaptation of restricted isometry property to low-rank and approximately sparse matrices, LASSO technique, and results on proximal alternating minimization. We show that A-T-LAS$_{2,1}$ is more efficient than convex relaxation and exhibits similar performance to the state of the art method SPF, outperforming it in strong noise regimes and for matrices whose singular vectors do not possess exact (joint-) sparse support. Moreover, contrary to SPF, A-T-LAS$_{2,1}$, if properly initialized, is shown to converge even for measurements not fulfilling the restricted isometry property to matrices with some guaranteed sparsity and minimal discrepancy to data.
Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Adaptive multi-penalty regularization based on a generalized Lasso pathApplied and Computational Harmonic Analysis, 2020
- 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
- PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex ProgrammingCommunications on Pure and Applied Mathematics, 2012
- Iterative hard thresholding for compressed sensingApplied and Computational Harmonic Analysis, 2009
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samplesApplied and Computational Harmonic Analysis, 2009
- On sparse reconstruction from Fourier and Gaussian measurementsCommunications on Pure and Applied Mathematics, 2007
- Stable signal recovery from incomplete and inaccurate measurementsCommunications on Pure and Applied Mathematics, 2006
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraintCommunications on Pure and Applied Mathematics, 2004
- Application of nonlinear sampling schemes to COSY-type spectraJournal of Biomolecular NMR, 1993