Math @ Duke

Publications [#235921] of Robert Calderbank
Papers Published
 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
(2009),
pp. 42994308, ISSN 00189448 [doi]
(last updated on 2018/03/24)
Abstract: Expander graphs have been recently proposed to construct efficient compressed sensing algorithms. In particular, it has been shown that any ndimensional vector that is ksparse 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 expandergraphbased 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 ksparse signal and then, using very simple optimization techniques, finds a ksparse signal which is close to the best kterm approximation of the original signal. © 2009 IEEE.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

