Annihilating filter-based decoding in the compressed sensing framework

Ali Hormati; Martin Vetterli

doi:10.1117/12.732308

20 September 2007 Annihilating filter-based decoding in the compressed sensing framework

Ali Hormati, Martin Vetterli

Author Affiliations +

Proceedings Volume 6701, Wavelets XII; 670121 (2007) https://doi.org/10.1117/12.732308
Event: Optical Engineering + Applications, 2007, San Diego, California, United States

Abstract

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.

Citation Download Citation

Ali Hormati and Martin Vetterli "Annihilating filter-based decoding in the compressed sensing framework", Proc. SPIE 6701, Wavelets XII, 670121 (20 September 2007); https://doi.org/10.1117/12.732308

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

;

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE