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 × q matrix, ${{\mathbf{X}}^{\ast}} = \left[ {x_1^{\ast},x_2^{\ast}, \cdots ,x_q^{\ast}} \right]$ from m independent linear projections of each of its q columns, given by ${{\mathbf{y}}_k}: = {{\mathbf{A}}_k}{\mathbf{x}}_k^{\ast},k \in [q]$. Here, y
k
is an m-length vector with m < n. We assume that the matrix X
^*
can be decomposed as X
^*
= L
^*
+ S
^*
, where L
^*
is a low rank matrix of rank r ≪ min(n, q) and S
^*
is a sparse matrix. Each column of S contains ρ non-zero entries. The matrices 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.