  We address the problem of sparse recovery in an online setting, where random
linear measurements of a sparse signal are revealed sequentially and the
objective is to recover the underlying signal. We propose a reweighted least
squares (RLS) algorithm to solve the problem of online sparse reconstruction,
wherein a system of linear equations is solved using conjugate gradient with
the arrival of every new measurement. The proposed online algorithm is useful
in a setting where one seeks to design a progressive decoding strategy to
reconstruct a sparse signal from linear measurements so that one does not have
to wait until all measurements are acquired. Moreover, the proposed algorithm
is also useful in applications where it is infeasible to process all the
measurements using a batch algorithm, owing to computational and storage
constraints. It is not needed a priori to collect a fixed number of
measurements; rather one can keep collecting measurements until the quality of
reconstruction is satisfactory and stop taking further measurements once the
reconstruction is sufficiently accurate. We provide a proof-of-concept by
comparing the performance of our algorithm with the RLS-based batch
reconstruction strategy, known as iteratively reweighted least squares (IRLS),
on natural images. Experiments on a recently proposed focal plane array-based
imaging setup show up to 1 dB improvement in output peak signal-to-noise ratio
as compared with the total variation-based reconstruction.
