A Fast Algorithm for Low Rank + Sparse column-wise Compressive Sensing

This paper focuses studies the following low rank + sparse (LR+S) column-wise compressive sensing problem. We aim to recover an $n\times q$ matrix, ${\text{X}}^{\ast }=[{\text{x}}_1^{\ast },{\text{x}}_2^{\ast },\cdots ,{\text{x}}_q^{\ast }]$ from $m$ independent linear projections of each of its $q$ columns, given by ${\text{y}}_k:={\text{A}}_k{\text{x}}_k^{\ast }$, $k\in [q]$. Here, ${\text{y}}_k$ is an $m$-length vector with $m<n$. We assume that the matrix ${\text{X}}^{\ast }$ can be decomposed as ${\text{X}}^{\ast }={\text{Ł}}^{\ast }+{\mathrm{\S }}^{\ast }$, where ${\text{Ł}}^{\ast }$ is a low rank matrix of rank $r<<\min (n,q)$ and ${\mathrm{\S }}^{\ast }$ is a sparse matrix. Each column of $\mathrm{\S }$ contains $\rho$ non-zero entries. The matrices ${\text{A}}_k$ are known and mutually independent for different $k$. To address this recovery problem, we propose a novel fast GD-based solution called AltGDmin-LR+S, which is memory and communication efficient. We numerically evaluate its performance by conducting a detailed simulation-based study.