Sudocodes ߝ Fast Measurement and Reconstruction of Sparse Signals
- 1 July 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21578095,p. 2804-2808
Abstract
Sudocodes are a new scheme for lossless compressive sampling and reconstruction of sparse signals. Consider a sparse signal x isin RopfN containing only K Lt N non-zero values. Sudo-encoding computes the codeword via the linear matrix-vector multiplication y = Phix, with K < M Lt N. We propose a non-adaptive construction of a sparse Phi comprising only the values 0 and 1; hence the computation of y involves only sums of subsets of the elements of x. An accompanying sudodecoding strategy efficiently recovers x given y. Sudocodes require only M = O(Klog(N)) measurements for exact reconstruction with worst-case computational complexity O(Klog(K) log(N)). Sudocodes can be used as erasure codes for real-valued data and have potential applications in peer-to-peer networks and distributed data storage systems. They are also easily extended to signals that are sparse in arbitrary basesKeywords
This publication has 4 references indexed in Scilit:
- Signal Recovery From Random Measurements Via Orthogonal Matching PursuitIEEE Transactions on Information Theory, 2007
- Compressed sensingIEEE Transactions on Information Theory, 2006
- Combinatorial Algorithms for Compressed Sensing2006
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency informationIEEE Transactions on Information Theory, 2006