Geometric Constructions for Sparse Integer Signal Recovery

Explore geometric constructions for sparse integer signal recovery in this 47-minute lecture from the USC Probability and Statistics Seminar. Delve into the problem of constructing m x d integer matrices with small entries and large d compared to m, ensuring that for all vectors x in Z^d with at most s ≤ m nonzero coordinates, the image vector Ax is not 0. Examine how these constructions enable robust recovery of the original vector x from its image Ax. Investigate the existence of such matrices for appropriate choices of d as a function of m, considering both probabilistic arguments and deterministic constructions. Learn about a family of matrices derived from a geometric covering problem and discover the connection between these constructions and a simple variant of the Tarski plank problem. Gain insights from joint works with B. Sudakov, D. Needell, and A. Hsu in this comprehensive exploration of compressed sensing applications in wireless communications and medical imaging.