Lenny Fukshansky
Claremont McKenna College
[on zoom only]

Abstract: We investigate the problem of constructing m x d integer matrices with small entries and d large comparing to m so that for all vectors x in Z^d with at most s ≤ m nonzero coordinates the image vector Ax is not 0. Such constructions allow for robust recovery of the original vector x from its image Ax. This problem is motivated by the compressed sensing paradigm and has numerous potential applications ranging from wireless communications to medical imaging. We discuss existence of such matrices for appropriate choices of d as a function of m. In addition to some probabilistic arguments, we demonstrate a deterministic construction of a family of such matrices stemming from a certain geometric covering problem. We also discuss a connection of our constructions to a simple variant of the Tarski plank problem. This talk is based on joint works with B. Sudakov and D. Needell, as well as with A. Hsu.