A Caltech Library Service

Efficient and Robust Compressed Sensing using High-Quality Expander Graphs

Jafarpour, Sina and Xu, Weiyu and Hassibi, Babak and Calderbank, Robert (2008) Efficient and Robust Compressed Sensing using High-Quality Expander Graphs. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Expander graphs have been recently proposed to construct efficient compressed sensing algorithms. In particular, it has been shown that any n-dimensional vector that is k-sparse (with k≪n) can be fully recovered using O(k log n/k)measurements and only O(k log n) simple recovery iterations. In this paper we improve upon this result by considering expander graphs with expansion coefficient beyond 3/4 and show that, with the same number of measurements, only O(k) recovery iterations are required, which is a significant improvement when n is large. In fact, full recovery can be accomplished by at most 2k very simple iterations. The number of iterations can be made arbitrarily close to k, and the recovery algorithm can be implemented very efficiently using a simple binary search tree. We also show that by tolerating a small penalty on the number of measurements, and not on the number of recovery iterations, one can use the efficient construction of a family of expander graphs to come up with explicit measurement matrices for this method. We compare our result with other recently developed expander-graph-based methods and argue that it compares favorably both in terms of the number of required measurements and in terms of the recovery time complexity. Finally we will show how our analysis extends to give a robust algorithm that finds the position and sign of the k significant elements of an almost k-sparse signal and then, using very simple optimization techniques, finds in sublinear time a k-sparse signal which approximates the original signal with very high precision.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Additional Information:The work of B. Hassibi was supported in parts by the National Science Foundation under grant CCF 0729203, by the David and Lucille Packard Foundation and by Caltech’s Lee Center for Advanced Networking.
Funding AgencyGrant Number
David and Lucile Packard FoundationUNSPECIFIED
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Record Number:CaltechAUTHORS:20190702-111100896
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:96885
Deposited By: Tony Diaz
Deposited On:08 Jul 2019 17:22
Last Modified:02 Jun 2023 00:03

Repository Staff Only: item control page