title: Bayesian online compressed sensing.
abstract: 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.
authors.affiliation: Departamento de Física Geral, Instituto de Física, University of São Paulo, CP 66318, São Paulo, SP 05314-970, Brazil.
authors.forename: Paulo V
authors.initials: PV
authors.lastname: Rossi
authors.affiliation: Department of Mathematical and Computing Science, Tokyo Institute of Technology, Yokohama 226-8502, Japan.
authors.forename: Yoshiyuki
authors.initials: Y
authors.lastname: Kabashima
authors.affiliation: Graduate School of Information Science and Technology, Hokkaido University, N14-W9, Kita-ku, Sapporo 060-0814, Japan.
authors.forename: Jun-Ichi
authors.initials: J
authors.lastname: Inoue