  In this paper, we explore the possibilities and limitations of recovering
sparse signals in an online fashion. Employing a mean field approximation to
the Bayes recursion formula yields an online signal recovery algorithm that can
be performed with a computational cost that is linearly proportional to the
signal length per update. Analysis of the resulting algorithm indicates that
the online algorithm asymptotically saturates the optimal performance limit
achieved by the offline method in the presence of Gaussian measurement noise,
while differences in the allowable computational costs may result in
fundamental gaps of the achievable performance in the absence of noise.
