Recent results in compressed sensing or compressive sampling suggest that a relatively small set of measurements taken as the inner product with universal random measurement vectors can well represent a source that is sparse in some fixed basis. By adapting a deterministic, non-universal and structured sensing device, this paper presents results on using the annihilating filter to decode the information taken in this new compressed sensing environment. The information is the minimum amount of nonadaptive knowledge that makes it possible to go back to the original object. We will show that for a k-sparse signal of dimension n, the proposed decoder needs 2k measurements and its complexity is of O(k²) whereas for the decoding based on the l₁ minimization, the number of measurements needs to be of O(k log(n)) and the complexity is of O(n³). In the case of noisy measurements, we first denoise the signal using an iterative algorithm that finds the closest rank k and Toeplitz matrix to the measurements matrix (in Frobenius norm) before applying the annihilating filter method. Furthermore, for a k-sparse vector with known equal coefficients, we propose an algebraic decoder which needs only k measurements for the signal reconstruction. Finally, we provide simulation results that demonstrate the performance of our algorithm.

Date Published: 20 September 2007
PDF: 10 pages
Proc. SPIE 6701, Wavelets XII, 670121 (20 September 2007); doi: 10.1117/12.732308

Published in SPIE Proceedings Vol. 6701:
Wavelets XII
Dimitri Van De Ville; Vivek K. Goyal; Manos Papadakis, Editor(s)