Compressed sensing with sequential observations

Abstract

Compressed sensing allows perfect recovery of sparse signals (or signals sparse in some basis) using only a small number of measurements. The results in the literature have focused on the asymptotics of how many samples are required and the probability of making an error for & fixed batch of samples. We investigate an alternative scenario where observations are available in sequence and can be stopped as soon as there is reasonable certainty of correct reconstruction. This approach does not require knowing how sparse is the signal, and allows reconstruction using the smallest number of samples. Central to our sequential approach is the stopping rule. For the random Gaussian ensemble we show that a simple stopping rule gives the absolute minimum number of observations required for exact recovery, with probability one. However, for other ensembles like Bernoulli or Fourier, this is no longer true, and the rule is modified to trade off delay in stopping and probability of error. We also consider near-sparse signals and describe how to estimate the reconstruction error from the sequence of solutions. This enables stopping once the error falls below a desired tolerance. Our sequential approach to compressed sensing involves a sequence of linear programs, and we outline how such a sequence can be solved efficiently.