A Caltech Library Service

Efficient and Robust Compressed Sensing Using Optimized Expander Graphs

Jafarpour, Sina and Xu, Weiyu and Hassibi, Babak and Calderbank, Robert (2009) Efficient and Robust Compressed Sensing Using Optimized Expander Graphs. IEEE Transactions on Information Theory, 55 (9). pp. 4299-4308. ISSN 0018-9448.

PDF - Published 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 can be fully recovered using O(klog n) measurements and only O(klog 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 reduced arbitrarily close to k, and the recovery algorithm can be implemented very efficiently using a simple priority queue with total recovery time O(nlog(n/k))). We also show that by tolerating a small penal- ty 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 time complexity and the simplicity of recovery. 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 a k-sparse signal which is close to the best k-term approximation of the original signal.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© Copyright 2009 IEEE. Manuscript received May 25, 2008; revised March 12, 2009. Current version published August 19, 2009. The work of B. Hassibi was supported in parts by the National Science Foundation (NSF) under Grant CCF 0729203, by the David and Lucille Packard Foundation and by Caltech’s Lee Center for Advanced Networking. The work of R. Calderbank was supported in part by NSF under Grant 0701226, by ONR under Grant N00173-06-1-G006, and by AFOSR under Grant FA9550-05-1-0443. The authors would like to thank Piotr Indyk, Justin Romberg, the readers and the anonymous reviewers of the paper for their insights and suggestions.
Funding AgencyGrant Number
NSFCCF 0729203
David and Lucile Packard FoundationUNSPECIFIED
Lee Center for Advanced Networking, CaltechUNSPECIFIED
Office of Naval ResearchN00173-06-1-G006
Air Force Office of Scientific ResearchFA9550-05-1-0443
Subject Keywords:Compressive sensing; expander graphs; sparse recovery; sparse sensing matrices; unique neighborhood property
Issue or Number:9
Record Number:CaltechAUTHORS:20090908-083705068
Persistent URL:
Official Citation:Jafarpour, S.; Xu, W.; Hassibi, B.; Calderbank, R., "Efficient and Robust Compressed Sensing Using Optimized Expander Graphs," Information Theory, IEEE Transactions on , vol.55, no.9, pp.4299-4308, Sept. 2009 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:15653
Deposited By: George Porter
Deposited On:09 Sep 2009 16:12
Last Modified:03 Oct 2019 01:00

Repository Staff Only: item control page