Sudocodes - Fast measurement and reconstruction of sparse signals

Shriram Sarvotham, Dror Baron, Richard G. Baraniuk

Research output: Chapter in Book/Report/Conference proceedingConference contribution

96 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2006 IEEE International Symposium on Information Theory, ISIT 2006
Pages2804-2808
Number of pages5
DOIs
StatePublished - Dec 1 2006
Event2006 IEEE International Symposium on Information Theory, ISIT 2006 - Seattle, WA, United States
Duration: Jul 9 2006Jul 14 2006

Other

Other2006 IEEE International Symposium on Information Theory, ISIT 2006
CountryUnited States
CitySeattle, WA
Period7/9/067/14/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Sudocodes - Fast measurement and reconstruction of sparse signals'. Together they form a unique fingerprint.

Cite this