## 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 language | English (US) |
---|---|

Title of host publication | Proceedings - 2006 IEEE International Symposium on Information Theory, ISIT 2006 |

Pages | 2804-2808 |

Number of pages | 5 |

DOIs | |

State | Published - Dec 1 2006 |

Event | 2006 IEEE International Symposium on Information Theory, ISIT 2006 - Seattle, WA, United States Duration: Jul 9 2006 → Jul 14 2006 |

### Other

Other | 2006 IEEE International Symposium on Information Theory, ISIT 2006 |
---|---|

Country/Territory | United States |

City | Seattle, WA |

Period | 7/9/06 → 7/14/06 |

## ASJC Scopus subject areas

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