Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235921] of Robert Calderbank

Papers Published

  1. Jafarpour, S; Xu, W; Hassibi, B; Calderbank, R, Efficient and Robust Compressed Sensing Using Optimized Expander Graphs, Ieee Transactions on Information Theory, vol. 55 no. 9 (September, 2009), pp. 4299-4308, Institute of Electrical and Electronics Engineers (IEEE), ISSN 0018-9448 [doi]
    (last updated on 2019/04/23)

    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(k log n) 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 2 k 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(n log(n/k))). 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 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. © 2009 IEEE.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320