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

Abstract

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, $\X^* =[ \x_1^*, \x_2^*, \cdots , \x_q^*]$ from $m$ independent linear projections of each of its $q$ columns, given by $\y_k :=\A_k\x_k^*$, $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^*=Ł^*+§^*$, where ${Ł}^{\ast }$ is a low rank matrix of rank $r<<\min (n,q)$ and ${\S }^{\ast }$ is a sparse matrix. Each column of $\S$ contains $\rho$ 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.

6 pages, 2 figures, conference