CaltechAUTHORS
  A Caltech Library Service

Efficient Compressive Sensing with Deterministic Guarantees Using Expander Graphs

Xu, Weiyu and Hassibi, Babak (2007) Efficient Compressive Sensing with Deterministic Guarantees Using Expander Graphs. In: IEEE Information Theory Workshop (ITW '07), Lake Tahoe, CA, 2-6 September 2007. IEEE , Piscataway, NJ, pp. 414-419. ISBN 1-4244-1564-0. http://resolver.caltech.edu/CaltechAUTHORS:XUWitw07a

[img]
Preview
PDF
See Usage Policy.

152Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:XUWitw07a

Abstract

Compressive sensing is an emerging technology which can recover a sparse signal vector of dimension n via a much smaller number of measurements than n. However, the existing compressive sensing methods may still suffer from relatively high recovery complexity, such as O(n^3), or can only work efficiently when the signal is super sparse, sometimes without deterministic performance guarantees. In this paper, we propose a compressive sensing scheme with deterministic performance guarantees using expander-graphs-based measurement matrices and show that the signal recovery can be achieved with complexity O(n) even if the number of nonzero elements k grows linearly with n. We also investigate compressive sensing for approximately sparse signals using this new method. Moreover, explicit constructions of the considered expander graphs exist. Simulation results are given to show the performance and complexity of the new method.


Item Type:Book Section
Additional Information:© Copyright 2007 IEEE. Reprinted with permission. [Posted online: 2007-09-24]
Record Number:CaltechAUTHORS:XUWitw07a
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:XUWitw07a
Alternative URL:http://dx.doi.org/10.1109/ITW.2007.4313110
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9071
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:25 Oct 2007
Last Modified:26 Dec 2012 09:45

Repository Staff Only: item control page