An algebraic perspective on integer sparse recovery

10/10/2017 - 12:15pm
10/10/2017 - 1:10pm
Speaker: 
Lenny Fukshansky (CMC)
Abstract: 

A basic problem of compressed sensing is that of sparse recovery: accurately reconstruct a sparse signal x in R^d from its noisy measurement Ax+e in R^m, where m < d, A is an m x d compression matrix, and e is an error vector. The signal x is called s-sparse if it has only s nonzero coordinates, where s is usually no bigger than m. There are known recovery algorithms for the situations when m = O(s lod (d)), which usually rely on incoherence or restricted isometry properties of the matrix A. In this talk, we will discuss an approach to this problem when the sparse signal vector x is assumed to have integer coordinates, a direction with many potential applications in digital communications and related fields. We will outline a number-theoretic construction of matrices A that allow for efficient recovery over noisy channels. We will also talk about some limitations of this approach. This is joint work with Deanna Needell and Benny Sudakov.

Where: 
Millikan 2099, Pomona College