Recursive Compressed Sensing
This work addresses the challenge of efficient compressed sensing for streaming data, which is incremental as it builds on existing methods with specific improvements.
The paper tackles the problem of performing compressed sensing on streaming data by introducing a recursive algorithm that uses overlapping windows and previous measurements to speed up processing. The result shows an order of magnitude speed-up over traditional compressed sensing and significantly lower reconstruction error under mild conditions.
We introduce a recursive algorithm for performing compressed sensing on streaming data. The approach consists of a) recursive encoding, where we sample the input stream via overlapping windowing and make use of the previous measurement in obtaining the next one, and b) recursive decoding, where the signal estimate from the previous window is utilized in order to achieve faster convergence in an iterative optimization scheme applied to decode the new one. To remove estimation bias, a two-step estimation procedure is proposed comprising support set detection and signal amplitude estimation. Estimation accuracy is enhanced by a non-linear voting method and averaging estimates over multiple windows. We analyze the computational complexity and estimation error, and show that the normalized error variance asymptotically goes to zero for sublinear sparsity. Our simulation results show speed up of an order of magnitude over traditional CS, while obtaining significantly lower reconstruction error under mild conditions on the signal magnitudes and the noise level.