Title :
Compressed sensing with sequential observations
Author :
Malioutov, D.M. ; Sanghavi, S. ; Willsky, A.S.
Author_Institution :
Massachusetts Inst. of Technol., Cambridge, MA
fDate :
March 31 2008-April 4 2008
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.
Keywords :
Gaussian processes; data compression; random processes; signal reconstruction; signal sampling; compressed sensing; error probability; linear programs; near-sparse signals; random Gaussian ensemble; reconstruction error; sequential approach; sparse signals recovery; Compressed sensing; Costs; Decoding; Delay; Gaussian noise; Guidelines; Military computing; Noise measurement; Pursuit algorithms; Signal analysis; Sequential compressed sensing;
Conference_Titel :
Acoustics, Speech and Signal Processing, 2008. ICASSP 2008. IEEE International Conference on
Conference_Location :
Las Vegas, NV
Print_ISBN :
978-1-4244-1483-3
Electronic_ISBN :
1520-6149
DOI :
10.1109/ICASSP.2008.4518370