Lenny Fukshansky


Claremont McKenna College


Wednesday, February 16, 2022 - 2:00pm to 3:00pm



RH 340N


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 and 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.