TY - GEN
T1 - Sudocodes - Fast measurement and reconstruction of sparse signals
AU - Sarvotham, Shriram
AU - Baron, Dror
AU - Baraniuk, Richard G.
PY - 2006
Y1 - 2006
N2 - Sudocodes are a new scheme for lossless compressive sampling and reconstruction of sparse signals. Consider a sparse signal x ∈ ℝN containing only K ≪ N non-zero values. Sudo-encoding computes the codeword y ∈ ℝM via the linear matrix-vector multiplication y = Φx, with K < M ≪ N. We propose a non-adaptive construction of a sparse Φ 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(K log(N)) measurements for exact reconstruction with worst-case computational complexity O(K log(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 bases.
AB - Sudocodes are a new scheme for lossless compressive sampling and reconstruction of sparse signals. Consider a sparse signal x ∈ ℝN containing only K ≪ N non-zero values. Sudo-encoding computes the codeword y ∈ ℝM via the linear matrix-vector multiplication y = Φx, with K < M ≪ N. We propose a non-adaptive construction of a sparse Φ 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(K log(N)) measurements for exact reconstruction with worst-case computational complexity O(K log(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 bases.
UR - http://www.scopus.com/inward/record.url?scp=39049110737&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=39049110737&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2006.261573
DO - 10.1109/ISIT.2006.261573
M3 - Conference contribution
AN - SCOPUS:39049110737
SN - 1424405041
SN - 9781424405046
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 2804
EP - 2808
BT - Proceedings - 2006 IEEE International Symposium on Information Theory, ISIT 2006
T2 - 2006 IEEE International Symposium on Information Theory, ISIT 2006
Y2 - 9 July 2006 through 14 July 2006
ER -