Share Email Print

Proceedings Paper

Annihilating filter-based decoding in the compressed sensing framework
Author(s): Ali Hormati; Martin Vetterli
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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(k2) whereas for the decoding based on the l1 minimization, the number of measurements needs to be of O(k log(n)) and the complexity is of O(n3). 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.

Paper Details

Date Published: 20 September 2007
PDF: 10 pages
Proc. SPIE 6701, Wavelets XII, 670121 (20 September 2007); doi: 10.1117/12.732308
Show Author Affiliations
Ali Hormati, Ecole Polytechnique Federale de Lausanne (Switzerland)
Martin Vetterli, Ecole Polytechnique Federale de Lausanne (Switzerland)

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

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?