Title: An Asynchronous Parallel Approach to Sparse Recovery,
Abstract: Asynchronous parallel computing and sparse recovery are two areas that have
received recent interest. Asynchronous algorithms are often studied to solve
optimization problems where the cost function takes the form $\sum_{i=1}^M
f_i(x)$, with a common assumption that each $f_i$ is sparse; that is, each
$f_i$ acts only on a small number of components of $x\in\mathbb{R}^n$. Sparse
recovery problems, such as compressed sensing, can be formulated as
optimization problems, however, the cost functions $f_i$ are dense with respect
to the components of $x$, and instead the signal $x$ is assumed to be sparse,
meaning that it has only $s$ non-zeros where $s\ll n$. Here we address how one
may use an asynchronous parallel architecture when the cost functions $f_i$ are
not sparse in $x$, but rather the signal $x$ is sparse. We propose an
asynchronous parallel approach to sparse recovery via a stochastic greedy
algorithm, where multiple processors asynchronously update a vector in shared
memory containing information on the estimated signal support. We include
numerical simulations that illustrate the potential benefits of our proposed
asynchronous method.